Русская Википедия:Эпсилон-равновесие

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

Формально, пусть <math>G=(N,A=A_1\times...\times A_N, u: A \rightarrow \reals^N)</math> — игра N лиц со множествами стратегий игроков <math>A_i</math> и вектором функций выигрыша u. Набор стратегий <math>\sigma \in \Delta = \Delta_1 \times ... \times \Delta_N</math> является <math>\epsilon</math>-равновесием в игре G, если:

<math>u_i(\sigma)\geq u_i(\sigma_i^',\sigma_{-i})-\epsilon</math> для всех <math>\sigma \in \Delta, \sigma_i^' \in \Delta_i</math>

Пример

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

Простейшим примером является следующий вариант игры «Орлянка», предложенный Г. Эвереттом. Игрок 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.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Васин А.А. Некооперативные игры в природе и обществе. М.: Макс Пресс, 2005, 412 с. ISBN 5-317-01306-2.