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

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

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

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

US) = {аеЛ: (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)cVS). ms ms.

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

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

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

С содержательной точки зрения недопустимость исхода означает его неприемлемость для коалиции S. Действительно, в этом случае у коалиции S существует стратегия, которая гарантирует ей при любом выборе стратегий игроками дополнительной коалиции NS получение исхода, строго лучшего для нее, чем исход а. Множество исходов допустимых в игре 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 своей стратегии в зависимости от выбора стратегии дополнительной коалиции NS.

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

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

F (xs, yNs)>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,).

ИСХОДОМ ПО ПОрЯДКу 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. Полагая yNS = xNXS, получаем o) s.

OS.

Обозначая xs (xNXS) = xs имеем F (xs', хыкз)>F (x). Так как ситуация (xs', xNXS) v. t совпадает с ситуацией xs', получаем F (xs, yNs)> 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).

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

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

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

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

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

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

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

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

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

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

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

Аналогичным образом могут быть охарактеризованы ситуации, вполне допустимые для коалиций игры G. А именно, ситуация х игры G является вполне допустимой для коалиции S тогда и только тогда, когда в ситуации х существует предостережение со стороны коалиции NS, не зависящее от отклонения коалиции 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.