Доверие, эгоизм и Дилемма заключенного
Dec. 5th, 2009 06:21 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
alik_ntuВ теории игр дилемма заключённого (далее ДЗ, реже употребляется название «дилемма бандита») — некооперативная игра, в которой игроки стремятся получить выгоду, сотрудничая друг с другом или предавая. Как во всей теории игр, предполагается, что игрок («заключённый») максимизирует свой собственный выигрыш, не заботясь о выгоде других.
Например, один из вариантов:
В этой игре участвуют два игрока. Каждый раунд оба игрока выбирают одно из двух действий: делиться или не делиться некоторой суммой денег (заранее договариваться нельзя). Если оба игрока делятся, оба получают по 3 условных доллара, если оба не хотят делиться — по 2 условных доллара. Если же один делится, а другой делиться не хочет, первый получает всего 1 условный доллар, а второй получает целых 4 условных доллара.
В ДЗ предательство строго доминирует над сотрудничеством, поэтому единственное возможное равновесие — предательство обоих участников. Проще говоря, неважно, что сделает другой игрок, каждый выиграет больше, если предаст. Поскольку в любой ситуации предать выгоднее, чем сотрудничать, все рациональные игроки выберут предательство.
Но гораздо интереснее расширенный вариант.
В повторяющейся дилемме заключённого игра происходит периодически, и каждый игрок может «наказать» другого за несотрудничество ранее.
В книге «Эволюция кооперации» (1984) Роберт Аксельрод (англ.) исследовал расширение сценария ДЗ, которое он назвал повторяющаяся дилемма заключённого (ПДЗ). В ней участники делают выбор снова раз за разом и помнят предыдущие результаты. Аксельрод пригласил академических коллег со всего мира, чтобы разработать компьютерные стратегии, чтобы соревноваться в чемпионате по ПДЗ. Программы, вошедшие в него, различались по алгоритмической сложности, начальной враждебности, способности к прощению и так далее.
Аксельрод открыл, что если игра повторялась долго среди множества игроков, каждый с разными стратегиями, «жадные» стратегии давали плохие результаты в долгосрочном периоде, тогда как более «альтруистические» стратегии работали лучше, с точки зрения собственного интереса. Он использовал это, чтобы показать возможный механизм эволюции альтруистического поведения из механизмов, которые изначально чисто эгоистические, через естественный отбор.
Лучшей детерминистской стратегией оказалась «Око за око» (англ. Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простейшей из всех участвовавших программ, состояла всего из 4 строк кода на языке Бейсик. Стратегия проста: сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Чуть лучше работает стратегия «Око за око с прощением». Когда оппонент предаёт, на следующем шаге игрок иногда в любом случае сотрудничает с небольшой вероятностью (1-5 %). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится недопонимание — когда решение одного игрока сообщается другому с ошибкой.
Анализируя стратегии, набравшие лучшие результаты, Аксельрод назвал несколько условий, необходимых, чтобы стратегия получила высокий результат:
Если в одноходовой игре в любом случае доминирует стратегия предать, то в многоходовой оптимальная стратегия зависит от поведения других участников. К примеру, если среди населения все друг друга обманывают, а один ведёт себя по принципу «око за око», он оказывается в небольшом проигрыше из-за потери на первом ходе. В такой популяции оптимальная стратегия — всегда предавать. Если же число исповедующих принцип «око за око» больше, то результат уже зависит от их доли в обществе.
Хотя стратегия «око за око» считалась самой удачной простой стратегией, команда Университета Саутгемптона из Англии (под руководством профессора Николаса Дженнингса) представила новую стратегию на 20-ю годовщину Чемпионата по ПДЗ. Эта стратегия оказалась более успешной, чем «око за око». Она основывалась на взаимодействии между программами, чтобы получить максимальный счёт для одной из них. Университет выставил на чемпионат 60 программ, которые распознавали друг друга по ряду действий на первых 5-10 ходах. Узнав другую, одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю. Если программа понимала, что оппонент — не саутгемптонский, она дальше всё время предавала его, чтобы минимизировать результат соперника. В результате эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.
Хотя эта эволюционно стабильная стратегия оказалась более эффективной в соревновании, это было достигнуто за счёт того, что в этом конкретном соревновании команда могла участвовать несколькими агентами. Если игрок может контролировать только одного агента, «око за око» оказывается лучшей. Она также соблюдает правило запрета на коммуникации между игроками. То, что саутгемптонские программы исполняли «ритуальный танец» в первые 10 ходов, чтобы узнать друг друга, только подтверждает, насколько важна коммуникация в сдвиге баланса игры.
Если ПДЗ играется ровно N раз (некая известная константа N), есть ещё один интересный факт. Равновесие Нэша — всегда предавать. Доказываем по индукции: если оба сотрудничают, на последнем ходу выгодно предать, тогда у соперника не будет возможности отомстить. Поэтому оба предадут друг друга на последнем ходу. Раз соперник предаст на последнем ходу в любом случае, любой игрок захочет предать на предпоследнем ходу, и так далее. Чтобы сотрудничество оставалось выгодным, необходимо, чтобы будущее было неопределённым для обоих игроков. Одно из решений — делать число N случайным и подсчитывать результаты по среднему выигрышу за ход.
Дилемма заключённого — фундаментальная для некоторых теорий о взаимодействии людей и доверии. Из предположения модели ДЗ, что транзакция между двумя людьми требует доверия, доверительное поведение в популяциях может быть смоделировано при помощи многоигроковой повторяющейся версии игры. Это годами вдохновляло многих учёных. В 1975 году Грофман и Пул оценивали число работ, посвящённых этой теме, в количестве около 2000.
Источник: http://ru.wikipedia.org/wiki/Дилемма_заключенного
См. также:
http://ru.wikipedia.org/wiki/Трагедия_общин
http://ru.wikipedia.org/wiki/Трагедия_антиобщин
Например, один из вариантов:
В этой игре участвуют два игрока. Каждый раунд оба игрока выбирают одно из двух действий: делиться или не делиться некоторой суммой денег (заранее договариваться нельзя). Если оба игрока делятся, оба получают по 3 условных доллара, если оба не хотят делиться — по 2 условных доллара. Если же один делится, а другой делиться не хочет, первый получает всего 1 условный доллар, а второй получает целых 4 условных доллара.
В ДЗ предательство строго доминирует над сотрудничеством, поэтому единственное возможное равновесие — предательство обоих участников. Проще говоря, неважно, что сделает другой игрок, каждый выиграет больше, если предаст. Поскольку в любой ситуации предать выгоднее, чем сотрудничать, все рациональные игроки выберут предательство.
Но гораздо интереснее расширенный вариант.
В повторяющейся дилемме заключённого игра происходит периодически, и каждый игрок может «наказать» другого за несотрудничество ранее.
В книге «Эволюция кооперации» (1984) Роберт Аксельрод (англ.) исследовал расширение сценария ДЗ, которое он назвал повторяющаяся дилемма заключённого (ПДЗ). В ней участники делают выбор снова раз за разом и помнят предыдущие результаты. Аксельрод пригласил академических коллег со всего мира, чтобы разработать компьютерные стратегии, чтобы соревноваться в чемпионате по ПДЗ. Программы, вошедшие в него, различались по алгоритмической сложности, начальной враждебности, способности к прощению и так далее.
Аксельрод открыл, что если игра повторялась долго среди множества игроков, каждый с разными стратегиями, «жадные» стратегии давали плохие результаты в долгосрочном периоде, тогда как более «альтруистические» стратегии работали лучше, с точки зрения собственного интереса. Он использовал это, чтобы показать возможный механизм эволюции альтруистического поведения из механизмов, которые изначально чисто эгоистические, через естественный отбор.
Лучшей детерминистской стратегией оказалась «Око за око» (англ. Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простейшей из всех участвовавших программ, состояла всего из 4 строк кода на языке Бейсик. Стратегия проста: сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Чуть лучше работает стратегия «Око за око с прощением». Когда оппонент предаёт, на следующем шаге игрок иногда в любом случае сотрудничает с небольшой вероятностью (1-5 %). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится недопонимание — когда решение одного игрока сообщается другому с ошибкой.
Анализируя стратегии, набравшие лучшие результаты, Аксельрод назвал несколько условий, необходимых, чтобы стратегия получила высокий результат:
- Добрая. Важнейшее условие — стратегия должна быть «доброй», то есть не предавать, пока этого не сделает оппонент. Почти все стратегии-лидеры были добрыми. Поэтому чисто эгоистичная стратегия по чисто эгоистическим причинам не будет первой «бить» соперника.
- Мстительная. Успешная стратегия не должна быть слепым оптимистом. Она должна всегда мстить. Пример немстительной стратегии — всегда сотрудничать. Это очень плохой выбор, поскольку «подлые» стратегии воспользуются этим.
- Прощающая. Другое важное качество успешных стратегий — уметь прощать. Отомстив, они должны вернуться к сотрудничеству, если оппонент не продолжает предавать. Это предотвращает бесконечное мщение друг другу и максимизирует выигрыш.
- Не завистливая. Последнее качество — не быть завистливым, то есть не пытаться набрать больше очков, чем оппонент (что в принципе невозможно для «доброй» стратегии, то есть добрая стратегия никогда не может набрать больше очков, чем оппонент).
Если в одноходовой игре в любом случае доминирует стратегия предать, то в многоходовой оптимальная стратегия зависит от поведения других участников. К примеру, если среди населения все друг друга обманывают, а один ведёт себя по принципу «око за око», он оказывается в небольшом проигрыше из-за потери на первом ходе. В такой популяции оптимальная стратегия — всегда предавать. Если же число исповедующих принцип «око за око» больше, то результат уже зависит от их доли в обществе.
Хотя стратегия «око за око» считалась самой удачной простой стратегией, команда Университета Саутгемптона из Англии (под руководством профессора Николаса Дженнингса) представила новую стратегию на 20-ю годовщину Чемпионата по ПДЗ. Эта стратегия оказалась более успешной, чем «око за око». Она основывалась на взаимодействии между программами, чтобы получить максимальный счёт для одной из них. Университет выставил на чемпионат 60 программ, которые распознавали друг друга по ряду действий на первых 5-10 ходах. Узнав другую, одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю. Если программа понимала, что оппонент — не саутгемптонский, она дальше всё время предавала его, чтобы минимизировать результат соперника. В результате эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.
Хотя эта эволюционно стабильная стратегия оказалась более эффективной в соревновании, это было достигнуто за счёт того, что в этом конкретном соревновании команда могла участвовать несколькими агентами. Если игрок может контролировать только одного агента, «око за око» оказывается лучшей. Она также соблюдает правило запрета на коммуникации между игроками. То, что саутгемптонские программы исполняли «ритуальный танец» в первые 10 ходов, чтобы узнать друг друга, только подтверждает, насколько важна коммуникация в сдвиге баланса игры.
Если ПДЗ играется ровно N раз (некая известная константа N), есть ещё один интересный факт. Равновесие Нэша — всегда предавать. Доказываем по индукции: если оба сотрудничают, на последнем ходу выгодно предать, тогда у соперника не будет возможности отомстить. Поэтому оба предадут друг друга на последнем ходу. Раз соперник предаст на последнем ходу в любом случае, любой игрок захочет предать на предпоследнем ходу, и так далее. Чтобы сотрудничество оставалось выгодным, необходимо, чтобы будущее было неопределённым для обоих игроков. Одно из решений — делать число N случайным и подсчитывать результаты по среднему выигрышу за ход.
Дилемма заключённого — фундаментальная для некоторых теорий о взаимодействии людей и доверии. Из предположения модели ДЗ, что транзакция между двумя людьми требует доверия, доверительное поведение в популяциях может быть смоделировано при помощи многоигроковой повторяющейся версии игры. Это годами вдохновляло многих учёных. В 1975 году Грофман и Пул оценивали число работ, посвящённых этой теме, в количестве около 2000.
Источник: http://ru.wikipedia.org/wiki/Дилемма_заключенного
См. также:
http://ru.wikipedia.org/wiki/Трагедия_общин
http://ru.wikipedia.org/wiki/Трагедия_антиобщин
