Кооперативные игры и многошаговые процессы принятия решений

 

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

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

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

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

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

Обозначим через N множество всех игроков, причем игроков принято различать по их номерам, т. е. N ={1,2,..., n }, а через S – любое его под-множество, которое является коалицией. Очевидно, что число коалиций, состоящих из k игроков, равно числу сочетаний из n по k, то есть C_n^k а число всевозможных коалиций равно2 ⁿ  . 

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

Пусть игроки из N, образуя различные коалиции, могут получать некоторые сравнимые между собой выигрыши. Обозначим выигрыш, который может уверенно обеспечить себе коалиция S,через V (S).

Функция V, ставящая в соответствие каждой коалиции S наибольший уверенно получаемый ею выигрыш V (S), называется характеристической функцией. Таким образом: Кооперативной игрой называется пара N, V, где N – это множество игроков, а V – это характеристическая функция. Характеристическая функция описывает величину выгоды, которую данное подмножество игроков может достичь путем объединения в коалицию и определяет выигрыш получаемый коалицией S при рациональных действиях её участников.

Характеристическая функция обладает следующими свойствами:
1.	Персональность:V 0
Предполагается, что пустая коалиция (не состоящая ни из одного
игрока) зарабатывает ноль.
2.	Дополнительность: V (K) + V(N\ K) = V (N)
Сумма выигрышей коалиции и остальных игроков должна равняться
общей сумме выигрышей всех игроков;
3.	Монотонность: A > B: V (A) > V (B)
У больших коалиций выигрыши больше;
4.	Супераддитивность V (A + B) >= V (A) +V (B)

 

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

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

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

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

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

Первое допущение – симметрия. Предполагается, что решение не зависит от того, какие номера присвоены игрокам.

Второе допущение – инвариантность относительно линейных преобразований. Решение не зависит от монотонных линейных преобразований платежей.

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

Четвертое допущение – оптимальность по Парето; не может быть решением такой набор платежей, помимо которого существует другой набор, более выгодный хотя бы для одного игрока. При выполнении этих условий, единственным решением является пара платежей X ₁, X ₂, которые максимизируют произведение превышений этих платежей над платежами при угрозе Y ₁, Y ₂

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

V (A + B) = V (A) + V (B),при всех A  и B

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

Таким образом, вектор X =(x ₁, x ₂... x_n),удовлетворяющий условиям

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

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

Классические кооперативные игры называют играми в форме характеристической функции.

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

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

Дележ x доминирует дележ y, если существует такая коалиция K, для которой дележ х превосходит у для всех членов коалиции K (доминирование х над у по коалиции K).

То есть если выполняются следующие соотношения:

x_i   > y_i для всех i из K,

∑x_i = V (K)

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

 

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: