Дилемма заключенного

Материал из Вики LessWrong.ru
Перейти к: навигация, поиск

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

Классическая дилемма заключенного[править]

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

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

Предполагая, что каждый игрок заботится только о собственном благополучии, для первого игрока рейтинг предпочитетельности исходов будет такой (где C — Cooperate, Сотрудничать, D — Defect, Предать): DC (0 лет), CC (0.5 лет), DD (2 года), CD (10 лет).

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

Другая формулировка дилеммы заключенного с аналогичными выводами: «Некий меценат предлагает двум соседям (каждому независимо от другого) выбор: взять один миллион долларов самому или передать два миллиона долларов другому».

Способы разрешения классической дилеммы заключенного[править]

Если между двумя агентами существует общее знание о том, что они достаточно похожи друг на друга (настолько, что придут к одинаковым выводам и выберут одинаковую стратегию), то есть реализуется либо исход CC, либо DD, но не CD и не DC, то делая выбор между миром, в котором оба выбрали кооперацию, и миром, в котором оба выбрали предательство, они оба предпочтут сделать ход C.

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

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

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

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

В соревнованиях компьютерных программ наилучший результат часто показывает стратегия Tit-for-tat («Око за око»), имеющая следующий простой алгоритм: «Сотрудничать в первом раунде; в N+1 раунде делать тот же ход, что делал оппонент в N раунде (поощрять за предыдущее сотрудничество, наказывать за предыдущее предательство)».

Чтобы набирать большое количество баллов в соревнованиях, стратегия обычно должна обладать следующими качествами:

  • Добрая (не предавать до тех пор, пока оппонент не предал вас);
  • Мстительная (время от времени предавать оппонента после предательства с его стороны, чтобы оппонент не мог эксплуатировать вас);
  • Прощающая (с некоторой вероятностью не предавать оппонента в ответ на предательство с его стороны: в ситуациях ошибки «палец дрогнул, нажал D вместо C», зашумленного канала «нажал C, но оппоненту показалось, что было нажато D» или прощупывания оппонента «нажму D — а вдруг его можно эксплуатировать?» игроки могут войти в цикл постоянного взаимного предательства; желательно иметь возможность вернуться к циклу взаимной кооперации после наказания за предательство);
  • Независтливая (максимизировать свой собственный счет, а не пытаться всеми силами обойти счет оппонентов).

Дилемма заключенного с доступом к исходному коду[править]

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

Программу, которая всегда сотрудничает, называют CooperateBot; программу, которая всегда предает, называют DefectBot.

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

CliqueBot[править]

Такая программа сравнивает исходный код оппонента со своим собственным (задача получения программой собственного кода известна как quine и всегда технически разрешима). Если код обеих программ совпадает, то CliqueBot сотрудничает со своим оппонентом, иначе — предает.

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

FairBot[править]

Алгоритм работы FairBot следующий: попытаться доказать, что оппонент (про которого известно, что он получит на вход исходный код FairBot) будет сотрудничать с ним; если это удалось, то сотрудничать; иначе — предать.

Реализация такого алгоритма через прямую эмуляцию нецелесообразна, так как в случае игры FairBot1 против FairBot2 первый вначале запустит эмуляцию второго, который запустит эмуляцию первого, который запустит эмуляцию второго и т. п. В подобной ситуации одна из программ рано или поздно исчерпает стек/память, не сумев доказать, что оппонент будет сотрудничать, и предаст его. Другая программа (которая исчерпает ресурсы позже) сможет это показать в своей эмуляции, и в ответ тоже предаст.

Однако, если FairBot реализован через математический анализ кода оппонента, то с помощью [теоремы Лёба] можно доказать, что два таких алгоритма будут сотрудничать друг с другом даже при наличии различий в структуре своего кода (в отличие от CliqueBot).

OptimisticBot[править]

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

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

Т.о., OptimisticBot не является неэкспуатируемым.

PrudentBot[править]

FairBot имеет недостаток, состоящий в том, что он сотрудничает с CooperateBot, хотя мог бы эксплуатировать его и предавать, получая дополнительные очки (это может звучать этически сомнительно, но в ряде случаев является полностью морально оправданно).

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

PrudentBot сотрудничает как со своими разновидностями, так и с FairBot, и при этом предает CooperateBot.

Статьи по теме[править]

См. также[править]