Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

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

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

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

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

Дилемма состоит в следующем. Представьте себе, что вы и ваш сообщник были арестованы после ограбления банка. Вас содержат в отдельных тюремных камерах. Теперь вы должны решить, будете ли вы поддерживать друг друга, храня молчание, или нарушите прежние договоренности о партнерстве и донесете на сообщника. При этом вы оба знаете, что если каждый будет хранить молчание, то суд, не имея достаточных доказательств для вынесения обвинительного приговора, будет вынужден освободить вас обоих и вы сможете разделить добычу поровну, получив, скажем, по $0,5 млн каждый. Если же один из вас донесет на сообщника, а другой при этом будет хранить молчание, то информатор выйдет на свободу и ему достанется весь $1 млн, в то время как молчаливый сообщник будет осужден и как единственный виновник преступления получит 10 лет тюрьмы. А если вы оба начнете доносить друг на друга, то оба будете осуждены и разделите наказание: пять лет каждому.

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

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

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

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

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

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

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

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

Хотя о каком, собственно, вреде идет речь? Удивительно, но Тим Ругарден и Ева Тардос из Корнеллского университета доказали в 2002 году, что у такого подхода («эгоистичная маршрутизация») цена анархии не превышает 4/3. То есть свободный и доступный для всех выбор всего лишь на 33 % хуже, чем идеально просчитанный и совершенным образом скоординированный.

Работа Ругардена и Тардос оказала существенное влияние не только на планирование маршрутов городского транспорта, но и на сетевую инфраструктуру. Именно эгоистичная маршрутизация с низкой ценой анархии объясняет, например, почему тот же интернет хорошо работает без какого-либо центрального координирующего органа, управляющего маршрутизацией отдельных пакетов. При том что даже если такая координация была бы возможна, она не принесла бы значимых преимуществ.