Что такое дилемма заключенного в теории игр
Теория игр «Дилемма заключённого». Теоретическое обоснование
Теория игр
Посредством теории игр в современном мире экономического анализа весьма точно можно обозначить проблемы картелей, ЕС и зоны евро, более того, с их помощью смоделировать иные виды взаимодействий с большим количеством участников.
Теория игр – это математический раздел, предмет которого – анализ и предсказание решений, которые принимают участники любого стратегического взаимодействия – шахматисты и карточные игроки, конкуренты на олигополистическом рынке и государства, которое взаимодействует с бизнесом, противоборствующих сторон вооружённого конфликта и стран, являющиеся участниками международного объединения.
В теории игр игрой называется взаимодействие, участники данного взаимодействия называются игроками. В игре благосостояние каждого игрока зависит от его собственных действий и от действий других игроков. Все альтернативные методы и способы действий, которые предпринимал любой из игроков, назывались стратегиями. Получать платежи возможно в результате различных стратегий и действий всех участников игры.
Формализация игры
Существует несколько способов, чтобы формализовать игру. Зачастую это математический способ, хотя для простых игр чаще всего используется платёжная таблица.
Платёжная таблица – это таблица, в которой записываются все платежи игроков для всех без исключения комбинаций и стратегий.
В таблице ниже приводится пример платёжной матрицы для пары игроков, которые играют на один рубль в игру «Камень, ножницы, бумага».
«Дилемма заключённого»
Самая популярная игра во всей теории игр – «Дилемма заключённого». Её смысл заключается в следующем. Два заключённых, которые подозреваются в совершении преступления, были задержаны полицией и после помещены в разные камеры. Каждый из них находится перед дилеммой – сознаваться в преступлении или нет.
Ни один из них не знает, как поступит другой, не знает, какую стратегию выберет подельник. У них есть информация только о том, что:
Платёжная матрица этой игры представлена в таблице ниже. Необходимо обратить внимание на то, что платежи отрицательные по причине того, что представляют собой количество лет, проведённых в тюрьме.
Самый лучший сценарий для заключённых в том, что оба из них должны сохранять молчание, и только в таком случае они смогут оба выйти из тюрьмы через полгода. Но ведь не зря таких преступников чаще всего сажают в разные камеры и пытаются получить правдивые показания по отдельности. На психологическом уровне преступники подозревают друг друга и думаю, что кто-то всё же сознается и тогда одному из них придётся провести за решёткой гораздо больший срок. Вряд ли заранее они договорились о какой-то стратегии защиты и в силу этого, они не имеют информации о том, какую лини. Защиты выберет сторонник. Не имея никакой информации о подельнике, но при этом зная о математической матрице, каждый из них может размышлять так: есть ли стратегия, которая наиболее выгодна для меня вне зависимости от того, какую стратегию выберет напарник. В теории игр такую стратегию называют доминирующей. Важно понимать, что такая стратегия возможна для двух преступников, у каждого она своя – это стратегия сознаться.
По той же схеме можно доказать, что для второго также выгодно сознаться и то будет его доминирующая стратегия. Если оба подозреваемых выберут доминирующую стратегия, то результат будет парадоксальным – каждый проведёт по два года в тюрьме, одновременно с тем, они оба питали надежды, что выйдут на свободу не позднее, чем через полгода.
Особенности «дилеммы заключённых»
Ключевая особенность «дилеммы заключённых» состоит в том, что при всей простоте данной стратегии, в преимущественном большинстве случаев оказывается, что в тот момент, когда участникам взаимодействия необходимо вести себя сознательно, они ведут себя бессознательно. Экономисты называют это поведение в первом случае – кооперативно, во втором – оппортунистически. В конечном итоге подводят друг друга.
Участникам картеля выгоднее всего было бы соблюдать соглашения, но при этом каждый стремиться его нарушить, итогом является разрушенный картель.
Подобная ситуация с фермерами, которым выгоднее всего было бы беречь общее поле и не пасти на нём слишком много воров, но, к сожалению, они так не делаю, что приводит к тому, что поле приходит в общую негодность.
Каждый из примеров, ярко показывает взаимное недоверие участников взаимодействия, на основании которых они и выбирают доминирующую стратегию для себя, хоть результат в конечном итоге остаётся далёк от идеала.
Что такое дилемма заключенного в теории игр
Дилемма заключенных в теории игр: от абстракций к конкретике
Дилемма заключенных относится к типу экономической игры, в которой равновесие Нэша таково, что оба игрока оказываются в худшем положении, даже если они оба выбирают свои оптимальные стратегии.
Дилемма заключенных — это классический пример игры, в которой участвуют два подозреваемых, скажем P и Q, арестованные полицией и которые должны решить, признаваться им или нет.
Если один сознается, а другой нет, то заключенный, который сознается, получает более легкий тюремный срок, скажем, 1 год, а заключенный, который не сознается, получает очень суровый срок, скажем, 8 лет.
Если ни один из них не признается, они оба получают более легкие сроки, скажем, по 2 года каждый; но если оба признаются, то оба получают строгий срок, скажем, по 4 года каждый.
Игра может быть визуализирована с помощью следующей матрицы выплат:
| Выплаты в тюрьме | Заключенный Q | ||
| Признаться | Не признаться | ||
| Заключенный P | Признаться | -4, -4 | -1, -8 |
| Не признаться | -8, -1 | -2, -2 | |
Комбинированная оптимальная стратегия для обоих заключенных — не признаваться в содеянном. Именно потому, что это привело бы к минимальному объединенному тюремному сроку для них.
Но поскольку они не могут общаться и сотрудничать, пытаясь сделать все возможное индивидуально, они выбирают стратегии, которые обрекают их обоих.
Давайте посмотрим на игру с точки зрения заключенного P. Если заключенный Q сознается, то заключенному Р тоже лучше признаться, потому что в противном случае он получил бы срок 8 лет вместо 4 лет.
Точно так же, если заключенный Q не сознается, то в интересах заключенного P сознаться, потому что, признавшись, он получит срок в 1 год вместо 2 лет. Следовательно, независимо от того, что делает заключенный Q, признание является доминирующей стратегией для заключенного P.
Теперь давайте рассмотрим точку зрения заключенного Q. Он знает, что признание является доминирующей стратегией заключенного P. Он не хочет не признаваться и получить 8-летний срок и признаться. Но когда он это делает, оба получают по 4 года тюремного заключения каждый.
В конечном счете и тот и другой находятся в худшем положении, потому что они получают по 4 года каждый вместо всего лишь 2 лет каждый.
Но они не могут избежать этого печального исхода, потому что не могут сотрудничать, и любая другая стратегия была бы худшей для каждого заключенного в отдельности.
Равновесие Нэша в дилемме заключенных
Результатом дилеммы заключенного является равновесие Нэша. Равновесие Нэша — это такая комбинация стратегий, при которой у фирмы-игрока есть какой-либо стимул в одностороннем порядке изменить свою стратегию.
Когда оба игрока в игре имеют доминирующие стратегии, результатом, который является пересечением доминирующих стратегий, является равновесие Нэша.
В дилемме заключенных, поскольку признание является доминирующей стратегией для каждого заключенного, равновесие Нэша возникает, когда оба признаются.
Это равновесие Нэша, потому что ни один заключенный не станет лучше, если в одностороннем порядке изменит свою стратегию.
Например, если заключенный Р решит не признаваться, в то время как заключенный Q действительно признается, то заключенный Р получит 8 лет вместо 4 лет. Следовательно, заключенному Р будет хуже, если он отойдет от равновесия Нэша.
Он не станет выбирать иной стратегии, кроме той, что диктует равновесие Нэша. Этот пример показывает, что равновесие Нэша является самоподкрепляющимся и стабильным.
Примеры
Хотя дилемма заключенных, рассмотренная выше, является абстрактной концепцией, многие реальные ситуации очень похожи на нее.
Пример 1. Фирмы знают, что если они не рекламируют, то могут сохранить свою существующую долю рынка и прикарманить сэкономленный рекламный бюджет в качестве дополнительной прибыли, но они все равно рекламируют, потому что каждая фирма боится, что если она не рекламирует, а другая фирма делает это, то она потеряет свою долю рынка.
Поскольку обе фирмы испытывают один и тот же страх, обе они рекламируют, обе имеют более низкую прибыль (из-за более высоких расходов на рекламу), и никто не получает никакой доли рынка.
Пример 2. Фирмы, принимающие решение о том, следует ли нанять адвоката, чтобы представлять их интересы в арбитраже, будут коллективно лучше, если они решат не нанимать адвоката.
Но каждая фирма нанимает адвоката из страха, что если другая фирма наймет адвоката, а они этого не сделают, вероятность того, что другая фирма выиграет в арбитраже, значительно возрастет.
Пример 3. Фирмы в олигополии находятся в лучшем положении, если они могут одновременно ограничивать свой выпуск и устанавливать монопольную цену.
Но так как сговор незаконен, то и то, и другое дает более высокую отдачу, что снижает отдачу каждой фирме. Модель Курно является иллюстрацией такой дилеммы заключенных.
Дилемма заключенного в бизнесе и экономике
Опубликовано 12.07.2021 · Обновлено 12.07.2021
Дилемма заключенного, одна из самых известных теорий игр, была концептуализирована Мерриллом Фладом и Мелвином Дрешером из Rand Corporation в 1950 году. Позднее она была формализована и названа математиком из Принстона Альбертом Уильямом Такером.
Дилемма заключенного в основном дает основу для понимания того, как найти баланс между сотрудничеством и конкуренцией, и является полезным инструментом для принятия стратегических решений.
В результате он находит применение в самых разных областях, от бизнеса, финансов, экономики и политологии до философии, психологии, биологии и социологии.
Ключевые выводы
Основы дилеммы заключенного
Сценарий дилеммы заключенного работает следующим образом: двое подозреваемых были задержаны за преступление и теперь находятся в разных комнатах в полицейском участке, не имея возможности общаться друг с другом. Прокурор отдельно сказал им следующее:
Что делать подозреваемым? В этом суть дилеммы заключенного.
Оценка наилучшего образа действий
Начнем с построения матрицы выплат, как показано в таблице ниже. «Выплата» здесь показана в виде продолжительности тюремного заключения (что обозначено знаком минус; чем выше число, тем лучше). Термины «сотрудничать» и «отступать» относятся к подозреваемым, которые сотрудничают друг с другом (например, если ни один из них не признается) или дезертируют (т. Е. Не сотрудничают с другим игроком, как в случае, когда один подозреваемый сознается, но другой нет). Первая цифра в ячейках с (a) по (d) показывает выигрыш для подозреваемого A, а вторая цифра показывает выигрыш для подозреваемого B.
Доминирующая стратегия для игрока – это та, которая приносит ему наилучший выигрыш, независимо от стратегий, используемых другими игроками. Здесь доминирующая стратегия состоит в том, чтобы каждый игрок дезертировал (т. Е. Признался), так как признание минимизирует среднюю продолжительность пребывания в тюрьме. Вот возможные результаты:
Так что, если А. признается, они либо освобождаются, либо получают два года тюрьмы. Но если они не признаются, им грозит либо год, либо три года тюрьмы. B сталкивается с той же дилеммой. Ясно, что лучшая стратегия – признаться, независимо от того, что делает другой подозреваемый.
Последствия дилеммы заключенного
Дилемма заключенного элегантно показывает, что, когда каждый преследует свои собственные интересы, результат хуже, чем если бы они оба сотрудничали. В приведенном выше примере за сотрудничество – при котором А и Б оба хранят молчание и не признаются – два подозреваемых приговорены к тюремному заключению сроком на два года. Все остальные исходы повлекут за собой комбинированное наказание в виде двух из трех или четырех лет.
На самом деле рациональный человек, который заинтересован только в получении максимальной выгоды для себя, обычно предпочитает отступить, а не сотрудничать. Если оба решат дезертировать, предполагая, что другой этого не сделает, вместо того, чтобы оказаться в ячейке (b) или (c) вариант – как каждый из них надеялся – они окажутся в ячейке (d), и каждый получит два лет в тюрьме.
В примере с заключенным, сотрудничество с другим подозреваемым влечет за собой неизбежное наказание в виде одного года, в то время как признание вины в лучшем случае приведет к освобождению, а в худшем – к двум годам лишения свободы. Однако отказ от признания влечет за собой риск тюремного заключения на срок до трех лет, если, скажем, уверенность A в том, что B также останется мамой, окажется неуместной, а B действительно признается (и наоборот).
Эта дилемма, при которой стимул к отказу (не к сотрудничеству) настолько силен, даже если сотрудничество может дать наилучшие результаты, проявляется по-разному в бизнесе и экономике, как обсуждается ниже.
Приложения для бизнеса
Классический пример дилеммы заключенного в реальном мире встречается, когда два конкурента борются на рынке.Часто у многих секторов экономики есть два основных соперника.В США, например, идет ожесточенное соперничество между Coca-Cola (KO ) и PepsiCo (PEP ) в сфере безалкогольных напитков и Home Depot (HD ) против Lowe’s (LOW ) в строительных материалах.Этот конкурс послужил поводом для многочисленных тематических исследований в бизнес-школах.2 Другие ожесточенные соперничества включают Starbucks ( SBUX ) против Тима Хортона ( THI ) в Канаде и Apple ( AAPL ) против Samsung в мировом секторе мобильных телефонов.
Рассмотрим случай Coca-Cola против PepsiCo и предположим, что первая думает о снижении цен на свою легендарную газировку. Если это произойдет, у Pepsi может не быть другого выбора, кроме как последовать их примеру, чтобы кола сохранила свою долю рынка. Это может привести к значительному падению прибыли обеих компаний.
Таким образом, снижение цен любой из компаний может быть истолковано как дефект, поскольку оно нарушает неявное соглашение о поддержании высоких цен и максимизации прибыли. Таким образом, если Coca-Cola снижает цену, но Pepsi продолжает поддерживать цены на высоком уровне, первая отказывается, а вторая сотрудничает (придерживаясь духа неявного соглашения). В этом сценарии Coca-Cola может завоевать долю рынка и получить дополнительную прибыль, продавая больше колы.
Матрица выплат
Предположим, что дополнительная прибыль, получаемая Coca-Cola и Pepsi, выглядит следующим образом:
Матрица выплат выглядит следующим образом (числа представляют собой дополнительные долларовые прибыли в сотнях миллионов):
Другие часто цитируемые примеры дилеммы заключенного относятся к таким областям, как разработка новых продуктов или технологий или расходы компаний на рекламу и маркетинг.
Например, если две фирмы заключили неявное соглашение о том, что рекламные бюджеты не будут меняться в конкретный год, их чистая прибыль может остаться на относительно высоком уровне. Но если одна из них откажется и увеличит свой рекламный бюджет, она может получить большую прибыль за счет другой компании, поскольку более высокие продажи компенсируют возросшие расходы на рекламу. Однако, если обе компании увеличат свои рекламные бюджеты, возросшие рекламные усилия могут компенсировать друг друга и оказаться неэффективными, что приведет к снижению прибыли – из-за более высоких рекламных расходов – чем было бы, если бы рекламные бюджеты остались неизменными.
Приложения к экономике
Возникающий время от времени долговой тупик США между демократами и республиканцами является классическим примером дилеммы заключенного.
Допустим, полезность или выгода от решения проблемы долга США будет заключаться в выигрыше на выборах для партий на следующих выборах. Под сотрудничеством в данном случае понимается готовность обеих сторон работать над поддержанием статус-кво в отношении растущего дефицита бюджета США. Отклонение подразумевает отказ от этого неявного соглашения и принятие мер, необходимых для установления контроля над дефицитом.
Если обе стороны будут сотрудничать и поддерживать бесперебойную работу экономики, некоторые преимущества на выборах обеспечены. Но если Сторона A пытается решить проблему долга проактивным образом, в то время как Сторона B не сотрудничает, это упорство может стоить B голосов на следующих выборах, которые могут достаться A.
Однако, если обе стороны откажутся от сотрудничества и будут жестко пытаться решить проблему долга, последовавшие за этим экономические потрясения (скользящие рынки, возможное снижение кредитного рейтинга и закрытие правительства ) могут привести к снижению электоральных преимуществ для обеих сторон.
Как вы можете это использовать?
Дилемма заключенного может быть использована для принятия решений в ряде областей личной жизни, таких как покупка машины, переговоры о заработной плате и так далее.
Например, предположим, что вы хотите купить новую машину и зашли в автосалон. Полезность или выигрыш в данном случае не является числовым атрибутом (т. Е. Удовлетворенностью сделкой). Вы хотите получить максимально выгодную сделку с точки зрения цены, характеристик автомобиля и т. Д., В то время как продавец автомобилей хочет получить максимально возможную цену, чтобы максимизировать свою комиссию.
Сотрудничество в этом контексте означает отсутствие торгов; вы входите, платите указанную цену (к большому удовольствию продавца) и уезжаете на новой машине. С другой стороны, отступление означает торг. Вы хотите более низкую цену, а продавец хочет более высокую цену. Присвоение числовых значений уровням удовлетворенности, где 10 означает полное удовлетворение сделкой, а 0 означает отсутствие удовлетворения, матрица выплат выглядит так, как показано ниже:
Что нам говорит эта матрица? Если вы ведете жесткую сделку и получаете существенное снижение цены на автомобиль, вы, скорее всего, будете полностью удовлетворены сделкой, но продавец, скорее всего, будет недоволен из-за потери комиссии (как видно в ячейке b).
Ваш уровень удовлетворенности может быть меньше, если вы просто войдете и заплатите полную цену (ячейка а). Продавец в этой ситуации, вероятно, будет менее чем полностью удовлетворен, поскольку ваша готовность заплатить полную цену может заставить его задуматься, мог ли он «направить» вас к более дорогой модели или добавить еще несколько наворотов, чтобы получить больше. комиссия.
Ячейка (d) показывает гораздо меньшую степень удовлетворения как покупателя, так и продавца, поскольку продолжительный торг, возможно, в конечном итоге привел к неохотному компромиссу по цене, заплаченной за автомобиль.
Точно так же при переговорах о зарплате вам может быть неразумно принимать первое предложение, которое потенциальный работодатель делает вам (при условии, что вы знаете, что стоите больше).
Сотрудничество путем принятия первого предложения может показаться легким решением на сложном рынке труда, но это может привести к тому, что вы оставите немного денег на столе. Переход (т.е. переговоры) о более высокой зарплате действительно может принести вам более высокую зарплату. И наоборот, если работодатель не желает платить больше, вы можете быть недовольны окончательным предложением.
Будем надеяться, что переговоры о заработной плате не станут ожесточенными, поскольку это может снизить уровень удовлетворенности вас и работодателя. Показанная ранее матрица вознаграждения покупателя-продавца может быть легко расширена, чтобы показать уровень удовлетворенности соискателя работы по сравнению с работодателем.
Дилемма заключенного показывает нам, что простое сотрудничество не всегда отвечает нашим интересам. Фактически, при покупке дорогостоящего предмета, такого как автомобиль, торг – это предпочтительный образ действий с точки зрения потребителей. В противном случае автосалон может придерживаться политики негибкости в переговорах о ценах, максимизируя свою прибыль, но в результате потребители будут переплачивать за свои автомобили.
Понимание относительной выгоды сотрудничества и отказа может побудить вас вступить в серьезные переговоры о цене, прежде чем совершить крупную покупку.
Дилемма заключенного
В теории игр дилемма заключённого (ДВ) — игра с ненулевой суммой, в которой игроки стремятся получить выгоду, сотрудничая друг с другом или изменяя. Как во всей теории игр, предполагается, что игрок («узник») максимизирует свой собственный выигрыш, не заботясь о выгоде других.
Обращаясь отдельно рационально, вместе участники приходят к нерациональному решение: если оба предадут, они получат в сумме меньше выигрыш, чем если бы сотрудничали (единственная равновесие в этой игре не ведет к Парето-оптимального решения). В этом и заключается дилемма.
В дилемме заключенного, повторяющееся игра происходит периодически, и каждый игрок может «наказать» другого за несотрудничество раньше. В такой игре сотрудничество может стать равновесием, а стимул предать может перевешиваться угрозой наказания (с ростом числа итераций равновесие Нэша стремится Парето-оптимума).
Классическая дилемма заключённого
Классическая дилемма заключенного такова:
Двое подозреваемых, А и Б, арестованы. У полиции нет достаточных доказательств для обвинения, и изолировав их друг от друга, они предлагают им одну и ту же операцию: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается, а второй получает 10 лет тюрьмы. Если оба молчат, в полиции мало доказательств, и они приговариваются к 6 месяцев. Если оба свидетельствуют против друг друга, они получают по 2 года. Каждый заключенный выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдет?
Игру можно представить в виде следующей таблицы:
| Узник Б хранит молчание | Узник Б дает показания | |
|---|---|---|
| Узник А хранит молчание | Оба получают полгода. | А получает 10 лет Б освобождается |
| Узник А дает показания | А освобождается Б получает 10 лет тюрьмы | Оба получают 2 года тюрьмы |
Дилемма появляется, если предположить, что оба заботятся только о минимизации собственного срока заключения.
Представим рассуждения одного из заключенных. Если партнер молчит, то лучше его изменить и выйти на свободу (иначе — полгода тюрьмы). Если партнер говорит, то лучше тоже свидетельствовать против него, чтобы получить 2 года (иначе — 10 лет). Стратегия «свидетельствовать» строго доминирует над стратегией «молчать». Аналогично другой заключенный приходит к тому же выводу.
С точки зрения группы (этих двух заключенных) лучше сотрудничать друг с другом, хранить молчание и получить по полгода, поскольку это уменьшит суммарный срок заключения. Любое другое решение будет менее выгодным. Это очень наглядно демонстрирует, что в игре с ненулевой суммой Парето-оптимум может быть противоположным равновесии Нэша.
Обобщенная форма
Можно раскрыть скелет игры далее, абстрагировавшись от подтекста заключенных. Обобщенная форма игры часто используется в экспериментальной экономике. Вот правила, которые дают типичную реализацию игры.
В игре — два игрока и банкир. Каждый игрок держит 2 карты: на одной написано «сотрудничать», на другой — «предать» (это стандартная терминология игры). Каждый игрок кладет одну карту перед банкиром надписью вниз (то есть никто не знает чужого решения, хотя знание чужого решения не влияет на анализ доминирования). Банкир открывает карты и выдает выигрыш.
Если оба выбрали «сотрудничать», оба получают C. Если один выбрал «предать», другой «сотрудничать» — первый получает D, второй с. Если оба выбрали «предать» — оба получают d.
Значения переменных C, D, с, d могут быть любого знака (в примере выше все меньше или равны 0). Обязательно должна соблюдаться неравенство D> C> d> c, чтобы игра была ДВ.
| Сотрудничать | Изменить | |
|---|---|---|
| Сотрудничать | C, C | c, D |
| Изменить | D, c | d, d |
Если игра повторяется, то есть играет более 1 раза подряд, общий выигрыш от сотрудничества должен быть большим суммарного выигрыша в ситуации, когда один изменяет, а другой — нет (объяснения — ниже):
Эти правила были установлены Дугласом Гофштадтером и образуют канонический описание типичной дилеммы заключенного.
Похожая, но другая игра
Гофштадтер предположил, что люди проще понимают задачи, как задача ДВ, если она представлена в виде отдельной игры или процесса торговли. Один из примеров — «обмен закрытыми сумками»: Два человека встречаются и обмениваются закрытыми сумками, понимая, что одна из них содержит деньги, другая — товар. Каждый игрок может уважать операцию и положить в сумку то, о чем договорились, или обмануть партнера, дав пустую сумку.
В этой игре обман всегда будет наилучшим решением, означая также, что рациональные агенты никогда не играть в нее, и рынок обмена закрытыми сумками будет отсутствовать.
В вариации, популярной у программистов и хакеров каждый агент этой игры помнит предыдущие результаты (или имеет доступ к общественному мнению, «коллективной памяти»), и множество обменов повторяются длительное время.
Как указано выше, без памяти эта игра имеет мало смысла, она мало что объясняет в поведении систем и групп людей, кроме описания взаимодействий, не проходить. Сложностей вводится больше, чем можно ожидать. Программист (особенно специализирующийся на функциональном программировании) сразу поймет значимость времени и состояния (памяти). Но и без написания программ можно предположить, как поведут себя агенты. Насколько велика память каждого агента? Какая стратегия каждого из них? Как агенты с различными стратегиями распределены и определяет, кто с кем взаимодействует и в каком порядке?
Сложность создания какой-то многозначной модели может смущать, но она поднимает некоторые интересные и ценные технические и философские вопросы.
Выполнена некоторая работа по моделированию этого. Различные программисты и математики утверждают, что стратегия «око за око» — наилучшая общая стратегия, однако не было сделано серьезных академических усилий, чтобы классифицировать различные типы и распределения агентов, обучающихся с различными стратегиями.
О потенциале этой задачи свидетельствует тот факт, что в этой дискуссии еще не упоминались возможность формировать коалиции и рядиться коллективно. А как насчет агентов, которые по плату организовывали переговоры? Или агентов, которые накапливали информацию о самых операции?
Примеры из реальной жизни
Примеры с заключенными, карточной игрой и обменом закрытыми сумками могут казаться надуманными, но на самом деле есть множество примеров взаимодействия людей и животных, имеющих такую же матрицу выигрышей. Поэтому ДВ представляет интерес социальным наукам, таким как экономика, политология и социология, а также разделам биологии — этологии и эволюционной биологии. Многие природные процессы были обобщены в модели, в которых живые существа участвуют в бесконечных играх типа дилеммы заключенного. Такая широкая применимость ДВ придает этой игре значительную важность.
В политологии, например, сценарий ДВ часто используется для иллюстрации проблемы двух стран, вовлеченных в гонку вооружений. Обе заявлять, что у них есть две возможности: либо увеличить расходы на военные нужды, или сокращать вооружения. Ни одна из сторон не может быть уверена, что другая соблюдать договоренность, следовательно обе стремиться к военной экспансии. Это можно считать теоретическим объяснением политики запугивания.
В автоспорте яркий пример дилеммы заключенного — Формула-1, где последние 20 лет происходит гонка бюджетов команд, через какое количество машин участников сократилось с 36 в 1990 до 20 в 2003.
Случай дилеммы узника может быть найден в бизнесе. Две конкурирующие фирмы должны определиться, сколько средств тратить на рекламу. Эффективность рекламы и прибыль каждой фирмы уменьшается с ростом расходов на рекламу у конкурента. Обе фирмы принимают решение увеличить расходы на рекламу, при этом их доли рынка и, возможно, объемы продаж остаются неизменными, а прибыль сокращается. Предел гонки рекламных бюджетов — прибыль, впрочем, они могут пытаться некоторое время работать и в убыток. Фирмы могут пойти на соглашение о сокращении расходов на рекламу, но всегда есть стимул его нарушить.
В олигополистических рынках ценовая политика — это повторение ДВ. Конечно олигополисты сотрудничают друг с другом и не доводят ситуацию до ценовой войны.
Уильям Паундстоун в книге о проблеме узника описывает ситуацию в Новой Зеландии, где почтовые ящики оставляют открытыми. Газету можно взять, не заплатив за нее, но мало кто так делает, потому что большинство осознает вред, который был бы, если бы все воровали газеты. Поскольку ДВ в чистом виде одновременно для всех игроков (никто не может повлиять на решение других), эта распространенная линия рассуждений называется «магическое мышление».
Теоретический вывод ДВ — одна из причин, почему во многих странах сделка о признании вины запрещена. Часто сценарий ДВ повторяется очень точно: в интересах обеих подозреваемых признаться и свидетельствовать против другого подозреваемого, даже если оба невиновны. Возможно, наихудший случай — когда только один виноват, в этом случае виноват вряд ли признается в чем, а виноват пойдет на это и даст показания против невинного.
Многие проблемам в реальной жизни включают множество игроков. Хотя и метафорическая «трагедии общин» Ардена можно рассматривать как обобщение ДВ для множества игроков. Каждый житель общины выбирает — или пасти скот на общем пастбище и получить выгоду, истощая его ресурсы, или ограничить свой доход. Коллективный результат от общего (или частого) максимального использования пастбища — низкий доход (что ведет к разрушению общины). Однако такая игра не является формальной, так как может быть разбита на последовательность классических игр с 2 участниками.
Дилемма узника, повторяющееся
В книге «Эволюция кооперации» (1984) Роберт Акселрод исследовал расширение сценария ДВ, которое он назвал дилемма узника, повторяется (НДС). В ней участники делают опять время от времени и помнят предыдущие результаты. Акселрод пригласил академических коллег со всего мира, чтобы разработать компьютерные стратегии, чтобы соревноваться в чемпионате по НДС. Программы, вошедшие в него различались по алгоритмической сложности, начальной враждебностью, способностью к прощению и так далее.
Акселрод открыл, что если игра повторялась долго среди множества игроков, каждый с различными стратегиями, «жадные» стратегии давали плохие результаты в долгосрочном периоде, тогда как более «альтруистические» стратегии работали лучше, с точки зрения собственного интереса. Он использовал это, чтобы показать возможный механизм эволюции альтруистического поведения из механизмов, которые сначала чисто эгоистические, через естественный отбор.
Лучшей детерминистской стратегией оказалась «Око за око» (англ. Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простой из всех программ, участвовавших состояла всего из 4 строк кода на языке Бейсик. Стратегия проста: сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Немного лучше работает стратегия «Око за око с прощением». Когда оппонент изменяет, на следующем шаге игрок иногда в любом случае сотрудничает с небольшой вероятностью (1-5%). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится непонимание — когда решение одного игрока сообщается другому с ошибкой.
Анализируя стратегии, набравшие лучшие результаты, Акселрод назвал несколько условий, необходимых, чтобы стратегия получила высокий результат.
Хорошая
Важнейшее условие — стратегия должна быть «доброй», то есть не предавать, пока этого не сделает оппонент. Почти все стратегии-лидеры были хорошими. Поэтому чисто эгоистическая стратегия с чисто эгоистических причинам не будет первой «бить» соперника.
Мстительная
Однако успешная стратегия не должна быть слепым оптимистом. Она должна всегда мстить. Пример немстивои стратегии — всегда сотрудничать. Это очень плохой выбор, поскольку «подлые» стратегии воспользуются этим.
Прощая
Другая важная качество успешных стратегий — уметь прощать. Отомстив, они должны вернуться к сотрудничеству, если оппонент не продолжает предавать. Это предотвращает бесконечной мести друг другу и максимизирует выигрыш.
НЕ завистливая
Последнее качество — не являться завистливым, то есть не пытаться набрать больше очков, чем оппонент (что в принципе невозможно для «хорошей» стратегии, то есть хорошая стратегия никогда не может набрать больше очков, чем оппонент).
Итак, Акселрод пришел утопично звучащему выводу, что эгоистичные индивиды во имя их же эгоистического блага будут стремиться быть добрыми и прощая и не завистливыми.
Рассмотрим снова модель гонки вооружений. Был дан вывод, что единственная рациональная стратегия — вооружаться, даже если обе страны хотели бы тратить ВВП на масло, а не орудия. Интересно, что попытки продемонстрировать, что вывод ДВ работает на практике (делая анализ «высоких» и «низких» военных расходов между периодами, на основе предположений НДС), часто показывают, что такого поведения не происходит. Например, греческие и турецкие военные расходы меняются не в соответствии со стратегией «око за око», а скорее следуют внутренней политике). Это может быть примером рационального поведения, отличается от одноразовых и многоходовых игр.
Если в одноходовой игре в любом случае доминирует стратегия предать, то в многоходовой оптимальная стратегия зависит от поведения других участников. Например, если среди населения все друг друга обманывают, а один ведет себя по принципу «око за око», он оказывается в небольшом проигрыше из-за потери на первом ходе. В такой популяции оптимальная стратегия — всегда предавать. Если же число исповедуют принцип «око за око» больше, то результат уже зависит от их доли в обществе.
Определить оптимальную стратегию можно двумя путями:
Хотя стратегия «око за око» считалась удачной простой стратегией, команда Университета Саутгемптона из Англии (под руководством профессора Николаса Дженнингса) представила новую стратегию на 20-ю годовщину Чемпионата по НДС. Эта стратегия оказалась успешной, чем «око за око». Она основывалась на взаимодействии между программами, чтобы получить максимальный счет для одной из них. Университет выставил на чемпионат 60 программ, которые распознавали друг друга по ряду действий на первых 5-10 ходах. Распознав другую, одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю. Если программа понимала, что оппонент — не Саутгемптонского, она дальше все время изменяла ему, чтобы минимизировать результат соперника. В результате эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.
Хотя эта стратегия оказалась эффективной в соревновании, это было достигнуто за счет того, что в этом конкретном соревновании команда могла участвовать несколькими агентами. Если игрок может контролировать только одного агента, «око за око» оказывается лучшим. Она также придерживается правила запрета на коммуникации между игроками. То, что Саутгемптонского программы исполняли «ритуальный танец» в первые 10 ходов, чтобы узнать друг друга, только подтверждает, насколько важна коммуникация в сдвиге баланса игры.
Если НДС играет ровно N раз (какая-то известная константа N), есть еще один интересный факт. Равновесие Нэша — всегда предавать. Доводим по индукции: если оба сотрудничают, на последнем ходе выгодно предать, тогда у соперника не будет возможности отомстить. Поэтому оба предадут друг друга на последнем ходу. Раз соперник предаст на последнем ходе в любом случае, любой игрок захочет предать на предпоследнем ходу, и так далее. Чтобы сотрудничество оставалась выгодной, необходимо, чтобы будущее было неопределенным для обоих игроков. Одно из решений — делать число N случайным и подсчитывать результаты по среднему выигрышем за ход.
Дилемма заключенного — фундаментальная для некоторых теорий о взаимодействии людей и доверие. С предположение модели ДВ, что транзакция между двумя людьми требует доверия, доверительная поведение в популяциях может быть смоделирована с помощью многие гравцевои версии игры, повторяется. Это годами вдохновляло многих ученых. В 1975 году Грофман и Пул оценивали число работ, посвященных этой теме, их около 2000.
Психология обучения и теория игр
Если игроки могут оценивать возможность предательства со стороны других игроков, на их поведение влияет опыт. Простая статистика показывает, что неопытные игроки обычно ведут себя чрезмерно хорошо или плохо. Если они все время будут действовать так, то проигрывают из-за своей излишней агрессивности или лишнюю доброту. С получением большого опыта они реально оценивают вероятность измены и добиваются лучших результатов. Ранние розыгрыше сильно влияют на неопытных игроков, чем более поздние на опытных. Это пример, почему ранний опыт имеет такое влияние на молодых, и почему они особенно уязвимы к немотивированной агрессии, иногда сами становясь такими.
Можно уменьшить вероятность измены в популяции посредством сотрудничества в ранних играх, позволив укрепить доверие. Итак самопожертвование может в некоторых ситуациях усилить моральный дух группы. Если группа маленькая, на позитивное поведение с большей вероятностью ответят взаимностью, что поощрит индивидов на дальнейшее сотрудничество. Это связано с еще одной дилеммой, хорошее отношение без причины — это потерянные, которое может ухудшить моральные качества.
Эти процессы — главное поле интереса взаимного альтруизма, группового отбора, семейного отбора и этики.
Восточная философия
В боевых искусствах изучается даосское пословица, которая гласит, что:
Второе и четвертое утверждение кажутся сомнительными, особенно с позиций христианства, но дилемма заключенного объясняет их. В древнем Китае «добро» и «зло» считались незыблемыми истинами (например, их нельзя поменять местами), таким образом, эта пословица можно прочитать еще и как «плюс на минус дает минус». Есть усиленный вариант этой пословицы, где в двух последних строках выходит «двойное зло».
Библиография
(источники, названные в англоязычной статьи)