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

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


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

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

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

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

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

Кооперативные игры получаются в тех случаях, когда, в игре nигроков разрешается образовывать определённые коалиции. Обозначим через Nмножество всех игроков, N={1, 2,..., n}, а через K— любое его подмножество. Пусть игроки из Kдоговариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из rигроков, равно числу сочетаний из nпо r, то есть <img width=«21» height=«24» src=«ref-2_1256227471-108.coolpic» v:shapes="_x0000_i1058">, а число всевозможных коалиций равно
<img width=«43» height=«45» src=«ref-2_1256227579-277.coolpic» v:shapes="_x0000_i1059">= 2n— 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, обозначаемая в этом случае через uR, называется простейшей.

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

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

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

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

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

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

супераддитивность
uG(KÈL) ³uG(K) + uG(L), если K
,
L

Ì

N, KÇL¹Æ,
т.е. общий выигрыш коалиции не меньше суммарного выигрыша всех участников коалиции;

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

uG(K) + u(N\K) = u(N) <img width=«20» height=«31» src=«ref-2_1256227856-191.coolpic» v:shapes="_x0000_i1060">


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

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

Î
N<img width=«21» height=«31» src=«ref-2_1256228047-199.coolpic» v:shapes="_x0000_i1061">
т.е. любой игрок должен получить выигрыш в коалиции не меньше, чем он получил бы, не участвуя в ней (в противном случае он не будет участвовать в коалиции); во-вторых, должно удовлетворяться условиеколлективной рациональности
<img width=«41» height=«36» src=«ref-2_1256228246-257.coolpic» v:shapes="_x0000_i1062">= u(N) <img width=«21» height=«31» src=«ref-2_1256228503-200.coolpic» v:shapes="_x0000_i1063">
т.е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем u(N), то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше, чем u(N), то это значит, что игроки должны делить между собой сумму большую, чем у них есть).

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

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

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

Nимеет место равенство:
u1(K) = ku(K) +<img width=«43» height=«36» src=«ref-2_1256228703-261.coolpic» v:shapes="_x0000_i1064"><img width=«20» height=«31» src=«ref-2_1256228964-195.coolpic» v:shapes="_x0000_i1065">
Смысл определения стратегической эквивалентности кооперативных игр (с. э. к. и) состоит в том что характеристические функции с. э. к. и. отличаются только масштабом измерения выигрышей kи начальным капиталом Ci. Стратегическая эквивалентность кооперативных игр с характеристическими функциями uи u1обозначается так u~u1. Часто вместо стратегической эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических функций.

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

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

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

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

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