визуал · №026
турниры Аксельрода
1980–1981 · как кооперация победила предательство. два компьютерных турнира которые изменили теорию игр.
// контекст · 1979
«Как возникает кооперация между эгоистичными агентами если нет никакой внешней власти которая принуждает к честности?»
1979 год. Роберт Аксельрод — профессор политологии Мичиганского университета — задаёт этот вопрос. Холодная война. Гонка вооружений. Ядерный тупик. Он решает найти ответ через компьютерный эксперимент. Пригласить учёных. Устроить турнир. И посмотреть какая стратегия выживет.
// формат · повторяющаяся дилемма заключённого
| оппонент: C | оппонент: D | |
|---|---|---|
| ты: C | 3 / 3 | 0 / 5 |
| ты: D | 5 / 0 | 1 / 1 |
200 раундов · round-robin · каждый против каждого
C = cooperate · D = defect
NE = оба предают (1/1) · красная рамка
Парето-оптимум = оба кооперируют (3/3) · зелёный фон
бенчмарк взаимной кооперации = 600 очков за 200 раундов
C = cooperate · D = defect
NE = оба предают (1/1) · красная рамка
Парето-оптимум = оба кооперируют (3/3) · зелёный фон
бенчмарк взаимной кооперации = 600 очков за 200 раундов
// турнир 1 · март 1980 · 14 стратегий
Аксельрод разослал приглашения специалистам по теории игр. 14 FORTRAN-программ пришли по почте — из психологии, экономики, политологии, математики, социологии. Его ассистент Джефф Пиннонен написал код турнира. Программы отнесли в вычислительный центр. Ждали overnight пока мэйнфрейм обрабатывал данные.
| # | стратегия | автор | дисциплина |
|---|---|---|---|
| 1 | Tit-for-Tat | Анатолий Рапопорт | математика/психология · Торонто · 504.5 |
| 2 | Tideman and Chieruzzi | Т. Тайдман и П. Кьеруцци | политология · Корнелл |
| 3 | Nydegger | Руди Нидеггер | психология |
| 4 | Grofman | Бернард Грофман | политология |
| 5 | Shubik | Мартин Шубик | экономика · Йель |
| 6 | Stein and Rapoport | Штейн и А. Рапопорт | математика |
| 7 | Grudger (Grim Trigger) | Джеймс Фридман | экономика |
| 8 | Davis | Мортон Дэвис | математика |
| 9 | Graaskamp | Джим Граскамп | — |
| 10 | Downing | Лесли Даунинг | психология |
| 11 | Feld | Скотт Фелд | социология |
| 12 | Joss | Иоганн Йосс | математика |
| 13 | Tullock | Гордон Таллок | экономика/политология |
| 14 | Anonymous | неизвестен | — |
| — | RANDOM | Аксельрод (baseline) | — |
* TfT отправлена единственной 4-строчной программой. все сложные стратегии — ниже в рейтинге.
// результаты · турнир 1
1
Tit-for-Tat
504.5
2
Tideman & Chieruzzi
500.4
3
Nydegger
499.4
4
Grofman
487.5
5
Shubik
482.7
6
Stein & Rapoport
479.7
—
Always Defect (худший)
401.2
отрыв TfT от второго места: 4.1 очка
бенчмарк взаимной кооперации: 600 очков
бенчмарк взаимной дефекции: 200 очков
бенчмарк взаимной кооперации: 600 очков
бенчмарк взаимной дефекции: 200 очков
// четыре свойства победы
1
добрая
никогда не предаёт первой. не провоцирует эскалацию без причины.
2
наказывающая
немедленно отвечает на предательство. нельзя эксплуатировать безнаказанно.
3
прощающая
после наказания возвращается к кооперации. не застревает в бесконечной войне.
4
прозрачная
оппонент легко понимает логику. можно выстроить взаимную кооперацию.
«самая короткая программа турнира оказалась самой успешной. сложность не помогла никому.» — Роберт Аксельрод · анализ турнира · 1980
// турнир 2 · 1981 · 62 стратегии
// участников
62
+48 от первого
// стран
6
США · Канада · Британия · Норвегия · Швейцария · Н. Зеландия
// победитель
TfT
снова Рапопорт
// публикация
Science
1981 с У. Гамильтоном
Аксельрод разместил объявления в журналах для любителей компьютеров — Personal Computing и других. Он открыто сообщил что TfT победил в первом турнире и объяснил почему. Поставил цель: побить TfT. Среди 62 участников — профессора, студенты и 10-летний вундеркинд. Уильям Гамильтон — эволюционный биолог, основатель теории инклюзивной приспособленности — присоединился к анализу. Результат: TfT победил снова. Вместе они опубликовали работу в Science. Это сделало результаты известными всему миру.
Второй турнир отличался форматом — вместо фиксированных 200 раундов каждый матч заканчивался с вероятностью 0.00346 в каждом раунде. Это делало горизонт неизвестным — ближе к реальным взаимодействиям.
| код | автор | примечание |
|---|---|---|
| K31R | Gail Grisell | GoByMajority стратегия |
| K32R | Charles Kluepfel | — |
| K33R | Harold Rabbie | — |
| K34R | James W Friedman | Grudger — участник обоих турниров |
| K35R | Abraham Getzler | — |
| K36R | Roger Hotz | — |
| K37R | George Lefevre | — |
| K38R | Nelson Weiderman | — |
| K39R | Tom Almy | — |
| K40R | Robert Adams | — |
| K41R | Herb Weiner | — |
| K42R | Otto Borufsen | — |
| K43R | R D Anderson | — |
| K44R | William Adams | — |
| K67R | Craig Feathers | Tranquilizer стратегия |
| K68R | Danny Champion | Champion стратегия |
| K69R | Graham Eatherley | Eatherley стратегия |
| — | Anatol Rapoport | Tit-for-Tat · победитель · единственный кто переотправил ту же стратегию |
показаны 18 из 62 участников · остальные ~44 — читатели журналов для компьютерных энтузиастов (Personal Computing и др.) включая 10-летнего участника чьё имя неизвестно
// эволюция · репликаторная динамика
После турниров Аксельрод запустил симуляцию. Стратегии «размножались» пропорционально приспособленности. Через 1000 поколений TfT лидировала с темпом роста 0.05%/поколение. Always Defect вымирала — когда кооператоры исчезали, ей не с кем было взаимодействовать кроме себя.
// поколений
40
// старт TfT %
20%
// три условия кооперации
кооперация возможна без центральной власти. три необходимых условия:
- игра повторяется — есть завтра
- игроки ценят будущее — «тень будущего» достаточно длинна
- игроки узнают друг друга — репутация работает
предательство оптимально один раз. кооперация оптимальна всегда — если есть завтра.
¹ Axelrod R. · «Effective Choice in the Prisoner's Dilemma» · Journal of Conflict Resolution · 24(1) · 1980
² Axelrod R. · «More Effective Choice in the Prisoner's Dilemma» · Journal of Conflict Resolution · 24(3) · 1980
³ Axelrod R., Hamilton W.D. · «The Evolution of Cooperation» · Science · 211 · 1981
⁴ Имена участников: Axelrod Python Library документация · axelrod.readthedocs.io
² Axelrod R. · «More Effective Choice in the Prisoner's Dilemma» · Journal of Conflict Resolution · 24(3) · 1980
³ Axelrod R., Hamilton W.D. · «The Evolution of Cooperation» · Science · 211 · 1981
⁴ Имена участников: Axelrod Python Library документация · axelrod.readthedocs.io