ПДЗ ( терия игр)

[lidias86]

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

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

Заключённый Б хранит молчание Заключённый Б даёт показания
Заключённый А хранит молчание Оба получают по полгода. А получает 10 лет,Б освобождается
Заключённый А даёт показания Б получает 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 (объяснение см. ниже).
Эти правила были установлены Дугласом Хофштадтером и образуют каноническое описание типичной дилеммы заключённого.

Похожая, но другая игра
. Один из примеров — «обмен закрытыми сумками»:

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

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

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

Таким образом, Аксельрод пришёл к утопично звучащему выводу,

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

Если в одноходовой игре в любом случае доминирует стратегия предать, то в многоходовой оптимальная стратегия зависит от поведения других участников.
К примеру, если среди населения все друг друга обманывают, а один ведёт себя по принципу «око за око»,
он оказывается в небольшом проигрыше из-за потери на первом ходе. В такой популяции оптимальная стратегия — всегда предавать.
Если же число исповедующих принцип «око за око» больше, то результат уже зависит от их доли в обществе.
Определить оптимальную стратегию можно двумя путями:
Равновесие Байеса-Нэша: если определено статистическое распределение встречаемого поведения
(например, 33 % «око за око», 33 % всегда обманывают и 33 % всегда сотрудничают),
то стратегию можно вычислить математически[5]. Этим детально занимается теория эволюционной динамики.
По методу Монте-Карло делались симуляции популяций, где индивиды с низкими результатами вымирали,
а с высокими воспроизводились (использовался генетический алгоритм поиска оптимальной эволюционно стабильной стратегии).
Структура поведения в конечной популяции зависит от структуры в начале.
Хотя стратегия «око за око» считалась самой удачной простой стратегией, команда Университета Саутгемптона из Англии (под руководством профессора Николаса Дженнингса)
представила новую стратегию на 20-ю годовщину Чемпионата по ПДЗ. Эта стратегия оказалась более успешной, чем «око за око».
Она основывалась на взаимодействии между программами, чтобы получить максимальный счёт для одной из них.
Университет выставил на чемпионат 60 программ, которые распознавали друг друга по ряду действий на первых 5-10 ходах.
Узнав другую, одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю.
Если программа понимала, что оппонент — не саутгемптонский, она дальше всё время предавала его, чтобы минимизировать результат соперника.
В результате эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.
Хотя эта эволюционно стабильная стратегия оказалась более эффективной в соревновании, это было достигнуто за счёт того,
что в этом конкретном соревновании команда могла участвовать несколькими агентами. Если игрок может контролировать только одного агента, «око за око» оказывается лучшей. Она также соблюдает правило запрета на коммуникации между игроками. То, что саутгемптонские программы исполняли «ритуальный танец» в первые 10 ходов, чтобы узнать друг друга, только подтверждает, насколько важна коммуникация в сдвиге баланса игры.
Если ПДЗ играется ровно N раз (некая известная константа N), есть ещё один интересный факт. Равновесие Нэша — всегда предавать.
Доказываем по индукции: если оба сотрудничают, на последнем ходу выгодно предать, тогда у соперника не будет возможности отомстить.
Поэтому оба предадут друг друга на последнем ходу. Раз соперник предаст на последнем ходу в любом случае, любой игрок захочет предать на предпоследнем ходу, и так далее.
Чтобы сотрудничество оставалось выгодным, необходимо, чтобы будущее было неопределённым для обоих игроков.
Одно из решений — делать число N случайным и подсчитывать результаты по среднему выигрышу за ход.
Дилемма заключённого — фундаментальная для некоторых теорий о взаимодействии людей и доверии.
Из предположения модели ДЗ, что транзакция между двумя людьми требует доверия,
доверительное поведение в популяциях может быть смоделировано при помощи многоигроковой повторяющейся версии игры.
Это годами вдохновляло многих учёных. В 1975 году Грофман и Пул оценивали число работ, посвящённых этой теме, в количестве около 2000.
Психология обучения и теория игр
Если игроки могут оценивать возможность предательства со стороны других игроков, на их поведение влияет опыт.
Простая статистика показывает, что неопытные игроки обычно ведут себя чрезмерно хорошо или плохо.
Если они всё время будут действовать так, то проиграют из-за своей излишней агрессивности или излишней доброты.
С получением большего опыта они реальнее оценивают вероятность предательства и добиваются лучших результатов.
Ранние розыгрыши сильнее влияют на неопытных игроков, чем более поздние на опытных.
Это пример, почему ранний опыт имеет такое влияние на молодых, и почему они особенно уязвимы к немотивированной агрессии, иногда сами становясь такими же.
Можно уменьшить вероятность предательства в популяции при помощи сотрудничества в ранних играх, позволив укрепить доверие.
Следовательно, самопожертвование может в некоторых ситуациях усилить моральный дух группы.
Если группа маленькая, на позитивное поведение с большей вероятностью ответят взаимностью, что поощрит индивидов на дальнейшее сотрудничество.
Это связано с ещё одной дилеммой, что хорошее отношение без причины — это потакание, которое может ухудшить моральные качества.