Повторная игра - Repeated game

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

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

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

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

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

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

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

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

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

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

• Дисконтирование - Если оценка игры игроком i со временем снижается в зависимости от коэффициент дисконтирования ${ displaystyle delta <1}$, затем игрок я'Полезность:

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

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

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

Повторные игры позволяют изучить взаимосвязь между немедленной выгодой и долгосрочными стимулами. Игра с конечным числом повторений - это игра, в которой одна и та же игра с одним выстрелом повторяется многократно в течение ряда дискретных периодов времени или раундов. Каждый период времени индексируется как 0 [1]

В каждый период конечной игры игроки выполняют определенное количество действий. Эти действия приводят к выигрышу для игроков. Сценическую игру можно обозначить {A, ты} где A = A1 * A2 * ... * An - это набор профилей, а ui (a) - это выигрыш игрока i на этапе игры при игре по профилю a. В каждом периоде проводится сценическая игра. Кроме того, мы предполагаем, что в каждом периоде т, игроки наблюдали историю игры или последовательность профилей действий с первого периода до периода т-1. Выигрыш всей игры - это сумма выигрышей от этапной игры в периоды с 1 по Т. Иногда следует предположить, что все игроки дисконтируют будущее, и в этом случае мы включаем коэффициент дисконтирования в спецификацию выплаты.^[2]

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

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

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

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

	Икс	Y	Z
А	5 , 4	1, 1	2 , 5
B	1, 1	3 , 2	1, 1

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

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

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

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

	M	N	О
C	5 , 4	1, 1	0, 5
D	1, 1	3 , 2	1, 1

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

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

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

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

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

Повторяющиеся игры могут содержать неполную информацию. Пионерами повторных игр с неполной информацией стали Ауманн и Maschler.^[5] Хотя легче обрабатывать ситуацию, когда один игрок информирован, а другой нет, и когда информация, полученная каждым игроком, является независимой, можно иметь дело с играми с нулевой суммой с неполной информацией с обеих сторон и сигналами, которые не являются независимыми. .^[6]

Рекомендации

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

внешняя ссылка

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