Народная теорема (теория игр) - Folk theorem (game theory)

В теория игры, народные теоремы представляют собой класс теорем, описывающих обилие равновесие по Нэшу профили выплат в повторяющиеся игры (Фридман 1971 ).^[1] Первоначальная Народная теорема касалась выплат всех равновесий Нэша в бесконечно повторяющейся игре. Этот результат был назван Народной теоремой, потому что он был широко известен среди теоретиков игр в 1950-х годах, хотя его никто не опубликовал. Теорема Фридмана (1971) касается выплат некоторых совершенное по подиграм равновесие по Нэшу (SPE) бесконечно повторяющейся игры и, таким образом, усиливает исходную народную теорему за счет использования более сильной концепции равновесия: идеальных по подиграм равновесий по Нэшу, а не равновесий по Нэшу.^[2]

Народная теорема предполагает, что если игроки достаточно терпеливы и дальновидны (т.е. если фактор дисконтирования ${ displaystyle delta to 1}$ ), то повторное взаимодействие может привести практически к любому среднему выигрышу в равновесии SPE.^[3] «Практически любой» здесь технически определяется как «выполнимый» и «индивидуально рациональный».

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

Настройка и определения

Начнем с основная игра, также известный как сценическая игра, который является н-игра игрока. В этой игре у каждого игрока есть конечное число действий на выбор, и они делают свой выбор одновременно и не зная о выборе другого игрока. Коллективный выбор игроков приводит к профиль выплат, т.е. до выплаты каждому из игроков. Отображение коллективных выборов в профили выплат известно игрокам, и каждый игрок стремится максимизировать свой выигрыш. Если коллективный выбор обозначить Икс, выигрыш этого игрока я получает, также известный как игрок яс полезность, будем обозначать ${ Displaystyle и_ {я} (х)}$ .

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

Любой равновесие по Нэшу Профиль выплат повторной игры должен удовлетворять двум свойствам:

1. Индивидуальная рациональность: выигрыш должен слабо доминировать над профилем минимального максимума выигрыша составляющей стадии игры. То есть равновесный выигрыш каждого игрока должен быть не меньше минимального максимального выигрыша этого игрока. Это связано с тем, что игрок, получающий выигрыш ниже минимального максимума, всегда имеет стимул отклоняться, просто играя свою стратегию минимального максимума на каждой истории.

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

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

Есть разные народные теоремы; одни относятся к играм с конечным числом повторений, другие - к играм с бесконечным повторением.^[4]

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

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

Когда игра бесконечна, общей моделью полезности в бесконечно повторяющейся игре является ограничивать низший средней полезности: если игра приводит к путям результатов ${ displaystyle x_ {t}}$ , куда ${ displaystyle x_ {t}}$ обозначает коллективный выбор игроков на итерации т (t = 0,1,2, ...), игрок я'полезность определяется как

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

куда ${ displaystyle u_ {i}}$ функция полезности основной игры игрока я.

Бесконечно повторяющуюся игру без дисконтирования часто называют «суперигрой».

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

В доказательстве используется то, что называется мрачный^[5] или же мрачный спусковой крючок^[6] стратегия. Все игроки начинают с выполнения предписанного действия и продолжают делать это, пока кто-нибудь не отклонится. Если игрок я отклоняется, все остальные игроки переключаются на выбор действия, которое минимизирует игрока я навсегда после. Одноступенчатый выигрыш от отклонения дает 0 вкладов в общую полезность игрока. я. Полезность отклоняющегося игрока не может быть выше, чем его минимальный выигрыш. Следовательно, все игроки остаются на намеченном пути, и это действительно равновесие по Нэшу.

Совершенство подигры

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

Идеальное равновесие в подигре требует немного более сложной стратегии.^[5]^[7]^:146–149 Наказание не должно длиться вечно; он должен длиться ограниченное время, достаточное, чтобы свести на нет выгоды от отклонений. После этого остальные игроки должны вернуться на путь равновесия.

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

Коалиция - идеальное равновесие по подиграм:^[8] Равновесие называется коалиция равновесие по Нэшу если никакая коалиция не может выиграть от отклонения. Это называется коалиция - идеальное равновесие по подиграм если ни одна коалиция не сможет получить выгоду от отклонения после любой истории.^[9] С критерием предела средних, профиль выигрыша достижим в коалиционном-равновесном-по Нэше или в-коалиционном-подигровом-совершенном-равновесии, если и только если это так. Парето эффективный и слабо коалиционно-индивидуально-рационально.^[10]

Обгон

Некоторые авторы утверждают, что критерий предела средних нереалистичен, потому что он подразумевает, что полезности в любом конечном промежутке времени вносят 0 в общую полезность. Однако, если полезности в любом конечном промежутке времени вносят положительное значение, и это значение не учитывается, тогда невозможно приписать конечную числовую полезность бесконечной последовательности результатов. Возможное решение этой проблемы состоит в том, что вместо определения числовой полезности для каждой бесконечной исходной последовательности мы просто определяем отношение предпочтения между двумя бесконечными последовательностями. Мы говорим, что агент ${ displaystyle i}$ (строго) предпочитает последовательность результатов ${ displaystyle y_ {t}}$ по последовательности ${ displaystyle x_ {t}}$ , если:^[6]^[7]^:139^[8]

{ displaystyle liminf _ {T to infty} sum _ {t = 0} ^ {T} (u_ {i} (y_ {t}) - u_ {i} (x_ {t}))> 0 }

Например, рассмотрим последовательности ${ Displaystyle и_ {я} (х) = (0,0,0,0, ldots)}$ и ${ Displaystyle и_ {я} (у) = (- 1,2,0,0, ldots)}$ . Согласно критерию предела средств, они предоставляют игроку такую же полезность. я, но по критерию обгона, ${ displaystyle y}$ лучше, чем ${ displaystyle x}$ для игрока я. Видеть критерий обгона для дополнительной информации.

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

Строгое стационарное равновесие:^[6] Равновесие по Нэшу называется строгий если каждый игрок строго предпочитает бесконечную последовательность результатов, достигаемых в равновесии, любой другой последовательности, от которой он может отклониться. Равновесие по Нэшу называется стационарный если результат один и тот же в каждый период времени. Результат возможен в условиях строгого стационарного равновесия тогда и только тогда, когда для каждого игрока результат строго лучше, чем минимаксный результат игрока.^[11]
Строгие стационарные совершенные по подиграм равновесия:^[6] Результат возможен в строгом-стационарном-идеальном-идеальном-равновесии, если для каждого игрока результат строго лучше, чем минимаксный исход игрока (обратите внимание, что это не результат «если и только если»). Чтобы достичь идеального равновесия в подигре с критерием обгона, необходимо наказывать не только игрока, который отклоняется от пути соглашения, но также и каждого игрока, который не сотрудничает в наказании отклоняющегося.^[7]^:149–150
- Концепция «стационарного равновесия» может быть обобщена до «периодического равновесия», в котором конечное число исходов периодически повторяется, а выигрыш за период является средним арифметическим выигрышем в результатах. Этот средний выигрыш должен быть строго выше минимаксного.^[6]
Строгие стационарные коалиционные равновесия:^[8] С критерием обгона, если результат достижим в равновесии коалиции и Нэша, то он Парето эффективный и слабо коалиционно-индивидуально-рационально. С другой стороны, если это Парето эффективный и строго коалиционно-индивидуально-рационально^[12] она может быть достигнута в условиях строго стационарного коалиционного равновесия.

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

Предположим, что выигрыш игрока в бесконечно повторяющейся игре определяется средний дисконтированный критерий с коэффициентом дисконтирования 0 <δ < 1:

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

Фактор дисконтирования показывает, насколько терпеливы игроки.

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

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

1. Все игроки начинают с игры. а и продолжай играть а если отклонения нет.

2. Если какой-либо игрок, скажите игрок я, отклонился, играйте в профиль стратегии м который minmaxes я навсегда после.

3. Игнорировать многосторонние отклонения.

Если игрок я получает ε больше, чем его минимальный выигрыш на каждом этапе после 1, тогда потенциальный проигрыш от наказания составляет

{ displaystyle { frac {1} {1- delta}} varepsilon.}

Если δ близко к 1, это перевешивает любой конечный выигрыш за одну стадию, что делает стратегию равновесной по Нэшу.

Альтернативная формулировка этой народной теоремы^[4] позволяет получить равновесный профиль выплат ты быть любым индивидуально рациональным возможным профилем выплат; это только требует, чтобы существовал индивидуально рациональный допустимый профиль выплат, который строго доминирует над минимальным профилем выплат. Тогда народная теорема гарантирует, что можно подойти к ты в равновесии с любой желаемой точностью (для каждого ε существует равновесие по Нэшу, где профиль выигрыша - это расстояние ε далеко от ты).

Совершенство подигры

Достижение подигра идеальна Равновесие в играх со скидкой труднее, чем в играх без скидки. Стоимость наказания не исчезает (как в случае критерия предела средств). Не всегда возможно наказывать ненаказателей бесконечно (как в случае с критерием обгона), поскольку фактор дисконтирования делает наказания в далеком будущем несущественными. Для подарка. Следовательно, нужен другой подход: карателей нужно вознаграждать.

Это требует дополнительного предположения, что набор допустимых профилей выплаты является полноразмерным, а профиль min-max лежит внутри него. Стратегия следующая.

1. Все игроки начинают с игры. а и продолжай играть а если отклонения нет.

2. Если какой-либо игрок, скажите игрок я, отклонился, играйте в профиль стратегии м который minmaxes я за N периоды. (Выбирать N и δ достаточно большой, чтобы ни у одного игрока не было стимула отклониться от фазы 1.)

3. Если ни один из игроков не отклонился от фазы 2, все игроки j ≠ я получает вознаграждение ε над j 's min-max навсегда после, пока игрок я продолжает получать свои мин-макс. (Здесь необходимы полномасштабность и внутреннее предположение.)

4. Если игрок j отклонился от фазы 2, все игроки перезапускают фазу 2 с j как цель.

5. Игнорируйте многосторонние отклонения.

Игрок j ≠ я теперь нет стимула отклоняться от фазы наказания 2. Это доказывает идеальную народную теорему для подыгры.

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

Предположим, что выигрыш игрока я в игре, которая повторяется Т раз определяется простым средним арифметическим:

{ displaystyle U_ {i} = { frac {1} {T}} sum _ {t = 0} ^ {T} u_ {i} (x_ {t})}

Народная теорема для этого случая имеет следующее дополнительное требование:^[4]

В основной игре для каждого игрока я, существует равновесие по Нэшу

{ displaystyle E_ {i}}

это строго лучше, ибо я, затем его минимальный выигрыш.

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

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

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

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

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

Приложения

Народные теоремы можно применять в самых разных областях. Например:

Антропология: в сообществе, где все поведение хорошо известно, и где члены сообщества знают, что им по-прежнему придется иметь дело друг с другом, тогда любой образец поведения (традиции, табу и т. д.) может поддерживаться социальные нормы до тех пор, пока отдельным лицам сообщества выгоднее оставаться в сообществе, чем им покидать сообщество (условие минимакса).
Международная политика: невозможно обеспечить эффективное соблюдение соглашений между странами. Однако они сохраняются, потому что отношения между странами являются долгосрочными и страны могут использовать «минимаксные стратегии» друг против друга. Эта возможность часто зависит от коэффициента дисконтирования соответствующих стран. Если страна очень нетерпелива (мало обращает внимания на будущие результаты), то наказать ее (или заслужить заслуженное наказание) может быть сложно.^[5]

С другой стороны, экономист MIT Франклин Фишер отметил, что народная теорема не является положительной теорией.^[13] Рассматривая, например, олигополия поведения, народная теорема не говорит экономисту о том, чем будут заниматься фирмы, а скорее о том, что функций затрат и спроса недостаточно для общей теории олигополии, и экономисты должны включить контекст, в котором действуют олигополии, в свою теорию.^[13]

В 2007 году Borgs et al. доказал, что, несмотря на народную теорему, в общем случае вычисление равновесий Нэша для повторяющихся игр не проще, чем вычисление равновесий Нэша для одноразовых конечных игр, проблема, которая заключается в PPAD класс сложности.^[14] Практическим следствием этого является то, что неизвестен эффективный (полиномиальный) алгоритм, который вычисляет стратегии, требуемые народными теоремами в общем случае.

Краткое содержание народных теорем

В следующей таблице сравниваются различные народные теоремы в нескольких аспектах:

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

Опубликовано	Горизонт	Утилиты	Условия на G	Условия на x	Гарантия	Тип равновесия	Тип наказания
Бенуа и Кришна^[15]	Конечное ( ${ displaystyle T}$ )	Среднее арифметическое	Для каждого игрока существует равновесный выигрыш, строго превышающий минимаксный.	Никто	Для всех ${ displaystyle varepsilon> 0}$ есть ${ displaystyle T_ {0} in mathbb {N}}$ так что, если ${ displaystyle T geq T_ {0}}$ , для каждого ${ displaystyle x}$ есть равновесие с выплатой ${ displaystyle varepsilon}$ -рядом с ${ displaystyle x}$ .	Нэш
Ауман и Шепли^[5]	Бесконечный	Предел средств	Никто	Никто	Выплата точно ${ displaystyle x}$ .	Нэш	Мрачный
Ауман и Шепли^[5] и Рубинштейн^[8]^[16]	Бесконечный	Предел средств	Никто	Никто	Выплата точно ${ displaystyle x}$ .	Идеальная под-игра	Ограниченное по времени наказание.^[7]^:146–149
Рубинштейн^[6]	Бесконечный	Обгон	Никто	Строго выше минимакса.	Единичный исход или периодическая последовательность.	Идеальная под-игра	Наказание ненаказателей.^[7]^:149–150
Рубинштейн^[8]	Бесконечный	Предел средств	Никто	Парето-эффективные и слабо коалиционные индивидуально рациональные^[10]	Никто	Коалиция-под-игра-идеальна
Рубинштейн^[8]	Бесконечный	Обгон	Никто	Парето-эффективный и строго коалиционно-индивидуально-рациональный^[12]	Никто	Коалиция-Наш
Фуденберг и Маскин^[17]	Бесконечный	Сумма со скидкой ${ displaystyle delta}$	Допускаются коррелированные смешанные стратегии.	Строго выше минимакса.	Когда ${ displaystyle delta}$ достаточно близко к 1, существует равновесие с выплатой ровно ${ displaystyle x}$ .	Нэш	Мрачный
Фуденберг и Маскин^[17]	Бесконечный	Сумма со скидкой ${ displaystyle delta}$	Разрешены только чистые стратегии.	Строго выше минимакса.	Для всех ${ displaystyle varepsilon> 0}$ есть ${ displaystyle delta _ {0} <1}$ так что, если ${ displaystyle delta geq delta _ {0}}$ , для каждого ${ displaystyle x}$ есть равновесие с выплатой ${ displaystyle varepsilon}$ -рядом с ${ displaystyle x}$ .	Нэш	Суровое наказание.
Фридман (1971, 1977)	Бесконечный	Сумма со скидкой ${ displaystyle delta}$	Допускаются коррелированные смешанные стратегии.	Строго выше равновесия по Нэшу в G.	Когда ${ displaystyle delta}$ достаточно близко к 1, равновесие с выплатой ровно ${ displaystyle x}$ .	Идеальная под-игра	Суровое наказание с использованием равновесия по Нэшу.
Фуденберг и Маскин^[17]	Бесконечный	Сумма со скидкой ${ displaystyle delta}$	Два игрока	Строго выше минимакса.	Для всех ${ displaystyle x}$ есть ${ displaystyle delta _ {0} <1}$ так что, если ${ displaystyle delta geq delta _ {0}}$ , равновесие с выплатой ровно ${ displaystyle x}$ .	Идеальная под-игра	Ограниченное по времени наказание.
Фуденберг и Маскин^[17]	Бесконечный	Сумма со скидкой ${ displaystyle delta}$	Возможное инфракрасное пространство является полномерным.^[18]	Строго выше минимакса.	Для всех ${ displaystyle x}$ есть ${ displaystyle delta _ {0} <1}$ так что, если ${ displaystyle delta geq delta _ {0}}$ , равновесие с выплатой ровно ${ displaystyle x}$ .	Идеальная под-игра	Награждение карателей.^[7]^:150–153

Примечания

^ В математике термин народная теорема обычно относится к любой теореме, в которую верят и которая обсуждается, но не была опубликована. Роджер Майерсон рекомендовал более описательный термин «общая теорема выполнимости» для обсуждаемых здесь теорем теории игр. См. Майерсон, Роджер Б. Теория игр, Анализ конфликта, Кембридж, издательство Гарвардского университета (1991)
^ Р. Гиббонс (1992). Учебник по теории игр. Комбайн пшеничный сноп. п. 89. ISBN 0-7450-1160-8.CS1 maint: использует параметр авторов (связь)
^ Джонатан Левин (2002). «Торг и повторные игры» (PDF).
^ ^а ^б ^c Майкл Машлер, Эйлон Солан И Шмуэль Замир (2013). Теория игры. Издательство Кембриджского университета. С. 176–180. ISBN 978-1-107-00548-8.CS1 maint: использует параметр авторов (связь)
^ ^а ^б ^c ^d ^е Ауманн, Роберт Дж .; Шепли, Ллойд С. (1994). «Долгосрочная конкуренция - теоретико-игровой анализ». Очерки теории игр. п. 1. Дои:10.1007/978-1-4612-2648-2_1. ISBN 978-1-4612-7621-0.
^ ^а ^б ^c ^d ^е ^ж Рубинштейн, Ариэль (1979). «Равновесие в супериграх по критерию обгона». Журнал экономической теории. 21: 1. Дои:10.1016/0022-0531(79)90002-4.
^ ^а ^б ^c ^d ^е ^ж . ISBN 0-262-15041-7. LCCN 94008308. ПР 1084491M. Отсутствует или пусто | название = (помощь)
^ ^а ^б ^c ^d ^е ^ж Рубинштейн, А. (1980). «Сильное идеальное равновесие в супериграх». Международный журнал теории игр. 9: 1. Дои:10.1007 / BF01784792.
^ В статье используется термин «сильное равновесие». Здесь, чтобы избежать двусмысленности, вместо этого используется термин «коалиционное равновесие».
^ ^а ^б Для каждой непустой коалиции ${ displaystyle B}$ , есть стратегия других игроков ( ${ Displaystyle N setminus B}$ ) такая, что для любой стратегии, которую играет ${ displaystyle B}$ , выигрыш при ${ displaystyle B}$ игры ${ displaystyle c ^ {B}}$ не [строго лучше для все Члены ${ displaystyle B}$ ].
^ В статье 1979 года Рубинштейн утверждает, что результат достижим в условиях строгого стационарного равновесия, если и только если для каждого игрока результат ЛИБО строго лучше, чем минимаксный результат игрока, ИЛИ результат слабо лучше, чем любой другой результат. игрок может в одностороннем порядке отклониться от. Неясно, как второй вариант реализуется при строгом равновесии. В книге 1994 года этого утверждения нет.
^ ^а ^б для каждой непустой коалиции ${ displaystyle B}$ , есть стратегия других игроков ( ${ Displaystyle N setminus B}$ ) такая, что для любой стратегии, которую играет ${ displaystyle B}$ , выигрыш строго хуже для хотя бы один член ${ displaystyle B}$ .
^ ^а ^б Фишер, Франклин М. Игры, в которые играют экономисты: позиция отказа от сотрудничества Экономический журнал RAND, Vol. 20, No. 1. (Spring, 1989), pp. 113–124, это конкретное обсуждение находится на странице 118
^ Кристиан Боргс; Дженнифер Чейес; Николь Имморлика; Адам Тауман Калаи; Вахаб Миррокни; Христос Пападимитриу (2007). «Миф о народной теореме» (PDF).
^ Бенуа, Жан-Пьер; Кришна, Виджай (1985). «Конечно-повторяющиеся игры». Econometrica. 53 (4): 905. Дои:10.2307/1912660. JSTOR 1912660.
^ Рубинштейн, Ариэль (1994). «Равновесие в супериграх». Очерки теории игр. п. 17. Дои:10.1007/978-1-4612-2648-2_2. ISBN 978-1-4612-7621-0.
^ ^а ^б ^c ^d Фуденберг, Дрю; Маскин, Эрик (1986). «Народная теорема в повторяющихся играх с дисконтом или с неполной информацией». Econometrica. 54 (3): 533. CiteSeerX 10.1.1.308.5775. Дои:10.2307/1911307. JSTOR 1911307.
^ Есть набор возможных результатов IR ${ displaystyle y_ {1}, dots, y_ {n}}$ , по одному на игрока, так что для каждого игрока ${ displaystyle i, j}$ , ${ displaystyle x_ {i}> y_ {i, i}}$ и ${ displaystyle y_ {j, i}> y_ {i, i}}$ .

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

Народная теорема (теория игр) - Folk theorem (game theory)

Содержание

Настройка и определения

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

Совершенство подигры

Обгон

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

Совершенство подигры

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

Приложения

Краткое содержание народных теорем

Примечания

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