7.5.3Кооперативные игры
Рассмотрим только кооперативные биматричные игры. В правила таких игр входят, например, следующие:
1) все сообщения до игры, сформулированные одним участником, передаются другому без всяких искажений и понимаются ими;
2) все соглашения, достигнутые игроками, затем ими соблюдаются;
3) переговоры, проводимые до игры, не нарушают полезности матрицы игры;
4) уклониться от переговоров до игры нельзя;
5) игра происходит с достаточно большим числом партий.
В кооперативных играх игроки обычно действуют по согласованной совместной стратегии. Чистая совместная стратегия есть просто указание совместного выбора игроками какого-нибудь элемента биматрицы. Совместная смешанная стратегия есть распределение вероятностей на множестве элементов биматрицы.
Рассмотрим опять «Семейный спор». Вполне очевидные соображения влекут следующее возможное решение этого конфликта: с вероятностью 1/2 супруги вместе идут на бокс и с такой же вероятностью идут на балет, при этом средний выигрыш каждого участника равен 3/2.
Этот вывод можно подкрепить и следующими рассуждениями.
Г(2, 1)
(-1, -1)1
т.е. «Семей-
Кооперативная игра с биматрицей
К-1, -1) (1,2) ный спор», сводится фактически к нахождению оптимальной, в некотором смысле, для участников игры смешанной стратегии (р^, р^, р-ц, р^), в которой ру есть вероятность совместного выбора участниками игры элемента (д„, Ьу) биматрицы выигрышей.
72
Множество точек плоскости, координаты которых есть пары сумм 2^>ц -
-Р\1 -р!\ +Р11,Р\\ -Р\1 -Р21 + 2^2, ГДС
числа ру есть вероятности, т.е. ру > 0 и Рп + Ри + Ри + Р12= 1, есть греуголь-ник АВС, «натянутый» на точки (2, 1), (-1, -1), (1, 2). Любая точка отрезка ВС , может семейной парой считаться решением рассматриваемого конфликта. При равноправии участников ре- а' шением естественно считать точку 0(3/2, 3/2).
+ -1
Рис 1
7.5.4Оптимальность по Парето, переговорное множество
Примерно так же проводится анализ кооперативной биматричной игры двух лиц в общем случае. Для матрицы игры (а^, Ъ^ находится на плоскости многоугольник АВСО (рис. 2) — выпуклая оболочка множества всех точек (о^, &„). Каждая точка (х, у) этого многоугольника может трактоваться как средний выигрыш игроков при некоторой смешанной совместной стратегии игроков. При этом точка (х, у) доминирует точку (х', у'), если х>х'иу>у'и хотя бы одно из этих неравенств строгое. Сама точка (х', у') называется доминируемой. Понятно, что оптимальная стратегия игроков не может дать доминируемую точку.
Множество недоминируемых точек называется множе- «и ством оптимальности по Парето (на рис. 2 — ломаная ВСО). Как указано выше, оптимальная стратегия должна определяться точкой из множества Парето.
Рис 2
Существует еще меньшее множество, чем множество Парето. Оно называется перего-ворньш множеством. Определяется оно следующим образом.
Определим выигрыш ^ ^-го игрока, который он может обеспечить себе независимо от действий другого игрока. Для этого предположим, что никакого сотрудничества между игроками нет, каждый из них действует независимо от другого.
Несложно доказать, что если игрок при своей стратегии Г обеспечивает себе какой-то выигрыш I при любой чистой стратегии другого игрока, то этот игрок при этой стратегии обеспечивает себе выигрыш ( при любой смешанной стратегии другого игрока.
Поэтому для нахождения выигрыша ^ ^-й игрок должен обеспечить себе этот выигрыш при любой чистой стратегии другого игрока.
Пусть Р = (р,, ..., р^) — произвольная смешанная стратегия 1-го игрока, тогда в игре против у-й чистой стратегии 2-го игрока средний
выигрыш 1-го равен ^а^р,, поэтому для нахождения v надо решить
;
следующую задачу максимизации: v —> тах, ^<з р, >. v для всякого
I
]= 1,...,п, ^, = 1, все/7,2: 0.
;
Найденная из этой задачи стратегия игрока называется его макси-минной стратегией, а соответствующие выигрыши — максгшинньши выигрышами игроков. Ясно, что при любом исходе переговоров игроков друг с другом ни один из них не согласится получить меньше своего максиминного выигрыша. Это обстоятельство урезает множество Парето до меньшего множества, которое и называется переговорным: точка (а, Ь) из множества Парето принадлежит переговорному множеству если и только если а > у[, Ь >. у^. На рис. 2 переговорное множество есть ломаная МСМ (для нахождения переговорного множества нужно знать не многоугольник АВСО, а матрицу выигрышей).
Отметим теперь, что при выборе точки — оптимальной стратегии — в переговорном множестве сотрудничество игроков кончается и их интересы становятся противоположными: Первый тянет точку вправо, Второй — вверх.
Многие исследователи теории игр считают, что дальнейший анализ кооперативной игры, т.е. обоснование выбора точки — решения уже из переговорного множества, невозможен, ибо слишком большое значение приобретают трудноформализуемые факторы, возникающие в игре, например, различные психологические моменты.
п „ Г(0, 100) (100, 0) Рассмотрим, например, игру с матрицей: ' ^' \ ^ _
Конфронтация невыгодна игрокам (хотя каждый имеет рычаги влияния на другого). Разумной следует признать чистую стратегию выбора элемента (100,0) с передачей части дохода Первым игроком Второму.
Для разрешения всяческих спорных вопросов в теории кооперативных игр придумано много арбитражных схем. Каждая арбитражная схема есть некоторая целостная система для разрешения подобных вопросов, основанная на некоторых разумных принципах. Для кооперативных игр с двумя участниками наиболее известна арбитражная схема Нэша. К сожалению, нужно констатировать, что арбитражная схема Нэша (как, впрочем, и другие подобные схемы) имеет исключительно теоретический интерес и не привела к какому-то заметному вкладу в теорию кооперативных игр.