Дилемма заключённого (дилемма бандита)

Привет, Вы узнаете о том , что такое дилемма заключённого, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое дилемма заключённого, prisoner's dilemma, дилемма бандита , настоятельно рекомендую прочитать все из категории Теория принятия решений.

Дилемма заключенного (англ. Prisoner's dilemma, реже употребляется название «дилемма банди́та») — фундаментальная проблема в теории игр, согласно которой рациональные игроки не всегда будут сотрудничать друг с другом, даже если это в их интересах. Предполагается, что игрок («заключенный») максимизирует свой собственный выигрыш, не заботясь о выгоде других.

Суть проблемы была сформулирована Мерилом Фладом^[en] и Мелвином Дрешером^[en] в 1950 году. Название дилемме дал математик Альберт Такер.

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

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

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

Классическая дилемма заключенного

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

Классическая формулировка дилеммы заключенного такова:

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

Игру можно представить в виде следующей таблицы:

Дилемма появляется, если предположить, что оба заботятся только о минимизации собственного срока заключения.

Представим рассуждения одного из узников. Если партнер молчит, то лучше его предать и выйти на свободу (иначе — полгода тюрьмы). Если партнер свидетельствует, то лучше тоже свидетельствовать против него, чтобы получить 2 года (иначе — 10 лет) тюрьмы. Стратегия «свидетельствовать» строго доминирует над стратегией «молчать». Аналогично другой узник приходит к тому же выводу.

С точки зрения группы (этих двух узников) лучше всего сотрудничать друг с другом, хранить молчание и получить по полгода, так как это уменьшит суммарный срок заключения. Любое другое решение будет менее выгодным. Это очень наглядно демонстрирует, что в игре с ненулевой суммой Парето-оптимум может быть противоположным равновесию Нэша.

Обобщенная форма

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

1. В игре — два игрока и банкир. Каждый игрок держит 2 карты: на одной написано «сотрудничать», на другой — «предать» (это стандартная терминология игры). Каждый игрок кладет одну карту перед банкиром лицом вниз (то есть никто не знает чужого решения, хотя знание чужого решения не влияет на анализ доминирования ). Банкир открывает карты и выдает выигрыш.
2. Если оба выбрали «сотрудничать», оба получают C. Если один выбрал «предать», другой «сотрудничать» — первый получает D, второй с. Если оба выбрали «предать» — оба получают d.
3. Значения переменных C, D, c, d могут быть любого знака (в примере выше все меньше либо равны 0). Обязательно должно соблюдаться неравенство D > C > d > c, чтобы игра представляла собой «дилемму заключенного».
4. Если игра повторяется, то есть играется больше 1 раза подряд, общий выигрыш от сотрудничества должен быть больше суммарного выигрыша в ситуации, когда один предает, а другой — нет, то есть 2C > D + c. Об этом говорит сайт https://intellect.icu . Это неравенство говорит о том, что в случае взаимного сотрудничества достигается строгий Парето-оптимум – ситуация, когда любая альтернатива приводит к снижению выигрыша хотя бы для одного игрока.

Эти правила были установлены Дугласом Хофштадтером и образуют каноническое описание типичной дилеммы заключенного.

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

Хофштадтер предположил, что люди проще понимают такие задачи, как дилемма заключенного, если она представлена в виде отдельной игры или процесса торговли. Один из примеров — «обмен закрытыми сумками»:

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

В этой игре обман всегда будет решением с максимальной краткосрочной материальной выгодой.

Примеры из реальной жизни

В некоторых телевикторинах подобный принцип применяется для определения победителей или раунда, или финала. Пример дилеммы демонстрировался в 2012 году в британской телевикторине The Bank Job в финале каждого сезона: двум игрокам, вышедшим в финал, предстояло принять решение о том, как распорядиться выигрышем. По половине от суммарного разыгрываемого джекпота лежало в чемоданах с надписью CASH, в двух других были газетные обрывки с надписью TRASH (у игрока по одному чемодану каждого типа). Каждый игрок должен был взять один из своих чемоданов и отдать другому. Если оба игрока получали чемоданы CASH, то делили выигрыш пополам. Если один отдавал чемодан TRASH, то он забирал весь банк игры. Если оба отдавали TRASH — оба оставались без денег, а выигрыш доставался выбывшим на предыдущих этапах игрокам финала.

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

В политическом реализме, к примеру, сценарий дилеммы часто используется для иллюстрации проблемы двух государств, вовлеченных в гонку вооружений. Оба государства будут заявлять, что у них есть две возможности: либо увеличить расходы на военные нужды, либо сокращать вооружения. При этом очевидным образом выполняются постулаты дилеммы заключенного (D > C > d > c) :

• D — «мы вооружились, а противник — нет» — наилучший исход, наибольшая безопасность;
• C — «никто не вооружился» — следующий по предпочтительности исход;
• d — «оба вооружились» — плохо, но не катастрофично;
• c — «мы не вооружились, а противник вооружился» — катастрофический исход.

С точки зрения стороны А, если сторона Б не вооружается, то для А выбор идет между D и C — лучше вооружаться. Если же Б вооружается, то для А выбор идет между d и c — опять-таки выгоднее вооружаться. Тем самым при любом выборе Б для стороны А выгоднее вооружаться. Ситуация для стороны Б совершенно аналогична и в итоге обе стороны будут стремиться к военной экспансии.

Уильям Паундстоун в книге о дилемме заключенного описывает ситуацию в Новой Зеландии, где газетные ящики оставляют открытыми. Газету можно взять, не заплатив за нее, но мало кто так делает, потому что большинство осознает вред, который был бы, если бы все воровали газеты. Поскольку дилемма заключенного в чистом виде одновременна для всех игроков (никто не может повлиять на решения других), эта распространенная линия рассуждений называется «магическое мышление». Будучи объяснением отсутствия мелкого воровства, магическое мышление объясняет добровольное голосование на выборах (когда неголосующий считается зайцем). В качестве альтернативы, это поведение может объясняться ожиданием будущих действий (и не требовать связи с «магическим мышлением»). Моделирование будущих действий требует добавление измерения времени, что делается в повторяющейся дилемме.

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

Многие дилеммы в реальной жизни включают множество игроков. Хотя и метафорическую, «трагедию общин» Хардина можно рассматривать как обобщение дилеммы для множества игроков. Каждый житель общины выбирает — пасти ли скот на общем пастбище и получить выгоду, истощая его ресурсы, либо ограничить свой доход. Коллективный результат от всеобщего (или частого) максимального использования пастбища — низкий доход (ведущий к разрушению общины). Однако такая игра не является формальной, поскольку может быть разбита на последовательность классических игр с 2 участниками.^{[источник не указан 1300 дней]}

Повторяющаяся дилемма заключенного

В книге «Эволюция кооперации» 1984 года Роберт Аксельрод исследовал расширение сценария дилеммы, которое он назвал повторяющаяся дилемма заключенного (ПДЗ). В ней участники делают выбор снова раз за разом и помнят предыдущие результаты. Аксельрод пригласил академических коллег со всего мира, чтобы разработать компьютерные стратегии, чтобы соревноваться в чемпионате по ПДЗ. Программы, вошедшие в него, различались по алгоритмической сложности, начальной враждебности, способности к прощению и так далее.

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

Лучшей детерминистской стратегией оказалась «Око за око» (англ. Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простейшей из всех участвовавших программ, состояла всего из 4 строк кода на языке Бейсик. Стратегия проста: сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Чуть лучше работает стратегия «Око за око с прощением». Когда оппонент предает, на следующем шаге игрок иногда, вне зависимости от предыдущего шага, сотрудничает с небольшой вероятностью (1—5 %). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится недопонимание — когда решение одного игрока сообщается другому с ошибкой.

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

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

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

Рассмотрим снова модель гонки вооружений. Был дан вывод, что единственная рациональная стратегия — вооружаться, даже если обе страны хотели бы тратить ВВП на масло, а не пушки . Интересно, что попытки продемонстрировать, что вывод дилеммы работает на практике (делая анализ «высоких» и «низких» военных расходов между периодами, на основе предположений ПДЗ), часто показывают, что такого поведения не происходит (например, греческие и турецкие военные расходы меняются не в соответствии со стратегией «око за око», а, вероятнее всего, следуют внутренней политике). Это может быть примером рационального поведения, отличающегося от одноразовой и многоходовой игр.

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

Определить оптимальную стратегию можно двумя путями:

• равновесие Байеса-Нэша: если определено статистическое распределение встречаемого поведения (например, 33 % «око за око», 33 % всегда обманывают и 33 % всегда сотрудничают), то стратегию можно вычислить математически . Этим детально занимается теория эволюционной динамики;
• по методу Монте-Карло делались симуляции популяций, где индивиды с низкими результатами вымирали, а с высокими воспроизводились (использовался генетический алгоритм поиска оптимальной эволюционно стабильной стратегии). Структура поведения в конечной популяции зависит от структуры в начале.

Хотя стратегия «око за око» считалась самой удачной простой стратегией, команда университета Саутгемптона под руководством профессора Николаса Дженнингса представила новую стратегию на 20-ю годовщину Чемпионата по ПДЗ. Эта стратегия оказалась более успешной, чем «око за око». Она основывалась на взаимодействии между программами, чтобы получить максимальный счет для одной из них. Университет выставил на чемпионат 60 программ, которые распознавали друг друга по ряду действий на первых 5—10 ходах. Узнав другую, одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю. Если программа понимала, что оппонент — не саутгемптонский, она дальше все время предавала его, чтобы минимизировать результат соперника. В результате эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.

Хотя эта эволюционно стабильная стратегия оказалась более эффективной в соревновании, это было достигнуто за счет того, что в этом конкретном соревновании команда могла участвовать несколькими агентами. Если игрок может контролировать только одного агента, «око за око» оказывается лучшей. Она также соблюдает правило запрета на коммуникации между игроками. То, что саутгемптонские программы исполняли «ритуальный танец» в первые 10 ходов, чтобы узнать друг друга, только подтверждает, насколько важна коммуникация в сдвиге баланса игры.

Если ПДЗ играется ровно N раз (некая известная константа N), есть еще один интересный факт. Равновесие Нэша — всегда предавать. Доказываем по индукции: если оба сотрудничают, на последнем ходу выгодно предать, тогда у соперника не будет возможности отомстить. Поэтому оба предадут друг друга на последнем ходу. Раз соперник предаст на последнем ходу в любом случае, любой игрок захочет предать на предпоследнем ходу, и так далее. Чтобы сотрудничество оставалось выгодным, необходимо, чтобы будущее было неопределенным для обоих игроков. Одно из решений — делать число N случайным и подсчитывать результаты по среднему выигрышу за ход.

Дилемма заключенного — фундаментальная для некоторых теорий о взаимодействии людей и доверии. Из предположения модели дилеммы, что транзакция между двумя людьми требует доверия, доверительное поведение в популяциях может быть смоделировано при помощи многоигроковой повторяющейся версии игры. Это годами вдохновляло многих ученых. В 1975 году Грофман и Пул оценивали число работ, посвященных этой теме, в количестве около 2000.

Психология обучения и теория игр

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

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

Эти процессы — главное поле интереса взаимного альтруизма, группового отбора, семейного отбора и этики.

Влияние религии

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

Вау!! 😲 Ты еще не читал? Это зря!

• Доверие
• Оптимум
• Парадокс неожиданной казни
• Парадокс сатанинской бутылки Стивенсона
• Охота на оленя
• Задача трех узников
• Социальные дилеммы
• Оконная дилемма
• Дилемма автобусной остановки
• цугцванг (нем. Zugzwang «принуждение к ходу») — положение в шашках и шахматах, в котором любой ход игрока ведет к ухудшению его позиции.

Данная статья про дилемма заключённого подтверждают значимость применения современных методик для изучения данных проблем. Надеюсь, что теперь ты понял что такое дилемма заключённого, prisoner's dilemma, дилемма бандита и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория принятия решений