Парадокс заключенных

Классическая формулировка

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

Двое преступников — А и Б — попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и каждый из них приговаривается к полугоду тюрьмы. Если оба свидетельствуют друг против друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?

  Игру эту придумали где-то на Западе и, наверно, достаточно давно. Вероятно, такой тюремной культуры, как у нас, у них там нет, и подельники рассуждают, исходя только из разумных оснований (а не из воровской чести). Парадоксом заключённых игра называется потому, что моделью для неё послужили отношения между соучастниками преступления, сидящими в (не соседних) одиночных камерах предварительного заключения. На соучастников заведено дело, ведётся следствие, доказательств недостаточно, и следователь рассчитывает добыть их с помощью допроса. На допросе он, разумеется, не будет спрашивать подследственного о том, что делал сам подследственный - он спросит о том, что делал ДРУГОЙ.
Представьте: их (Вас и Вашего подельника) поодиночке вызывают на допрос. У Вас есть две возможности: уйти в несознанку, не сдав подельника, либо во всём сознаться, сдав его.
И точно такие же два варианта поведения есть и у подельника.Расклады следующие:

1.  Вы ушли в несознанку, подельник тоже. Поверьте, вам обоим найдётся за что сидеть, но отсидите вы по мелочи. Например, оба по полгода.
2.  Вы сознались, подельник ушёл в несознанку. Вас освобождают (срок присуждают условно, учитывая сотрудничество со следствием и отсутствие доказательств Вашей вины), подельнику впаивают по полной за преступление и за запирательство 10 лет.
3. Сознался подельник, а Вы запирались. Теперь уже освобождают подельника, а Вы садитесь на десять лет !!!
4. Сознались оба. Обоим что-то дадут за преступление, но учтут сотрудничество со следствием с обеих сторон. Например, каждому по два года.

Вот как они рассуждают. Разумеется, в общем и целом было бы лучше всего, если бы оба - и Вы, и Ваш подельник - ушли в несознанку. Скооперировались. Обоим вам от этого не то чтобы очень хорошо, но терпимо.Однако если Вы уйдёте в несознанку, а подельник сдаст Вас, Вам впаяют 10! лет. Поэтому если Вы предполагаете, что он Вас сдаст, Вам куда выгоднее сдать его: всё-таки два года меньше, чем десять.Но и в том случае, если Вы предположили, что подельник не расколется, Вам выгоднее сдать его: Вас за это освободят, а освобождение всё-таки, как ни крути, лучше чем полугодовая отсидка.
Таким образом выходит, что Вам в любом случае выгоднее сдать подельника, чем запираться.
Поскольку Ваш подельник разумен (а мы с Вами предположили, что он разумен), он рассуждает точно так же, как и Вы. И тоже Вас сдаёт.
Вот Вам и парадокс: обоим очевидно, что в целом выгоднее было бы уйти в несознанку, но оба, рассуждая рационально, сдают друг друга.

Альтернативные формулировки игры

Хофштадтер(американский физик и информатик; сын лауреата Нобелевской премии по физике Роберта Хофштадтера) предположил, что люди проще понимают такие задачи, как дилемма заключённого, если она представлена в виде отдельной игры или процесса торговли. Один из примеров — «обмен закрытыми сумками»:
Два человека встречаются и обмениваются закрытыми сумками, понимая, что одна из них содержит деньги, другая — товар. Каждый игрок может уважать сделку и положить в сумку то, о чём договорились, либо обмануть партнёра, дав пустую сумку.
В этой игре обман всегда будет наилучшим решением, означая также, что не доверяющие друг другу рациональные игроки будут вынуждены нести транзакционные издержки на проверку содержимого сумок. Тем не менее, в большинстве отраслей выработан кодекс чести, снижающий эти издержки даже для незнакомых между собой игроков, когда проверка выполняется выборочно или практически не выполняется. Например, на бирже это касается системы жестов, выполнение заключенных с помощью которых сделок обязательно. Кодекс чести купца также строго соблюдался/

Использование теории игры и результатов

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

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

Модель игры

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

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

 

Корреляционная зависимость

 Поскольку в игре участвуют 2х2 карты, то имеется четыре возможных исхода :

• Исход I.  Оба сыграли СОТРУДНИЧАЮ. Банк выплачивает каждому  по 300 фишек (очков) .  «Награда за взаимное кооперирование».
• Исход II. Оба сыграли ПРЕДАТЬ(отказ).  Банкт штрафует на 10 очков (отбирает у каждого  10 фишек). «Наказание за взаимный отказ».
• Исход III. Первый сыграл СОТРУДНИЧАЮ, а второй ПРЕДАТЬ(отказ). Банк выплачивает второму 500 ( Плата за Риск ) очков и штрафует первого ( Штраф Простаку) на 100 Фишек(очков).
• Исход IV. Первый сыграл ПРЕДАТЬ, а второй СОТРУДНИЧАЮ. Банкомет выплачивает первому  500  ( Плата за Риск ) очков и штрафует второго ( Штраф Простаку) на 100 очков.

 Совершенно очевидно, что исходы III и IV представляют собой зеркальные отражения один другого: один игрок выигрывает, а другой проигрывает. При исходах I и II оба оказываются в равном положении, но исход I обоим выгоднее, чем исход II. Точная сумма выигрыша не имеет значения. Не играет также роли и то, сколько исходов оказываются положительными (выплаты), а сколько – отрицательными (штрафы). Самое главное условие для того, чтобы игра стала настоящим Парадоксом заключенных, – это относительный ранг (цена) исходов.
«Tабель о рангах» должен быть следующим:

• Плата за риск.
• Награда за взаимное кооперирование.
• Наказание за взаимный отказ.
• Штраф Простаку.

(Строго говоря, есть еще одно условие, соблюдение которого необходимо для признания игры настоящим Парадоксом заключенных: среднее между Платой за риск и Штрафом Простаку не должно превышать Награды. Основания для этого дополнительного условия станут понятны позднее.) С1

Парадокс оптимальной стратегии

При чем же тут «Парадокс»? Из матрицы следует  вывод, что для сокращения  потерь от хода противника надо выбрать Предать, а для максимального выйгрыша Игрок должен  отказаться от Сотрудничества.  Таким образом, когда встречаются два разумных игрока, они оба будут отказываться и оба в конечном счете либо заплатят штраф, либо получат небольшую выплату. При этом каждый из них прекрасно знает, что если бы только они оба играли Сотрудничать, то каждый получил бы довольно высокую Награду за взаимное кооперирование (в нашем случае 300 очков ). Поэтому то игра и называется Парадоксом, причем она так парадоксальна, что может довести до исступления, и поэтому раздавались голоса за то, чтобы издать закон о ее запрещении…)) 
 

Модели стратегий

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

После 10 партий  теоретически можно выиграть 5000 очков, но только в том случае, если противники необыкновенно глупы (или праведны) и всякий раз играли Кооперируюсь, несмотря на то, что игрок все время ходил Отказываюсь. Более реально допустить, что каждый  получит по 300 очков за счет банка, если  оба игрока все 10 раз сыграли Кооперируюсь. Для этого не надо быть особенно праведными, так как игроки могуть  убедиться на основании предшествующей игры противника, что ему можно доверять. Можно, в сущности, регулировать поведение друг друга. Вполне вероятен также и другой оборот: ни один из игроков не вериг другому и мы оба играют Отказываюсь все десять раз, и проигрывают банку по 100 очков в виде штрафов. Если принять очки за доллары Скорее всего игроки частично доверятся друг другу, каждый будет играть вперемешку то Кооперируюсь, то Отказываюсь, и в результате получат некую промежуточную сумму денег. Но не проиграют банку.

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

Аксельрод описал все 15 стратегий на одном общем языке программирования. Каждая стратегия сравнивалась по эффективности поочередно с каждой из остальных (в том числе и с собственной копией) в игре Итерированный Парадокс заключенных. Поскольку стратегий было 15, то компьютер сыграл 15 х 15, или 225, отдельных игр. После того, как каждая пара сделала по 200 ходов, все выигрыши были суммированы и был объявлен победитель.

Нас здесь не интересует, какая именно стратегия вышла победителем в игре против каждого отдельного противника. Важно установить, какая стратегия выиграла больше всего «денег» за все свои 15 вариантов. «Деньги» – это просто «очки», присуждаемые по следующей схеме: взаимное Кооперирование – 3 очка; Риск – 5 очков; Наказание за взаимный отказ – 1 очко (эквивалент небольшого штрафа в игре, описанной ранее); Штраф Простаку – 0 очков (эквивалент большого штрафа в игре, описанной ранее).

Максимально возможный выигрыш, который могла бы получить та или иная стратегия, составляет 15 000 очков (200 партий по 5 очков за партию с каждым из 15 противников). Минимальный результат составляет 0. Излишне говорить, что ни один из этих крайних результатов на самом деле не наблюдался. Наибольший выигрыш, на который может реально надеяться данная стратегия в среднем из своих 15 турниров, не может сколько нибудь значительно превысить 600 очков. Это все, что мог бы получить каждый из двух игроков, если бы они оба все время играли Кооперируюсь, зарабатывая по 3 очка за каждую из 200 сыгранных партий. Если бы один из них поддался искушению отказаться, то число его очков, вероятно, оказалось бы меньше 600, так как другой игрок отплатил бы ему тем же (в большей части представленных стратегий было заложено в той или иной форме стремление к ответному удару). Мы можем использовать число 600 в качестве своего рода точки отсчета для данной игры и выражать результаты в процентах от этого числа. По такой шкале оценок теоретически можно довести выигрыш до 166% (1000 очков), но практически ни одна стратегия не заработала в среднем больше 600 очков.

Не забывайте, что «игроками» в турнире были не люди, а программы, точнее – запрограммированные стратегии. На самом деле кто то из авторов мог бы представить не одну, а несколько программ (хотя было бы жульничеством – которого Аксельрод, вероятно, не допустил бы, – если бы тот или другой автор «забил» весь турнир своими стратегиями, и одна из них воспользовалась бы плодами жертвенного кооперирования со стороны других).

Стратегии

  Было предложено несколько очень хитроумных стратегий, хотя они были, конечно, далеко не столь хитроумными, как их авторы. Интересно, что победившая стратегия была проще всех других и на первый взгляд наименее хитроумной. Она называлась «Око за око» и была представлена проф. Анатолем Рапопортом (Anatol Rapoport), известным психологом и специалистом по теории игр из Торонто. По этой стратегии первым ходом должно быть СОТРУДНИЧАЮ, а в дальнейшем следует просто повторять предыдущий ход другого игрока.

Класс Добропорядочные стратегии

Класс Добропорядочная стратегия определяется как такая стратегия, которая никогда не отказывается первой. Подробно разбирать отдельные стратегии не так уж интересно. В задачи этой статьи не входит обсуждение изобретательности программистов. Гораздо интереснее распределить имеющиеся стратегии по определенным категориям и изучать эффективность этих более крупных подразделений. Самая важная из различаемых Аксельродом категорий названа «добропорядочной».Примером служит Око за око. Она способна отказаться ( предать ), но делает это только в порядке возмездия.

Класс Недобропорядочные стратегии

Как Наивный испытатель, так и Раскаивающийся испытатели – недобропорядочные стратегии, потому что они иногда, хотя и редко, отказываются без всякого к тому повода. Из 15 стратегий, участвовавших в турнире, 8 были добропорядочными. Показательно, что эти же 8 стратегий набрали наибольшее число очков, а 7 недобропорядочных остались далеко позади. Стратегия Око за око набрала в среднем 504,5 очка, что составляет 84% от нашей точки отсчета (600 очков) и может считаться хорошим результатом. Другие добропорядочные стратегии набрали лишь немного меньше очков от 83,4 до 78,6%, оставив далеко позади самую успешную из всех непорядочных стратегий – Грааскамп, набравшую 66,8% очков.

Око за око

 Стратегия Око за Око. Развитие событий зависит от поведения второго игрока. Допустим для начала, что второй игрок – это тоже стратегия Око за око (напомним, что каждая стратегия играла не только против каждой из 14 других стратегий, но также против копии самой себя). Обе стратегии Око за око начинают с кооперирования. При следующем ходе каждый игрок повторяет предыдущий ход противника, т. е. кооперируется. Оба продолжают играть Сотрудничаю до конца игры, которую оба заканчивают, достигнув на 100% суммы очков, принятой за точку отсчета, т. е. заработав по 600 очков.

Наивный испытатель

Допустим, что Око за око играет против стратегии, названной Наивный испытатель. На самом деле Наивный испытатель не участвовал в конкурсе Аксельрода, но тем не менее этот пример поучителен. Наивный испытатель в основном идентичен программе Око за око, с той разницей, что время от времени, скажем один раз за десять ходов, причем без всякой закономерности, он совершенно беспричинно играет Отказываюсь и требует 5 очков, причитающиеся ему за риск. До тех пор, пока Наивный испытатель не предпримет один из своих зондирующих отказов, оба игрока ведут себя в соответствии со стратегией Око за око. Однако внезапно, без предупреждения, скажем на восьмом ходу. Наивный испытатель отказывается. Око за око, разумеется, сыграла в этот раз Кооперируюсь, а поэтому получила 0 очков, как это положено Простаку. Наивный испытатель, казалось бы, добился успеха, заработав за этот ход 5 очков. Но своим следующим ходом Око за око «мстит». Она играет Отказываюсь, просто следуя заложенному в нее правилу копировать предыдущий ход противника. Тем временем стратегия Наивный испытатель, следуя правилу копировать противника, заложенному в нее самое, повторила ее ход – Кооперируюсь. В результате ей достается Штраф Простаку, т. е. О очков, тогда как Око за око получает высшую плату – 5 очков. Своим следующим ходом Наивный испытатель – довольно несправедливо, как можно подумать, – «мстит» за отказ стратегии Око за око. И такое чередование продолжается. При этом оба игрока получают в среднем по 2,5 очка за ход (среднее между 5 и 0). Это меньше, чем те верные 3 очка за ход, которые получают игроки, если они оба играют Кооперируюсь (кстати, это и есть причина введения того «дополнительного условия», которому не было дано объяснения на с1). Итак, когда Наивный испытатель играет против стратегии Око за око, оба выигрывают меньше, чем в игре Око за око против Ока за око. Если же игра идет между двумя Наивными испытателями, дела обоих обстоят еще хуже, так как серии взаимных отказов начинаются раньше.

Раскаивающийся испытатель

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

Некоторые из стратегий, участвовавших в турнире Аксельрода, были гораздо более хитроумными, чем Раскаивающийся испытатель или Наивный испытатель, однако они также набирали в среднем меньше очков, чем простая стратегия Око за око. В сущности наименее успешной из всех стратегий (если исключить Случайную) оказалась самая сложная, тщательно разработанная стратегия. Она была представлена под девизом «Автор пожелал остаться неизвестным», что послужило поводом для веселых гипотез. Кто автор? Какой то серый кардинал в Пентагоне? Глава ЦРУ? Генри Киссинджер? Сам Аксельрод? Я думаю, что этого мы никогда не узнаем.

Прощение

Еще один из технических терминов Аксельрода – это «прощение». У прощающей стратегии короткая память, хотя она может давать сдачи. Она очень быстро забывает о прошлых обидах. Око за око – прощающая стратегия. Она немедленно дает отказчику по рукам, но тут же забывает о нанесенной ей обиде.  Злопамятный никогда не прощает. Он сохраняет в памяти все события до самого конца игры. Он никогда не забывает, если кто то из игроков хотя бы один раз сыграл против него Отказываюсь.

Злопамятный

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

Стратегия Око за два ока

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

Выводы

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

Аксельрод объявил о втором турнире. Он получил 62 заявки на участие и снова добавил к ним Случайную стратегию, что в сумме составило 63 стратегии. На этот раз по причине, о которой я скажу позднее, точное число ходов за партию – 200 – не было оговорено заранее. Мы снова можем выражать в процентах оценки от точки отсчета или же от результатов, получаемых при условии «Всегда кооперируйся», несмотря на то, что определение этой точки отсчета требует более сложных вычислений и она уже не всегда равна 600 очкам.

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

Однако недобропорядочность опять оказалась невыгодной. Снова стратегия Око за око, представленная Анатолем Раппопортом, вышла победителем, и результат составил целых 96% от 600. И еще раз добропорядочные стратегии в общем оказались более эффективными, чем непорядочные. Все 15 более эффективных стратегий, за исключением одной, были добропорядочными, а из 15, набравших меньше очков, все, за исключением одной, были непорядочными. Но хотя праведная стратегия Око за два ока выиграла бы в первом турнире, если бы в нем участвовала, она не вышла победителем из второго. Это объясняется тем, что во втором турнире участвовали более коварные стратегии, способные безжалостно наброситься на столь откровенного придурка.