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

редактировать

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

СОДЕРЖАНИЕ

  • 1 Конечно и бесконечно повторяющиеся игры
  • 2 Бесконечно повторяющиеся игры
  • 3 Конечно повторяющиеся игры
  • 4 Примеры сотрудничества в конечно повторяющихся играх
  • 5 Решение повторяющихся игр
  • 6 Неполная информация
  • 7 ссылки
  • 8 Внешние ссылки

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

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

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

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

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

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

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

  • Предел средств - если игра приводит к пути результатов и у игрока i есть функция полезности базовой игры, полезность игрока i равна: Икс т {\ displaystyle x_ {t}} ты я {\ displaystyle u_ {i}}
U я знак равно Lim Т инф 1 Т т знак равно 0 Т ты я ( Икс т ) {\ displaystyle U_ {i} = \ lim _ {T \ to \ infty} \ inf {\ frac {1} {T}} \ sum _ {t = 0} ^ {T} u_ {i} (x_ {t })}
U я знак равно т 0 δ т ты я ( Икс т ) {\ displaystyle U_ {i} = \ sum _ {t \ geq 0} \ delta ^ {t} u_ {i} (x_ {t})}

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

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

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

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

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

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

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

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

Икс 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 O
C 5, 4 1, 1 0, 5
D 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). Первое блюдо по повторяющимся играм с нулевой суммой. Берлин: Springer. ISBN   3-540-43028-8.

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

Последняя правка сделана 2023-04-05 11:22:32
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте