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

редактировать

Эпсилон-равновесие
A концепция решения в теория игр
Взаимосвязь
Надмножество	равновесия Нэша
Значимость
Используется для	стохастических игр

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

Содержание

1 Определение
- 1.1 Стандартное определение
- 1.2 Хорошо подтвержденное приблизительное равновесие
2 Результаты
3 Пример
4 Ссылки

Определение

Есть еще чем одно альтернативное определение.

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

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

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

ui (σ) ≥ ui (σ я ', σ - я) - ε {\ Displaystyle и_ {я} (\ сигма) \ GEQ и_ {я} (\ сигма _ {я} ^ {'}, \ сигма _ {- я}) - \ varepsilon}

u_{i}(\sigma)\geq u_{i}(\sigma _{i}^{'},\sigma _{{-i}})-\varepsilon

для всех

σ i ′ ∈ ∆ i, i ∈ N. {\ displaystyle \ sigma _ {i} ^ {'} \ in \ Delta _ {i}, i \ in N.}

\sigma _{i}^{'}\in \Delta _{i},i\in N.

Примерное равновесие с хорошей поддержкой

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

∑ s ∈ S - pup (js) xs>ε + ∑ s ∈ S - pup (j ′ s) xs ⟹ xj ′ p = 0. {\ 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.}

\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, ε-Na sh-равновесия могут быть вычислены за полиномиальное время Для игр с выплатами в диапазоне [0,1] и ε = 2/3, ε-хорошо поддерживаемые равновесия могут быть вычислены за полиномиальное время

Пример

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

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

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

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

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

Ссылки

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

Источники

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