Кооперативные игры 2

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

ИНСТИТУТ КИБЕРНЕТИКИ, ИНФОРМАТИКИ И СВЯЗИ

ОТДЕЛЕНИЕ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Задание на курсовой проект

Студент __________________________________________________________

(Ф.И.О., группа)

Тема курсового проекта: Кооперативные игры

Перечень вопросов подлежащих исследованию и разработке:

Арбитражные схемы.

Классические кооперативные игры

Кооперативные игры с бесконечным числом игроков

Руководитель курсового проекта _____________________________

(подпись, дата)

Зав. отделением ИТВТ _____________________________

(подпись, дата)

Задание принял к исполнению _____________________________

(подпись, дата)

АРБИТРАЖНАЯ СХЕМА - правило, по которому каждой игре с дележами ставится в соответствие единственный дележ этой игры, называется арбитражным решением. Первоначально А. с. были рассмотрены Дж. Нэшем для случая игры двух лиц. Пусть

u = {u(u1, ..., un)} - множество дележей, d = (d1, ..., dn) - точка status quo, т. е. точка, соответствующая случаю, когда никакой дележ не осуществляется, [R, d] - игра с дележами, u - ее арбитражное решение. Дележ u* наз. решением Нэша, если

Решение Нэша и только оно удовлетворяет следующим аксиомам:

1) если f - линейное неубывающее преобразование, то fuЇ есть арбитражное решение игры [fR, fd] (инвариантность относительно преобразований полезности); 2) uЇ ≥ d, uЇ ∈ R и нет такого u ∈ R, чтобы u ≥ uЇ (оптимальность по Парето); 3) если R' ⊂ R, d' = d, uЇ ∈ R', то uЇ ' = uЇ (независимость несвязанных альтернатив); 4) если di = dj, i, j = 1, ..., n и R симметрична, то uЇi = uЇj, i, j = 1, ..., n (симметрия).

Другую А. с. с характеристич. функцией v(S), S ⊂ N = (1, ..., n) для игр n лиц дал Л. С. Шепли [2]. Решение Шепли φ (v) = (φ1 (v), ..., φn (v)), где

γn (s) = (s - 1)!(n - s)!/n!, s - число элементов множества S, также удовлетворяет аксиоме симметрии, кроме того, ∑i φi (v) = v(N) и для любых двух игр u и v выполняется φ (u + v) = φ (u) + φ (v). Были также рассмотрены А. с. для случая сравнимых индивидуальных выигрышей (см. [3]).

Арбитражные схемы Дж. Нэша и Л. С. Шепли обобщил Дж. Харшаньи [4]. Решение Харшаньи, кроме соответствующих четырех аксиом Нэша, удовлетворяет еще двум аксиомам: 1) решение монотонно зависит от обоснованных требований игрока, 2) если u* и u** - решения, то решением будет и uЇ,

если только uЇ принадлежит границе множества R.

А. с. непрерывно зависят от параметров игры, если в R имеются лучшие дележи, чем точка status quo.

Арбитраж

Итак, математик сделал своё дело и уходит в сторону, а игроки торгуются. Чем окончится торг - неизвестно. Хорошо, если они люди сговорчивые и покладистые. К сожалению, встречаются люди (и не только люди, а целые государства), которые, желая получит себе возможно больше, торгуются очень упорно, пуская в ход всё, даже угрозы. В результате переговоры оканчиваются ничем, угрозы приводятся в исполнение… Чем это кончается можно очень часто наблюдать в жизни.

Одним из выходов из этой ситуации является приглашение со стороны некоторого арбитра, который бы одинаково относился к обеим сторонам, и предложить ему указать совместную стратегию “по справедливости”. Если арбитр действительно “справедливый” и “беспристрастный”, он может вынести устраивающее обоих игроков решение. Но что означает “справедливый” и “беспристрастный”?

Достаточно очевидно, что к такому арбитру должны быть предъявлены следующие требования.

Арбитражное решение должно быть элементом переговорного множества.

Арбитражная схема должна быть независимой от имён или обозначений игроков.

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

Арбитражное решение должно отражать действенность угроз игроков.

В теории игр для решения подобных задач часто используют аксиоматический метод, когда подобные требования пытаются формализовать в виде математических аксиом. Ниже мы изложим систему таких аксиом, принадлежащую Дж. Нэшу. В дальнейшем считается, что игрок № 1 имеет  ходов, игрок номер 2 -  ходов, платёжная матрица имеет вид , , . Через  мы будем обозначать выпуклую оболочку точек ,  - переговорное множество,  - точка status quo,  - решение арбитра.

Аксиома 1.(Оптимальность по Парето). Точка  должна быть элементом переговорного множества, то есть

в  нет точки , отличной от точки , такой, что , .

Аксиома 2.(Симметрия). Пусть игра обладает следующими свойствами:

;

если точка ,

то и точка .

Тогда должно выполняться условие .

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

Следующие две аксиомы далеко не столь очевидны, как предыдущие.

Аксиома 3.(Инвариантность относительно линейного преобразования). Пусть имеются две игры с одинаковым числом ходов для каждого игрока и с платёжными матрицами, связанными соотношениями

.

Тогда арбитражные решения для них также должны быть связаны соотношениями

Аксиома 4. (Независимость несвязанных альтернатив). Если к игре добавить новые ходы для игроков с добавлением новых элементов платёжных матриц таким образом, что точка status quo не меняется, то либо арбитражное решение также не меняется, либо оно совпадает с одной из добавленных сделок.

Дж. Нэш показал, что существует единственная арбитражная схема, удовлетворяющая этим четырём аксиомам. Арбитражное решение должно выносится из условия

,

то есть “справедливое” решение арбитра  должно удовлетворять условию

<для всех точек принадлежащих переговорному множеству.

Кстати, в игре “семейный спор”, в силу симметрии обеих игроков, арбитражным решением должна быть точка (3/2, 3/2), лежащая на середине отрезка, соединяющего точки (1, 2) и (2, 1). Она получается при следующей совместной стратегии

.

Муж и жена должны ходить вместе на футбол или в театр одинаково часто (например, по очереди).

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

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

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

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

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

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N ={1, 2,..., n}, а через K - любое его подмножество. Пусть игроки из K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r, то есть , а число всевозможных коалиций равно

= 2n - 1.

Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от числа всех игроков в данной игре. Для исследования этих игр необходимо учитывать все возможные коалиции, и поэтому трудности исследований возрастают с ростом n. Образовав коалицию, множество игроков K действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков.

Функция , ставящая в соответствие каждой коалиции K наибольший, уверенно получаемый его выигрыш  (K), называется характеристической функцией игры. Так, например, для бескоалиционной игры n игроков  (K) может получиться, когда игроки из множества K оптимально действуют как один игрок против остальных NK игроков, образующих другую коалицию (второй игрок).

Характеристическая функция  называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция  простая, то коалиции K, для которых  (K) =1, называются выигрывающими, а коалиции K, для которых  (K) = 0, - проигрывающими.

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

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

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

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

Обозначим через G характеристическую функцию бескоалиционной игры. Эта функция обладает следующими свойствами:

персональность

G () = 0,т.е. коалиция, не содержащая ни одного игрока, ничего не выигрывает;

супераддитивность

G (KL)  G (K) + G (L), если K, L  N, KL  ,

т.е. общий выигрыш коалиции не меньше суммарного выигрыша всех участников коалиции;

дополнительность

G (K) +  (NK) =  (N)

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

Распределение выигрышей (делёж) игроков должно удовлетворять следующим естественным условиям: если обозначить через xi выигрыш i-го игрока, то, во-первых, должно удовлетворяться условие индивидуальной рациональности

xi   (i), для i N

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

=  (N)

т.е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем  (N), то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше, чем  (N), то это значит, что игроки должны делить между собой сумму большую, чем у них есть).

Таким образом, вектор x = (x1,..., xn), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции .

Система {N, }, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.

Кооперативная игра с множеством игроков N и характеристической функцией  называется стратегически эквивалентной игрой с тем же множеством игроков и характеристической функцией 1, если найдутся такие к  0 и произвольные вещественные Ci (iN), что для любой коалиции К  N имеет место равенство:

1 (K) = k  (K) +

Смысл определения стратегической эквивалентности кооперативных игр (с. э. к. и) состоит в том что характеристические функции с. э. к. и. отличаются только масштабом измерения выигрышей k и начальным капиталом Ci. Стратегическая эквивалентность кооперативных игр с характеристическими функциями  и 1 обозначается так 1. Часто вместо стратегической эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических функций.

Справедливы следующие свойства для стратегических эквивалентных игр:

1. Рефлексивность, т.е. каждая характеристическая функция эквивалентна себе .

2. Симметрия, т.е. если 1, то 1.

3. Транзитивность, т.е. если 1 и 12, то 2.

Одними из наиболее интересных способов решения коалиционных игр являются решения с применением аксиом Шелли.

Аксиомы Шепли:

1. Аксиома эффективности. Если S - любой носитель игры с характеристической функцией , то

=  (S)

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

2. Аксиома симметрии. Для любой перестановки  и iN должно выполняться () = i (), т.е. игроки, одинаково входящие в игру, должны “по справедливости” получать одинаковые выигрыши.

3. Аксиома агрегации. Если есть две игры с характеристическими функциями  и , то

 i ( + ) =  i () +  i (),

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

Определение. Вектором цен (вектором Шепли) игры с характеристической функцией  называется n-мерный вектор

 () = (1 (), 2 (),..., n ()),

удовлетворяющий аксиомам Шепли.

Существование вектора Шепли вытекает из следующей теоремы

Теорема. Существует единственная функция , определённая для всех игр и удовлетворяющая аксиомам Шепли.

Определение. Характеристическая функция S (T), определённая для любой коалиции S, называется простейшей, если

S (T) =

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

Вектор Шепли содержательно можно интерпретировать следующим образом: предельная величина, которую вносит i-й игрок в коалицию T, выражается как  (T)   (T {i}) и считается выигрышем i-го игрока; i (T) - это вероятность того, что i-й игрок вступит в коалицию T {i}; i () - средний выигрыш i-го игрока в такой схеме интерпретации. В том случае, когда  - простейшая,

Следовательно

,

где суммирование по T распространяется на все такие выигрывающие коалиции T, что коалиция T {i}не является выигрывающей.

Пример. Рассматривается корпорация из четырёх акционеров, имеющих акции соответственно в следующих размерах

a1 = 10, a2 = 20, a3 = 30, a4 = 40.

Любое решение утверждается акционерами, имеющими в сумме большинство акций. Это решение считается выигрышем, равным 1. Поэтому данная ситуация может рассматриваться как простая игра четырёх игроков, в которой выигрывающими коалициями являются следующие:

{2; 4}, {3; 4},

{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},

{1; 2; 3; 4}.

Найдём вектор Шепли для этой игры.

При нахождении 1 необходимо учитывать, что имеется только одна коалиция T = {1; 2; 3}, которая выигрывает, а коалиция T {1} = {2; 3} не выигрывает. В коалиции T имеется t = 3 игрока, поэтому

.

Далее, определяем все выигрывающие коалиции, но не выигрывающие без 2-го игрока: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому

.

Аналогично получаем, что , .

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

Анализ игры показывает, что компоненты 2-го и 3-го игроков равны, хотя третий игрок имеет больше акций. Это получается вследствие того, что возможности образования коалиций у 2-го и 3-го игрока одинаковые. Для 1-го и 4-го игрока ситуация естественная, отвечающая силе их капитала.

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

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

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