Лекция 6 (Лекции (4))

Subgame perfect equilibriumНабор поведенческих стратегий называется совершенным подыгровымравновесием (СПРН), если для любой подыгры (под-игры?) данный наборстратегий является равновесием по Нэшу..Теорема.В. любой позиционной игре с полной информацией существует СПРН.И.В.Кацев (СПб ЭМИ)Динамические игры20121 / 10Динамические игрыДинамическая игра - это последовательность одинаковых игр.Важные моменты:И.В.Кацев (СПб ЭМИ)Динамические игры20122 / 10Динамические игрыДинамическая игра - это последовательность одинаковых игр.Важные моменты:ДлительностьИ.В.Кацев (СПб ЭМИ)Динамические игры20122 / 10Динамические игрыДинамическая игра - это последовательность одинаковых игр.Важные моменты:ДлительностьНаблюденияИ.В.Кацев (СПб ЭМИ)Динамические игры20122 / 10Динамические игрыДинамическая игра - это последовательность одинаковых игр.Важные моменты:ДлительностьНаблюденияСтратегииВыигрышиИ.В.Кацев (СПб ЭМИ)Динамические игры20122 / 10Динамические игрыДинамическая игра - это последовательность одинаковых игр.Важные моменты:ДлительностьНаблюденияСтратегииВыигрышиИ.В.Кацев (СПб ЭМИ)Динамические игры20122 / 10Бесконечное количество повторенийНесколько вариантов определить выигрыши:И.В.Кацев (СПб ЭМИ)Динамические игры20123 / 10Бесконечное количество повторенийНесколько вариантов определить выигрыши:(Предел среднего выигрыша: limT→∞И.В.Кацев (СПб ЭМИ)T∑)ui (t)/Tt=1Динамические игры20123 / 10Бесконечное количество повторенийНесколько вариантов определить выигрыши:(Предел среднего выигрыша: limT→∞T∑)ui (t)/Tt=1Нижний предел выигрышаИ.В.Кацев (СПб ЭМИ)Динамические игры20123 / 10Бесконечное количество повторенийНесколько вариантов определить выигрыши:(Предел среднего выигрыша: limT→∞T∑)ui (t)/Tt=1Нижний предел выигрышаИспользуем дисконтирующий множитель δ(1 − δ)∞∑∈ (0, 1):δ t−1 ui (t).t=1И.В.Кацев (СПб ЭМИ)Динамические игры20123 / 10Бесконечное количество повторенийНесколько вариантов определить выигрыши:(Предел среднего выигрыша: limT→∞T∑)ui (t)/Tt=1Нижний предел выигрышаИспользуем дисконтирующий множитель δ(1 − δ)∞∑∈ (0, 1):δ t−1 ui (t).t=1При δПри δ= 0 получаем однократную игру.= 1 получаем сумму выигрышей.И.В.Кацев (СПб ЭМИ)Динамические игры20123 / 10Пример: дилемма заключенного(И.В.Кацев (СПб ЭМИ)−1, −1 −10, 00, −10 −9, −9Динамические игры).20124 / 10”Очень много” vs ”бесконечно”Почему результаты для очень большого (но конечного!) и для бесконечного числаповторений так отличаются?И.В.Кацев (СПб ЭМИ)Динамические игры20125 / 10”Очень много” vs ”бесконечно”Почему результаты для очень большого (но конечного!) и для бесконечного числаповторений так отличаются?Слишком много предположений о рациональности и точное знание моментаконца игры.И.В.Кацев (СПб ЭМИ)Динамические игры20125 / 10Folk theoremОбозначения: пусть G - игра, P(G) - выпуклая оболочка множества исходов G,G∞ (δ) - суперигра с дисконтирующим множителем δ .

Пусть αi гарантированный выигрыш i-того игрока в игре G. Тогда верна теоремаИ.В.Кацев (СПб ЭМИ)Динамические игры20126 / 10Folk theoremОбозначения: пусть G - игра, P(G) - выпуклая оболочка множества исходов G,G∞ (δ) - суперигра с дисконтирующим множителем δ . Пусть αi гарантированный выигрыш i-того игрока в игре G.

Тогда верна теорема.Теорема (Folk theorem for Nash equilibrium).Пусть вектор x = (x1 , x2 ) ∈ P(G) таков, что xi ≥ αi для i = 1, 2. Тогдасуществует такое 0 < δ < 1, что в игре G∞ (δ) есть равновесие по Нэшу с.выигрышами x.И.В.Кацев (СПб ЭМИ)Динамические игры20126 / 10Эволюционная теория игрСовершенное равновесиеИ.В.Кацев (СПб ЭМИ)Динамические игры20127 / 10Эволюционная теория игрСовершенное равновесиеЭволюционная устойчивостьИ.В.Кацев (СПб ЭМИ)Динамические игры20127 / 10Эволюционная теория игрСовершенное равновесиеЭволюционная устойчивостьСтохастическая устойчивостьИ.В.Кацев (СПб ЭМИ)Динамические игры20127 / 10Симметричные игрыИгра называется симметричной, если матрица игры симметрична.И.В.Кацев (СПб ЭМИ)Динамические игры20128 / 10Симметричные игрыИгра называется симметричной, если матрица игры симметрична..Теорема.В.

симметричной игре существует симметричное равновесие по Нэшу.И.В.Кацев (СПб ЭМИ)Динамические игры20128 / 10Эволюционно устойчивые стратегии.Определение.Стратегия x называется эволюционно устойчивой, если для любойстратегии y ̸= x существует такое εy ∈ (0, 1), что для любого ε ∈xA(εy + (1 − ε)x).И.В.Кацев (СПб ЭМИ)(0, ε)> yA(εy + (1 − ε)x)Динамические игры20129 / 10Эволюционно устойчивые стратегии.Определение.Стратегия x называется эволюционно устойчивой, если для любойстратегии y ̸= x существует такое εy ∈ (0, 1), что для любого ε ∈xA(εy + (1 − ε)x).(0, ε)> yA(εy + (1 − ε)x).Теорема.1. Множество эволюционно устойчивых стратегий конечно.2.

Если ЭС стратегия является вполне смешанной, то она единственна3.. ЭС стратегий может не быть.И.В.Кацев (СПб ЭМИ)Динамические игры20129 / 10Пример: Hawk-Dove game(И.В.Кацев (СПб ЭМИ)0, 0 3, 11, 3 2, 2)Динамические игры.201210 / 10.