В одном из основополагающих выводов теории игр математик Джон Нэш доказал в 1951 году, что каждая игра двух игроков имеет по крайней мере одно равновесие. Это крупное открытие принесло Нэшу в 1994 году Нобелевскую премию по экономике (и послужило поводом для написания книги и создания фильма «Игры разума» о жизни Нэша). Такое равновесие теперь часто называют равновесием Нэша, и именно этот «Нэш» всегда пытается отследить Дэн Смит.
На первый взгляд, тот факт, что равновесие Нэша всегда существует в поединках между двумя игроками, казалось бы, должно принести нам некоторое облегчение от рекурсий зеркальной комнаты, которые характерны для покера и многих других привычных соревнований. Когда мы чувствуем, что падаем в рекурсивную кроличью нору, у нас всегда есть возможность покинуть голову оппонента и поискать равновесие, напрямую ведущее к лучшей стратегии, предполагающей рациональную игру. В игре «Камень, ножницы, бумага» попытка прочесть по лицу оппонента, что он выберет в следующий раз, может оказаться не слишком полезной, если вы знаете, что даже простой случайный выбор означает непобедимую стратегию в долгосрочной перспективе.
В более общем смысле равновесие Нэша выражает прогноз стабильного долгосрочного результата для любого набора правил. Таким образом, этот подход – бесценный инструмент не только для прогнозирования и формирования экономической политики, но также и для социальной политики в целом. Как утверждает лауреат Нобелевской премии экономист Роджер Майерсон, равновесие по Нэшу «имело такое фундаментальное и всеобъемлющее влияние на экономику и социальные науки, которое сопоставимо с открытием двойной спирали ДНК в биологии».
Однако информатика усложняет эту ситуацию. В самом широком смысле объектом исследований в математике является истина; объектом исследований в информатике является сложность. Нетрудно заметить, что недостаточно иметь решение проблемы, если такая проблема трудноразрешима.
В контексте теории игр знание, что равновесие существует, не говорит нам, что это такое или как его найти. Как пишет ученый Калифорнийского университета в Беркли Христо Пападимитриу, теория игр «предсказывает равновесное поведение агентов, как правило, без учета того, каким образом такое состояние будет достигнуто, оставляя это в первую очередь на усмотрение того, кто будет этим заниматься». Стэнфордский ученый Тим Ругарден вторит ему, выражая свою неудовлетворенность доказательством Нэша о том, что равновесие всегда существует. «Хорошо, – говорит он, – мы ведь программисты, не так ли? Тогда дайте нам что-нибудь, что мы можем использовать. Не надо говорить мне, что это где-то там; скажите мне, как это найти». Итак, исходное поле боя в теории игр породило теорию алгоритмических игр, то есть изучение теоретически идеальных игровых стратегий переросло в изучение того, как машины (и люди)