Кооперативные принципы оптимальности для игр с упорядоченными исходами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

ПАСЕЧНИК Мария Владимировна

КООПЕРАТИВНЫЕ ПРИНЦИПЫ ОПТИМАЛЬНОСТИ ДЛЯ ИГР С УПОРЯДОЧЕННЫМИ ИСХОДАМИ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Саратов - 2004

Работа выполнена на кафедре геометрии Саратовского гос\ дарственного университета им Н Г. Чернышевского

Научный руководитель

доктор физико-математических наук, профессор Виктор Владимирович Розен.

Официальные оппоненты

доктор физико-математических наук, профессор Сергей Иванович Дудов, кандидат физико-математических наук Виталий Владимирович Печенкин.

Ведущая организация

Санкт - Петербургский государственный университет.

Защита состоится 2004 г. в ¿Гч з_о_ мин. на

заседании Диссертационного Совета К 212.243 02 при Саратовском государственном университете по адресу 410026 г. Саратов, ул Астраханская, 83, СГУ, механико-математический факультет

С диссертацией можно ознакомиться в Научной библиотеке Саратовского государственного университета

Автореферат разослан «

Л

М/М, 2004 г

Ученый секретарь Диссертационного Совета кандидат физико-математических наук, доцент

Корнев В.В.

ЕКвЗо

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В теовии игр сложилось два подхода к исследованию игры некоопер. ный и кооперативный. При некооперативном подходе анализ игры проводится в предположении независимости действий игроков. При кооперативном подходе, напротив, предполагается, что игроки могут создавать коалиции, наделенные собственными интересами и возможностями воздействия на появление тех или иных исходов игры. В последние десятилетия значительное внимание исследователей, как в нашей стране, так и за рубежом, было привлечено к играм, в котрых предпочтения игроков задаются не функциями выигрыша (функциями полезности), а их отношениями предпочтения. Это объясняется на наш взгляд двумя обстоятельствами. Во-первых, понятие предпочтения является первичным, в то время как понятие функции полезности -производным Во-вторых, построение функции полезности в практических задачах требует большого объема дополнительной информации и связано с преодолением значительных трудностей как технического, так и принципиального характера Среди ученых, внесших значительный вклад в разработку теории игр с отношениями предпочтения, следует отметить Р.Аумана, Б.Пелега, Э.Й.Вилкаса, О.Н.Бондареву, Т.Е. Кулановскую, В.В.Подиновского, В В.Розена.

Можно выделить следующие направления, активно развивающиеся в последние десятилетия в теории игр с отношениями предпочтения: выработка принципов оптимальности для классов игр с отношениями предпочтения; нахождение условий существования ситуации равновестия как в чистых, так и в смешанных стратегиях; перенос важнейших понятий теории игр с функциями выигрышей игроков на игры с отношениями предпочтения (нижняя и верхняя цена игры, обобщение соотношения максимина, ситуации равновесия, характеристическая функция игры, построение смешенного расширения игры и другие). В то же время вопросы кооперативной теории игр с отношениями предпочтения затронуты лишь в отдельных работах Из сказанного ясно, что разработка кооперативной теории для игр с отношениями предпочтения является весьма актуальной.

Цель диссертационной работы состоит в переносе кооперативных принципов оптимальности, известных для стратегических игр с функциями

выигрыша игроков, на более широкий кл сс стратегических игр с квазиупорядоченными исходами, нахождении достаточных условий существования оптимальных решений и описании их структуры.

Методы исследований. При выполнении работы использовались методы теории игр с функциями выигрыша, теории упорядоченных

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

множеств, отдельные результаты и методы алгебры множеств и алгебры бинарных отношений.

Научная новизна. Для класса антагонистических игр с квазиупорядоченными исходами введены принципы оптимальности принцип К - равновесия, принцип К - допустимости исходов, принцип К -вполне допустимости ситуаций или исходов игры, где К - произвольное семейство коалиций При сужении на подкласс стратегических игр с функциями выигрыша игроков эти принципы оптимальности переходят в известные принципы оптимальности в классической теории игр При этом, как и в теории игр с функциями выигрыша игроков, оптимальные ситуации всех введенных типов характеризуются тем, что они могут быть стабилизированы с помощью простых угроз

Найдены различные достаточные условия непустоты множества индивидуально рациональных исходов для антагонистических игр с упорядоченными исходами. Найдены достаточные условия непустоты множества индивидуально рациональных исходов и множества дележей для игр с квазиупорядоченными исходами Указаны условия существования единственного индивидуально рационального исхода в антагонистических играх с упорядоченными исходами и играх п лиц с квазиупорядоченными исходами Найдена взаимосвязь между существованием единственного индивидуально рационального исхода в играх п лиц с квазиупорядоченными исходами и существованием ситуации равновесия по Нэшу.

Выяснена структура множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами, а также в антагонистических играх с векторными выигрышами.

Рассмотрены обратные задачи для класса стратегических кооперативных игр с квазиупорядоченными исходами. В частности, решена задача восстановления антагонистической игры с упорядоченными исходами и задача восстановления игр^л п лиц с квазиупорядоченными исходами по ее оценочной структуре и по множеству индивидуально рациональных исходов. Рассмотрена задача восстановления игры с квазиупорядоченными исходами по ее характеристической функции.

Теоретическая и практическая значимость. Работа носит теоретический характер Полученные в работе результаты могут быть использованы при анализе социально-экономических моделей конфликтов, в которых предпочтения участвующих сторон заданы в порядковых шкалах.

Апробация работы. Основные результаты, изложенные в диссертации, докладывались и обсуждались на научных семинарах Саратовского государственного университета, на ежегодных научных конференциях механико-математического факультета 2001-2004гг., на научных

конференциях факультета КНИТ СГУ, на международной конференции памяти проф. А М Богомолова (Саратов 2002), на объединенном научном семенаре кафедр факультета компьютерных наук и информационных технологий (руководитель проф Д В Сперанский, на научном семенаре по теории игр Санкт-Петербургского государственного университета (руководитель проф. Л.А. Петросян).

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении дается краткое описание основных направлений теории игр с отношениями предпочтения игроков. Вводятся основные кооперативные принципы оптимальности для стратегических игр с отношениями предпочтения игроков. Указано, что оптимальные (по введенным принципам оптимальности) ситуации в играх с отношениями предпочтения стабилизируются с помощью простых угроз.

В главе 1 изучаются кооперативные принципы оптимальности в антагонистических играх с квазиупорядоченными исходами. Для них множество индивидуально рациональных исходов совпадает с множеством дележей и совпадает с а - ядром.

Выяснена структура множества индивидуально рациональных исходов в бесконечных антагонистических играх с функциями выигрыша, в частности, найдено условие непустоты и условие единственности индивидуально рационального исхода в таких играх. Для антагонистических игр с векторными выигрышами доказана непустота множества индивидуально рациональных исходов и выяснена его структура.

Антагонистическая игра с упорядоченными исходами общего вида может быть задана как набор объектов

С = (Х,¥,А,со,Р), (1.1.1)

где Х - множество стратегий игрока 1, У - множество стратегий игрока 2, А -множество исходов, со - отношение порядка, выражающее предпочтения игрока 1 (предпочтения игрока 2 выражаются обратным отношением порядка а}'), Р:XА - функция реализации.

Для описания множества £>((/) индивидуально рациональных исходов игры О введены следующие характеристические множества:

а

((7) = {а е А : (3* е X) (Vу е У) Р(х, у)>а} - множество исходов, гарантированных для игрока 1;

*

и г (G) = Iя 6 А 6 е ^Х*» .У) < - множество исходов

строго гарантированных для игрока 2;

а

F, (G) = {а е А : (Уу е У) (Эх е X) F(x, у) > а} - множество не запрещенных исходов игрока 1;

V2 (G) = {аеА : (Ух е X) (3у е У) F(x, у)<а} - множество незапрещенных исходов игрока 2.

Полагаем

Z(G) = Vx (G) п V2 (G) - центр игры, P(G) = (V^G) u V2(G))' - периферия игры, R(G) = Л, (G) и R2 (G) - шы/о игры ,

где Л, (G) = (V) (G) \ U' (G)) W2(G) - левое полукольцо и R2 (G) = (V2 (G) \ U\(G)) \ Vl (G) - правое полуколцо.

Теорема 1.3.1 Структура множества индивидуально рациональных исходов в антагонистической игре с упорядоченными исходами.

В антагонистической игре с упорядоченными исходами G=<X,Y,A,(0,F> множество всех индивидуально рациональных исходов может быть представлено в виде непересекающегося объединения следующих трех множеств: центра, кольца и периферии.

Указаны подклассы антагонистических игр с упорядоченными исходами, в которых множество индивидуально рациональных исходов совпадает с центром, периферией или кольцом.

Найдены условия непустоты множества индивидуально рациональных исходов для антагонистических игр с упорядоченными исходами, а именно доказаны следующие теоремы.

Теорема 1.4.1 Пусть в антагонистической игре G=<X,Y,A,a),F> с упорядоченными исходами все цепи упорядоченного множества <А,а>> конечны. Тогда множество индивидуально рациональных исходов в игре G непусто: D(G)*<Z

Теорема 1.4.2 В антагонистической игре С-<Х, У, А, со,Р> с упорядоченными исходами, в которой множества стратегий игроков конечны, множество индивидуально рациональных исходов непусто.

Получено условие единственности индивидуально рационального исхода для игры вида (1 1.1), в которой все цепи упорядоченного множества конечны, в том числе доказана следующая теорема.

Теорема 1.4.3 Необходимое и достаточное условие единственности индивидуально рационального исхода в играх с упорядоченными исходами.

Для того, чтобы антагонистическая игра с упорядоченными исходами С=<Х, У, А, со, Р>, в которой все цепи упорядоченного множества <А, а>> конечны, имела единственный индивидуально- рациональный исход, необходимо и достаточно, чтобы игра й имела седловую точку, исход в которой сравним с любым исходом игры по порядку со.

В главе 2 исследуются условия непустоты и единственности индивидуально рациональных исходов и дележей для игр п лиц с квазиупорядоченными исходами.

Стратегическая игра с квазиупорядоченными исходами есть игра в которой предпочтения игроков задаются отношениями квазипорядка. Формально стратегическая игра п лиц с квазиупорядоченными исходами определяется как система вида

С=<И,{Х,)хГПА,{ф1)^,Р> , (2.2.1)

где N — {1,..., п} - множество игроков, Х1 - множество стратегий игрока /', А -множество исходов, (01 - отношение квазипорядка на множестве исходов А, выражающее предпочтения игрока /.

При исследовании условий непустоты множества индивидуально рациональных исходов в игре С вида (2.2.1) существенную роль играет отношение ^доминирования стратегий, которое определяется следующим образом.

Определение 2.1.1 Пусть X., х^ е Х1. Будем говорить, что стратегия

1 2

х1 доминирует стратегию х1 по отношению /^-доминирования игрока / и

д

записывать это в виде > х~, если для любой стратегии У^ е X существует такая стратегия у ^ € Х^, что

> F(x;,yl).

Каждой стратегии x, e Xi поставим в соответствие мажорантно стабильное замыкание дг, -строки, полагая

[F(x, ,XNjf - {ае A: (3yN,, е XN,,) а \ F(x„yN,)}

Теорема 2.1.1 Пусть С - игра с квазиупоядоченными исходами вида (2.2 1) Если при любом / е N всякая строго убывающая цепь мажорантно стабильных подмножеств вида

обрывается на конечном номере, то множество индивидуально-рациональных исходов игры (7 непусто.

Теорема 2.1.2 Достаточное условие непустоты множества дележей в игре п лип с квазиупорядоченными исходами.

Если в игре п лиц с квазиупорядоченными исходами вида (2.2.1) каждое квазиупорядоченное множество <А,<а1>{1еЩ удовлетворяет условию ОВЦ, то множество дележей игры С7 непусто.

Отношение эквивалентности £ ~ (~]£, , где £, - &>, О О)'1 , будем

называть естественной эквивалентностью игры С.

Далее дается характеризация игр с квазиупорядоченными исходами, имеющих единственный индивидуально рациональный исход, с точностью до естественной эквивалентности е. Положим

и',(С) = |аеЛ:(Зх$ е Хв)(\/у еХт,)Р(х3,у)Ш>а|.

Теорема 2.2.1 Пусть С игра с квазиупорядоченными исходами вида (2.2.1), в которой каждое квазиупорядоченное множество <А,(0, > удовлетворят условию обрыва возрастающих цепей (ОВЦ). Для того, чтобы исход С е А был единственным с точностью до эквивалентности £

индивидуально рациональным исходом в игре G, необходимо и достаточно чтобы выполнялись следующие условия'

1 )U'(G)c{aeA:a<c} (ieN);

2))JU](G)=)J{azA:a<c-},

juN /еЛ>

3) для любого исхода а е А, не эквивалентного относительно е исходу с , найдется такой индекс ieN, дчя которого а<с .

Показано, что единственность индивидуально рационального исхода в игре G эквивалентна существованию в ней ситуации равновесия по Нэшу, удовлетворяющей некоторым дополнительным условиям.

Определение 2.2.5 Ситуация х° в игре п лиц с квазиупорядоченными исходами называется ситуацией К- равновесия, если ни у какой коалиции S е К не существует такой стратегии xs е Xs при

II

которой F(*0||xs)>F(x°). Ситуация К - равновесия при К =2N называется ситуацией сильного равновесия.

Теорема 2.2.2 Пусть К - семейство тех коалиций S q N игры G, для которых подмножество D(G) является антицепью относительно квазипорядка cos. Тогда ситуация, состоящая из Д - максимальных стратегий игроков, является ситуацией К - равновесия в игре G.

Следствие Если в каждом квазиупорядоченном множестве <А,й)1> (ieN) подмножество допустимых исходов игры D(G)

является антицепью, то ситуация = , состоящая из Р -

максимальных стратегий игроков, будет ситуацией сильного равновесия.

В главе 3 рассматриваются обратные задачи следующего вида. Задана оценочная структура игры с (квази)упорядоченными исходами, а также известна некоторая информация, отражающая возможности игроков или коалиций. Требуется восстановить саму игру (восстановить ее реализационную структуру), так чтобы указанные характеристики совпали с заданными.

В диссертации решается обратная задача в классе антагонистических игр с упорядоченными исходами, когда в качестве заданной характеристики игры выступает множество ее индивидуально рациональных исходов.

Теорема 3.3.1 Пусть - конечное упорядоченное множество, в

котором зафиксировано подмножество Ос^ Для того, чтобы

подмножество совпадало с множеством индивидуально рациональных исходов некоторой антагонистической игры с упорядоченными исходами вида Х,У,А,а>,Р- , необходимо и достаточно, чтобы подмножество О было выпуклым, а его дополнение

было представимо в виде непересекающегося объединения двух подмножеств С, и С2, удовлетворяющих следующим условиям:

1. (УдеС,) (У6еС2) {а,Ь)*а,

2. условия а е С,, М(а) с М(а') влекут а'е С,;

3. условия

ЪеС2, т(Ь)стф')

влекут ОьЦ Здесь М(а)= {а'е А:а'> а}, т(а)={а'е А:а'<а}.

Так же дается решение задачи восстановления игры в классе игр и лиц с квазиупорядоченными исходами по заданному множеству индивидуально рациональных исходов.

Теорема 3.2.1 Пусть А- конечное множество на котором заданы отношения квазипорядка й)],й)2,..,СОп и зафиксировано некоторое подмножество О с А . Для того, что бы подмножество И совпадало с множеством индивидуально рациональных исходов в некоторой игре й вида (2.2.1), необходимо и достаточно, чтобы его дополнение £)'= Л \ Л допускало представление в виде объединения п подмножеств С,,..,Сл) удовлетворяющих следующим условиям.

1) Пусть для каждого N зафиксирован я, еС, Тогда

аы

2) Если для геД^.оеС,, а'е А и выполнено включение М( (а) с М, (а'), тогда а'е С, .

Рассматривается задача восстановления игры п лиц с квазиупорядоченными исходами по ее характеристической функции. Характеристическая функция игры О вида (2.2.1) определяется следующим образом:

V(S) = {aeA:(3xe Xs)(\/y e XNXS)F(x,y) > a}. Полагаем V(n)=A.

Показано, что характеристическая функция V(s) игры G вида (2 2 1) обладает следующим свойством типа супераддитивности: для любых коалиций S1,S2c:N игры G, для которых S,nS2=0, выполняется включение.

^(sJnKsJcFfousJ.

Далее доказывается следующий результат.

Теорема 3.3.1 Следующие условия являются необходимыми для того, чтобы существовала игра G вида (2 2 1) в которой для каждой коалиции S С N множество Cs совпадало с V(S), и достаточньши для того, чтобы в игре G имело место включение Cs с K(S) :

1) К(0) = 0; Г) V(N)= А;

2) при любом S C.N подмножество Cs минорантно стабильно относительно квазипорядка 0)s;

3) для любых непересекающихся коалиций Sx,..,Sm С N и любых a, е Сх,..,ат е Ст выполняется

ПК.U>0.

1 S/Sm

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1 Для стратегических игр с квазиупорядоченными исходами введены основные принципы оптимальности и показано, что они обосновываются с помощью «сценария предостережений».

2 Выяснена структура множества индивидуально рациональных исходов для антагонистических игр с упорядоченными исходами.

3 Найдены условия непустоты множества индивидуально рациональных исходов и множества дележей в антагонистических играх п лиц с квазиупорядоченными исходами.

Найдены условия единственности индивидуально рационального исхода для игр п лиц с квазиупорядоченными исходами

Решены обратные задачи для класса кооперативных игр с квазиупорядоченными исходами.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Пасечник М В Условия непустоты Са - ядра в антагонистических играх с упорядоченными исходами. // Механика Математика Сб науч. трудов Саратов Изд. Сарат ун-та, 2001 -Вып.З - С 101-104.

2 Пасечник М В. Дележи в бесконечных играх с квазиупорядоченными исходами. // Механика Математика. Сб науч турдов - Саратов Изд Сарат. ун-та, 2002, - Вып.4 - С. 114-117.

3 Пасечник М В. Условия единственности дележа в антагонистических играх с упорядоченными исходами // Компьютерные науки и информационые технологии II Тез К63 докл Междунар. Конф. - Саратов. Изд Сарат. Ун-та, 2002, с.84.

4 Пасечник М.В.Характеризация множества индивидуально рациональных исходов и множества дележей в играх с кввазиупорядоченными исходами// Математика Механика: Сб. науч. тр. - Саратов Изд. Сарат. 2003,-Вып.З-С.84-87.

5 Пасечник М.В. Розен В.В. Игры с квазиупорядоченными исходами, имеющие единственный индивидуально рациональный исход// Математика Механика. Сб. науч. тр. - Саратов Изд. Сарат. ун-та, 2002. Вып.З - С. 87-90.

6 Пасечник М В Характеризация гарантированных исходов коалиций в играх с квазиупорядоченными исходами, /в. - Рус. - Деп. в ВИНИТИ 09.03 04 № 405-В 2004

Подписано в печать 28.04.2004 Формат 60x84 1/16. Бумага офсетная. Гарнитура Times. Печать RISO. Объем 1,0 печ.л. Тираж 100 экз. Заказ № 024.

Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю.Б. Свидетельство №3117 410600, Саратов, ул. Московская, д. 152, офис 19

«-97 90

РНБ Русский фонд

2005-4 ,4477

Введение.

Глава I. Индивидуально рациональные исходы в антагонистических играх с упорядоченными исходами.

1.1 Антагонистические игры с функциями выигрыша.

1.2 Антагонистические игры с векторными выигрышами.

1.3 Структура множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами.

1.4 Непустота и единственность множества индивидуально рациональных исходов в антагонистических играх с упорядоченными исходами

Глава II. Игры п лиц с квазиупорядоченными исходами.

2.1 Условия непустоты множества индивидуально рациональных исходов и множества дележей.

2.2 Условие единственности индивидуально рационального исхода в играх п лиц с квазиупорядоченными исходыми.

Глава III. Обратные задачи для кооперативных игр с упорядоченными исходами.

3.1 Задача восстановления антагонистической игры с упорядоченными исходами по множеству индивидуально рациональных исходов.

3.2 Задача восстановления игры п лиц с квазиупорядоченными исходами по множеству индивидуально рациональных исходов.

3.3 Задача восстановления игры с квазиупорядоченными исходами по характеристической функции

1. В последние десятилетия в теории игр значительное развитие получили исследования игр, в которых предпочтения игроков задаются не функциями выигрыша, а их отношениями предпочтения. Укажем основные направления этих исследований, ведущихся как в нашей стране, так и за рубежом: a) разработка подходов к общему определению игры с отношениями предпочтения (Н.Н. Воробьев [ 11], Э.И. Вилкас [8 ]); b) выработка принципов оптимальности для классов игр с отношением предпочтения (Э. Вилкас [7,8], Б. Пелег [41 ], В.В. Подиновский [28, 29], В.В. Розен [ 32, 33, 34], Б .Г. Миркин [17]); c) нахождение условий существования ситуаций равновесия в играх с отношениями предпочтения ( Р.Ауманн [40], Е.Б. Яновская [39], В.В.Розен [32,33]); d) нахождение условий существования ядра и решения для бинарных отношений, заданных на топологических пространствах (О.Н. Бондарева [4], Т.Е. Кулаковская [15], А.А. Аракелян [2] ).

Отдельные вопросы, касающиеся игр с отношениями предпочтения, затронуты в монографиях К. Бержа [3], Льюса и Райфа [16], В.В. Розена [31], Миркина [17], статьях ( Фаркуарсон Р [42], Зенкевич Н.А, Сурвилло Т.Г.[13], Шолпо И.А.) и другие.

Систематическое изучение игр с упорядоченными исходами предпринято В.В. Розеном. В работах [31,33] введены различные принципы оптимальности для стратегических игр с упорядоченными исходами и найдены достаточные условия их реализуемости. В статье [32] предложены различные способы введения характеристических функций для игр с упорядоченными исходами и изучены их свойства.

2. В теории игр сложилось два подхода к анализу игры: некооперативный и кооперативный. При некооперативном подходе анализ игры ведется в предположении независимости действий игроков, которая объяснятся либо правилами игры, либо разобщенностью игроков (в частности, отсутствием возможности обмена информацией между ними). При кооперативном подходе, напротив, предполагается, что игроки могут создавать коалиции, наделенные собственными интересами и возможностями воздействия на появление тех или иных исходов игры. В кооперативной теории игр основное ее внимание сосредоточено на поведение коалиций.

Тематика данной диссертации относится к кооперативной теории стратегических игр. Основной изучаемой моделью является стратегическая игра вида:

G =<N, (Xj )jeN, A, {coi )jeN, F > , (1) где N = {\у.,п} - множество игроков, Х( -множество стратегий игрока /, А -множество исходов, со,- бинарное отношение на А, выражающее предпочтения игрока /', F- функция реализации, представляющая собой отображение множества XN = Xi ситуаций игры G в множестве ее исходов: F \XN А. ieN

Подсистема <(X/)ieJV,A,F > системы (1) представляет собой реализационную структуру, а подсистема <A,(coi)ieN> - оценочную структуру игры G. Далее полагаем п > 2; \ X, |> 2 (г е N); | А |> 2.

Игра протекает следующим образом. Каждый игрок / е N независимо от остальных выбирает стратегию xf еХп в результате складывается ситуация x = (x,)ieNt приводящая к исходу a=F{x). Если(ара2) е соп то исход а2 считается не менее предпочтительным для игрока /, чем исход ах. Далее мы используем запись ах<а2 как эквивалентную для (al,a2)e <x>i; через < обозначается строгая часть отношения со,. Заметим, что отношение предпочтения, заданное на множестве исходов, переносится и на ситуации игры: для любого игрока / сравнимость по предпочтению двух ситуаций эквивалентна сравнимости соответствующих им исходов.

Если все отношения co^ieN) являются отношениями порядка, то игра G называется игрой с упорядоченными исходами. Если отношения co^ieN) являются отношениями квазипорядка - игрой с квазиупорядоченными исходами.

Для анализа кооперативного аспекта игры G необходимо для каждой коалиции SqN определить множество ее стратегий X, и ее отношение предпочтения cos. В данной диссертации мы полагаем для S с N:

Х = (2) =ГН • (3) ieS

Замечание 1. Равенство (2) означает, что коалиция S в состоянии «воспроизвести» любую ситуацию, обусловленную возможностями входящих в нее игроков. Таким образом, при создании коалиции S, она действует как один игрок, агрегируя возможности входящих в нее членов. Равенство (3) постулирует, что для коалиции S предпочтительней тот исход, который является более предпочтительным для всех ее игроков. Если все coi(/ € N) являются отношениями (квази) порядка, то cos также будет отношением (квази) порядка.

3. Перейдем к описанию основных кооперативных принципов оптимальности для игр вида (1). В дальнейшем изложении существенную роль будут играть характеристические множества коалиций игры G. Заметим, что характеристические множества вводились разными авторами для различных классов игр: Г. Иенчем для игр с векторными выигрышами; Ауманом [40] и Пелегом [41] для кооперативных игр без побочных платежей; В.В. Подиновский [28,29] для игр с бинарными отношениями предпочтения; В.В. Розеном [30] для игр с упорядоченными исходами.

Определение 1 В игре G вида (1) исход а называется гарантированным исходом коалиции S, если существует такая стратегия xs е Xs, что выполняется соотношение cos

QJyms е Xms)F(xs,y) > а.

Множество U(S) всех гарантированных исходов коалиции S есть a>s

U{S) = {а е A: (3xs е Xs) (Vyms е Xms) F(xs,yms)> а}.

COS C°S

Заменяя в определении 1 нестрогое предпочтение > на строгое предпочтение >, получим множество U (S) строго гарантированных исходов коалиции S:

Og

U\S) = {аеЛ: (3xs е Xs)(Vyms е ^nJ^CWms) > а).

Определение 2 В игре G вида (1) исход а называется незапрещенным исходом коалиции S, если для каждой стратегии yms е XNXS, существует такая стратегия cos xs е А',,,что F(xSiyNXS) > а. Множество V(S), состоящее из всех незапрещенных исходов коалиции S, определяется равенством a>s {a е А : е Xnxs)(3xs е Xs)F(xs,yms) > а) .

Заменяя в определении 2 нестрогое предпочтение на строгое, получим множество V*(S) строго незапрещенных исходов коалиции S:

0.S

У* (S) = {а е А: ('\/yNXS е XNSS )(3xs е Xs )F(xs , yNXS) > a}

Утверждение 1 В игре G вида (I) для всякой коалиции SciN выполняются следующие включения: a )U'{S)^U(S);

C)U(S)CV(S); d)U'(s)cV\S). ms ms

Доказательство. Включения а) и b) очевидны, так как > с >. Включения с) и d) выполняются в силу логического закона перестановки разноименных кванторов в направлении 3V=> V3. Утверждение 1 доказано.

Перейдем к понятию допустимости исхода для коалиции S.

Определение 3 Стратегия xs е Xs называется возражением коалиции S на 3 исход а, если при любой стратегии yNXS e выполняется F(xs,yms)>a. Исход а называется допустимым для коалиции S, если она не имеет на него возражений в форме стратегий. В противном случае, а называется недопустимым для коалиции S.

С содержательной точки зрения недопустимость исхода означает его неприемлемость для коалиции S. Действительно, в этом случае у коалиции S существует стратегия, которая гарантирует ей при любом выборе стратегий игроками дополнительной коалиции N\S получение исхода, строго лучшего для нее, чем исход а. Множество исходов допустимых в игре G для коалиции S, будет обозначать DS(G): as

DS(G) = {а е А:-, е Xs) (Vy^ е Х^) F(xs,yNV5)> а }.

Таким образом, исход а допустим для коалиции S тогда и только тогда, когда он не является строго гарантированным исходом этой коалиции.

Пусть % - некоторое фиксированное семейство коалиций игры G. Определим % - допустимый исход игры G как исход, допустимый для всех коалиций из ТС • Обозначая через DK(G) множество допустимых исходов игры G, имеем:

SeK

Следующие конкретизации семейства % особенно важны.

1. Индивидуально рациональные исходы - это исходы, допустимые для всех ее одноэлементных коалиций (т.е. для всех игроков). Множество индивидуально рациональных исходов будем обозначать D (<7).

2. Исходы, допустимые для коалиции N всех игроков, называются оптимальными по Парето. Исход а оптимален по Парето, если не существует такой стратегии ам х е XN, что F{x) > а.

3. Дележи - это исходы, допустимые для всех одноэлементных коалиций и для коалиции всех игроков N. Множество дележей игры G будем обозначать через

D{G).

4. Исходы, допустимые для всех коалиций игры G, составляют ее or- ядро: оно обозначается через Са (G).

Замечание 2 Любой исход игры является допустимым для пустой коалиции.

В дальнейшем мы исключаем из рассмотрения пустую коалицию, если не оговорено противное.

Утверждение 2 Каковы бы ни были семейства коалиций %j и 70 условие влечет йКг(G)с: DKi(G). Доказательство. Следует непосредственно из определений.

Следствие Для любой игры G вида (1) выполняются включения св(с)свдсад.

4. Наряду с условием допустимости ситуации (или исхода), в теории игр иногда рассматривается одно его усиление - условие вполне допустимости. Оно может быть введено следующим определением.

Определение 4. Метастратегией коалиции S называется отображение

Теоретико-игровой смысл метастратегии коалиции S -это условный выбор коалицией S своей стратегии в зависимости от выбора стратегии дополнительной коалиции N\S.

Заметим, что пара (^.у^.?) однозначно определяет ситуацию (xs (^д-^), yx,s)' исход в которой обозначается F(xSiyNXS).

Определение 5 Метастратегия xs коалиции S называется возражением этой коалиции на исход а, если при любой стратегии yNXS е Xms выполняется ws

F(xs,yN\s)>a

Исход а называется вполне допустимым для коалиции S ciN, если у коалиции S нет на него возражений в форме ее метастратегии.

Замечание 3 Поскольку возражение в форме стратегии является так же возражением в форме метастратегии, то всякий вполне допустимый для коалиции S исход такэ/се допустим для нее.

Утверждение 3 Исход а является вполне допустимым для коалиции S тогда и только тогда, когда он не является строго незапрещенным исходом этой коалиции

Доказательство. Предположим, что исход а является строго не запрещенным исходом коалиции S, то есть

0)s eXj F(xs,yNX3)>a. (4)

Фиксируя для каждой стратегии yNSS существующую согласно (4) стратегию xs е Xs, получаем метастратегию xs коалиции 5, для которой при любой yms е Хк s выполняется F(xs,yms) > а. Тогда xs будет возражением на исход а коалиции S в форме метастратегии, то есть исход а не будет вполне допустимым. Множество исходов, вполне допустимых для коалиции S cz N, обозначается далее Ds(G). Для любого семейства коалиций полагаем

SeK

Определение 6 Множество исходов, вполне допустимых для всех коалиций игры G, называется /?- ядром и обозначается В силу утверждения 3 выполняется С Ca(G).

5. Напомним определение равновесной ситуации в игре G. Определение 7 Ситуация х е XN игры G называется приемлемой для коалиции StzN, если не существует такой стратегии xseXs, для которой Н

F{x\\xs)>F(x).

Ситуация приемлемая для всех коалиций 5е % с2\ называется ситуацией тс-равновесия. В частности, ситуация, приемлемая для всех игроков игры, называется ситуацией равновесия. Она характеризуется условием: для любого ieN и любой ш, стратегии дг.'е^ выполняется F(.x||

Частным случаем ситуации равновесия является ситуация равновесия по Нэшу. Она характеризуется условием: для любого ieN и любой стратегии ш,

X > выполняется F(x\\x,,)<F(x). Отметим, что ситуация равновесия xeXN будет ситуацией равновесия по Нэшу тогда и только тогда, когда любой исход F(*||*/)(/ 6 N,xt'e X) сравним с

ИСХОДОМ ПО ПОрЯДКу COj.

Ситуация, приемлемая для всех коалиций игры G, называется ситуацией сильного равновесия; множество всех ситуаций сильного равновесия игры G обозначается SE(G).

Утверждение 4 Если ситуация xeXN является приемлемой для коалиции S, то исход в этой ситуации F(x) будет вполне допустимым для коалиции S, а следовательно допустимым для нее.

Доказательство: Достаточно доказать для произвольной коалиции S с= N и ситуации xeXN, что если исход F(x) не является вполне допустимым для коалиции S, то ситуация х не будет приемлемой для S. Действительно, предположим, что исход F(x) не является вполне допустимым для коалиции S. Тогда у коалиции S существует возражение на исход F(x) в форме метастратегии xs, т.е. tos соотношение F(xs,yms)> F(x) выполняется при любой стратегии yN,seXss. Полагая yN\S = xNXS, получаем o)s

OS

Обозначая xs(xNXS) = xs\ имеем F(xs',хыкз)>F(x). Так как ситуация (xs',xNXS) v.t совпадает с ситуацией xs', получаем F(xs,yN\s)> F(x) в противоречие с тем, что ситуация х является приемлемой для коалиции S.

Следствие 1 Если х- ситуация равновесия в игре G, то исход в ней является вполне допустимым исходом игры G, а, следовательно, индивидуально рациональным.

Следствие 2 Если х- ситуация сильного равновесия в игре G, то исход в ней принадлежит [3 - ядру, а значит и а- ядру игры G.

6. Дадим теперь, следуя Э. Мулену [18], для введенных выше принципов оптимальности общее описание в терминах угроз. Заметим вначале, что понятия допустимости и вполне допустимости, введенные для исходов игры, переносятся на ее ситуации: ситуация xeXN называется (вполне) допустимой, если исход F(x) (вполне) допустим.

Фиксируем коалицию S с N. Отображение ^ : Xs -> Xms называется предостережением для коалиции S в ситуации xeXN, если оно удовлетворяет следующим двум условиям:

1) если xs'=xs ,то %ms(xs,) = xN,s;

0>s

2) если jcjVjc^to F{xs\^s(xs'))^ F{x).

Теоретико-игровой смысл предостережения состоит в том, что оно дает «сценарий реагирования» дополнительной коалиции N\S на возможные отклонения коалиции S от сложившейся ситуации х\

Г) если коалиция S не отклоняется от своей первоначальной стратегии xs, то реагирования дополнительной коалиции не происходит;

2') если коалиция S отклоняется от первоначальной стратегии, заменяя xs на xs', то результат реагирования дополнительной коалиции N\S есть ее стратегия (xs'), такая, что исход в полученной ситуации не будет строго лучшим для коалиции S по ее отношению предпочтения cos, чем исход в первоначальной ситуации х.

Таким образом, наличие указанного отображения предостерегает в ситуации х коалицию S от изменения своей первоначальной стратегии.

Определение 8 Говорят, что ситуация х е XN игры G стабилизируется с помощью простых угроз, если для нее существует «сценарий предостережений» в виде набора предостережений S с N.

Замечание 4 Пассивное предостережение дополнительной коалиции N\S есть ее предостережение вида %N\S(xs*) = xNXS (т.е. на любое отклонение коалиции S от первоначальной стратегии дополнительная коалиция не реагирует). Очевидно, что ситуация х является ситуацией сильного равновесия тогда и только тогда, когда для нее существует сценарий пассивных предостережений.

Утверждение 4. Ситуация х игры G является допустимой для коалиции S тогда и только тогда, когда в ситуации х существует предостережение со стороны дополнительной коалиции N\S.

Доказательство: Ситуация х допустима для коалиции S тогда и только тогда, когда то есть уs fxseXs) (Зу ms

Последнее эквивалентно существованию отображения %NXS : Xs -» Л- с й>,у условием: F(jf,' xs'))t>F(x) Vx s'eXs, т.е. эквивалентно существованию предостережения для коалиции S в ситуации х (можно положить <HNXS(xs) = yms, так как в этом случае требуемое соотношение выполняется).

Следствие 1 Ситуация х игры G является допустимой для всех игроков (индивидуально рациональной) тогда и только тогда, когда в ситуации х существует сценарий предостережений вида , т.е. сценарий предостережений со стороны коалиций АЛ/, где i eN.

Следствие 2 Ситуация х является допустимой для всех коалиций игры G (т.е. принадлежит ее а-ядру) тогда и только тогда, когда в ситуации х существует сценарий предостережения вида (4n\s) S^N, т.е. сценарий предостережений со стороны всех коалиций N\S, где S czN.

Аналогичным образом могут быть охарактеризованы ситуации, вполне допустимые для коалиций игры G. А именно, ситуация х игры G является вполне допустимой для коалиции S тогда и только тогда, когда в ситуации х существует предостережение со стороны коалиции N\S, не зависящее от отклонения коалиции S (т.е. предостережение в виде константной функции).

7. В данной диссертации основное внимание уделено принципам оптимальности, основанным на понятии допустимости исхода. В соответствии с этим, исследуются вопросы, связанные с существованием в играх с упорядоченными исходами индивидуально рациональных исходов, дележей, и а-ядра, а также вопросы, касающееся структуры этих множеств. Этот материал составляет содержание первых двух глав работы. Содержанием третьей главы диссертации являются обратные задачи для класса кооперативных игр с квазиупорядоченными исходами. Обратная задача в теории игр есть задача восстановления игры по некоторым ее характеристикам (пример решения обратной задачи в классической теории игр - известная теорема (см. например [И] или [3]), дающая восстановление игры п лиц с численными выигрышами по заданной характеристической функции V(S). В нашем случае обратная задача принимает следующий вид: по заданной оценочной структуре и некоторой информации о возможностях игроков или коалиций требуется построить реализационную структуру игры, т.е. восстановить саму игру.

1. Аракелян А.А. Решение для системы нерефлексивных транзитивных отношений заданных в метрическом пространстве.//Уч.зап.Ереван.ун-та. Естеств. Науки., 1973,№1 (122),с. 155-159.

2. Аракелян А.А. Бинарные отношения на компактных пространствах и их ядра. // В сб. Успехи теории игр. изд. МИНТИС, Вильнюс, 1973, с.125-126

3. Берж К. Общая теория игр нескольких лиц. М.: ФМ, 1961, 127с.

4. Бондарева О.Н. Решение и ядро ациклического отношения на константе // Успехи теории игр. изд. МИНТИС, Вильнюс, 1973, с. 127-130

5. Вилкас Э. Й. Относительность в играх и решениях. М.: Наука ФМ, 1990, 256с.W

6. Вилкас Э. И. Понятия относительности в теории игр. // Современные направления теории игр. изд. МОКСЛАС, Вильнюс, 1976, с.25-43

7. Вилкас Э. И. Согласованность коалиционных утверждений // Успехи теории игр. изд. МИНТИС, Вильнюс, 1973, 83-92

8. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. -М.: Радио и связь, 1981, 328с.

9. Вопросы анализа и процедуры принятия решений. // Сб. переводов под ред. Шахнова И.Ф. М.: Мир, 1976, 203с.

10. Воробьев Н.Н. Современное состояние теории игр. УМН, чХХУ вып.2 (152), 1970, с.81-140И. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985, 272с.

11. Данилов Н.Н., Зенкевич Н.А. Неантагонистические игры двух лиц. Учеб пособ. изд. Кемеровского РУ. Кемерово, 1990, 99с.

12. Зенкевич Н.А., Сурвило Т.Г. К вопросу об играх с неопределенными платежными материалами //Вестник ХГУ им Н. Катанова, Вып.1, сер.1, Абакан, 1996, с. 14-17

13. Кукушкин Н.С., Морозов В.В. Теория неантагонистических игр. М.: изд. МГУ.- 1984, 104с.

14. Кулаковская Т.Е. Классические принципы оптимальности для бесконечных кооперативных игр. // В сб. Современные направления теории игр. изд. МОКСЛАС. Вильнюс, 1976, с.94-108

15. Льюс Р, Райфа X. Игры и решения: пер с анг. Под ред. Юдина Д.Б. М.: ИЛ. 1961.

16. Миркин Б.Г. Проблема группового выбора. М.: Наука, 1979.

17. Мулен Э. Кооперативное принятие решений: аксиомы и модели.//Пре. С анг. М.: Мир, 1991,464с.

18. Пасечник М.В. Условия непустоты Са ядра в антагонистических играх с упорядоченными исходами. // Механика. Математика Сб. науч. трудов Саратов. Изд. Сарат. ун-та, 2001 - Вып.З - С 101-104.

19. Пасечник М.В. Дележи в бесконечных играх с квазиупорядоченными исходами. // Механика. Математика. Сб. науч. турдов Саратов. Изд. Сарат. ун-та, 2002, - Вып.4 - С. 114-117.

20. Пасечник М.В. Условия единственности дележа в антогонистических играх с упорядоченными исходами // Компьютерные науки и информационые технологии // Тез. К63 докл. Междунар. Конф. Саратов. Изд. Сарат. Ун-та, 2002, с.84.

21. Пасечник М.В.Характеризация множества индивидуально рациональных исходов и множества дележей в играх с кввазиупорядоченными исходами// Математика. Механика: Сб. науч. тр. Саратов Изд. Сарат. 2003. - Вып.З -С.84-87.

22. Пасечник М.В. Розен В.В. Игры с квазиупорядоченными исходами, имеющие единственный индивидуально рациональный исход// Математика. Механика. Сб. науч. тр. Саратов Изд. Сарат. ун-та, 2002. Вып.З - С. 87-90.

23. Пасечник М.В. Характеризация гарантированных исходов коалиций в играх с квазиупорядоченными исходами, /в. Рус. - Деп. в ВИНИТИ 09.03.04 № 405-В 2004.

24. Петросян J1.A., Данилов Н.Н. Кооперативные дифференциальные игры и их приложения. Томск, 1985, с.

25. Петросян JI.A., Зенкевич Н.А. Семлина Е.А. Теория игр. М.: Книжный дом. Университет Высшая школа. - 1998, 301с.

26. Печерский C.J1., Соболев А.И. Проблема оптимального распределения в социально-экономических задачах и кооперативные игры. Наука JIO. -1983. 176с.

27. Подиновский В.В. Общие антогонистические игры. ЖВМ и МФ, том 21, №5,1981. С.1140-1153

28. Розен В.В. Порядковые инварианты и проблема «окружения» для игр с упорядоченными исходами. Кибернетика и системный анализ, №2, 2001, с. 145-159.

29. Розен В.В. Игры с упорядоченными исходами и моноконтактно порожденные решетки // В сб. упорядоченные множества и решетки. Вып. 5, изд. СГУ. Саратов, 1978, с.90-97.

30. Розен В.В. Математические модели принятия решений в экономике. М.: Книжный дом. Университет - Высшая школа, 2002, 288с.

31. Розен В.В. Ситуации равновесия в играх с упорядоченными исходами.// Сб. Современные направления теории игр. Вильнюс, изд.МОКСЛАС, 1976, с.115-118

32. Розен В.В. Смешанные расширения игр с упорядоченными исходами. -ЖВМ и МФ, №6,1976, с.1436-1450

33. Розен В.В. Цель оптимальность - решение. М.: Радио и связь, 1982, 169с.

34. Скорняков Л.А. Элементы теории структур. М.:

35. Смоляков Э.Р. Равновесные модели при несовпадающих интересах участников. М.: Наука, 1986, 224с.

36. Соболев А.И. Кооперативные игры. Проблемы кибернетики. Вып.39 М.: 1982, с.201-222

37. Харшаньи Д, Зельтен Р. Общая теория выбора равновесия в играх. // пер. с англ. Под ред. Зенкевича Н.А. СПб, 2001,406с.

38. Яновская Е.Б. Решение бесконечных антогонистических игр в конечно-аддитивных стратегиях. Теория вероятностей и ее применение. 1970, t.XV, №1, с.162-168

39. Aumann R.J. Utility theory without the completeness axiom. Econometrica, 1962, v.30, №3 p.445-462

40. Peleg B. The independence of Game theory of utility theory. Bull. American Math/ Soc. Vol. 72, №6,1966. P.995-999

41. Farquharson R. Sur une generalisation de la notion d'equilibrium. Cr Acad sci. Paris, 1955, 240, №1 p.46-48

42. Яновская Е.Б. конечно-аддитивные расширения бескоалиционных игр. //В сб. Современные направления теории игр. Изд. MOKCJ1AC. Вильнюс, -1976, с.136-142