25. Равновесие и доминирование в биматричных играх.

Мы предполагаем уделить основное внимание случаю, когда у каждого из игроков имеется ровно две стратегии, т. е. случаю т = п = 2. Поэтому нам кажется уместным выписать приведенные выше формулы именно для такого случая.

В 2  2 биматричной игре платежные матрицы игроков имеют следующий вид

, ,

вероятности игра решение

а средние выигрыши вычисляются по формулам

Где ,

Сформулируем основное определение.

Определение. Будем считать, что пара чисел , ,

определяет равновесную ситуацию, если для любых р и q, подчиненных условиям одновременно выполнены следующие неравенства

(1)

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

Теорема 1 (Дж. Нэш). Всякая биматричная игра имеет хотя бы одну равновесную ситуацию (точку равновесия) в смешанных стратегиях.

Если некоторая пара чисел (р*, q*) претендует на то, чтобы определять ситуацию равновесия, то для того, чтобы убедиться в обоснованности этих претензий, или, наоборот, доказать их необоснованность, необходимо проверить справедливость неравенств (1) для любого р в пределах от 0 до 1 и для любого q в пределах от 0 до 1. В общем случае число таких проверок бесконечно. И, следовательно, действенный способ определения равновесной ситуации нужно искать где-то в ином месте.

Теорема 2. Выполнение неравенств

(1)

равносильно выполнению неравенств

(2)

Иными словами, для того, чтобы убедиться в обоснованности претензий пары (р*, q*) на то, чтобы определять равновесную ситуацию, нужно проверить справедливость неравенства

только для двух чистых стратегий игрока А (р = 0 и р = 1) и неравенства

только для двух чистых стратегий игрока В (q = 0 и q= 1).

26. Основные понятия кооперативных игр.

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

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

Обозначим через N множество всех игроков, причем игроков принято различать по их номерам, т.е. N={1,2,...,n}, а через S – любое его подмножество, которое является коалицией. Очевидно, что число коалиций,состоящих из k игроков, равно числу сочетаний из n по k, то есть k n C ,Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от количества n всех игроков в данной игре.Образовав коалицию, множество игроков S действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков. Общность интересов игроков из S означает, что выигрыш объединенного игрока есть сумма выигрышей составляющих его игроков из S.Пусть игроки из N, образуя различные коалиции, могут получать некоторые сравнимые между собой выигрыши. Обозначим выигрыш, который может уверенно обеспечить себе коалиция S Ì N, через V(S). Функция V, ставящая в соответствие каждой коалиции S наибольший уверенно получаемый ею выигрыш V(S), называется характеристической функцией. Если для всех непересекающихся подмножеств А и В выполняется

Неравенство V(A È B) ≥ V(A) + V(B) (1), то характеристическая функция является супераддитивной. Свойство супераддитивности означает, что если нет ни одного игрока, который входил бы одновременно в обе коалиции А и В, то коалиция, составленная как объединение этих двух подмножеств, будет иметь выигрыш не меньший, чем сумма выигрышей А и В. Предположение о супераддитивности является вполне логичным, т.к. создание коалиций было бы бессмысленным,

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

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

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

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

Четвертое допущение – оптимальность по Парето; не может быть решением такой набор платежей, помимо которого существует другой набор, более выгодный хотя бы для одного игрока. При выполнении этих условий, единственным решением является пара платежей (Х1, Х2), которые максимизируют произведение превышений этих платежей над платежами при угрозе (Y1, Y2)

27. Игры с неполной информацией.

Игры с неполной информацией – игры, в которых часть игровой информации взаимно скрыта от всех участников игры.

К данному типу относятся карточные игры (преферанс, деберц, дурак, тысяча, покер, кинг и т.д.), нарды (короткие, длинные), маджонг, домино.

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

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