Представьте себе светский приём в Версале, где каждый гость пытается не выглядеть полным идиотом. Не блистать остроумием, не покорять сердца – просто не опозориться окончательно. Казалось бы, минимальная планка, не правда ли? Однако математики обнаружили нечто удивительное: организовать такой приём, где никто не совершит совершенно катастрофической социальной ошибки, оказывается столь же сложной задачей, как и организовать идеальный бал, где каждый гость достигнет максимума счастья.
Это не метафора – это суровая математическая реальность теории игр. Коллективная галлюцинация рациональности, как я люблю её называть, обладает странным свойством: она одинаково сложна на всех своих уровнях, от гениальности до простого здравого смысла.
Начнём с классики. Равновесие Нэша – это состояние, где каждый игрок выбирает оптимальную стратегию, учитывая выбор остальных. Никто не может улучшить свою позицию, действуя в одиночку. Звучит элегантно, но есть проблема: найти такое равновесие в реальной игре примерно так же просто, как предсказать траекторию каждой молекулы в бокале шампанского.
Математики давно знают, что задачи поиска, подсчёта или даже простого определения существования равновесия Нэша относятся к классу вычислительно неразрешимых проблем. В техническом языке это означает принадлежность к классам NP-полных, NP-трудных и #P-полных задач – тем самым категориям, которые заставляют компьютеры потеть и молиться.
Причина очевидна: мы требуем от каждого игрока оптимальности. Это как требовать от каждого придворного выбрать идеальный костюм, идеальную реплику, идеальный момент для поклона – и всё это одновременно, учитывая выбор всех остальных придворных.
Здесь возникает естественный вопрос: а что если мы снизим планку? Не до полной иррациональности, конечно, но до какого-то минимального порога разумности? Что если потребовать от игроков не оптимальности, а лишь избегания наихудшего?
Это выглядит как максимально слабый критерий рациональности. Вы не обязаны выбирать лучшую стратегию – просто не выбирайте наихудшую. Не надевайте пижаму на королевский приём. Не ставьте все деньги на зеро, когда знаете, что выпадет чёрное. Не покупайте акции компании, которая уже объявила о банкротстве.
Концепция не-худшего ответа (NWR, not worst response) формализует именно это интуитивное понятие. Стратегия является не-худшим ответом, если существует хотя бы одна другая стратегия, которая приносит меньший выигрыш при данных действиях остальных игроков. Иными словами, вы не на самом дне возможностей.
Профиль стратегий, где каждый игрок выбирает не-худший ответ, называется профилем NWR. Это коллективное состояние минимальной разумности – никто не ведёт себя откровенно катастрофически глупо.
Логика подсказывает: если снизить требования, задача должна упроститься. Если поиск оптимума сложен, то поиск «просто не худшего» должен быть проще. Это как разница между созданием шедевра и избеганием полного провала – первое требует таланта, второе лишь здравого смысла.
Однако математика, эта безжалостная разрушительница интуиций, говорит иное. Исследование показывает, что задачи, связанные с профилями NWR, обладают той же вычислительной сложностью, что и задачи для равновесия Нэша. Это один из тех редких моментов, когда реальность оказывается более парадоксальной, чем любая метафора.
Рассмотрим три фундаментальные задачи:
Существование
Первая задача: определить, существует ли вообще профиль NWR в данной игре. Можно ли организовать ситуацию, где никто не совершит наихудшего выбора? Оказывается, эта задача является NP-полной – той же категории сложности, что и знаменитая проблема удовлетворимости булевых формул.
Доказательство элегантно в своей жестокости. Математики конструируют игру, где существование профиля NWR эквивалентно решению задачи 3-SAT – классической NP-полной проблемы. Представьте игру с несколькими типами участников: игроки-переменные выбирают между «истиной» и «ложью», игроки-условия проверяют выполнение логических требований, а игрок-наблюдатель следит за общей картиной.
Выигрыши устроены так хитро, что профиль NWR существует тогда и только тогда, когда существует решение исходной логической формулы. Это как построить социальную систему, где возможность всем избежать катастрофы зависит от решения сложнейшей головоломки.
Поиск
Вторая задача: если профиль NWR существует, найдите его. Это оказывается NP-трудной проблемой – по определению не проще, чем определение существования. Если бы мы могли быстро находить такие профили, мы могли бы быстро определять и их существование, что решило бы проблему первой задачи.
Ирония в том, что даже зная, что решение где-то там существует, мы не можем его эффективно найти. Это как знать, что в толпе есть человек, который не совершает грубейших ошибок, но не иметь способа его идентифицировать без проверки каждого.
Подсчёт
Третья задача: сколько существует профилей NWR? Эта проблема является #P-полной – ещё более сложной категорией. Подсчёт часто сложнее поиска, потому что требует исследования всего пространства решений.
Каждое уникальное решение логической формулы соответствует уникальному профилю NWR в сконструированной игре. Таким образом, подсчёт профилей NWR оказывается эквивалентным подсчёту всех решений сложной комбинаторной задачи.
В теории игр существует особый класс – потенциальные игры. Их особенность в том, что они обладают специальной потенциальной функцией, и поиск равновесия Нэша сводится к поиску экстремума этой функции. Существование чистого равновесия Нэша здесь гарантировано, и его часто можно найти за разумное время.
Казалось бы, вот он – спасительный островок простоты. Если в потенциальных играх равновесие Нэша находится легко, то уж профили NWR, с их минимальными требованиями, должны находиться ещё проще?
Нет. Задача поиска профиля NWR даже в потенциальных играх оказывается PLS-полной. PLS (Polynomial Local Search) – это класс задач локального поиска, где решение находится путём последовательных локальных улучшений. Звучит не так страшно, как NP-полнота, но это всё ещё вычислительная трясина.
Доказательство использует редукцию от задачи поиска локального максимума в проблеме MAX-CUT – классической оптимизационной головоломке о разделении графа. Конструируется игра, где каждая вершина графа соответствует игроку, выбирающему одну из двух сторон разреза. Профиль NWR в этой игре соответствует локальному максимуму функции разреза.
Даже в этом структурированном, почти дружелюбном контексте минимальная рациональность остаётся вычислительно неуловимой.
Что всё это говорит нам о природе рациональности и коллективного поведения? Вывод глубже, чем просто технические детали вычислительной сложности.
Во-первых, сложность не исчезает при снижении требований. Мы интуитивно полагаем, что меньшая рациональность должна быть проще. Но математика показывает: координация даже минимально разумного поведения так же трудна, как координация оптимального поведения. Проблема не в уровне рациональности – проблема в самой необходимости координации.
Во-вторых, это объясняет, почему человеческие общества так часто застревают в очевидно плохих равновесиях. Мы видим ситуации, где, кажется, любой разумный человек мог бы сделать лучше, просто избегая откровенно идиотских решений. Но коллективный переход к такому состоянию оказывается столь же труден, как и переход к оптимуму.
В-третьих, это создаёт интересный парадокс для теории ограниченной рациональности. Многие исследователи предполагали, что ослабление требований рациональности сделает модели более реалистичными и вычислимыми. Но данное исследование показывает: ослабление помогает только до определённого предела. Как только мы требуем какой-то минимальной рациональности от всех участников, вычислительная сложность возвращается в полной мере.
Исследование намекает на фундаментальный компромисс: можно либо требовать сильных гарантий рациональности от небольшой доли игроков, либо слабых гарантий от всех игроков. Но нельзя требовать любых гарантий от всех без вычислительных последствий.
Это как закон сохранения сложности в социальных системах. Вы не можете одновременно иметь универсальность и вычислимость. Либо вы допускаете, что некоторые люди будут вести себя иррационально (и тогда задача упрощается), либо вы требуете минимальной разумности от всех (и тогда задача остаётся сложной).
Реальные рынки, политические системы, социальные сети – все они существуют в этом пространстве компромисса. Мы не можем гарантировать, что каждый участник действует хотя бы минимально разумно, именно потому что проверка и обеспечение такой гарантии вычислительно невозможны.
Джон Нэш в начале 1950-х годов предложил своё знаменитое понятие равновесия, опираясь на идею взаимной оптимальности. Это была революция – впервые появился математически строгий способ предсказывать исходы стратегических взаимодействий. Нобелевская премия 1994 года лишь подтвердила значимость этой идеи.
Но уже в 1970-е годы начали накапливаться свидетельства вычислительной сложности. К концу 2000-х годов было строго доказано, что поиск равновесия Нэша относится к классу PPAD-полных задач – ещё одной категории вычислительной неразрешимости.
Это создало интеллектуальную напряжённость: с одной стороны, равновесие Нэша – фундаментальная концепция, существование которой гарантировано (по крайней мере, в смешанных стратегиях). С другой стороны, найти его практически невозможно. Как будто мы знаем, что сокровище существует, но карта к нему написана на языке, который никто не может прочитать за разумное время.
Ослабление до не-худшего реагирования выглядело как естественный путь выхода из этого тупика. Но, как показывает данное исследование, этот путь оказался иллюзией. Сложность укоренена глубже, чем предполагалось.
Есть что-то глубоко ироничное в том, что даже минимальная коллективная рациональность вычислительно недостижима. Это как если бы вселенная установила принципиальный предел на нашу способность координировать разумное поведение.
Возможно, это объясняет устойчивость того, что экономисты называют «координационными провалами». Мы все видим, что текущая ситуация плоха. Мы все знаем, что могли бы действовать лучше. Но переход к лучшему состоянию – или даже просто к состоянию, где никто не совершает наихудших ошибок – оказывается невозможным не из-за человеческой глупости, а из-за фундаментальных математических ограничений.
Финансовые пузыри, политические тупики, экологические кризисы – все они могут быть проявлениями этой фундаментальной неразрешимости. Не потому, что люди не видят проблемы, и не потому, что решения не существует, а потому что координация даже минимально разумного поведения всех участников натыкается на непреодолимые вычислительные барьеры.
Практические последствия: от теории к реальности
Какое значение эти абстрактные результаты имеют для реального мира? Больше, чем может показаться.
Во-первых, это ставит под вопрос идею «рациональных ожиданий» в экономике. Если агенты не могут даже вычислить, как избежать наихудших решений, как они могут формировать рациональные ожидания об оптимальных стратегиях?
Во-вторых, это объясняет, почему алгоритмическая теория игр и механизм-дизайн так сложны. Попытки спроектировать рынки, аукционы или протоколы, гарантирующие разумное поведение участников, натыкаются на эти фундаментальные барьеры. Даже минимальные гарантии оказываются вычислительно дорогими.
В-третьих, это имеет значение для децентрализованных систем – от блокчейнов до децентрализованных финансов (DeFi). Эти системы часто полагаются на предположение, что участники будут действовать разумно (или хотя бы избегать явно глупых действий). Но обеспечение таких гарантий для всех участников может быть принципиально невозможным.
Есть своеобразная красота в этих результатах. Они показывают, что некоторые вещи сложны не потому, что мы недостаточно умны или недостаточно технологичны. Они сложны потому, что сама структура логики и вычислений налагает фундаментальные ограничения.
Минимальная коллективная рациональность – избегание наихудшего всеми участниками – оказывается столь же неуловимой, как и коллективная оптимальность. Это не недостаток теории игр, а её глубокая истина. Координация трудна не случайно, а по необходимости.
Мы живём в мире, где даже согласиться всем не быть идиотами оказывается вычислительно эквивалентным достижению совершенства. Это одновременно обескураживает и освобождает. Обескураживает, потому что снимает надежды на простые решения социальных проблем. Освобождает, потому что объясняет, почему столь многие очевидно неоптимальные ситуации так устойчивы – дело не в злой воле или глупости, а в математике.
Деньги, как я часто говорю, – коллективная галлюцинация. Но теперь мы знаем, что даже самая минимальная коллективная рациональность – тоже галлюцинация, причём вычислительно неразрешимая. Возможно, именно поэтому человеческая история – это череда не оптимальных решений, а скорее хаотичного блуждания между различными уровнями коллективного безумия.
И в этом, признаюсь, есть что-то утешительное.
