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

Сжатая статья Р.Докинза. Плюшки для ЛЛ в конце.

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

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

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

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

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

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

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

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

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

Для анализа игры вводится следующая система баллов:

Награда за взаимное кооперирование — 3 очка;

Плата за риск — 5 очков;

Наказание за взаимный отказ — 1 очко (эквивалент небольшого штрафа в игре, описанной ранее);

Штраф Простаку — 0 очков (эквивалент большого штрафа в игре, описанной ранее).

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

В отличие от простого варианта игры, которая довольно предсказуема в том смысле, что Отказываюсь — единственная разумная стратегия, итеративный вариант предлагает много разных стратегий. В простом варианте возможны лишь две стратегии: Кооперируюсь и Отказываюсь. Итерация, однако, допускает множество стратегий, и какая из них лучше всех — отнюдь не очевидно.

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

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

Нас здесь не интересует, какая именно стратегия вышла победителем в игре против каждого отдельного противника. Нам важно установить, какая стратегия набрала больше всего очков «денег» за все свои 15 вариантов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Совместно с У. Гамильтоном Аксельрод перешел к рассмотрению стратегий итерированного «Парадокса заключенных» с свете теории ЭСС (Эволюционно стабильная Стратегия). см

http://pikabu.ru/story/agressiya_i_yevolyutsionno_stabilnaya...

http://pikabu.ru/story/rasputnitsyi_skromnitsyi_i_muzhiki_50...

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

Аксельрод провел третий раунд своего турнира так, как его мог бы вести естественный отбор, стремящийся найти некую ЭСС. Правда, он не назвал это третьим раундом, поскольку он не обращался с просьбами о новых предложениях, а использовал те же 63 стратегии, что и в раунде 2.

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

В конце концов по прошествии примерно 1000 поколений дальнейшие изменения обстановки прекратились. Была достигнута стабильность. Некоторые стратегии пошли на убыль с самого начала, а к 200-му поколению большая их часть вымерла. Одна или две из непорядочных стратегий стали встречаться все чаще, однако их процветание было недолгим. Единственная непорядочная стратегия, сохранившаяся по прошествии 200 поколений, была стратегия под названием Харрингтон. Выигрыши этой стратегии резко возрастали на протяжении первых 150 поколений, а затем довольно медленно снижались, и стратегия практически вымерла к 1000-му поколению. Стратегия Харрингтон была успешной в течение некоторого времени пока она эксплуатировала придурков вроде стратегии Око за два ока, пока они еще существовали. Затем, после того как эти придурки были доведены до вымирания, стратегия Харрингтон, лишившись легкой добычи, последовала за ними. Арена оказалась свободной для таких добропорядочных, но дерзких стратегий, как Око за око.

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

Также я хочу ввести еще один из будоражащих воображение технических терминов Аксельрода: Око за око «независтлива». Быть «завистливым», по терминологии Аксельрода, означает стремление выиграть больше очков, чем другой игрок, а не стараться получить как можно большую сумму в абсолютном выражении. Быть независтливым означает чувствовать себя вполне удовлетворенным, если другой игрок получает ровно столько же, сколько и вы, при условии, что вы оба выигрываете таким образом больше. Око за око никогда по-настоящему не «выигрывает» игру. Подумайте об этом и вы поймете, что она не может набрать больше очков, чем ее «противник», в каждой отдельной игре, потому что она отказывается лишь в отместку. Она может, самое большее, сыграть вничью со своим противником. Однако каждая ничья приносит обоим игрокам помногу очков. Когда речь идет о стратегии Око за око и о других добропорядочных стратегиях, слово «противник» неуместно. Но, к сожалению, когда психологи проводят игру Итерированный Парадокс заключенных между реальными людьми, почти все игроки поддаются чувству зависти и поэтому в денежном выражении их успехи относительно невелики. Создается впечатление, что многие люди, может быть даже не сознавая этого, готовы лучше потопить другого игрока, чем кооперироваться с ним, чтобы разорить банкомета. Всю ошибочность такой стратегии показал Аксельрод.

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

Однако все это реализуется лишь в случае итерированной игры. Игроки должны знать (или знать в кавычках), что происходящая между ними в данной момент игра — не последняя для них. «Тень будущего», о которой говорил Аксельрод, должна быть длинной. Но насколько длинной? Не может же она быть бесконечной. С теоретической точки зрения продолжительность игры не имеет значения; важно лишь, чтобы ни один из игроков не знал, когда она закончится. Допустим, что мы с вами играем друг против друга и нам обоим известно, что в этой игре должно быть сыграно 100 партий. Разумеется, мы оба понимаем, что 100-я партия, будучи последней, будет равносильна простой одноразовой игре Парадокс заключенного. Поэтому единственной разумной стратегией для любого из нас в 100-й партии должна быть Отказываюсь, и каждый из нас может допустить, что другой игрок вычислит это и твердо решит в последней партии тоже отказаться. Поэтому последнюю партию можно списать со счета как предсказуемую. Но теперь эквивалентом одноразовой игры становится 99-я партия и единственным разумным выбором для каждого игрока в этой предпоследней игре также будет Отказываюсь. К тому же решению им придется прибегнуть в 98-й партии и так далее в обратном направлении. Два совершенно рационально мыслящих игрока, каждый из которых предполагает, что другой строго рационален, могут лишь отказываться, если оба они знают, сколько партий им предстоит играть. Поэтому специалисты по теории игр, рассуждая об Итерированном или Повторяющемся Парадоксе заключенных, всегда исходят из допущения, что конец игры непредсказуем для игроков.

Для ЛЛ:

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

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