1.8. Антагонистические игры
Напомним определение игр с «нулевой суммой»:
Определение 1.8.1.
Игра Г = {/, {Si}, {иг}} называется игрой с нулевой суммой, если для любого s ? S выполняется условие I]"=1M8(si,s2,...,sn) = 0.Иными словами, такая игра представляет собой замкнутую систему: все то, что кто-нибудь выиграл, должно быть кем- то проиграно. Большинство салонных игр являются играми такого типа.
Будем далее считать, что I = {1, 2} .
Определение 1.8.2. Игра Г двух лиц с нулевой суммой называется антагонистической.
В такой игре интересы игроков диаметрально противоположны, поскольку MI(SI,s2) +^2(51,52) = 0 ИЛИ UI (.SI, 82) = — (si) ^2)) Vsi ? Si, S2 ? S2 . К числу примеров антагонистических игр можно отнести игру «Орел или Решка». В этой игре каждый из двух игроков выбирает, независимо от другого, монетку, повернутую вверх либо «Орлом», либо «Решкой». Если выбор игроков различен, то игрок 2 платит игроку 1 один доллар. Если выбор совпадает, то — наоборот. Матрица выигрышей такой игры представлена на рис. 23. «Орел» «Решка»
Рис. 23.
Как уже отмечалось, конечная антагонистическая игра называется матричной, поскольку выигрыши игроков полностью задаются матрицей выигрышей первого игрока.
Будем говорить, что игрок i выбирает максиминную стратегию, если эта стратегия является наилучшей для него в предположении, что игрок j будет выбирать свою стратегию так, чтобы максимально навредить игроку i.
Рассмотрим такую стратегию на примере игры, представленной на рис. 24.
Рис. 24.
и
Ci Ri Здесь приведена матрица выигрышей 1-го игрока. Как выбирает максиминную стратегию 1-й игрок? Он может рассуждать следующим образом: «Если я выберу свою стратегию Li, то сколько я смогу получить?» Поскольку его противник выбирает свою стратегию так, чтобы навредить игроку 1 насколько возможно, то он в ответ на Li ответит своей стратегией С2- В этом случае игрок 2 проиграет лишь 1.
Аналогично, если игрок 1 задумает сыграть С\, в ответ игрок 2 ответит С2, тогда 1-й игрок сможет выиграть лишь 2. Если же игрок 1 задумает сыграть R\, то противник накажет его, сыграв Ь2. В этом случае 1-й игрок проиграет 3, а следовательно, 2-й игрок выиграет 3. Очевидно, что для игрока 1 наилучшим будет выбор такой стратегии, которая даст емумаксимальным выигрыш из тех минимальных, которые позволит ему выиграть игрок 2, т.е. стратегии С\.
Аналогичные рассуждения применимы и для игрока 2 при выборе им своей максиминной стратегии.
Покажем, что если в антагонистической игре Г существует равновесие по Нэшу, то пара стратегий будет являться равновесной тогда и только тогда, когда стратегия каждого игрока — максиминная. Этот в некотором смысле удивительный результат обеспечивает связь между индивидуальным принятием решения и рассуждением, объясняющим причину введения такого понятия, как равновесие по Нэшу. Мы докажем заодно, что все равновесные ситуации в антагонистических играх приводят к одним и тем же выигрышам. Это свойство редко выполняется в неантагонистических играх.
Определение 1.8.3. Пусть Г — антагонистическая игра. Стратегия s^ ? Si является максиминной для игрока 1, если
min Mi(s^,s2) > min Mi(si,s2), V si ? Si.
S2ES2 S2ES2
Стратегия S2 ? S2 является максиминной для игрока 2, если min u2(si,S2) > min u2(si,s2), V s2 ? S2.
siESi siE-Si
Т.е. максиминная стратегия для игрока i является стратегией, обеспечивающей ему максимальный гарантированный выигрыш. Следовательно, максиминная стратегия игрока 1 решает задачу:
max min tti(si, S2).
Si ?Si S2ES2
Аналогично максиминная стратегия 2-го игрока решает задачу:
max min "^(si,^)-
S2ES2 siESi
Следующая очевидная лемма показывает, что нахождение максимального среди минимальных выигрышей игрока 2 эквивалентно нахождению минимума среди максимальных выигрышей игрока 1. Лемма 1.8.1. Пусть Г = {{1,2}, {Si}, {иг}} — антагонистическая игра, тогда maxS2es2 minSlg51 ^(si, S2) = - minS2G52 maxSlG5l ui(sb s2).
Доказательство этой леммы немедленно следует из следующих очевидных свойств: 1)
ттг(-/(г)) = -тахг/(г); 2)
argmmz(-f(z)) = argmax^ f(z) .
Из ЭТОГО результата следует, что стратегия s2 G S2 является решением задачи нахождения maxS2es2 minSlG51 u2(si,s2) тогда и только тогда, когда эта стратегия s2 является решением задачи minS2es2 maxSlG51 tti(si, S2) .
Поэтому при поиске такой стратегии можно воспользоваться той же матрицей выигрышей игрока 1 следующим образом: сначала в каждом столбце найти максимальный элемент, затем из всех максимальных элементов выбрать минимальный. Полученное значение является «наименьшим гарантированным проигрышем» игрока 2. Это означает, что если игрок 2 будет придерживаться стратегий, соответствующих этому минимаксному значению, то при любом поведении противника он проиграет не больше этого значения.Следующий результат устанавливает связь между равновесием по Нэшу в антагонистической игре и множеством пар максиминных стратегий.
Предложение 1.8.1. Пусть Г — антагонистическая игра. a.
Если («i,^) —равновесие по Нэшу в Г, тогда s^ является максиминной стратегией игрока 1, a sZ, — макси- ?минной стратегией игрока 2. b.
Если («i,^) — равновесие по Нэшу в игре Г, тогда
max min tti(si, S2) = min maxMi(si, s2) = S2)
si S2 S2 Si
и таким образом все равновесия по Нэшу в игре Г дают одни и те же выигрыши.
с. Если maxSl minS2 щ (si, = minS2 maxSl Mi(si, s2), является максиминной стратегией игрока 1, s^ — максиминной стратегией игрока 2, тогда (si,s2) является равновесием по Нэшу игры Г .
Доказательство.
а,Ь. Пусть («i,^) — равновесие по Нэшу, тогда
и2(«1, s2) > u2(sl, s2), V S2 е S2 или (т.к. U2 = -UI )
Ml(s^, S2) < Ml(s^, s2), V S2 E S2. Следовательно,
Mi(si)s2) = min Mi(si)s2) < maxmin Mi(si, s2). (8-1)
S2ES2 Sl s2
С другой стороны,
s2) > Mi(sb s2), V Si G Si.
Следовательно, -^(s^s^) > minS2 Mi (si, S2), V si G «Si, поэтому
Mi(si) s2) > maxmin Mi(si, S2). (8-2)
Sl S2
Таким образом, из (8.1) и (8.2) следует, что -w^s^s^) = maxSl minS2 Mi (si, S2) и s^ является максиминной стратегией игрока 1. Аналогично можно показать, что S2 является максиминной стратегией игрока 2.
Т. к. U2(SL, S2) = maxS2 minSl M2(si, S2) = -UI(SL, , то mi(s*, S2) = - maxS2 minSl m2(si, s2) = minS2 maxSl Mi(si,s2) . с. Обозначим через v* = maxSl minS2 Mi(si, S2) = minS2 maxSl Mi (si, S2) .
Из леммы следует, что maxS2 minSl M2(si, S2) = — v* . Поскольку s^ — максиминная стратегия 1-го игрока, то Mi(s^,s2) > v* Для всех s2 G S2 . Аналогично s^ — максиминная стратегия 2-го игрока, поэтомуU2(SI,S2) > —V* для всех si G «Si. Положим в этих неравенствах s2 = s2 и si = si ' тогда Mi(si's2) > V* ж > —v*. Но так как щ = -и2 ,
то Ui ^2) — v* • Отсюда следует, что -w^s^s^) = v* . Получим 111 ^2) > u2(si,s2) ИЛИ, ПОДСТаВЛЯЯ III = ~и2 имеем, U2, 82) > u2(si,s2)- А из второго неравенства u2(s1,s2) ^ — Ml(sl)s2) ИЛИ Ml(sl5s2) — Ml(sl)s2)- ЗнаЧИТ, пара (si,s2) является равновесием по Нэшу.
Заметим также, что из свойств (а), (с) следует, что равновесные стратегии являются взаимозаменяемыми в том смысле, что если (si,s2) и (s^s^) образуют равновесия, то и (si,^), (5^,52) также образуют равновесия по Нэшу. Свойство (Ь) показывает, что
max min ui (si, s2) = min max ui (si, s2)
Sl S2 S2 Si
для всех антагонистических игр, в которых существует равновесие по Нэшу.
В более общем случае, когда равновесия по Нэшу в чистых стратегиях нет, выполняется более общее свойство:
maxmin Mi(si, s2) < min maxMi(si, s2).
Sl S2 S2 Sl
Действительно, т.к. для любого s^ имеем
Mi(s'i!s2) < maxtii(si,s2), V s2 G S2,
Sl
поэтому
min Mi^, s2) < min maxMi(si, s2) V G 5*1.
S2 S2 Sl
Наличие равновесной ситуации предполагает выполнение противоположного неравенства. В примере «Орел или Решка» мы видим, что max min ui (si, s2) =
Sl s2
— 1 < min maxMi(si, s2) = 1.
s2 Sl Значит, в этой игре равновесия по Нэшу в чистых стратегиях нет, а вот во втором примере (рис. 24) мы получаем, что
max min Mi(si, s2) = 2 = min maxMi(si, s2),
si S2 S2 Sl
когда игрок 1 играет C\ , а игрок 2 играет C2 . Ситуация (Ci,C2) здесь является равновесной по Нэшу.
Если оказывается, что в антагонистической игре Г
max min щ (si, s2) = min max щ (si, s2) = v*,
Sl s2 S2 Sl
то говорят, что этот равновесный выигрыш 1-го игрока является значением игры. И, как следует из доказательства предложения, если v* является значением антагонистической игры, то это значит, что любая равновесная стратегия игрока 1 гарантирует ему выигрыш по крайней мере не меньше его равновесного выигрыша v* , а любая равновесная стратегия игрока 2 гарантирует ему не меньше его равновесного выигрыша —V* .
Поэтому любая такая стратегия игрока 2 гарантирует, что игрок 1 получит выигрыш не больше его равновесного. В неантагонистических играх равновесные стратегии игроков такими свойствами уже не обладают.
В заключение этого параграфа мы приведем классическую теорему о минимаксах, впервые доказанную Дж. фон Нейманом в 1928 г. (von Neumann, 1928)13. Теорема о минимаксах.
Если < {1, 2}, {Si, Е2}, {U\, и2} > — смешанное расширение матричной игры, то
max min mi(<7i,<72) = max min mi(<7i,<72).