Теперь, когда мы рассмотрели достаточно много примеров, давайте подробнее обсудим теоретические свойства равновесий Нэша, совершенных на подыграх. Во всех играх, которые мы рассматривали до этого, существовало равновесие Нэша, совершенное на подыграх. Верно ли, что оно существует вообще в любой игре? Ответ на этот вопрос дает теорема Цермело. Она утверждает, что в любой конечной последовательной игре c полной информацией существует равновесие Нэша, совершенное на подыграх. Всегда ли это равновесие, совершенное на подыграх, единственно? Нет, существует контрпример. Мы можем рассмотреть игру, которая сейчас представлена на ваших экранах. В этой игре — решаем ее c конца — второму игроку, если первый выбрал стратегию s1, у второго игрока есть выбор между стратегиями t1 и t2. Каждая из них приносит второму игроку 0. Значит, второй игрок безразличен между этими двумя стратегиями, значит — откатываемся назад — какое решение принять первому игроку? Он знает, что если он выберет стратегию s2, то точно получит единицу, а если s1, то либо 2, либо 3, в зависимости от того, что выбрал второй игрок. Но и двойка, и тройка больше единицы. Поэтому в этой игре будет два равновесия, совершенных на подыграх. Это профиль (s1, t1) и профиль (s1, t2). Это пример игры, в которой есть несколько равновесий Нэша, совершенных на подыграх. Бывают ли условия, которые могут гарантировать единственность равновесия, совершенного на подыграх. Всё-таки хочется от игры всегда единственного решения. Оказывается, что да. Существует класс игр, для которых равновесие Нэша, совершенное на подыграх, единственно. Если, например, платежи каждого из игроков различны в каждой терминальной вершине, в которую приходит игра, то тогда — и это можно проверить с помощью алгоритма обратной индукции — равновесие Нэша, совершенное на подыграх, будет единственное. Всё дело в том, что несколько равновесий могут появиться только в том случае, если на какой-то подыгре какой-то игрок безразличен между несколькими своими вариантами. У него есть несколько одинаково привлекательных для него вариантов. Если такую возможность исключить, потребовав разные платежи в каждой терминальной вершине для любого игрока, то тогда мы гарантируем, что алгоритм обратной индукции будет давать на каждой подыгре единственное оптимальное действие каждого из игроков. Отсюда следует, что если все платежи всех игроков различны, то в такой конечной последовательной игре с полной информацией существует единственное равновесие Нэша, совершенное на подыграх. Давайте рассмотрим еще один важный класс игр. Это так называемые игры с нулевой суммой. Представим, что у нас есть два игрока, которые играют на какую-то сумму — на один рубль, например. И чем бы ни закончилась игра, платежи, которые получат игроки, всегда противоположны. То есть платеж первого игрока — это минус платеж второго. Вот предположим, что у нас в такой игре оказалось два равновесия Нэша, совершенных на подыграх. Могут ли платежи игроков в этой игре различаться? Оказывается, что нет. Если в какой-то игре с нулевой суммой есть два равновесия, совершенных на подыграх, тогда платежи каждого из игроков в этих равновесиях равны. Почему это так? Очень просто. Давайте снова попробуем анализировать игру с конца. Если в какой-то момент у какого-то из игроков оказалось несколько одинаково привлекательных стратегий, то это означает, что какую бы из них он ни выбрал, в случае, если игра придет сюда, то он сможет гарантировать себе один и тот же платеж. Поскольку у нас игра с нулевой суммой, то это означает, что платеж второго игрока в каждом из этих исходов, в который может прийти игра, будет тоже одинаковым. Он будет противоположен платежу, который получит первый игрок. Проделывая это рассуждение несколько раз подряд, мы возвращаемся к началу игры и в начале игры убеждаемся, что в любом равновесии Нэша, совершенном на подыграх, в игре с нулевой суммой каждый игрок получает один и тот же платеж. Примером игры с нулевой суммой являются шашки. Если один из игроков выигрывает, то другой проигрывает. Давайте посмотрим на дерево игры в шашки. Шашки — это конечная игра. Из теоремы Цермело следует, что поскольку в любом равновесии Нэша, совершенном на подыграх, платежи всех игроков одинаковы, то возможно ровно одно из трех: либо в любом равновесии побеждают белые, либо в любом равновесии побеждают черные, либо в любом равновесии ничья. Невозможно придумать две такие партии, в которых игроки играют правильно, но в которых результаты этих игр различаются. И, соответственно, возникает вопрос: так а шашки, это ж какая игра? Выигрышная для белых? Выигрышная для черных? Или ничейная? Оказывается, — и это оказалось совсем недавно, в 2007 году, — что если просчитать всё дерево игры шашек с конца, то в любом равновесии, совершенном на подыграх, партия закончится вничью. Компьютеры, которые работали над тем, чтобы просчитать это дерево много лет, закончили работу в 2007 году, и стало понятно, что шашки — это ничейная игра. Стало ли от этого неинтересно играть в шашки? Нет, не стало, потому что ни один нормальный человек не может запомнить, как действовать на каждой подыгре, в которой чисто теоретически он может оказаться. Ни один человек не может просчитать до конца всё дерево игры в шашки. Поэтому чемпионаты по шашкам никуда не пропадут. Однако играть против компьютера, который точно знает, как правильно играть в каждой позиции, в которую только может прийти игра, будет очень тяжело. Если вы хотя бы один раз сделаете ошибку и сыграете стратегию, которая выходит за рамки равновесных, то тогда компьютер сразу же использует эту вашу ошибку и выиграет эту партию. Такой компьютер ошибок прощать не будет. Он знает, как играть правильно абсолютно в каждой подыгре. Однако если вы будете играть друг с другом, то тогда в ответ на вашу ошибку еще более серьезную ошибку может допустить соперник. Тогда у вас будут оставаться шансы на победу. Поэтому смысл игры в шашки, после того как стало понятно, что шашки — это ничейная игра, не пропадает. Про шахматы до сих пор неизвестно, а шахматы — это какая игра? Ничейная? Или, может быть, всё-таки существует стратегия, которая гарантированно позволяет белым обеспечить себе победу? А может быть, вообще, ходить первым — это недостаток, а не преимущество? И, может быть, существует стратегия, которая позволяет черным гарантировать себе победу? Пока мы не можем ответить на этот вопрос. Дерево игры в шахматы гораздо больше, чем дерево игры в шашки, и мощностей современных компьютеров пока не хватает для того, чтобы просчитать всё это дерево игры в шахматы с конца. Тем не менее можно не сомневаться, что рано или поздно этот алгоритм обратной индукции тоже завершит свою работу. Рано или поздно мы тоже узнаем: а какая же игра шахматы? Выигрышная для белых? Или выигрышная для черных? Или ничейная? Останется после этого утешать себя тем, что после шахмат есть еще го.