Эволюция кооперации
"Люди наказываются не за грехи, а самими грехами." (Элберт Хаббард)
Я вчера у fritzmorgen прочитал "про отличную игру, которая за пять минут не только объясняет, почему в одних местах человек человеку волк, а в других - друг, товарищ и брат, но и рассказывает, как правильно вести себя в этих местах?".
Данная игра находится по адресу: https://notdotteam.github.io/trust/
Эту игру придумал бостонский геймдизайнер Ник Кейс, он смоделировал отношения людей в обществе на основе книги Роберта Аксельрода 1984-го года «Эволюция кооперации». Ниже я напишу об авторе этой книги и собственно о книге.
Роберт Аксельрод (р. 27 мая 1943) - американский политолог, профессор политических наук и государственной политики в Мичиганском университете, где работает с 1974 года.
Аксельрод получил степень бакалавра в области математики в Чикагском университете в 1964 году. В 1969 году он получил докторскую степень в области политологии в Йельском университете. Позже преподавал в Калифорнийском университете в Беркли с 1968 до 1974 года. С 1974 года в Мичиганском университете.
Он более всего известен своими работами в области эволюции сотрудничества, которую развивал в многочисленных статьях и, в частности, в книге «Эволюция сотрудничества» (The Evolution of Cooperation). В настоящее время его научные интересы включают теорию сложности (особенно агент-ориентированное моделирование) и проблемы международной безопасности. Аксельрод является членом Совета по международным отношениям.
Среди его наград и премий - членство в Национальной академии наук, пятилетняя стипендия по премии Макартура, премия от Американской ассоциации содействия развитию наук за выдающийся вклад в науку. Он был избран членом Американской академии искусств и наук в 1985 году.
В книге «Эволюция кооперации» 1984 года Роберт Аксельрод исследовал расширение сценария дилеммы, которое он назвал повторяющаяся дилемма заключённого (ПДЗ). В ней участники делают выбор снова раз за разом и помнят предыдущие результаты. Аксельрод пригласил академических коллег со всего мира, чтобы разработать компьютерные стратегии, чтобы соревноваться в чемпионате по ПДЗ. Программы, вошедшие в него, различались по алгоритмической сложности, начальной враждебности, способности к прощению и так далее.
Аксельрод открыл, что если игра повторялась долго среди множества игроков, каждый с разными стратегиями, «жадные» стратегии давали плохие результаты в долгосрочном периоде, тогда как более «альтруистические» стратегии работали лучше, с точки зрения собственного интереса. Он использовал это, чтобы показать возможный механизм эволюции альтруистического поведения из механизмов, которые изначально чисто эгоистические, через естественный отбор.
Лучшей детерминистской стратегией оказалась «Око за око» (англ. Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простейшей из всех участвовавших программ, состояла всего из 4 строк кода на языке Бейсик. Стратегия проста: сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Чуть лучше работает стратегия «Око за око с прощением». Когда оппонент предаёт, на следующем шаге игрок иногда, вне зависимости от предыдущего шага, сотрудничает с небольшой вероятностью (1-5 %). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится недопонимание - когда решение одного игрока сообщается другому с ошибкой.
Анализируя стратегии, набравшие лучшие результаты, Аксельрод назвал несколько условий, необходимых, чтобы стратегия получила высокий результат:
- Добрая. Важнейшее условие - стратегия должна быть «доброй», то есть не предавать, пока этого не сделает оппонент. Почти все стратегии-лидеры были добрыми. Поэтому чисто эгоистичная стратегия по чисто эгоистическим причинам не будет первой «бить» соперника.
- Мстительная. Успешная стратегия не должна быть слепым оптимистом. Она должна всегда мстить. Пример прощающей стратегии - всегда сотрудничать. Это очень плохой выбор, поскольку «подлые» стратегии воспользуются этим.
- Прощающая. Другое важное качество успешных стратегий - уметь прощать. Отомстив, они должны вернуться к сотрудничеству, если оппонент не продолжает предавать. Это предотвращает бесконечное мщение друг другу и максимизирует выигрыш.
- Независтливая. Последнее качество - не быть завистливым, то есть не пытаться набрать больше очков, чем оппонент.
Таким образом, Аксельрод пришёл к утопично звучащему выводу, что эгоистичные индивиды во имя их же эгоистического блага будут стремиться быть добрыми, прощающими и не завистливыми.
Рассмотрим снова модель гонки вооружений. Был дан вывод, что единственная рациональная стратегия - вооружаться, даже если обе страны хотели бы тратить ВВП на масло, а не пушки. Интересно, что попытки продемонстрировать, что вывод дилеммы работает на практике (делая анализ «высоких» и «низких» военных расходов между периодами, на основе предположений ПДЗ), часто показывают, что такого поведения не происходит (например, греческие и турецкие военные расходы меняются не в соответствии со стратегией «око за око», а, вероятнее всего, следуют внутренней политике). Это может быть примером рационального поведения, отличающегося от одноразовой и многоходовой игр.
Если в одноходовой игре в любом случае доминирует стратегия предать, то в многоходовой оптимальная стратегия зависит от поведения других участников. К примеру, если среди населения все друг друга обманывают, а один ведёт себя по принципу «око за око», он оказывается в небольшом проигрыше из-за потери на первом ходе. В такой популяции оптимальная стратегия - всегда предавать. Если же число исповедующих принцип «око за око» больше, то результат уже зависит от их доли в обществе.
Определить оптимальную стратегию можно двумя путями:
- равновесие Байеса-Нэша: если определено статистическое распределение встречаемого поведения (например, 33 % «око за око», 33 % всегда обманывают и 33 % всегда сотрудничают), то стратегию можно вычислить математически. Этим детально занимается теория эволюционной динамики;
- по методу Монте-Карло делались симуляции популяций, где индивиды с низкими результатами вымирали, а с высокими воспроизводились (использовался генетический алгоритм поиска оптимальной эволюционно стабильной стратегии). Структура поведения в конечной популяции зависит от структуры в начале.
Хотя стратегия «око за око» считалась самой удачной простой стратегией, команда университета Саутгемптона под руководством профессора Николаса Дженнингса представила новую стратегию на 20-ю годовщину Чемпионата по ПДЗ. Эта стратегия оказалась более успешной, чем «око за око». Она основывалась на взаимодействии между программами, чтобы получить максимальный счёт для одной из них. Университет выставил на чемпионат 60 программ, которые распознавали друг друга по ряду действий на первых 5-10 ходах. Узнав другую, одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю. Если программа понимала, что оппонент - не саутгемптонский, она дальше всё время предавала его, чтобы минимизировать результат соперника. В результате эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.
Хотя эта эволюционно стабильная стратегия оказалась более эффективной в соревновании, это было достигнуто за счёт того, что в этом конкретном соревновании команда могла участвовать несколькими агентами. Если игрок может контролировать только одного агента, «око за око» оказывается лучшей. Она также соблюдает правило запрета на коммуникации между игроками. То, что саутгемптонские программы исполняли «ритуальный танец» в первые 10 ходов, чтобы узнать друг друга, только подтверждает, насколько важна коммуникация в сдвиге баланса игры.
Если ПДЗ играется ровно N раз (некая известная константа N), есть ещё один интересный факт. Равновесие Нэша - всегда предавать. Доказываем по индукции: если оба сотрудничают, на последнем ходу выгодно предать, тогда у соперника не будет возможности отомстить. Поэтому оба предадут друг друга на последнем ходу. Раз соперник предаст на последнем ходу в любом случае, любой игрок захочет предать на предпоследнем ходу, и так далее. Чтобы сотрудничество оставалось выгодным, необходимо, чтобы будущее было неопределённым для обоих игроков. Одно из решений - делать число N случайным и подсчитывать результаты по среднему выигрышу за ход.
Дилемма заключённого - фундаментальная для некоторых теорий о взаимодействии людей и доверии. Из предположения модели дилеммы, что транзакция между двумя людьми требует доверия, доверительное поведение в популяциях может быть смоделировано при помощи многоигроковой повторяющейся версии игры. Это годами вдохновляло многих учёных. В 1975 году Грофман и Пул оценивали число работ, посвящённых этой теме, в количестве около 2000.