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

Эпсилон-равновесие
Концепция решения в теории игр
Отношение
Суперсет	Равновесие Нэша
Значение
Используется для	стохастические игры

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

Определение

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

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

Учитывая игру и реальный неотрицательный параметр $\varepsilon$, стратегический профиль называется $\varepsilon$-равновесие, если ни один игрок не может получить больше, чем $\varepsilon$ в ожидаемом выигрыше за счет одностороннего отклонения от своей стратегии . Каждое равновесие Нэша эквивалентно $\varepsilon$-равновесие, где $\varepsilon =0$.

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

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

Хорошо

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

$\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) для ε-равновесий по Нэшу являетсяэквивалентно вопросу о том, существует ли такой для ε-хорошо подтвержденногоприближенные равновесия Нэша, но существование PTAS остается открытой проблемой.Для постоянных значений ε полиномиальные алгоритмы приближенного равновесияизвестны для более низких значений ε, чем известны для хорошо обоснованныхприблизительное равновесие.Для игр с выигрышами в диапазоне [0,1] и ε=0,3393 ε-равновесия Нэша могутвычисляться за полиномиальное время. Для игр с выигрышами в диапазоне [0,1] и ε=2/3 ε-хорошо поддерживаемые равновесия могутвычисляться за полиномиальное время.

Пример

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

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

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

Другим простым примером является конечно повторяющаяся дилемма заключенного для периодов T, где выигрыш усредняется за периоды T. Единственное равновесие Нэша в этой игре — это выбор Дефекта в каждом периоде. Теперь рассмотрим две стратегии «око за око» и «мрачный триггер» . Хотя ни «око за око» , ни «мрачный триггер» не являются равновесием Нэша в этой игре, оба они $\epsilon$-равновесия для некоторых положительных $\epsilon$. Приемлемые значения $\epsilon$ зависят от выигрышей составляющей игры и числа периодов T.

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

Ссылки

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

Источники

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