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

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

Определение

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

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

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

Формально, пусть будет -игрой с наборами действий для каждого игрока и функцией полезности . Пусть обозначает выигрыш игрока при игре в профиль стратегии . Пусть будет пространством распределений вероятностей по . Вектор стратегий является -равновесием Нэша для , если Г = ( Н , А = А 1 × ⋯ × А Н , ты : А → Р Н ) {\displaystyle G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})} Н {\displaystyle N} А я {\displaystyle A_{i}} я {\displaystyle я} ты {\displaystyle u} ты я ( с ) {\displaystyle u_{i}(s)} я {\displaystyle я} с {\displaystyle с} Δ я {\displaystyle \Дельта _{i}} А я {\displaystyle A_{i}} σ ∈ Δ = Δ 1 × ⋯ × Δ Н {\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 а} а {\displaystyle а} ε {\displaystyle \varepsilon} х с {\displaystyle x_{s}} с {\displaystyle с} п {\displaystyle p} С − п {\displaystyle S_{-p}} п {\displaystyle p} с ∈ С − п {\displaystyle s\in S_{-p}} дж {\displaystyle j} п {\displaystyle p} дж с {\displaystyle js} п {\displaystyle p} дж {\displaystyle j} с {\displaystyle с} ты п ( с ) {\displaystyle u_{p}(s)} п {\displaystyle p} с {\displaystyle с}

∑ с ∈ С − п ты п ( дж с ) х с > ε + ∑ с ∈ С − п ты п ( дж ′ с ) х с ⟹ х дж ′ п = 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.}

Результаты

Существование полиномиальной по времени аппроксимационной схемы (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.
Взято с "https://en.wikipedia.org/w/index.php?title=Эпсилон-равновесие&oldid=1213257696"