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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, рассмотрим последовательности и . Согласно критерию предела средств, они предоставляют игроку i одинаковую полезность, но согласно критерию обгона, лучше, чем для игрока i . Для получения дополнительной информации см. критерий обгона .${\displaystyle u_{i}(x)=(0,0,0,0,\ldots )}$${\displaystyle u_{i}(y)=(-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}),}$

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

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

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

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

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

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

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

${\displaystyle {\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 раз, определяется простым арифметическим средним:

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

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

В базовой игре для каждого игрока i существует равновесие Нэша , которое для i строго лучше, чем его минимально-максимальный выигрыш.${\displaystyle E_{i}}$

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

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

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

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

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

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

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

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

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

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

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

Опубликовано	Горизонт	Коммунальные услуги	Условия на 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 }$	Допускаются коррелированные смешанные стратегии.	Строго выше минимакса.	Когда достаточно близко к 1, существует равновесие с выигрышем ровно .${\displaystyle \delta }$${\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.	Когда достаточно близко к 1, достигается равновесие с выигрышем ровно .${\displaystyle \delta }$${\displaystyle x}$	Идеальная подигра	Жестокое наказание с использованием равновесия Нэша.
Фуденберг и Маскин [17]	Бесконечный	Сумма со скидкой${\displaystyle \delta }$	Два игрока	Строго выше минимакса.	Для всех существует такое, что если , то существует равновесие с выигрышем ровно .${\displaystyle x}$${\displaystyle \delta _{0}<1}$${\displaystyle \delta \geq \delta _{0}}$${\displaystyle x}$	Идеальная подигра	Ограниченное по времени наказание.
Фуденберг и Маскин [17]	Бесконечный	Сумма со скидкой${\displaystyle \delta }$	Допустимое пространство IR полномерно. [18]	Строго выше минимакса.	Для всех существует такое, что если , то существует равновесие с выигрышем ровно .${\displaystyle x}$${\displaystyle \delta _{0}<1}$${\displaystyle \delta \geq \delta _{0}}$${\displaystyle x}$	Идеальная подигра	Награждение карателей. [7] : 150–153

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

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