Эволюционная теория игр

1973 год: Джон Мэйнард Смит берёт концепции из экономики и применяет их к биологии - без предположения рациональности. Результат: популяции «решают» задачи оптимизации, которые не под силу отдельным особям. Ястребы и голуби сосуществуют не случайно - это математически устойчивое равновесие, где мутант-отклонение всегда проигрывает.

• **Биология поведения:** агрессия, территориальность, брачные ритуалы, альтруизм - всё предсказывается через ESS без предположения «осознанного выбора» у животных
• **Multi-agent RL:** обучение нескольких RL-агентов в одной среде - нестационарная задача. Понимание репликаторной динамики помогает дизайнить алгоритмы, которые сходятся
• **Финансовые рынки:** популяция торговых стратегий (momentum, value, arbitrage) подчиняется эволюционной динамике - прибыльные копируются, убыточные уходят

Предварительные знания

• Auction Theory

Эволюционно стабильная стратегия (ESS)

Рассмотрим популяцию птиц. Большинство - «голуби» (мирные). Появляется мутант-«ястреб» (агрессивный). Может ли он захватить популяцию? Это зависит от того, выгодно ли быть ястребом в мире голубей - и голубем в мире ястребов. ESS (Evolutionarily Stable Strategy) - стратегия, которую мутанты не могут вытеснить: если большинство играет ESS, редкий мутант проигрывает.

Стратегия I является ESS, если для каждой мутантной стратегии J ≠ I выполняется одно из: 1. u(I, I) > u(J, I) - I лучше J против населения из I 2. u(I, I) = u(J, I) AND u(I, J) > u(J, J) - ничья против I, но I лучше против J ESS ⊆ NE: каждая ESS - NE, но не каждое NE - ESS.

В игре Ястреб-Голубь ни чистая Hawk, ни чистая Dove не является ESS. ESS - смешанная стратегия: доля ястребов p* = v/c. При v=4, c=6: p* = 2/3. Это **стабильный полиморфизм** - в популяции сосуществуют ястребы и голуби. Эволюция «находит» то же равновесие, что и рациональный расчёт!

Репликаторная динамика

ESS говорит, куда система сойдётся в конечном итоге. Репликаторная динамика описывает, как она туда движется. Идея проста: стратегия размножается быстрее, если её приспособленность выше средней. Это дифференциальное уравнение для доли каждой стратегии в популяции - эволюционный аналог gradient ascent.

Для стратегий {1,...,k} с долями x = (x₁,...,xₖ): dxᵢ/dt = xᵢ · [f(i, x) - φ(x)] где f(i, x) = Σⱼ xⱼ · u(i, j) - приспособленность стратегии i, φ(x) = Σᵢ xᵢ · f(i, x) - средняя приспособленность. Свойство: равновесия репликатора = NE игры. ESS = асимптотически устойчивые точки.

Репликаторная динамика - непрерывная аппроксимация эволюционного отбора. Она имеет прямую связь с алгоритмами машинного обучения: Multiplicative Weights Update (MWU) и некоторые алгоритмы обучения с подкреплением - дискретные версии репликаторной динамики. Онлайн-обучение «открыло» теорию игр с обратной стороны.

Игра Ястреб-Голубь и полиморфизм

Игра Ястреб-Голубь - самый важный пример эволюционной теории игр. Ястреб атакует всегда и рискует получить травму. Голубь отступает перед ястребом, но мирно делит ресурс с другим голубем. Если ресурс ценнее риска - только ястребы, дорогая цена конфликта - только голуби. Но обычно оба сосуществуют в равновесии.

Матрица (для одного игрока): Ресурс v, стоимость травмы c H D H (v-c)/2 v D 0 v/2 Если v < c (конфликт дорог): единственное ESS - смешанная стратегия p* = v/c ястребов. Если v > c (конфликт дёшев): ESS = все ястребы (AllH). При p* в популяции выгода H = выгода D - маргинальный отбор равен нулю.

Полиморфизм (сосуществование стратегий) - одно из ключевых предсказаний эволюционной теории игр. В биологии: разные стратегии спаривания у самцов рыб (агрессивные альфа и «прячущиеся» бета). В поведенческой экономике: разные стратегии доверия и недоверия в экономических экспериментах. Одна стратегия редко «победит» - часто устойчив полиморфизм.

Динамика популяций и мультиагентные системы

Эволюционная теория игр описывает не только биологические популяции. Любая система, где стратегии «размножаются» по успеху - рынок фирм, пул торговых алгоритмов, А/Б тесты в продукте, обучение с подкреплением - подчиняется той же динамике. Это делает ESS и репликаторные уравнения инструментами для анализа многоагентных систем.

Multiplicative Weights Update (MWU): wᵢ(t+1) = wᵢ(t) · exp(η · rᵢ(t)) Это дискретная версия репликаторной динамики! При η → 0, непрерывное время → репликаторное уравнение. Q-learning, Cross learning, и многие online алгоритмы - варианты этой динамики. В мультиагентных системах их взаимодействие анализируется через эволюционную теорию игр.

Ключевой вопрос для многоагентных систем: сходится ли популяция к ESS, циклически осциллирует или хаотична? В играх с нулевой суммой (RPS: камень-ножницы-бумага) репликаторная динамика порождает постоянные циклы. В играх с координацией - быстрая сходимость к ESS. Это важно для дизайна RL алгоритмов в мультиагентных средах.

Ключевые идеи

• **ESS:** стратегия устойчива против мутантов - эволюционный аналог NE, но более строгий
• **Репликаторная динамика:** dx/dt = x·(f - φ) - успешные стратегии размножаются быстрее средней
• **Игра Ястреб-Голубь:** ESS - полиморфизм p* = v/c ястребов; эволюция не ведёт к социальному оптимуму
• **MWU = репликаторная динамика:** онлайн-алгоритмы ML - дискретная версия эволюционной динамики

Связанные темы

Эволюционная теория игр соединяет биологию, ML и экономику:

• Дилемма заключённого — Эволюция кооперации через повторяемые игры и репликаторную динамику
• Algorithmic Game Theory — Price of Anarchy в системах с эволюционирующими агентами
• Теория игр в ML — GAN training и multi-agent RL через линзу эволюционной теории

Вопросы для размышления

• Если торговые алгоритмы на рынке следуют репликаторной динамике (прибыльные копируются), к чему должен сойтись рынок по теории? Почему на практике этого не происходит?
• В командах разработки тоже происходит «эволюция практик»: успешные инженеры копируют подходы успешных коллег. Это репликаторная динамика? Какое ESS здесь?
• Multi-agent RL часто нестабилен и не сходится к NE. Какие архитектурные решения (централизованное обучение, коммуникация, shared reward) помогают? Как ESS связано с этим?

Связанные уроки

• prob-17