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

В теории игр , в эпсилон-равновесия , или близком равновесия Нэша, является профиль стратегии , что приблизительно удовлетворяет условию равновесия Нэша . В равновесии по Нэшу ни у одного игрока нет стимула изменить свое поведение. В приближенном равновесии по Нэшу это требование ослаблено, чтобы допустить возможность того, что у игрока может быть небольшой стимул сделать что-то другое. Это все еще может считаться подходящей концепцией решения, если предположить, например, предубеждение статус-кво. Эта концепция решения может быть предпочтительнее равновесия по Нэшу из-за того, что ее легче вычислить, или, альтернативно, из-за возможности того, что в играх более чем с двумя игроками вероятности, участвующие в точном равновесии Нэша, не обязательно должны быть рациональными числами . ^[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 \ двоеточие A \ к 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 периодов. Единственное равновесие по Нэшу в этой игре - выбирать Дефект в каждом периоде. Теперь рассмотрим две стратегии « око за око» и мрачный спусковой крючок . Хотя ни « око за око», ни мрачный триггер не являются равновесием по Нэшу для игры, они оба являются равновесиями для некоторого положительного . Допустимые значения зависят от выплат составляющей игры и от количества T периодов.${\displaystyle \epsilon }$${\displaystyle \epsilon }$${\displaystyle \epsilon }$

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

Ссылки [ править ]

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

Источники

• Приближенное равновесие по Бертрану Х. Диксона в воспроизводимой отрасли , Обзор экономических исследований, 54 (1987), страницы 47–62.
• Х. Эверетт. «Рекурсивные игры». В HW Kuhn и AW Tucker, редакторах. К теории игр , т. III, том 39 Анналов математических исследований . Издательство Принстонского университета, 1957.
• Лейтон-Браун, Кевин; Шохам, Йоав (2008), Основы теории игр: краткое, многопрофильное введение , Сан-Рафаэль, Калифорния: Издательство Morgan & Claypool, 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. Скачать бесплатно онлайн .
• SH Tijs. Равновесия Нэша для некооперативных игр n лиц в нормальной форме , SIAM Review, 23 , 225–237, 1981.