Лекция 11. Эволюционная устойчивость: сотрудничество, мутации и равновесие

Важность для курса: средняя — лекция даёт точный способ думать о мете в мультиплеере, но в основном занята определениями.

Суть простыми словами

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

Что было на лекции

Биологи сравнивают стратегию с геном, а выигрыш с числом потомков. Поведение животных врождённое, они не рассуждают. В экономике эволюция служит метафорой: рынок отсеивает фирмы, и банкротство похоже на вымирание.
Простая модель: соперничество внутри одного вида, симметричная игра двоих, большая популяция, случайные пары, размножение без смешения генов. Удачные стратегии растут, неудачные исчезают.
Идея Мейнарда Смита: вся популяция играет S, и появляется малая группа мутантов со стратегией S'. Если любая такая группа вымирает, S эволюционно устойчива.
Опыт в аудитории. Все студенты стали муравьями, которые всегда сотрудничают. Игра «дилемма заключённого»: два добряка по 2; добряк против хитреца 0 и 3; два хитреца по 1. Ассистенты стали мутантами-хитрецами. Рахул встретил Ника: Ник получил 0, Рахул 3. Мутанты размножаются, так что сотрудничество неустойчиво.
Обратный опыт: все хитрят, а единственный добрый мутант Мирто почти всегда получает 0 и вымирает. Хитрость устойчива.
Вывод: природа может прийти к плохому для всех исходу. Пример Полака: павианы, у которых детёнышей чаще всего убивают сородичи.
Почему же львы вместе охотятся, а муравьи защищают гнездо? Студенты предлагали соревнование групп и наказание обманщиков. Полак ждал другого: в модели размножение бесполое, а в природе родственники делят гены, и выигрыш считается для гена, а не для особи.
Строго доминируемая стратегия не бывает устойчивой: её вытеснит та, что доминирует.
Игра 3×3. Популяцию C захватывает B, как и подсказал студент Грег, но и B неустойчива. Пара (C, C) к тому же не равновесие Нэша. Вывод: устойчивая стратегия всегда образует равновесие Нэша.
Обратное неверно. В игре, где только пара (A, A) приносит 1, пара (B, B) тоже равновесие. Но мутанты A выигрывают, когда встречают друг друга. Студент Стивен заметил: B здесь лишь нестрого лучший ответ. Строгое равновесие всегда устойчиво.
Два определения устойчивости, биологическое и экономическое, равносильны. Полак сравнил это совпадение с открытием XVII века, что планеты и часы подчиняются одним законам.

Главные понятия

Эволюционно устойчивая стратегия (evolutionarily stable strategy, ESS) — поведение, которое нельзя вытеснить: любая малая группа мутантов набирает меньше и вымирает.
Мутация (mutation) — небольшая группа с новой стратегией. Она почти всегда встречает «старожилов» и лишь изредка своих.
Строгое равновесие Нэша (strict Nash equilibrium) — любое отклонение даёт строго меньше. Такая стратегия всегда устойчива.
Нестрогий лучший ответ (weak best response) — другой ход даёт столько же. Тогда решает, кто лучше играет против мутантов.

Зерно для создателя игр

Мета как эволюция. Игроки копируют то, что побеждает. Проверка будущей меты: если 5% игроков возьмут новую тактику, наберут ли они больше остальных? Если да, тактика расползётся.
Халява побеждает, если её не остановить. В командной игре тот, кто не вкладывается, но делит награду, обыгрывает добряка в каждой встрече. Мета сама к доброму поведению не придёт. Меняй выигрыши: награждай за вклад, делай общую победу важнее личной добычи.
Доминируемое умрёт. Если вариант хуже другого во всех ситуациях, его перестанут выбирать. Удали его или дай ему свою нишу.
Ничьи делают мету шаткой. Если новая тактика против меты играет вничью, всё решают её встречи с самой собой. Строгие преимущества дают устойчивую мету, ничьи дают дрейф.
Боты как пробирка. Правило «удачное размножается» легко запрограммировать. Тысячи матчей ботов заранее покажут, какая стратегия захватит сервер.

Мини-игра для урока

«Муравейник», повтор опыта Полака. Класс около 20 человек, 10 минут.

Раздай карточки: 18 «Делюсь» и 2 «Хитрю». Это «гены», менять их по желанию нельзя.
Каждый раунд случайные пары. Очки: два добряка по 2; добряк против хитреца 0 и 3; два хитреца по 1.
После раунда учитель считает средний счёт добряков и хитрецов. Четверо из группы с меньшим средним (или все, если их меньше) берут карточки другой группы.
Обычно за 4–5 раундов хитрецы захватывают класс. Обратный опыт: все хитрят, один делится. Он исчезает за раунд.
Ход дизайнера: «вместе делиться» теперь даёт по 4. Повтори первый опыт.

Что заметить: без правки хитрость побеждает, хотя всем выгоднее делиться. После правки добряки набирают в среднем около 3,6 против 3, и хитрецы вымирают. Поведение задаёт таблица очков.

Ошибки и заблуждения

«Что сложилось само, то и хорошо». Эволюция и мета могут закрепить плохой для всех исход.
«Любое равновесие Нэша устойчиво». Нет: равновесие с ничьей могут размыть мутанты.
«Игроки будут работать на команду, потому что так правильно». Если халява выгоднее, мета её найдёт.

Для продвинутых

Определение 1 (биология). Ŝ устойчива в чистых стратегиях, если для любой S' ≠ Ŝ найдётся ε̄ > 0, что при всех ε < ε̄: (1−ε)U(Ŝ,Ŝ) + εU(Ŝ,S') > (1−ε)U(S',Ŝ) + εU(S',S').
Определение 2 (экономика): (а) U(Ŝ,Ŝ) ≥ U(S',Ŝ) для всех S'; (б) если тут равенство, то U(Ŝ,S') > U(S',S'). Следствия: ESS даёт симметричное равновесие Нэша; строгое равновесие даёт ESS; строго доминируемая стратегия не ESS. В неформальном доказательстве в конце лекции есть описка: вместо U(Ŝ,S') должно стоять U(S',Ŝ).
Источники: J. Maynard Smith, G. R. Price, «The Logic of Animal Conflict» (Nature, 1973; в лекции назван 1972 год); J. Maynard Smith, «Evolution and the Theory of Games» (1982). Родственный отбор: W. D. Hamilton (1964). Геймдизайнеру полезна книга R. Axelrod «The Evolution of Cooperation» (1984) о турнирах стратегий.