Хорди Деулофеу - Дилемма заключенного и доминантные стратегии. Теория игр

Алгоритм Нэша (или по меньшей мере его суть) кажется простым. Допустим, что разные игроки проанализировали игру и каждый выбрал определенную стратегию. Зная результат игры, зададим каждому игроку вопрос: считает ли он результат удовлетворительным? Иначе говоря, предпочел бы он действовать иначе? Если ответ положителен, то есть все участники считают, что грамотно выбрали стратегию, то, согласно Нэшу, в игре достигнуто равновесие.

Рассмотрим применение этой идеи в конкретном случае. В следующей матрице приведены результаты игры с ненулевой суммой:

Оба игрока выбрали стратегию 2. Узнав результат, они остались довольны выбором и сочли, что сделали все возможное. Первый игрок (его стратегии указаны в строках) считает, что его выигрыш, 5, был максимально возможным. Второй игрок, узнав, что первый выбрал стратегию 2, также посчитал свой выбор оптимальным: он выиграл 2, а мог не выиграть ничего.

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

Следовательно, из четырех возможных результатов единственным, который не вызовет неприятия игроков, является (5, 2). Этот результат и является точкой равновесия Нэша . В партии с любым другим исходом один из игроков мог бы усомниться в правильности выбора. В этом случае в терминологии Нэша решение было бы нестабильным.

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

Однако так происходит не всегда, и порой точка равновесия выглядит непривычно и имеет необычные свойства.

Возможно, труды Нэша, особенно его первые работы, являются важнейшими после работ фон Неймана за всю короткую историю теории игр. Уже в детстве Нэш продемонстрировал выдающийся интеллект и в то же время обнаружил трудности в общении с другими людьми. Он начал изучать химию, но вскоре переключился на математику, где отличался особым талантом. В 1948 году он получил стипендию Принстонского университета, где в то время работали Эйнштейн и фон Нейман, для написания докторской диссертации по теории игр под руководством Альберта Такера. В 1950 году он представил свою диссертацию — краткую и оригинальную работу о некооперативных играх. Его труд быстро нашел широкое признание среди специалистов по теории игр. Нэш придумал настольную игру на поле с шестиугольными клетками, позднее получившую название «Геке». По-видимому, Нэш не знал, что несколькими годами ранее такую же игру придумал Пит Хейн. Нэш доказал, что в этой игре должна существовать выигрышная стратегия для первого игрока.

Начиная с 1950-х годов он работал в Массачусетском технологическом институте (MIT) и в корпорации RAND — знаменитой организации ВВС США, занимавшейся стратегическими исследованиями. Спустя некоторое время после свадьбы, в 1959 году, ему пришлось пройти курс лечения от шизофрении. Впоследствии болезнь усилилась и преследовала ученого в разные годы жизни. Несмотря на болезнь, он продолжал работать и в 1994 году получил Нобелевскую премию по экономике.

В 2001 году режиссер Рон Ховард снял фильм «Игры разума», удостоенный четырех «Оскаров», в котором рассказывается о жизни Джона Нэша и в особенности о его борьбе с шизофренией, от которой он страдал на протяжении многих лет.

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