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

ε-равновесие в теории игр — профиль стратегий игроков некооперативной игры, приблизительно удовлетворяющий условиям равновесия Нэша.

ε-равновесие
Концепция решения в теории игр
Связанные множества решений
Подмножества	Равновесие Нэша
Факты
Применение	Стохастические игры

ОпределениеПравить

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

Формально, пусть $G=(N,A=A_1\times <!--\; \times \; -->...\times <!--\; \times \; -->A_N,u:A\to <!--\; \to \; -->{\mathbb{R}}^N)$$G=(N,A=A_{1}\times ...\times A_{N},u:A\rightarrow \mathbb {R} ^{N})$  — игра N лиц со множествами стратегий игроков $A_i$$A_{i}$  и вектором функций выигрыша u. Набор стратегий $\mathrm{\sigma <!--\; \sigma \; -->}\in <!--\; \in \; -->\mathrm{\Delta <!--\; \Delta \; -->}={\mathrm{\Delta <!--\; \Delta \; -->}}_1\times <!--\; \times \; -->...\times <!--\; \times \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_N$$\sigma \in \Delta =\Delta _{1}\times ...\times \Delta _{N}$  является $\mathrm{ϵ<!--\; ϵ\; -->}$$\epsilon$ -равновесием в игре G, если:

$u_i(\mathrm{\sigma <!--\; \sigma \; -->})\ge <!--\; \ge \; -->u_i({\mathrm{\sigma <!--\; \sigma \; -->}}_i^{{}^{\prime }},{\mathrm{\sigma <!--\; \sigma \; -->}}_{-<!--\; -\; -->i})-<!--\; -\; -->\mathrm{ϵ<!--\; ϵ\; -->}$$u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\epsilon$  для всех $\mathrm{\sigma <!--\; \sigma \; -->}\in <!--\; \in \; -->\mathrm{\Delta <!--\; \Delta \; -->},{\mathrm{\sigma <!--\; \sigma \; -->}}_i^{{}^{\prime }}\in <!--\; \in \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_i$$\sigma \in \Delta ,\sigma _{i}^{'}\in \Delta _{i}$ 

ПримерПравить

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

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

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

СсылкиПравить

• Everett, H. Recursive Games // In: H.W. Kuhn and A.W. Tucker, eds. Contributions to the theory of games. — Vol. III, volume 39 of Annals of Mathematical Studies. — Princeton University Press, 1957.

ЛитератураПравить

• Петросян Л. А,, Зенкевич Н.А., Семина Е.А. Теория игр: Учеб. пособие для ун-тов. — М.: Высш. шк., Книжный дом «Университет», 1998. — С. 304. — ISBN 5-06-001005-8, 5-8013-0007-4.
• Васин А. А., Морозов В. В. Теория игр и модели математической экономики. — М.: Макс-пресс, 2005. — 272 с. — ISBN 5-317-01388-7.
• Васин А.А. Некооперативные игры в природе и обществе. М.: Макс Пресс, 2005, 412 с. ISBN 5-317-01306-2.