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

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]

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

[1] Рыцарь, Винс. «Конечно-повторяющиеся игры». Теория игры. Проверено 06.12.17. Проверить значения даты в: | дата доступа = (помощь)

[2] Уэстон, Джоэл (2013). Стратегия: введение в теорию игр. Нью-Йорк, Лондон: W.W Norton and Company. п. 292. ISBN 978-0-393-91838-0.

[:0-3] а ^б Бенуа, Дж. П. и Кришна, В. (1985). «Конечно-повторяющиеся игры». Econometrica: 905–922.CS1 maint: несколько имен: список авторов (связь)

[4] Левин, Джонатан (май 2006 г.). ""Повторные игры I: идеальный мониторинг"" (PDF). www.stanford.edu. Получено 12 декабря, 2017.

[5] Aumann, R.J .; Машлер, М. (1995). Повторные игры с неполной информацией. Кембридж Лондон: MIT Press.

[6] Мертенс, Ж.-Ф. (1987). «Повторные игры». Труды Международного конгресса математиков, Беркли, 1986 г.. Провиденс: Американское математическое общество. С. 1528–1577. ISBN 0-8218-0110-4.

[2]

[3]

[4]

[5]

[6]

v т е Темы в теория игры
Определения	Кооперативная игра Решительность Эскалация обязательств Игра в расширенной форме Победа первого и второго игрока Сложность игры Графическая игра Иерархия убеждений Информационный набор Игра в нормальной форме Предпочтение Последовательная игра Одновременная игра Выбор одновременного действия Решенная игра Лаконичная игра
Равновесие концепции	равновесие по Нэшу Совершенство подигры Устойчивое равновесие по Мертенсу Байесовское равновесие по Нэшу Идеальное байесовское равновесие Дрожащая рука Правильное равновесие Эпсилон-равновесие Коррелированное равновесие Последовательное равновесие Квази-совершенное равновесие Эволюционно устойчивая стратегия Доминирование риска Основной Значение Шепли Парето эффективность Равновесие Гиббса Квантовое равновесие отклика Самоподтверждающееся равновесие Сильное равновесие по Нэшу Марковское идеальное равновесие
Стратегии	Доминирующие стратегии Чистая стратегия Смешанная стратегия Аргумент кражи стратегии Око за око Мрачный спусковой крючок Сговор Обратная индукция Прямая индукция Марковская стратегия Затенение ставки
Классы игр	Симметричная игра Идеальная информация Повторная игра Сигнальная игра Показ игры Дешевый разговор Игра с нулевой суммой Конструкция механизма Проблема торга Стохастическая игра Среднее поле игры п-игровая игра Большая игра Пуассона Нетранзитивная игра Глобальная игра Строго определенная игра Возможная игра
Игры	Идти Шахматы Бесконечные шахматы Шашки Крестики-нолики Дилемма заключенного Игра по обмену подарками Необязательная дилемма заключенного Дилемма путешественника Координационная игра Курица Сороконожка игра Дилемма волонтера Долларовый аукцион Битва полов Охота на оленя Соответствующие пенни Ультиматум игра Камень ножницы Бумага Пиратская игра Диктаторская игра Игра в общественные блага Блотто игра Война на истощение Проблема с баром Эль Фарол Справедливое деление Ярмарка нарезки торта Игра Курно Тупик Дилемма закусочной Угадайте 2/3 среднего Покер куна Игра Нэша в торг Индукционные головоломки Доверительная игра Игра принцесс и монстров Проблема рандеву
Теоремы	Теорема о невозможности Эрроу Теорема согласия Ауманна Народная теорема Теорема о минимаксе Теорема Нэша Теорема очищения Принцип откровения Теорема Цермело
Ключ цифры	Альберт В. Такер Амос Тверски Антуан Огюстен Курно Ариэль Рубинштейн Клод Шеннон Даниэль Канеман Дэвид К. Левин Дэвид М. Крепс Дональд Б. Гиллис Дрю Фуденберг Эрик Маскин Гарольд В. Кун Герберт Саймон Эрве Мулен Жан Тироль Жан-Франсуа Мертенс Дженнифер Тур Чейес Джон Харсаньи Джон Мейнард Смит Джон Нэш Джон фон Нейман Кеннет Эрроу Кеннет Бинмор Леонид Гурвич Ллойд Шепли Мелвин Дрешер Меррилл М. Флуд Ольга Бондарева Оскар Моргенштерн Пол Милгром Пейтон Янг Райнхард Зельтен Роберт Аксельрод Роберт Ауманн Роберт Б. Уилсон Роджер Майерсон Сэмюэл Боулз Сюзанна Скотчмер Томас Шеллинг Уильям Викри
Смотрите также	All-pay аукцион Альфа – бета обрезка Парадокс Бертрана Ограниченная рациональность Комбинаторная теория игр Анализ конфронтации Сотрудничество Эволюционная теория игр Преимущество первого хода в шахматах Игровая механика Глоссарий теории игр Список теоретиков игр Список игр по теории игр Безвыигрышная ситуация Решение шахмат Топологическая игра Трагедия общественного достояния Тирания малых решений

Navigation