В теории игр нет единственно верного способа достичь равновесия

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

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

Аудиоверсия статьи: Podster | iTunes | YouTube | Скачать | Telegram

Благодаря этому открытию в 1994 году Джон Нэш получил Нобелевскую премию по экономике. Концепция равновесия — универсальный инструмент, который помогает понять, как работает стратегическое поведение не только в экономике, но и в психологии, эволюционной биологии и других сферах. Другой лауреат Нобелевской премии по экономике, Роджер Майерсон из Чикагского университета, писал: «Открытие концепции равновесия в экономической науке по значимости сопоставимо с открытием двойной спирали ДНК в биологии».

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

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

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

«Экономисты разработали стратегии, которые помогают быстро достичь равновесия», — рассказывает Авиад Рубинштейн. Сейчас он получает докторскую степень по теоретической информатике в Калифорнийском университете в Беркли. Однако он утверждает, что «существует множество довольно простых игр, в которых эти стратегии не работают».

Авиад Рубинштейн и Яков Бабиченко, математик из Израильского технологического института в Хайфе, объясняют, почему так происходит. В исследовании, опубликованном в сентябре прошлого года, они доказали, что не существует способа подстроить свою стратегию под игру так, чтобы достичь равновесия Нэша со стопроцентной вероятностью — насколько бы она не была продуманной, креативной и разумной. Это «слишком поспешный вывод», считает Рафгарден.

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

Игры с множеством игроков

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

Однако представьте себе, если 100 человек захотят пообедать вместе, не зная ничего о предпочтениях остальных. В 1950 году Нэш доказал, что даже в таких сложных играх с большим количеством игроков равновесие достижимо: по крайней мере, если добавить элемент случайности и предположить, что игроки в 60% случаев выберут китайский ресторан. Однако в 2015 году Нэш погиб в автокатастрофе, так и не предоставив механизм расчета такого равновесия.

Детально изучая доказательство Нэша, Бабиченко и Рубинштейн смогли доказать, что в целом для игроков не существует гарантированного метода даже приблизиться к равновесию, пока они не раскроют друг другу свои предпочтения. А с увеличением числа игроков, затраты времени, которые потребуются на всю эту коммуникацию, становятся непомерно высоки.

К примеру, в игре со 100 участниками существует 2^100 вариантов исхода игры, а значит, и 2^100 предпочтений, которыми следует поделиться игрокам между собой. Для сравнения, число секунд, прошедших с момента Большого взрыва, составляет лишь около 2^59.

Затруднения в коммуникации означают, что адаптирование стратегии от раза к разу не приведет к эффективному достижению равновесия, по крайней мере в случае некоторых сложных игр (как, например, в игре с выбором ресторана для 100 игроков). В конце концов, в каждом раунде игроки будут узнавать лишь малую часть новой информации друг о друге: как же счастливы они будут ужинать в одиночестве. Таким образом, пройдет 2^100 раундов, прежде чем они узнают все о предпочтениях друг друга (к этому времени, вероятно, рестораны китайской и итальянской кухни уже перестанут существовать).

«Разумеется, если время достижения равновесия превосходит возраст Вселенной, то это совершенно бессмысленно», — полагает Серджиу Харт, специалист по теории игр из Еврейского университета в Иерусалиме.

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

Открытие Бабиченко и Рубинштейна не означает, что большая часть или даже все игры подвержены данному ограничению — оно применимо лишь к некоторым из них. Многие экономисты, специализирующиеся в теории игр, моделируют реальный мир с дополнительной структурой, которая позволяет существенно сократить объем обмена информацией. К примеру, если каждый из 100 человек выбирает один из двух маршрутов, едва ли ученых будет интересовать выбор каждого отдельно взятого игрока — важно лишь число игроков на том или ином маршруте. Это значит, что данный набор установок будет симметричен, и потенциально можно будет выразить его во всей полноте за пару грамотно подобранных ходов вместо 2^100.

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

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

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

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

Надежный советчик

Новая работа проводит четкую грань между равновесием Нэша и другим, более общим понятием равновесия, появившемся через 24 года после статьи Нэша. В 1974 году Роберт Ауманн, еще один лауреат Нобелевской премии в области экономики, предложил понятие «коррелированного равновесия», описывающее сценарий, в котором каждый участник игры получает от достоверного посредника (или «коррелирующего устройства») совет для выбора стратегии. Если ни один игрок не получает стимула к отклонению от полученного совета и он уверен в том, что остальные игроки также следуют своим советам, совет посредника создает коррелированное равновесие.

Поначалу это может показаться каким-то загадочным мысленным экспериментом, однако на самом деле мы постоянно используем коррелированное равновесие: например, когда подбрасываем монетку, чтобы решить, пойдем мы в китайский ресторан или в итальянский, или когда проезжаем перекресток в порядке, указанном светофором.

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

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

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

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

Исследования показали, что при использовании многих способов минимизации сожалений игра в итоге приходит к коррелированному равновесию. Удивительно, но после примерно 100 раундов история игры будет выглядеть точно так же, как если бы посредник давал игрокам советы с самого начала. «Как будто через взаимодействие нашли [коррелирующее] устройство», — поясняет Константинос Даскалакис, ученый в области теоретической информатики Массачусетского технологического института.

Во время игры участники необязательно остаются в коррелированном равновесии: например, после 1000 раундов они могут оказаться в новом виде равновесия, как будто их игрой руководил другой посредник. Процесс похож на реальную жизнь, повторяется Рафгарден, ведь нормы общества, согласно которым устанавливается равновесие, постоянно меняются.

Во всех сложных играх, где трудно достичь равновесия Нэша, коррелированное равновесие — это «естественный ведущий кандидат» на роль решения, считает Нисан.

По мнению Майерсона, открытие равновесия Нэша раньше коррелированного равновесия — просто случайность. «Принято считать, что открытия, сделанные раньше, являются основой для всех последующих. Но в данном случае кому решать, что есть основа?»

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

«Этот вопрос начали изучать еще до моего рождения, — заявляет 30-летний Рубинштейн. — Однако мы до сих пор далеки от решения».

Оригинал: Quanta Magazine.
Автор: Эрика Кларрайх.

Переводили: Вероника Чупрова, Анна Василенко, Мария Елистратова.
Редактировали: Слава Солнцева, Илья Силаев.