Народная теорема (теория игр)

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

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

Настройка и определения [ править ]

Мы начнем с базовой игры , также известной как сценическая игра , которая представляет собой игру для n игроков . В этой игре у каждого игрока есть выбор из конечного числа действий, и они делают свой выбор одновременно и без знания выбора другого игрока. Коллективный выбор игроков приводит к профилю выигрыша, т.е. к выигрышу для каждого из игроков. Сопоставление коллективного выбора с профилями выигрышей известно игрокам, и каждый игрок стремится максимизировать свой выигрыш. Если коллективный выбор обозначен x, то выигрыш, который игрок i получает i игрока , также известный как полезность , будет обозначаться через $u_{i}(x)$ .

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

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

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

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

Существуют различные народные теоремы; некоторые относятся к играм с конечным повторением, а другие — к играм с бесконечным повторением. ^[4]

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

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

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

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

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

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

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

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

Совершенство подигры [ править ]

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

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

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

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

Обгон [ править ]

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

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

Например, рассмотрим последовательности $u_{i}(x)=(0,0,0,0,\ldots )$ и $u_{i}(y)=(-1,2,0,0,\ldots )$ . По критерию предела средств они обеспечивают игроку i одинаковую полезность, но по критерию обгона $y$ лучше, чем $x$ для игрока я . см. в критерии обгона Дополнительную информацию .

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

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

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

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

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

Коэффициент дисконтирования показывает, насколько терпеливы игроки. Фактор $(1-\delta )$ вводится так, чтобы выигрыш оставался ограниченным, когда $\delta \rightarrow 1$ .

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

Пусть a — стратегический профиль поэтапной игры с профилем выигрыша u, который строго доминирует над minmax профилем выигрыша. Равновесие по Нэшу в игре с u как результирующим профилем выигрышей можно определить следующим образом:

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

2. Если какой-либо игрок, скажем, игрок i , отклонился, играйте по стратегическому профилю m , который минимизирует i навсегда.

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

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

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

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

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

Совершенство подигры [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

В базовой игре для каждого игрока i существует равновесие Нэша.

E_{i}

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

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

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

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

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

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

Приложения [ править ]

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

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

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

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

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

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

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

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

в других условиях теоремы Народные

Ссылаясь на народные теоремы для повторяющихся игр, некоторые авторы использовали термин «народная теорема» для обозначения результатов о множестве возможных равновесий или равновесных выигрышей в других условиях, особенно если результаты схожи в том, какие равновесные выигрыши они допускают. Например, Тенненхольц доказывает «народную теорему» о программном равновесии . Многие другие народные теоремы были доказаны в условиях строгости. ^[19]^[20]^[21]^[22]

Примечания [ править ]

^ В математике термин « народная теорема» обычно относится к любой теореме, в которую верят и которая обсуждается, но не была опубликована. Роджер Майерсон рекомендовал более описательный термин «общая теорема осуществимости» для обсуждаемых здесь теорем теории игр. См. Майерсон, Роджер Б. Теория игр, Анализ конфликта , Кембридж, издательство Гарвардского университета (1991).
^ Р. Гиббонс (1992). Букварь по теории игр . Комбайн Уитшиф . п. 89. ИСБН 0-7450-1160-8 .
^ Джонатан Левин (2002). «Торг и повторяющиеся игры» (PDF) .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Майкл Машлер; Эйлон Солан ; Шмуэль Замир (2013). Теория игр . Издательство Кембриджского университета . стр. 176–180. ISBN 978-1-107-00548-8 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и Ауманн, Роберт Дж.; Шепли, Ллойд С. (1994). «Долгосрочная конкуренция — теоретико-игровой анализ» (PDF) . Очерки по теории игр . п. 1. дои : 10.1007/978-1-4612-2648-2_1 . ISBN 978-1-4612-7621-0 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Рубинштейн, Ариэль (1979). «Равновесие в супериграх с критерием обгона». Журнал экономической теории . 21 : 1–9. дои : 10.1016/0022-0531(79)90002-4 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Осборн, Мартин Дж.; Рубинштейн, Ариэль (12 июля 1994 г.). Курс теории игр . ISBN 0-262-15041-7 . LCCN 94008308 . ОЛ 1084491М .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Рубинштейн, А. (1980). «Сильное совершенное равновесие в супериграх». Международный журнал теории игр . 9 : 1–12. дои : 10.1007/BF01784792 . S2CID 122098115 .
^ В статье используется термин «сильное равновесие». Здесь, чтобы избежать двусмысленности, вместо этого используется термин «коалиционное равновесие».
↑ Перейти обратно: Перейти обратно: ^а ^б Для каждой непустой коалиции $B$ , существует стратегия остальных игроков ( $N\setminus B$ ) такая, что для любой стратегии, которую играют $B$ , выигрыш, когда $B$ играет $c^{B}$ не [строго лучше для всех членов $B$ ].
^ В статье 1979 года Рубинштейн утверждает, что результат достижим в строгом стационарном равновесии тогда и только тогда, когда для каждого игрока результат ЛИБО строго лучше, чем минимаксный результат игрока, ИЛИ результат немного лучше, чем любой другой результат, к которому игрок может в одностороннем порядке отклониться. Неясно, как второй вариант достижим в условиях строгого равновесия. В книге 1994 года это утверждение не встречается.
↑ Перейти обратно: Перейти обратно: ^а ^б для каждой непустой коалиции $B$ , существует стратегия остальных игроков ( $N\setminus B$ ) такая, что для любой стратегии, которую играют $B$ , выигрыш строго хуже по крайней мере для одного члена $B$ .
↑ Перейти обратно: Перейти обратно: ^а ^б Фишер, Франклин М. Игры, в которые играют экономисты: взгляд на отказ от сотрудничества The RAND Journal of Economics, Vol. 20, № 1. (Весна 1989 г.), стр. 113–124, это конкретное обсуждение находится на странице 118.
^ Кристиан Боргс; Дженнифер Чейс; Николь Имморлика ; Адам Тауман Калаи ; Вахаб Миррокни; Христос Пападимитриу (2007). «Миф о народной теореме» (PDF) . стр. 365–372.
^ Бенуа, Жан-Пьер; Кришна, Виджай (1985). «Конечно повторяющиеся игры». Эконометрика . 53 (4): 905. дои : 10.2307/1912660 . JSTOR 1912660 .
^ Рубинштейн, Ариэль (1994). «Равновесие в супериграх». Очерки по теории игр . стр. 17–27. дои : 10.1007/978-1-4612-2648-2_2 . ISBN 978-1-4612-7621-0 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д Фуденберг, Дрю; Маскин, Эрик (1986). «Народная теорема в повторяющихся играх со скидкой или с неполной информацией». Эконометрика . 54 (3): 533. CiteSeerX 10.1.1.308.5775 . дои : 10.2307/1911307 . JSTOR 1911307 .
^ Существует набор возможных результатов IR. $y_{1},\dots ,y_{n}$ , по одному на игрока, так что для каждого игрока $i,j$ , $x_{i}>y_{i,i}$ и $y_{j,i}>y_{i,i}$ .
^ Форж, Франсуаза (2013). «Народная теорема для байесовских игр с обязательством». Игры и экономическое поведение . 78 : 64–71. дои : 10.1016/j.geb.2012.11.004 .
^ Остерхельд, Каспар; Трейтлейн, Йоханнес; Гросс, Роджер; Конитцер, Винсент; Ферстер, Якоб (2023). «Кооперативное равновесие, основанное на сходстве» . Труды по нейронным системам обработки информации (NeurIPS) .
^ Калай, Адам Тауман ; Калай, Эхуд ; Лерер, Эхуд; Самет, Дов (2010). «Народная теорема обязательства». Игры и экономическое поведение . 69 (1): 127–137. дои : 10.1016/j.geb.2009.09.008 .
^ Блок, Хуан И.; Левин, Дэвид К. (2017). «Народная теорема с кодексами поведения и общения». Бюллетень экономической теории . 5 (1): 9–19. дои : 10.1007/s40505-016-0107-y .

Ссылки [ править ]

Фридман, Дж. (1971). «Некооперативное равновесие для суперигр». Обзор экономических исследований . 38 (1): 1–12. дои : 10.2307/2296617 . JSTOR 2296617 .
Итииси, Тацуро (1997). Микроэкономическая теория . Оксфорд: Блэквелл. стр. 263–269. ISBN 1-57718-037-2 .
Мас-Колелл, А .; Уинстон, М.; Грин, Дж. (1995). Микроэкономическая теория . Нью-Йорк: Издательство Оксфордского университета. ISBN 0-19-507340-1 .
Рэтлифф, Дж. (1996). «Образец народных теорем» (PDF) . Набор вводных примечаний к Народной теореме.

[1] В математике термин « народная теорема» обычно относится к любой теореме, в которую верят и которая обсуждается, но не была опубликована. Роджер Майерсон рекомендовал более описательный термин «общая теорема осуществимости» для обсуждаемых здесь теорем теории игр. См. Майерсон, Роджер Б. Теория игр, Анализ конфликта , Кембридж, издательство Гарвардского университета (1991).

[2] Р. Гиббонс (1992). Букварь по теории игр . Комбайн Уитшиф . п. 89. ИСБН 0-7450-1160-8 .

[3] Джонатан Левин (2002). «Торг и повторяющиеся игры» (PDF) .

[ZMS-4] Перейти обратно: Перейти обратно: ^а ^б ^с Майкл Машлер; Эйлон Солан ; Шмуэль Замир (2013). Теория игр . Издательство Кембриджского университета . стр. 176–180. ISBN 978-1-107-00548-8 .

[AumannShapley94-5] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и Ауманн, Роберт Дж.; Шепли, Ллойд С. (1994). «Долгосрочная конкуренция — теоретико-игровой анализ» (PDF) . Очерки по теории игр . п. 1. дои : 10.1007/978-1-4612-2648-2_1 . ISBN 978-1-4612-7621-0 .

[Rubinstein79-6] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Рубинштейн, Ариэль (1979). «Равновесие в супериграх с критерием обгона». Журнал экономической теории . 21 : 1–9. дои : 10.1016/0022-0531(79)90002-4 .

[OR-7] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Осборн, Мартин Дж.; Рубинштейн, Ариэль (12 июля 1994 г.). Курс теории игр . ISBN 0-262-15041-7 . LCCN 94008308 . ОЛ 1084491М .

[Rubinstein80-8] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж Рубинштейн, А. (1980). «Сильное совершенное равновесие в супериграх». Международный журнал теории игр . 9 : 1–12. дои : 10.1007/BF01784792 . S2CID 122098115 .

[9] В статье используется термин «сильное равновесие». Здесь, чтобы избежать двусмысленности, вместо этого используется термин «коалиционное равновесие».

[weakly-coalition-individually-rational-10] Перейти обратно: Перейти обратно: ^а ^б Для каждой непустой коалиции $B$ , существует стратегия остальных игроков ( $N\setminus B$ ) такая, что для любой стратегии, которую играют $B$ , выигрыш, когда $B$ играет $c^{B}$ не [строго лучше для всех членов $B$ ].

[11] В статье 1979 года Рубинштейн утверждает, что результат достижим в строгом стационарном равновесии тогда и только тогда, когда для каждого игрока результат ЛИБО строго лучше, чем минимаксный результат игрока, ИЛИ результат немного лучше, чем любой другой результат, к которому игрок может в одностороннем порядке отклониться. Неясно, как второй вариант достижим в условиях строгого равновесия. В книге 1994 года это утверждение не встречается.

[strongly-coalition-individually-rational-12] Перейти обратно: Перейти обратно: ^а ^б для каждой непустой коалиции $B$ , существует стратегия остальных игроков ( $N\setminus B$ ) такая, что для любой стратегии, которую играют $B$ , выигрыш строго хуже по крайней мере для одного члена $B$ .

[fisher-13] Перейти обратно: Перейти обратно: ^а ^б Фишер, Франклин М. Игры, в которые играют экономисты: взгляд на отказ от сотрудничества The RAND Journal of Economics, Vol. 20, № 1. (Весна 1989 г.), стр. 113–124, это конкретное обсуждение находится на странице 118.

[14] Кристиан Боргс; Дженнифер Чейс; Николь Имморлика ; Адам Тауман Калаи ; Вахаб Миррокни; Христос Пападимитриу (2007). «Миф о народной теореме» (PDF) . стр. 365–372.

[BenoitKrishna85-15] Бенуа, Жан-Пьер; Кришна, Виджай (1985). «Конечно повторяющиеся игры». Эконометрика . 53 (4): 905. дои : 10.2307/1912660 . JSTOR 1912660 .

[Rubinstein94-16] Рубинштейн, Ариэль (1994). «Равновесие в супериграх». Очерки по теории игр . стр. 17–27. дои : 10.1007/978-1-4612-2648-2_2 . ISBN 978-1-4612-7621-0 .

[FudenbergMaskin86-17] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Фуденберг, Дрю; Маскин, Эрик (1986). «Народная теорема в повторяющихся играх со скидкой или с неполной информацией». Эконометрика . 54 (3): 533. CiteSeerX 10.1.1.308.5775 . дои : 10.2307/1911307 . JSTOR 1911307 .

[18] Существует набор возможных результатов IR. $y_{1},\dots ,y_{n}$ , по одному на игрока, так что для каждого игрока $i,j$ , $x_{i}>y_{i,i}$ и $y_{j,i}>y_{i,i}$ .

[19] Форж, Франсуаза (2013). «Народная теорема для байесовских игр с обязательством». Игры и экономическое поведение . 78 : 64–71. дои : 10.1016/j.geb.2012.11.004 .

[20] Остерхельд, Каспар; Трейтлейн, Йоханнес; Гросс, Роджер; Конитцер, Винсент; Ферстер, Якоб (2023). «Кооперативное равновесие, основанное на сходстве» . Труды по нейронным системам обработки информации (NeurIPS) .

[21] Калай, Адам Тауман ; Калай, Эхуд ; Лерер, Эхуд; Самет, Дов (2010). «Народная теорема обязательства». Игры и экономическое поведение . 69 (1): 127–137. дои : 10.1016/j.geb.2009.09.008 .

[22] Блок, Хуан И.; Левин, Дэвид К. (2017). «Народная теорема с кодексами поведения и общения». Бюллетень экономической теории . 5 (1): 9–19. дои : 10.1007/s40505-016-0107-y .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

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