Что такое «Дилемма заключённого» ?

Всем привет! Сегодня я хочу рассказать про самую популярную игру в Теории Игр – Дилемму заключенного. Ее еще иногда называют, дилеммой бандитов. Эта игра является фундаментальной проблемой теории игр.

Сначала лучше всего представить классическое определение данной дилеммы:

Полиция поймала двух преступников и развела по разным камерам. Следователь предлагает каждому из них 2 варианта: заложить своего подельника или молчать.
4 варианта развития событий:

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

Можно записать в виде матрицы (таблицы):

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

Посмотрим на эту задачу с точки зрения первого заключенного:

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

Теперь с точки зрения второго заключенного:

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

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

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

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

Примеры дилеммы

Пример №1 Раздел областного бюджета

Есть какая-то область, допустим область N, у нее есть губернатор, и в этой области есть два конкурирующих соседних города, допустим N1 и N2, в каждом свой мэр.

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

И каждый мэр решает, что выбрать: себе один миллион или соседнему городу два?

Таблица будет выглядеть следующий образом:

Посмотрим на рассуждения первого мэра:
Если второй мэр отдаст мне два миллиона, то я лучше возьму себе еще один и у меня будет 3 миллиона. Если же второй мэр возьмет себе один миллион, то я лучше возьму себе один миллион, чем останусь вообще без денег.

Точно такие же рассуждения и у второго мэра.

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

Пример №2 Картель

Представим, что есть какой-то картель, состоящий из двух компаний. Допустим это две фабрики, производящие спички. Они договорились производить определенное количество коробков спичек, и договорились о цене одного коробка.

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

Таблица для этого будет выглядеть следующий образом:

1. Если обе компании будут соблюдать условия, то обе получат по 10 миллионов рублей прибыли;
2. Если обе нарушат, то обе получат по 7 миллионов;
3. Если первая нарушит, а вторая будет соблюдать, то первая получит 15 миллионов, а вторая всего 5;
4. Если первая будет соблюдать, а вторая нарушит, то первая получит 5, а вторая 15.

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

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

Пример №3 Враждующие страны

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

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

Но давайте посмотрим на рассуждение глав этих государств:

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

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

Пример №4 Рекламный бюджет конкурирующих компаний

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

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

В 1984 году Роберт Аксельрод написал книгу «Эволюция кооперации».

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

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

Не смотря на свою простоту (4 строчки кода), лучшей стратегией оказалась «Око за око», созданная Анатолием Рапопортом:
На первой итерации игры сотрудничать, на всех последующих итерация повторять решение, сделанное оппонентом на предыдущей итерации игры.

Затем появилась лучше работающая стратегия «Око за око с прощением», в которой иногда (вероятность 1% - 5%) даже при предательстве второго игрока на предыдущей итерации, первый мог простить его и сотрудничать на следующей итерации. Это помогало разорвать круг мести.

Примером повторяющейся дилеммы заключенного может служить гонка вооружений между США и СССР.

В период холодной войны между СССР и США было противостояние в превосходстве в области ядерного оружия.

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

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

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

Тут стоит отметить, что если у одной 50 ядерных бомб, а у другой 51, то разница будет не столь ощутима, т.к. если начнется война, то все равно всем будет конец, но если от этого абстрагироваться, то одна страна будет более «мощной», чем другая.

Еще один пример повторяющейся дилеммы заключенного – игра Мир/Война, в которой Предать/Молчать заменяются на Война/Мир.

Вообще, дилемма заключенного, важна не только в математике, но и экономике, социологии, политике, психологии, философии, даже в генетике!

Надеюсь эта статья будет вам и полезной, и интересной!
Картинка с лицензией CC0.

С уважением, @veritas