Устойчивое равновесие Мертенса

В теории игр устойчивость Мертенса — это концепция решения, используемая для прогнозирования результата некооперативной игры . Предварительное определение стабильности было предложено Илоном Кольбергом и Жаном-Франсуа Мертенсом. для игр с конечным числом игроков и стратегий. Позже Мертенс предложил более строгое определение, которое было далее развито Шрихари Говинданом и Мертенсом. Эту концепцию решения теперь называют устойчивостью Мертенса , или просто стабильностью .

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

Желательные свойства усовершенствования

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

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

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

Свойства стабильных множеств

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

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

Определение стабильного множества

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

Мертенс дал несколько формальных определений в зависимости от модуля коэффициентов, используемого для гомологии или когомологии .

Формальное определение требует некоторых обозначений. Для данной игры $G$ позволять $\Sigma$ быть продуктом симплексов смешанных стратегий игроков. Для каждого $0<\delta \leq 1$, позволять $P_{\delta }=\{\,\epsilon \tau \mid 0\leq \epsilon \leq \delta ,\tau \in \Sigma \,\}$ и пусть $\partial P_{\delta }$ быть его топологической границей . Для $\eta \in P_{1}$ позволять ${\bar {\eta }}$ — минимальная вероятность любой чистой стратегии. Для любого $\eta \in P_{1}$ определить возмущенную игру $G(\eta )$ как игра, в которой стратегия каждого игрока $n$ такое же, как и в $G$, но где выигрыш от профиля стратегии $\tau$ это выигрыш в $G$ из профиля $\sigma =(1-{\bar {\eta }})\tau +\eta$. Скажи это $\sigma$ является возмущенным равновесием $G(\eta )$ если $\tau$ представляет собой равновесие $G(\eta )$. Позволять ${\mathcal {E}}$ – график возмущенного соответствия равновесия над $P_{1}$, а именно, график ${\mathcal {E}}$ это набор этих пар $(\eta ,\sigma )\in P_{1}\times \Sigma$ такой, что $\sigma$ является возмущенным равновесием $G(\eta )$. Для $(\eta ,\sigma )\in {\mathcal {E}}$, $\tau (\eta ,\sigma )\equiv (\sigma -\eta )/(1-{\bar {\eta }})$ соответствующее равновесие $G(\eta )$. Обозначим через $p$ естественная карта проекции из ${\mathcal {E}}$ к $P_{1}$. Для $E\subseteq {\mathcal {E}}$, позволять $E_{0}=\{\,(0,\sigma )\in E\,\}$и для $0<\delta \leq 1$ позволять $(E_{\delta },\partial E_{\delta })=p^{-1}(P_{\delta },\partial P_{\delta })\cap E$. Окончательно, ${\check {H}}$ относится к когомологиям Чеха с целыми коэффициентами.

Ниже приводится версия наиболее всеобъемлющего определения Мертенса, называемого *-стабильностью.

Определение *-стабильного множества : $S\subseteq \Sigma$ является *-стабильным множеством, если для некоторого замкнутого подмножества $E$ из ${\mathcal {E}}$ с $E_{0}=\{\,0\,\}\times S$ он имеет следующие два свойства:

• Связность : для каждого района $V$ из $E_{0}$ в $E$, набор $V\setminus \partial E_{1}$ имеет компоненту связности, замыканием которой является окрестность $E_{0}$ в $E$.
• Когомологическая существенность : $p^{*}:{\check {H}}^{*}(P_{\delta },\partial P_{\delta })\to {\check {H}}^{*}(E_{\delta },\partial E_{\delta })$ ненулевое значение для некоторых $\delta >0$.

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