Дилемма заключенного - История изменений

Tookser: /* Классическая дилемма заключенного */ добавил матрицу игры

2023-11-05T03:46:33Z

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

ReverendBayes: Проставитьюю

2023-11-03T18:26:13Z

Проставитьюю

ReverendBayes: Немного дооформил

2023-01-08T10:58:50Z

Немного дооформил

ReverendBayes в 09:53, 8 января 2023

2023-01-08T09:53:22Z

ReverendBayes: Новая страница: «'''Дилемма заключенного''' — проблема из теории игр, демонстрирующая, что два агента мо…»

2023-01-08T09:52:53Z

Новая страница: «'''Дилемма заключенного''' — проблема из теории игр, демонстрирующая, что два агента мо…»

Новая страница

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

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

Двое преступников — А и Б — попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (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.

== Статьи по теме ==
* [https://intelligence.org/files/ProgramEquilibrium.pdf Program Equilibrium in the Prisoner’s Dilemma via Lob’s Theorem] — статья [[MIRI]] о дилемме заключенного с доступом к исходному коду

== См. также ==
* [[Молох]]
* [[Охота на оленя]]

[[Категория:Понятие]]
[[Категория:Теория игр]]

← Предыдущая		Версия 03:46, 5 ноября 2023
Строка 2:		Строка 2:

	== Классическая дилемма заключенного ==		== Классическая дилемма заключенного ==
		+
		+	{\| class="wikitable" style="text-align:center; float:right; margin-left:0.8em; clear:right;"
		+	\|+ Матрица исходной игры
		+	\|-
		+	! !! <span style="color:#20B2AA">Заключённый Б</span> молчит !! <span style="color:#20B2AA">Заключённый Б</span> предаёт
		+	\|-
		+	! <span style="color:#A81C07">Заключённый А</span> молчит
		+	\| <span style="color:#A81C07">0.5</span>/<span style="color:#20B2AA">0.5</span>\|\| <span style="color:#A81C07">10</span>/<span style="color:#20B2AA">0</span>
		+	\|-
		+	! <span style="color:#A81C07">Заключённый А</span> предаёт
		+	\| <span style="color:#A81C07">0</span>/<span style="color:#20B2AA">10</span> \|\| <span style="color:#A81C07">2</span>/<span style="color:#20B2AA">2</span>
		+	\|}
		+
		+
	Классическая формулировка такова:		Классическая формулировка такова:

@@ Строка 49: / Строка 49: @@
 Реализация такого алгоритма через прямую эмуляцию нецелесообразна, так как в случае игры FairBot1 против FairBot2 первый вначале запустит эмуляцию второго, который запустит эмуляцию первого, который запустит эмуляцию второго и т. п. В подобной ситуации одна из программ рано или поздно исчерпает стек/память, не сумев доказать, что оппонент будет сотрудничать, и предаст его. Другая программа (которая исчерпает ресурсы позже) сможет это показать в своей эмуляции, и в ответ тоже предаст.
-Однако, если FairBot реализован через математический анализ кода оппонента, то с помощью [теоремы Лёба] можно доказать, что два таких алгоритма будут сотрудничать друг с другом даже при наличии различий в структуре своего кода (в отличие от CliqueBot).
+Однако, если FairBot реализован через математический анализ кода оппонента, то с помощью [[Теорема Лёба|теоремы Лёба]] можно доказать, что два таких алгоритма будут сотрудничать друг с другом даже при наличии различий в структуре своего кода (в отличие от CliqueBot).
 === OptimisticBot ===

@@ Строка 12: / Строка 12: @@
 Другая формулировка дилеммы заключенного с аналогичными выводами: «Некий меценат предлагает двум соседям (каждому независимо от другого) выбор: взять один миллион долларов самому или передать два миллиона долларов другому».
-Способы разрешения классической дилеммы заключенного
+== Способы разрешения классической дилеммы заключенного ==
 Если между двумя агентами существует [[общее знание]] о том, что они достаточно похожи друг на друга (настолько, что придут к одинаковым выводам и выберут одинаковую стратегию), то есть реализуется либо исход CC, либо DD, но не CD и не DC, то делая выбор между миром, в котором оба выбрали кооперацию, и миром, в котором оба выбрали предательство, они оба предпочтут сделать ход C.
@@ Строка 35: / Строка 35: @@
 В повторяющейся дилемме заключенного агент может получить косвенные данные о стратегии оппонента по его прошлым ходам. Развитие этой идеи — возможность получить полную информацию о стратегии оппонента через анализ его полного исходного кода. В соответствующем гипотетическом турнире компьютерных программ все они играют друг с другом попарно по одному разу, и каждой на вход дается исходный код оппонента.
-Программу, которая всегда сотрудничает, называют CooperateBot; программу, которая всегда предает, называют DefectBot.
+Программу, которая всегда сотрудничает, называют '''CooperateBot'''; программу, которая всегда предает, называют '''DefectBot'''.
 Основное качество, которым должна обладать хорошая программа — не быть эксплуатируемой (то есть предотвращать ситуации, когда она сотрудничает с оппонентом, который предает ее). Большинство описанных ниже программ обладают этим качеством.

@@ Строка 72: / Строка 72: @@
 * [[Охота на оленя]]
-[[Категория:Понятие]]
+[[Категория:Понятия]]
 [[Категория:Теория игр]]