Эпсилон-равновесие

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

Определение

Существует более одного альтернативного определения.

Стандартное определение

При заданной игре и действительном неотрицательном параметре профиль стратегии называется -равновесием, если ни один игрок не может получить выигрыш больше ожидаемого, односторонне отклонившись от своей стратегии . ^{[2] : 45} Каждое равновесие Нэша эквивалентно -равновесию, где . ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon =0}$

Формально, пусть будет -игрой с наборами действий для каждого игрока и функцией полезности . Пусть обозначает выигрыш игрока при игре в профиль стратегии . Пусть будет пространством распределений вероятностей по . Вектор стратегий является -равновесием Нэша для , если ${\displaystyle G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})}$ ${\displaystyle N}$ ${\displaystyle A_{i}}$ ${\displaystyle i}$ ${\displaystyle u}$ ${\displaystyle u_{i}(s)}$ ${\displaystyle i}$ ${\displaystyle s}$ ${\displaystyle \Delta _{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle \sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}}$ ${\displaystyle \varepsilon }$ ${\displaystyle G}$

${\displaystyle u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\varepsilon }$для всех ${\displaystyle \sigma _{i}^{'}\in \Delta _{i},i\in N.}$

Хорошо поддерживаемое приблизительное равновесие

Следующее определение ^[3] налагает более строгое требование, что игрок может назначать положительную вероятность только чистой стратегии , если выигрыш имеет ожидаемый выигрыш не более, чем выигрыш наилучшего ответа. Пусть будет вероятностью того, что профиль стратегии будет сыгран. Для игрока пусть будут профили стратегий игроков, отличных от ; для и чистой стратегии пусть будет профиль стратегии, где играет и другие игроки играют . Пусть будет выигрыш в , когда используется профиль стратегии . Требование можно выразить формулой ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle \varepsilon }$ ${\displaystyle x_{s}}$ ${\displaystyle s}$ ${\displaystyle p}$ ${\displaystyle S_{-p}}$ ${\displaystyle p}$ ${\displaystyle s\in S_{-p}}$ ${\displaystyle j}$ ${\displaystyle p}$ ${\displaystyle js}$ ${\displaystyle p}$ ${\displaystyle j}$ ${\displaystyle s}$ ${\displaystyle u_{p}(s)}$ ${\displaystyle p}$ ${\displaystyle s}$

${\displaystyle \sum _{s\in S_{-p}}u_{p}(js)x_{s}>\varepsilon +\sum _{s\in S_{-p}}u_{p}(j's)x_{s}\Longrightarrow x_{j'}^{p}=0.}$

Результаты

Существование полиномиальной по времени аппроксимационной схемы (PTAS) для равновесий ε-Нэша эквивалентно вопросу о том, существует ли схема для ε-хорошо поддерживаемых приближенных равновесий Нэша, ^[4] но существование PTAS остается открытой проблемой. Для постоянных значений ε известны полиномиальные по времени алгоритмы для приближенных равновесий для более низких значений ε, чем для хорошо поддерживаемых приближенных равновесий. Для игр с выигрышами в диапазоне [0,1] и ε=0,3393, ε-равновесия Нэша могут быть вычислены за полиномиальное время. ^[5] Для игр с выигрышами в диапазоне [0,1] и ε=2/3, ε-хорошо поддерживаемые равновесия могут быть вычислены за полиномиальное время. ^[6]

Пример

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

Возможно, самым простым примером такого рода является следующий вариант Matching Pennies , предложенный Эвереттом. Игрок 1 прячет пенни, а Игрок 2 должен угадать, лежит ли он орлом вверх или решкой вверх. Если Игрок 2 угадает правильно, он выигрывает пенни у Игрока 1, и игра заканчивается. Если Игрок 2 неправильно угадает, что пенни лежит орлом вверх, игра заканчивается с нулевым выигрышем для обоих игроков. Если он неправильно угадает, что лежит решкой вверх, игра повторяется . Если игра продолжается вечно, выигрыш для обоих игроков равен нулю.

При заданном параметре ε > 0 любой профиль стратегии , где Игрок 2 угадывает орла с вероятностью ε и решки с вероятностью 1 −  ε (на каждом этапе игры и независимо от предыдущих этапов), является ε -равновесием для игры. Ожидаемый выигрыш Игрока 2 в таком профиле стратегии составляет по крайней мере 1 −  ε . Однако легко видеть, что не существует стратегии для Игрока 2, которая может гарантировать ожидаемый выигрыш ровно 1. Следовательно, в игре нет равновесия Нэша .

Другим простым примером является конечно повторяющаяся дилемма заключенного для T периодов, где выигрыш усредняется по T периодам. Единственное равновесие Нэша этой игры — выбрать Defect в каждом периоде. Теперь рассмотрим две стратегии tie-for-tat и grim trigger . Хотя ни tie-for-tat, ни grim trigger не являются равновесиями Нэша для игры, обе они являются -равновесиями для некоторого положительного . Допустимые значения зависят от выигрышей составляющей игры и от количества T периодов. ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

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

Ссылки

Встроенные цитаты

1. В. Бубелис (1979). «О равновесии в конечных играх». Международный журнал теории игр . 8 (2): 65–79. doi :10.1007/bf01768703. S2CID  122843303.
2. Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
3. PW Goldberg и CH Papadimitriou (2006). «Сводимость среди проблем равновесия». 38-й симпозиум по теории вычислений . стр. 61–70. doi :10.1145/1132516.1132526.
4. К. Даскалакис, П.В. Голдберг и CH Пападимитриу (2009). «Сложность расчета равновесия Нэша». SIAM Journal по вычислительной технике . 39 (3): 195–259. CiteSeerX 10.1.1.68.6111 . дои : 10.1137/070699652. 
5. H. Tsaknakis и Paul G. Spirakis (2008). «Оптимизационный подход для приближенных равновесий Нэша». Internet Mathematics . 5 (4): 365–382. doi : 10.1080/15427951.2008.10129172 .
6. Спирос К. Контогианнис и Пол Г. Спиракис (2010). «Хорошо поддерживаемые приближенные равновесия в биматричных играх». Algorithmica . 57 (4): 653–667. doi :10.1007/s00453-008-9227-6. S2CID  15968419.

Источники

• Х. Диксон. Приблизительное равновесие Бертрана в воспроизводимой отрасли, Обзор экономических исследований, 54 (1987), страницы 47–62.
• H. Everett. «Рекурсивные игры». В HW Kuhn и AW Tucker, редакторы. Вклад в теорию игр , т. III, том 39 Annals of Mathematical Studies . Princeton University Press, 1957.
• Лейтон-Браун, Кевин ; Шохам, Йоав (2008), Основы теории игр: краткое междисциплинарное введение, Сан-Рафаэль, Калифорния: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. 88-страничное математическое введение; см. раздел 3.7. Бесплатно онлайн Архивировано 15 августа 2000 г. на Wayback Machine во многих университетах.
• Р. Раднер . Сговор в некооперативных эпсилон-равновесиях олигополий с длительным, но конечным сроком жизни , Журнал экономической теории, 22 , 121–157, 1980.
• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Многоагентные системы: алгоритмические, игровые и логические основы, Нью-Йорк: Cambridge University Press , ISBN 978-0-521-89943-7. Полный справочник с точки зрения вычислений; см. раздел 3.4.7. Можно бесплатно загрузить онлайн.
• С. Х. Тийс. Равновесия Нэша для некооперативных игр n лиц в нормальной форме , SIAM Review, 23 , 225–237, 1981.