[Перевод] «Камень-ножницы-бумага» и теория игр
Игра «камень-ножницы-бумага» отлично подходит для того, чтобы решить, кому придётся выносить мусор. Но замечали ли вы, что происходит, когда вместо трёх выбрасываний игра продолжается раунд за раундом? Сначала вы выбираете принцип, который даёт вам преимущество, но потом противник быстро понимает его и обращает в свою пользу. В процессе изменения стратегий вы постепенно достигаете точки, в которой ни одна из сторон не может дальше совершенствоваться. Почему же такое происходит?
В 1950-х математик Джон Нэш доказал, что в любом виде игры с конечным количеством игроков и конечным количеством вариантов (таком, как «камень-ножницы-бумага») всегда существует смешение стратегий, при которой ни один игрок не может показать результатов лучше изменением только собственной стратегии. Теория таких устойчивых наборов стратегий, которые называются «равновесиями Нэша», совершила революцию в области теории игр, изменила направление развития экономики и способы изучения и анализа всего — от политических договоров до сетевого трафика. А ещё она позволила Нэшу получить в 1994 году Нобелевскую премию.
Так как же выглядит равновесие Нэша в игре «камень-ножницы-бумага»? Давайте смоделируем ситуацию, в которой есть вы (Игрок A) и ваш противник (Игрок B), снова и снова играющие в игру. В каждом раунде победитель получает очко, проигравший теряет очко, а ничья засчитывается как ноль очков.
Предположим, Игрок B выбрал (глупую) стратегию выбора в каждом раунде бумаги. Через несколько раундов побед, проигрышей и ничьих вы скорее всего заметите его систему и выработаете выигрышную контрстратегию, выбирая в каждом раунде ножницы. Давайте назовём этот набор стратегий (ножницы, бумага). Если в результате каждого раунда получаются ножницы против бумаги, то вы проложите себе дорогу к идеальной победе.
Но Игрок B вскоре замечает недальновидность этого набора стратегий. Увидев, что вы выбираете ножницы, он переключается на стратегию постоянного выбора камня. Этот набор стратегий (ножницы, камень) начинает выигрывать для Игрока B. Но, разумеется, теперь вы перейдёте к бумаге. На протяжении этих этапов игры Игроки A и B используют то, что называется «чистыми» стратегиями — единственные стратегии, выбираемые и реализуемые постоянно.
Очевидно, здесь нельзя достичь равновесия: для каждой чистой стратегии, например «всегда выбирать камень», можно выработать контрстратегию, например «всегда выбирать бумагу», которая заставит изменить стратегию ещё раз. Вы и ваш противник постоянно будете преследовать друг друга в круге стратегий.
Но вы также можете попробовать «смешанную» стратегию. Предположим, что вместо выбора одной стратегии вы можете в каждом раунде случайным образом выбирать одну из чистых стратегий. Вместо «всегда выбирать камень» смешанная стратегия может иметь вид «в половине случаев выбирать камень, в другой половине выбирать ножницы». Нэш доказал, что когда допустимы такие смешанные стратегии, в каждой подобной игре должна быть по крайней мере одна точка равновесия. Давайте её найдём.
Какова же разумная смешанная стратегия для «камня-ножниц-бумаги»? Интуитивно кажется разумным, что это «выбирать камень, бумагу или ножницы с равной вероятностью». Такая стратегия записывается как 
. Это означает, что камень, ножницы и бумага выбираются с вероятностью 
. Является ли эта стратегия хорошей?
Предположим, что стратегия вашего противника имеет вид «всегда выбирать камень». Это чистая стратегия, которую можно обозначить как 
. Какими будут результаты игры при наборе стратегий для Игрока A и для Игрока B?
Чтобы получить более чёткую картину игры, мы построим таблицу, в которой будут показаны вероятности каждого из девяти возможных результатов каждого раунда: камень у A, камень у B; камень у A, бумага у B; и так далее. В приведённой ниже таблице верхняя строка обозначает выбор Игрока B, а левый столбец — выбор Игрока A.
| A | B | К | Б | Н |
| К | |
0 | 0 |
| Б | |
0 | 0 |
| Н | |
0 | 0 |
Каждый элемент таблицы обозначает вероятность пары выбранных вариантов для каждого раунда. Это просто произведение вероятностей того, что каждый из игроков сделает соответствующий выбор. Например, вероятность того, что Игрок A выберет бумагу, равна , а вероятность того, что Игрок B выберет камень, равна 1, то есть вероятность (камень у A, камень у B) равна 
. Но вероятность (бумага у A, ножницы у B) равна 
, поскольку вероятность выбора Игроком B ножниц равна нулю.
Как же проявит себя Игрок A при своём наборе стратегий? Игрок A выиграет одну треть времени (бумага, камень), проиграет в одну треть времени (ножницы, камень) и в одну треть времени сыграет вничью (камень, камень). Мы можем вычислить количество очков, которые в среднем получит Игрок A в каждом раунде, вычислив сумму произведения каждого результата на соответствующую вероятность:
Таким образом, в среднем Игрок A будет получать по 0 очков за раунд. Вы будете выигрывать, проигрывать и играть вничью с одинаковой вероятностью. В среднем, количество побед и поражений уравновесят друг друга, и по сути, оба игрока придут к ничьей.
Но как мы уже говорили, вы можете улучшить свои результаты, изменив свою стратегию, предполагая, что противник не будет менять свою стратегию. Если вы перейдёте к стратегии (0,1,0) («каждый раз выбирать бумагу»), то таблица вероятностей будет выглядеть так:
| A | B | К | Б | Н |
| К | 0 | 1 | 0 |
| Б | 0 | 0 | 0 |
| Н | 0 | 0 | 0 |
В каждом раунде вы будете заворачивать в свою бумагу камень противника и получать за каждый раунд по одному очку.
То есть эта пара стратегий — для A и для B — не является равновесием Нэша: вы, как Игрок A, можете улучшить свои результаты, изменив стратегию.
Как мы увидели, чистые стратегии, похоже, не ведут к равновесию. Но что, если ваш противник попробует использовать смешанную стратегию, например 
? Это стратегия «в половине случаев выбираем камень; бумаге и ножницам достаётся по четверти случаев». Вот, как будет выглядеть таблица вероятностей:
А вот таблица «вознаграждений» с точки зрения Игрока A; это количество очков, получаемых Игроком A в каждом из результатов.
| A | B | К | Б | Н |
| К | 0 | -1 | 1 |
| Б | 1 | 0 | -1 |
| Н | -1 | 1 | 0 |
С помощью умножения мы объединим две таблицы, чтобы вычислить среднее количество очков, получаемых Игроком A за каждый раунд.
В среднем Игрок A снова за раунд зарабатывает 0 очков. Как и раньше, этот набор стратегий, для A и для B, в результате приводит к ничьей.
Но как и раньше, вы, как Игрок A, можете улучшить свои результаты, сменив стратегию: против стратегии Игрока B , Игрок A должен выбрать 
. Вот таблица вероятностей:
а вот итоговый результат для A:
То есть этот набор стратегий — для A и для B — даёт в среднем Игроку A по 
очка за раунд. После 100 игр Игрок A будет впереди на 6,25 очка. У Игрока A есть большой стимул к изменению стратегии. То есть набор стратегий для A и для B тоже не является равновесием Нэша.
Но теперь давайте рассмотрим пару стратегий для A и для B. Вот соответствующая таблица вероятностей:
Благодаря симметрии мы можем быстро вычислить общий результат:
И снова вы и ваш противник пришли к ничьей. Но разница здесь в том, что никакой из игроков не имеет стимула к изменению стратегий! Если Игрок B перешёл бы к любой неуравновешенной стратегии, где один вариант выбора — допустим, камень — выбирался чаще других, то Игрок A просто бы изменил свою стратегию и стал чаще выбирать бумагу. В конце концов это привело бы к положительному общему результату Игрока A в каждом раунде. Именно это и происходит, когда Игрок A выбирает стратегию против стратегии Игрока B .
Разумеется, если Игрок A перейдёт от к неуравновешенной стратегии, Игрок B аналогичным образом сможет получить преимущество. Поэтому ни один из игроков не может улучшить свои результаты только за счёт изменения собственной стратегии. Игра достигла равновесия Нэша.
Доказанный Нэшем факт, что такие игры имеют подобные равновесия, очень важен по нескольким причинам. Одна из причин заключается в том, что многие ситуации из реальной жизни можно смоделировать в виде игр. Когда группа людей вынуждена выбирать между личной и коллективной выгодой — например, при переговорах или в процессе конкуренции за общие ресурсы — можно увидеть, что используются стратегии и оцениваются выигрыши. Работа Нэша оказала такое большое влияние в том числе и благодаря вездесущей природе этой математической модели.
Другая причина заключается в том, что равновесие Нэша, в некотором смысле, является положительным результатом для всех игроков. При достижении этого равновесия никто из игроков не может улучшить свои результаты, меняя собственную стратегию. Могут существовать коллективные результаты, которых можно достичь, когда все игроки действуют в идеальном сотрудничестве, но если вы можете контролировать только себя, то равновесие Нэша будет наилучшим из результатов, которого вы можете добиться.
Поэтому можно надеяться, что «игры» наподобие экономических пакетов стимулирования, налоговых кодексов, условий договоров и конструкций сетей приведут к равновесиям Нэша, при которых отдельные лица, действующие в собственных интересах, придут к устраивающему всех результату и системы станут стабильными. Но играя в такие игры, разумно ли будет предположить, что игроки естественным образом придут к равновесию Нэша?
Есть искушение думать так. В нашей игре «камень-ножницы-бумага» мы сразу смогли догадаться, что ни один из игроков не смог бы сыграть лучше, кроме как играя совершенно случайно. Но частично так получается потому, что предпочтения всех игроков известны всем остальным игрокам: все знают, сколько каждый другой выиграет и проиграет при каждом из результатов. Но что, если предпочтения более скрыты и сложны?
Представьте новую игру, в которой Игрок B получает три очка, когда он побеждает против ножниц, и одно очко за любую другую победу. Это изменит смешанную стратегию: Игрок B чаще будет выбирать камень, надеясь на тройное вознаграждение при выборе Игроком A ножниц. И хотя разница в очках не влияет непосредственно на вознаграждения Игрока A, получившееся изменение стратегии Игрока B приведёт к новой контрстратегии A.
А если каждое из вознаграждений Игрока B было бы разным и скрытым, то Игроку A потребовалось бы какое-то время на выяснение стратегии Игрока B. Должно пройти много раундов, прежде чем Игрок A догадается, допустим, как часто Игрок B выбирает камень, чтобы понять, как часто ему нужно выбирать бумагу.
Теперь представьте, что в «камень-ножницы-бумагу» играют 100 человек, и у каждого из них есть разный набор тайных вознаграждений, каждое из которых зависит от того, сколько из 99 своих противников они побеждают с помощью камня, ножниц или бумаги. Сколько времени уйдёт на вычисление всего лишь правильной частоты выбора камня, ножниц или бумаги, которая необходима для достижения точки равновесия? Скорее всего, очень много. Возможно, больше, чем будет длиться сама игра. Возможно, дольше, чем срок жизни самой Вселенной!
По меньшей мере, совсем неочевидно, что даже абсолютно рациональные и вдумчивые игроки, выбирающие хорошие стратегии и действующие в собственных интересах, в результате прийдут к равновесию в игре. Эта мысль лежит в основе статьи, опубликованной онлайн в 2016 году. В ней доказывается, что не существует общего решения, которое во всех играх смогло бы привести хотя бы к приближенному равновесию Нэша. Нельзя сказать, что идеальные игроки никогда не стремятся к равновесию в играх — часто они действительно стремятся. Это просто значит, что нет никаких причин полагать, что если в игру играют идеальные игроки, равновесие будет достигнуто.
Когда мы разрабатываем транспортную сеть, мы можем надеяться, что все игроки, то есть водители и пешеходы, каждый из которых стремится найти скорейший путь домой, коллективно достигнут равновесия, в котором ничего нельзя выиграть, выбрав другой маршрут. Мы можем надеяться, что невидимая рука Джона Нэша направит их таким образом, что их конкурентные и совместные интересы — выбор кратчайшего возможного маршрута при избежании транспортных пробок — создадут равновесие.
Но наша игра в «камень-ножницы-бумагу» с постоянно увеличивающейся сложностью показывает, что таким надеждам, возможно, не суждено сбыться. Невидимая рука может и управлять некоторыми из таких игр, но другие игры сопротивляются ей, заманивая игроков в ловушку бесконечной конкуренции за выигрыш, который постоянно находится вне пределов досягаемости.
Упражнения
- Допустим, Игрок B играет со смешанной стратегией
. Какую смешанную стратегию должен выбрать A, чтобы максимизировать количество своих выигрышей в длительной перспективе? - Допустим, Игрок B играет со смешанной стратегией
. Какую смешанную стратегию должен выбрать A, чтобы максимизировать количество своих выигрышей в длительной перспективе? - Как может измениться динамика игры, если за ничью каждому из игроков будет даваться очко?
