Реферат: Кооперативные игры

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

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

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

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

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

Студент __________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

АРБИТРАЖНАЯ СХЕМА

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

u = {u(u₁ , ..., u_n )} - множество дележей, d = (d₁ , ..., d_n ) - точка 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) если d_i = d_j , i, j = 1, ..., n и R симметрична, то u¯_i = u¯_j , i, j = 1, ..., n (симметрия).

Другую А. с. с характеристич. функцией v(S), S ⊂ N = (1, ..., n) для игр n лиц дал Л. С. Шепли [2]. Решение Шепли φ (v) = (φ₁ (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. Арбитражная схема должна быть независимой от имён или обозначений игроков.

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

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

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

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

;

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

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

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 , то есть , а число всевозможных коалиций равно

= 2ⁿ - 1.

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

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

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

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

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

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

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

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

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

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

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

u_G (K ÈL ) ³u_G (K ) + u_G (L ), если K , L Ì N , K ÇL ¹Æ,

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

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

u_G (K ) + u (N \K ) = u (N )

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

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

x_i ³u (i ), для i Î N

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

= u (N )

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

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

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

Кооперативная игра с множеством игроков N и характеристической функцией u называется стратегически эквивалентной игрой с тем же множеством игроков и характеристической функцией u¹ , если найдутся такие к > 0 и произвольные вещественные C_i ( i Î N ), что для любой коалиции К Ì N имеет место равенство:

u¹ (K ) = k u (K ) +

Смысл определения стратегической эквивалентности кооперативных игр (с. э. к. и) состоит в том что характеристические функции с. э. к. и. отличаются только масштабом измерения выигрышей k и начальным капиталом C_i _. Стратегическая эквивалентность кооперативных игр с характеристическими функциями u и u¹ обозначается так u~u¹ . Часто вместо стратегической эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических функций.

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

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

2. Симметрия, т.е. если u~u¹ , то u¹ ~u.

3. Транзитивность , т.е. если u~u¹ и u¹ ~u² , то u~u² .

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

Решение кооперативной игры при помощи вектора шепли

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

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

= u (S )

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

2. Аксиома симметрии . Для любой перестановки p и i Î N должно выполняться (pu) = j_i ₍ u), т.е. игроки, одинаково входящие в игру, должны “по справедливости” получать одинаковые выигрыши.

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

j_i ₍ u¢ + u¢¢) = j_i ₍ u¢) + j_i ₍ u¢¢),

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

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

j₍ u) = (j₁ (u), j₂ (u),..., j_n (u)),

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

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

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

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

w_S (T ) =

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

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

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

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

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

a ₁ = 10, a₂ = 20, a ₃ = 30, a ₄ = 40.

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

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

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

{1; 2; 3; 4}.

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

При нахождении j₁ необходимо учитывать, что имеется только одна коалиция 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-го игрока ситуация естественная, отвечающая силе их капитала.

Заключение

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

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

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