Концепция равновесия Джона Нэша широко распространена в экономической теории, но новое исследование показывает, что достичь его эффективно зачастую невозможно. Комментарий Сохранить статью Прочитать позже
Во всех играх есть равновесие Нэша. Но смогут ли игроки его достичь?
Введение
В 1950 году Джон Нэш — математик, позже упомянутый в книге и фильме «Игры разума», — написал двухстраничную работу, которая перевернула экономическую теорию. Его ключевая, но при этом предельно простая идея заключалась в том, что в любой конкурентной игре существует понятие равновесия: набор стратегий, по одной для каждого игрока, такой, что ни один игрок не может выиграть больше, односторонне переключившись на другую стратегию.
Концепция равновесия Нэша, принесшая ему Нобелевскую премию по экономике в 1994 году, предлагает единую систему для понимания стратегического поведения не только в экономике, но и в психологии, эволюционной биологии и множестве других областей. Её влияние на экономическую теорию «сравнимо с влиянием открытия двойной спирали ДНК в биологических науках», – писал Роджер Майерсон из Чикагского университета, ещё один лауреат Нобелевской премии по экономике.
Когда игроки находятся в равновесии, у них нет причин отклоняться. Но как игроки вообще достигают равновесия? В отличие, скажем, от мяча, катящегося под гору и останавливающегося в долине, не существует очевидной силы, направляющей игроков к равновесию Нэша.
«Это всегда было занозой для микроэкономистов», — сказал Тим Рафгарден, специалист по теоретической информатике из Стэнфордского университета. «Они используют эти концепции равновесия и анализируют их так, как будто люди будут находиться в равновесии, но не всегда существует удовлетворительное объяснение, почему люди будут находиться в равновесии Нэша, а не просто будут его искать».
Если люди играют в игру лишь один раз, часто неразумно ожидать, что они найдут равновесие. Это особенно актуально, если — как это часто бывает в реальном мире — каждый игрок знает только, насколько он сам ценит различные результаты игры, а не насколько ценят их другие игроки. Но если бы люди могли играть многократно, возможно, они могли бы учиться на первых раундах и быстро прийти к равновесию. Однако попытки найти такие эффективные методы обучения всегда терпели неудачу.
«Экономисты предложили механизмы, позволяющие [быстро] прийти к равновесию», — сказал Авиад Рубинштейн, который заканчивает докторскую диссертацию по теоретической информатике в Калифорнийском университете в Беркли. Но для каждого такого механизма, добавил он, «существуют простые игры, которые можно построить там, где он не работает».
Рубинштейн и Яков Бабиченко, математик из Израильского технологического института (Технион) в Хайфе, объяснили, почему. В статье, опубликованной в интернете в сентябре прошлого года, они доказали, что никакой метод адаптации стратегий к предыдущим играм — каким бы разумным, креативным или умным он ни был — не приведёт к эффективному достижению даже приблизительного равновесия Нэша для каждой возможной игры. Это «очень резкий отрицательный результат», — сказал Рафгарден.
Экономисты часто используют анализ равновесия по Нэшу для обоснования предлагаемых экономических реформ, сказал Майерсон. Но новый результат говорит о том, что экономисты не могут предполагать, что игроки придут к равновесию по Нэшу, если они не могут обосновать особенности конкретной игры. «Если вы пытаетесь выяснить, легко ли ваша игра достигнет равновесия, — сказал Ноам Нисан, специалист по информатике из Еврейского университета, — вам нужно аргументировать, почему это так».
Многопользовательские игры
В некоторых простых играх легко обнаружить равновесия Нэша. Например, если я предпочитаю китайскую еду, а вы — итальянскую, но мы больше всего хотим пообедать вместе, то два очевидных равновесия — это либо мы оба пойдём в китайский ресторан, либо мы оба пойдём в итальянский. Даже если мы изначально знаем только свои предпочтения и не можем обсудить стратегии до игры, не потребуется слишком много раундов с пропущенными связями и ужинами в одиночестве, прежде чем мы полностью поймём предпочтения друг друга и, возможно, найдём путь к одному из этих равновесий.
Но представьте, что в планах ужина участвуют 100 человек, каждый из которых уже определился с тем, с кем он хотел бы пообедать, и никто из них не знает предпочтений других. В 1950 году Нэш доказал, что даже в таких больших и сложных играх, как эта, всегда существует равновесие (по крайней мере, если расширить понятие стратегии и допустить случайный выбор, например, выбор китайского ресторана с вероятностью 60%). Но Нэш, погибший в автокатастрофе в 2015 году, не дал никакого рецепта для вычисления такого равновесия.
Разобравшись в тонкостях доказательства Нэша, Бабиченко и Рубинштейн смогли показать, что в общем случае не существует гарантированного метода, позволяющего игрокам найти хотя бы приблизительное равновесие Нэша, если только они не сообщат друг другу практически всё о своих предпочтениях. И по мере роста числа игроков в игре время, необходимое для всей этой коммуникации, быстро становится невыносимым.
Например, в игре «Ресторан» на 100 игроков существует 2100 вариантов развития событий, и, следовательно, каждый игрок должен поделиться 2100 своими предпочтениями. Для сравнения, количество секунд, прошедших с момента Большого взрыва, составляет всего около 259.
Это узкое место в коммуникации означает, что любой возможный метод адаптации стратегий от раунда к раунду не сможет эффективно привести игроков к равновесию Нэша, по крайней мере, в некоторых сложных играх (например, в игре в ресторан на 100 игроков со сложными предпочтениями). В конце концов, в каждом раунде игроки узнают друг о друге лишь немного новой информации: насколько они довольны выбранным ужином. Таким образом, потребуется около 2100 раундов, прежде чем они узнают всё о ценностях друг друга (к этому времени, предположительно, китайский и итальянский рестораны уже закроются).
«Если это займет больше времени, чем возраст Вселенной, — сказал Серджиу Харт, специалист по теории игр из Еврейского университета в Иерусалиме, — то, конечно, это совершенно бесполезно».
Может показаться естественным, почти очевидным, что игрокам иногда потребуется знать всё о ценностях друг друга, чтобы найти равновесие Нэша. Однако в новой статье показано, что это же ограничение сохраняется, даже если игроки готовы ограничиться приблизительным равновесием Нэша — важный вывод для реальных приложений, где результат, близкий к равновесию Нэша, часто оказывается достаточным.
Результат Бабиченко и Рубинштейна не означает, что все или даже большинство игр будут подвержены этому ограничению — лишь то, что некоторые игры будут подвержены. Многие игры, которые экономисты используют для моделирования реального мира, обладают дополнительной структурой, значительно сокращающей объём информации, которую должен передать каждый игрок. Например, если 100 человек выбирают один из двух маршрутов для утренней поездки на работу, вам, вероятно, не важно, какие игроки поедут по каждому маршруту — вам важно только, сколько человек поедет. Это означает, что ваш набор предпочтений будет обладать высокой степенью симметрии, и вы потенциально сможете выразить его полностью парой хорошо подобранных предложений вместо 2100.
Экономисты могли бы использовать подобные аргументы для обоснования достижимости равновесия Нэша в конкретных играх. Однако новый результат подразумевает, что подобные обоснования должны проводиться в каждом конкретном случае; не существует универсального аргумента, который бы подходил для всех игр в любое время.
Более того, хотя многие игры, развивавшиеся вместе с цивилизацией, могут быть упрощены, эпоха Интернета порождает множество новых многопользовательских игр, от сайтов знакомств до онлайн-торговли акциями. «На данном этапе у нас нет медленной эволюции человечества, которая подталкивает нас только к играм, где легко найти равновесие», — сказал Нисан. «Мы разрабатываем новые игры, и если мы предполагаем, что сможем достичь равновесия, мы очень часто ошибаемся».
В реальной жизни люди часто не играют в игры, находящиеся в равновесии, и экономисты это прекрасно понимают, сказал Эндрю Макленнан, экономист из Университета Квинсленда в Брисбене, Австралия. Но, по его словам, «в экономике нет теоретической структуры, позволяющей задаться вопросом, насколько точной может быть экономика». Результаты теоретической информатики, подобные новому результату Бабиченко и Рубинштейна, «должны вдохновить на формальное рассмотрение этого вопроса», — сказал он.
Но у этих двух областей совершенно разный менталитет, что может затруднять междисциплинарное взаимодействие: экономисты склонны искать простые модели, отражающие суть сложного взаимодействия, в то время как специалисты по теоретической информатике часто больше заинтересованы в понимании того, что происходит по мере усложнения моделей. «Мне бы хотелось, чтобы мои коллеги-экономисты были более осведомлены и более заинтересованы в том, чем занимается информатика», — сказал Макленнан.
Доверенный советник
Новая работа проводит чёткую границу между равновесием Нэша и другой, более общей концепцией равновесия, которая получила известность спустя 24 года после публикации статьи Нэша. «Коррелированное равновесие», предложенное в 1974 году Робертом Ауманном, другим лауреатом Нобелевской премии по экономике, предполагает сценарий, в котором каждый игрок получает совет от доверенного посредника (или «коррелирующего устройства») о том, какую стратегию ему следует использовать. Совет посредника формирует коррелированное равновесие, если ни один из игроков не заинтересован в отклонении от полученного совета, если он уверен, что каждый из остальных игроков следует своим собственным советам.
На первый взгляд это может показаться загадочной конструкцией, но на самом деле мы постоянно используем коррелированные равновесия — например, всякий раз, когда мы позволяем подбрасыванию монеты решить, пойдем ли мы за китайской или итальянской едой, или позволяем светофору указывать, кто из нас первым проедет перекресток.
В этих двух примерах каждый игрок точно знает, какой совет «посредник» даёт другому игроку, и совет посредника по сути помогает игрокам скоординировать, какое равновесие Нэша они будут разыгрывать. Но когда игроки точно не знают, какой совет получают другие, — а знают только то, как различные виды советов коррелируют друг с другом, — Ауманн показал, что множество коррелированных равновесий может содержать больше, чем просто комбинации равновесий Нэша: оно может включать в себя формы игры, которые вообще не являются равновесиями Нэша, но иногда приводят к более позитивному общественному результату, чем любое из равновесий Нэша. Например, в некоторых играх, в которых сотрудничество принесло бы игрокам более высокий общий выигрыш, чем эгоистичные действия, посредник иногда может склонить игроков к сотрудничеству, утаивая, какой именно совет она даёт другим игрокам. Это открытие, сказал Майерсон, было «громом среди ясного неба».
И хотя посредник может давать множество различных советов, множество коррелированных равновесий игры, представленное набором линейных уравнений и неравенств, математически более поддаётся обработке, чем множество равновесий Нэша. «Если рассматривать это иначе, математика гораздо красивее», — сказал Майерсон.
Хотя Майерсон назвал теорию игр Нэша «одним из выдающихся интеллектуальных достижений XX века», он считает коррелированное равновесие, возможно, даже более естественной концепцией, чем равновесие по Нэшу. Он неоднократно высказывал мнение, что «если на других планетах существует разумная жизнь, то на большинстве из них коррелированное равновесие было бы обнаружено раньше, чем равновесие по Нэшу».
Когда речь идёт о повторяющихся раундах игры, многие из наиболее естественных способов, которые игроки могут выбрать для адаптации своих стратегий, в определённом смысле сходятся к коррелированным равновесиям. Возьмём, например, подходы «минимизации сожалений», в которых перед каждым раундом игроки увеличивают вероятность использования данной стратегии, если сожалеют, что не использовали её чаще в прошлом. Минимизация сожалений — это метод, «который действительно имеет некоторое сходство с реальной жизнью: он учитывает то, что хорошо работало в прошлом, в сочетании с периодическими экспериментами», — сказал Рафгарден.
Исследователи показали, что для многих подходов, минимизирующих сожаления, игра быстро приходит к коррелированному равновесию в следующем удивительном смысле: примерно после 100 раундов история игры будет выглядеть практически так же, как если бы посредник всё это время консультировал игроков. Как будто «[коррелирующее] устройство было каким-то образом неявно найдено в процессе взаимодействия», — сказал Константинос Даскалакис, специалист по теоретической информатике из Массачусетского технологического института.
По мере продолжения игры игроки не обязательно будут оставаться в одном и том же коррелированном равновесии — например, после 1000 раундов они могли сместиться к новому равновесию, так что теперь их история из 1000 игр выглядит так, будто ею руководил другой посредник, чем раньше. Этот процесс напоминает то, что происходит в реальной жизни, сказал Рафгарден, поскольку общественные нормы относительно того, какое равновесие должно быть реализовано, постепенно меняются.
По словам Нисана, в сложных играх, в которых трудно достичь равновесия Нэша, коррелированное равновесие является «естественным ведущим претендентом» на заменяющую концепцию решения.
Тот факт, что человечество пришло к идее равновесия Нэша раньше, чем к коррелированному равновесию, может быть просто исторической случайностью, сказал Майерсон. «Люди думают, что идеи, возникшие раньше, являются более фундаментальными», — сказал он, но в данном случае «кто скажет, какая идея более фундаментальна?»
Однако результаты, касающиеся быстрой сходимости, не означают, что любой отдельный раунд игры проходит в состоянии коррелированного равновесия, а лишь то, что долгосрочная история игры такова. Это означает, как отметил Рубинштейн, что подходы, минимизирующие сожаления, не всегда являются идеальным выбором для рациональных игроков в любом конкретном раунде. Это оставляет вопрос «Что будут делать рациональные игроки?» без однозначного ответа.
Этот вопрос «исследовался ещё до моего рождения», — сказал 30-летний Рубинштейн. «Но это только начало».
Эта статья была перепечатана на испанском языке на сайте Investigacionyciencia.es .
Источник: www.quantamagazine.org
