Теория игр охватывает невероятно широкий спектр сценариев сотрудничества и конкуренции, но начиналось все с покера – соревнования между двумя людьми, где выигрыш одного из игроков означает проигрыш другого. Математики, анализирующие эти игры, пытаются найти так называемое равновесие – некий набор стратегий, которым оба игрока могут следовать таким образом, чтобы ни один из игроков не хотел бы изменить собственную игру, даже учитывая игру соперников. Это называется равновесием потому, что это состояние стабильности: никакое количество дальнейших обдумываний не предоставит никому из игроков другого выбора. Я удовлетворен своей стратегией, принимая во внимание вашу, а вы довольны вашей стратегией, учитывая мою.

Например, в детской игре «Камень, ножницы, бумага» равновесие достигается примерно каждую треть времени при совершенно случайном выборе одного из названных жестов. Устойчивым это равновесие делает то, что раз оба игрока приняли эту то нет ничего лучше, чем и в дальнейшем ей следовать. (Если даже мы попытаемся чаще выбирать, скажем, камень, то наш противник быстро это заметит и начнет чаще выбирать бумагу, что заставит нас чаще выбирать ножницы; и так далее – до тех пор, пока вновь не восстановится равновесие

В одном из основополагающих выводов теории игр математик Джон Нэш доказал в 1951 году, что каждая игра двух игроков имеет по крайней мере одно равновесие. Это крупное открытие принесло Нэшу в 1994 году Нобелевскую премию по экономике (и послужило поводом для написания книги и создания фильма «Игры разума» о жизни Нэша). Такое равновесие теперь часто называют равновесием Нэша, и именно этот «Нэш» всегда пытается отследить Дэн Смит.

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

В более общем смысле равновесие Нэша выражает прогноз стабильного долгосрочного результата для любого набора правил. Таким образом, этот подход – бесценный инструмент не только для прогнозирования и формирования экономической политики, но также и для социальной политики в целом. Как утверждает лауреат Нобелевской премии экономист Роджер Майерсон, равновесие по Нэшу «имело такое фундаментальное и всеобъемлющее влияние на экономику и социальные науки, которое сопоставимо с открытием двойной спирали ДНК в биологии».

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

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

При этом выясняется, что попытки задавать слишком много вопросов о равновесии Нэша быстро приводят вас к ожидаемым неприятностям. К концу XX столетия выяснение того, имеет ли игра более одного равновесия (или имеет равновесие, которое дает игроку определенные преимущества, или имеет равновесие, которое подталкивает игрока к совершению какого-либо действия), оказалось неразрешимой проблемой. Позже, с 2005 по 2008 год, Пападимитриу и его коллеги доказали, что даже простые поиски равновесия Нэша также являются неразрешимой задачей.

Простые игры, как «Камень, ножницы, бумага», могут иметь равновесие, заметное с первого взгляда, но для игр с уровнем сложности реального мира – и это теперь ясно – мы не можем утверждать, что участники смогут обнаружить или достичь равновесия в игре. Это в свою очередь означает, что создатели игры не обязательно используют равновесие, чтобы предсказать, как будут вести себя игроки.

Последствия этого отрезвляющего результата оказались глубоки: равновесие Нэша заняло почетное место в экономической теории как способ моделировать и прогнозировать поведение рынка. Хотя некоторые считают, что это место занято незаслуженно. Как объясняет Пападимитриу, «если концепция равновесия не является успешно исчисляемой, то бóльшая часть ее надежности и убедительности, такая как предсказание поведения рациональных экономических агентов, попросту теряется». Ученый из Массачусетского технологического института Скотт Ааронсон с ним соглашается. «На мой взгляд, – говорит он, – если теорема о существовании равновесия Нэша считается уместной по отношению к дебатам на тему, скажем, свободных рынков против государственного регулирования, то теорему, что поиски этих равновесий неразрешимы, следует считать также уместной». Пророческие способности теоремы равновесия Нэша имеют значение только тогда, когда эти равновесия действительно могут быть найдены самими игроками. По словам бывшего директора по исследованиям eBay Камаля Джейна, «если ваш компьютер не может его найти, то и рынок не сможет это сделать».