Повторная игра

В теории игр повторяющаяся игра (или итерированная игра ) — это игра развернутой формы , состоящая из ряда повторений некоторой базовой игры (называемой этапной игрой ). Сценическая игра обычно представляет собой одну из хорошо изученных игр для двоих . В повторяющихся играх идея заключается в том, что игроку придется учитывать влияние своих текущих действий на будущие действия других игроков; это влияние иногда называют их репутацией. Одноэтапная игра или однократная игра — это названия неповторяющихся игр.

В качестве реального примера повторяющейся игры рассмотрим две заправочные станции , расположенные рядом друг с другом. Они конкурируют, публично публикуя цены, и имеют одинаковые и постоянные предельные издержки c ( оптовая цена на бензин). Предположим, что когда они оба взимают p = 10, их совместная прибыль максимальна, что приводит к высокой прибыли для всех. Несмотря на то, что для них это лучший результат, у них есть мотивация отклониться. Умеренно снизив цену, любой из них может переманить всех клиентов своих конкурентов, почти удвоив их доходы. P = c, где их прибыль равна нулю, является единственной ценой без этого отклонения прибыли. Другими словами, в игре ценовой конкуренции единственное равновесие Нэша является неэффективным (для заправочных станций), при котором обе взимают плату p = c. Это скорее правило, чем исключение: в поэтапной игре равновесие Нэша — единственный результат, который агент может последовательно получить в ходе взаимодействия, и обычно для него оно неэффективно. Это происходит потому, что агенты озабочены только своими личными интересами и не заботятся о выгодах или издержках, которые их действия приносят конкурентам. С другой стороны, заправочные станции получают прибыль, даже если рядом есть еще одна заправка. Одна из наиболее важных причин заключается в том, что их взаимодействие не является разовым. Это условие изображается повторяющимися играми, в которых две заправочные станции конкурируют за ценообразование (этапные игры) в неопределенном временном диапазоне t = 0, 1, 2,....

Конечно и бесконечно повторяющиеся игры

Повторяющиеся игры можно разделить на два класса: конечные и бесконечные, в зависимости от того, как долго ведется игра.

• Конечные игры — это игры, в которых оба игрока знают, что игра продолжается определенное (и конечное) количество раундов и что игра наверняка заканчивается после того, как будет сыграно это количество раундов. В общем, конечные игры можно решить методом обратной индукции .
• Бесконечные игры — это игры, в которых игра ведется бесконечное количество раз. Игра с бесконечным числом раундов также эквивалентна (с точки зрения игровых стратегий) игре, в которой игроки не знают, сколько раундов ведется в игре. Бесконечные игры (или игры, которые повторяются неизвестное количество раз) не могут быть решены с помощью обратной индукции, поскольку не существует «последнего раунда», с которого можно было бы начать обратную индукцию.

Даже если игра, в которую играют в каждом раунде, одинакова, повторение этой игры конечное или бесконечное число раз может, как правило, привести к совершенно разным результатам (равновесиям), а также к совершенно разным оптимальным стратегиям.

Бесконечно повторяющиеся игры

Наиболее широко изучаемыми повторяющимися играми являются игры, повторяющиеся бесконечное число раз. В повторяющихся играх с дилеммой заключенного обнаружено, что предпочтительной стратегией является не использование стратегии Нэша в сценической игре, а сотрудничество и использование социально оптимальной стратегии. Существенной частью стратегии в бесконечно повторяющейся игре является наказание игроков, отклоняющихся от этой совместной стратегии. Наказанием может быть стратегия, которая приводит к уменьшению выигрыша обоих игроков до конца игры (так называемая триггерная стратегия ). Обычно игрок может предпочесть действовать эгоистично, чтобы увеличить собственное вознаграждение, вместо того, чтобы использовать социально оптимальную стратегию. Однако если известно, что другой игрок следует триггерной стратегии, то он ожидает получить уменьшенные выплаты в будущем, если они отклонятся на этом этапе. Эффективная триггерная стратегия гарантирует, что сотрудничество принесет игроку больше пользы, чем эгоистичные действия сейчас и наказание другого игрока в будущем.

В теоремах, касающихся того, как достичь и поддерживать социально оптимальное равновесие в повторяющихся играх, содержится множество результатов. Эти результаты получили общее название «Народные теоремы» . Важной особенностью повторяющейся игры является способ моделирования предпочтений игрока. Существует множество различных способов моделирования отношений предпочтений в бесконечно повторяющейся игре, но два ключевых из них:

• Предел средств . Если игра приводит к определенному результату. $x_{t}$ и у игрока i есть функция полезности базовой игры $u_{i}$, player i : полезность

$U_{i}=\lim _{T\to \infty }\inf {\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t})$

• Дисконтирование — если оценка игры игроком i уменьшается со временем в зависимости от коэффициента дисконтирования. $\delta <1$, тогда игрока i будет следующей: полезность

$U_{i}=\sum _{t\geq 0}\delta ^{t}u_{i}(x_{t})$

Для достаточно терпеливых игроков (например, с достаточно высокими значениями $\delta$), можно доказать, что каждая стратегия, выигрыш которой превышает минимальный выигрыш, может быть равновесием Нэша - очень большим набором стратегий.

Конечно повторяющиеся игры

Повторяющиеся игры позволяют изучить взаимодействие между немедленной выгодой и долгосрочными стимулами. Конечно повторяющаяся игра — это игра, в которой одна и та же игра с одним этапом повторяется неоднократно в течение нескольких дискретных периодов времени или раундов. Каждый период времени индексируется 0 < t ≤ T, где T — общее количество периодов. Окончательный выигрыш игрока представляет собой сумму его выигрышей в каждом раунде.

Для повторяющихся игр с фиксированным и известным числом периодов времени, если сценическая игра имеет уникальное равновесие Нэша , то повторяющаяся игра имеет уникальный профиль стратегии идеального равновесия Нэша подыгры , заключающийся в достижении равновесия сценической игры в каждом раунде. Это можно вывести с помощью обратной индукции . Уникальное равновесие Нэша на этапе игры должно быть сыграно в последнем раунде независимо от того, что происходило в предыдущих раундах. Зная это, у игроков нет стимула отклоняться от уникального равновесия Нэша на этапе игры в предпоследнем раунде, и поэтому эта логика применяется обратно к первому раунду игры. Это «распутывание» игры с конечной точки можно наблюдать в парадоксе сетевого магазина .

Если в этапной игре имеется более одного равновесия Нэша, в повторяющейся игре может быть несколько идеальных равновесий Нэша подыгры . Хотя равновесие Нэша должно быть достигнуто в последнем раунде, наличие множественных равновесий открывает возможность стратегий вознаграждения и наказания, которые можно использовать для поддержки отклонения от равновесия Нэша на этапе игры в более ранних раундах.

С другой стороны, конечно повторяющиеся игры с неизвестным или неопределенным количеством периодов времени рассматриваются как бесконечно повторяющиеся игры. К этим играм невозможно применить обратную индукцию.

Примеры сотрудничества в конечно повторяющихся играх.

	Х	И	С
А	5 , 4	1, 1	2 , 5
Б	1, 1	3 , 2	1, 1

Пример 1: Двухэтапная повторяющаяся игра с множественными равновесиями Нэша

В примере 1 показана двухэтапная повторяющаяся игра с несколькими состояниями равновесия Нэша в чистой стратегии . Поскольку эти равновесия заметно различаются с точки зрения выигрышей для Игрока 2, Игрок 1 может предложить стратегию на нескольких этапах игры, которая включает в себя возможность наказания или вознаграждения для Игрока 2. Например, Игрок 1 может предложить сыграть (A, Х) в первом туре. Если Игрок 2 выполнит условия в первом раунде, Игрок 1 вознаградит его, сыграв в равновесии (A, Z) во втором раунде, что даст общий выигрыш за два раунда (7, 9).

Если Игрок 2 отклоняется от (A, Z) в первом раунде вместо того, чтобы играть в согласованные (A, X), Игрок 1 может пригрозить наказать его, играя в равновесие (B, Y) во втором раунде. Последняя ситуация приносит выигрыш (5, 7), в результате чего оба игрока оказываются в худшем положении.

Таким образом, угроза наказания в будущем раунде стимулирует совместную неравновесную стратегию в первом раунде. Поскольку последний раунд любой конечно повторяющейся игры по самой своей природе устраняет угрозу будущего наказания, оптимальной стратегией в последнем раунде всегда будет одно из игровых равновесий. Именно разница выигрышей между состояниями равновесия в игре, представленной в примере 1, делает стратегию наказания/поощрения жизнеспособной (подробнее о влиянии наказания и вознаграждения на стратегию игры см. « Игра общественного блага с наказанием и вознаграждением »).

	М	Н	ТО
С	5 , 4	1, 1	0, 5
Д	1, 1	3 , 2	1, 1

Пример 2: Двухэтапная повторяющаяся игра с уникальным равновесием Нэша

В примере 2 показана двухэтапная повторяющаяся игра с уникальным равновесием Нэша. Поскольку здесь существует только одно равновесие, ни один из игроков не может угрожать наказанием или обещать награду во втором раунде игры. Таким образом, единственная стратегия, которая может поддерживаться как идеальное равновесие Нэша в подигре, - это использование уникальной стратегии равновесия Нэша (D, N) в каждом раунде. В данном случае это означает прохождение (D, N) каждого этапа на двух этапах (n=2), но это будет справедливо для любого конечного числа этапов n . Интерпретируем: этот результат означает, что само наличие известного, конечного временного горизонта саботирует сотрудничество в каждом отдельном раунде игры. Кооперация в итерированных играх возможна только тогда, когда количество раундов бесконечно или неизвестно.

Решение повторяющихся игр

В общем, повторяющиеся игры легко решаются с использованием стратегий, предусмотренных народными теоремами . Сложные повторяющиеся игры можно решать с помощью различных методов, большинство из которых в значительной степени опираются на линейную алгебру и концепции, выраженные в вымышленной игре . Можно сделать вывод, что вы можете определить характеристики равновесных выигрышей в бесконечно повторяющихся играх. Благодаря чередованию двух выигрышей, скажем, a и f, профиль среднего выигрыша может представлять собой средневзвешенное значение между a и f.

Неполная информация

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

Ссылки

• Фуденберг, Дрю; Тироль, Жан (1991). Теория игр . Кембридж: MIT Press. ISBN  0-262-06141-4 .
• Майлат Г. и Самуэльсон Л. (2006). Повторяющиеся игры и репутация: долгосрочные отношения . Нью-Йорк: Издательство Оксфордского университета. ISBN  0-19-530079-3 .
• Осборн, Мартин Дж.; Рубинштейн, Ариэль (1994). Курс теории игр . Кембридж: MIT Press. ISBN  0-262-15041-7 .
• Сорин, Сильвен (2002). Первый курс повторяющихся игр с нулевой суммой . Берлин: Шпрингер. ISBN  3-540-43028-8 .

Внешние ссылки

• Теоретико-игровое решение покера с использованием фиктивной игры
• Заметки по теории игр о повторяющихся играх
• о повторяющихся играх и парадоксе сетевых магазинов