Стохастична гра
Стохастична гра в теорії ігор — повторювана гра з випадковими переходами станів, розігрується одним і більше гравцями .
Історія ред.
Стохастичні гри були винайдені Л. Шеплі на початку 1950-х років [1]. Найповнішим їх описом є збірка статей під редакцією А. Ноймана і С. Соріна [2]. Елементарніша книга Дж. Філар і К. Вріз містить загальний виклад теорії марківських процесів прийняття рішень та стохастичних ігор двох осіб[3]. Ними було використано термін конкурентні марковські процеси прийняття рішень (англ. Competitive MDPs) для обозначения стохастических игр одного и двух лиц.
Етапи ред.
Гра розігрується протягом ряду етапів. На початку кожного етапу гра знаходиться в деякому стані. Гравці вибирають свої дії і отримують виграші, залежні від поточного стану і дій. Після цього система переходить випадковим чином в інший стан, розподіл ймовірності переходів залежить від попереднього стану і дій гравців. Ця процедура повторюється протягом скінченного або нескінченного числа кроків. Загальний виграш гравців часто визначається як дисконтована сума виграшів на кожному етапі або нижня межа середніх виграшів за скінченне число кроків.
При скінченному числі гравців, скінченних множинах дій і станів гра з скінченним числом повторень завжди має рівновагу Неша. Це справедливо також для ігор з нескінченним числом повторень, якщо виграші учасників являють собою дисконтовану суму.
Н. Вайель показав, що всі стохастичні ігри двох осіб з скінченними множинами станів і дій мають наближену рівновагу Неша, якщо функції виграшу являють собою нижню межу середніх значень виграшу за скінченне число кроків [4]. Питання про існування таких рівноваг в іграх з великою кількістю учасників залишається відкритим.
Застосування ред.
Стохастичні ігри знаходять застосування в економіці і еволюційній біології. Вони являють собою узагальнення повторюваних ігор , які відповідають ситуації, коли є тільки один стан.
Див. також ред.
Посилання ред.
- ↑ Shapley, L.S. Stochastic games // Proc. Nat. Acad. Science. — 1953. — vol. 39. — P. 1095—1100.
- ↑ Stochastic Games and Applications / A. Neyman, S. Sorin, eds. — Kluwer Academic Press, 2003.
- ↑ Filar, J., Vrieze, K. Competitive Markov Decision Processes. — Springer-Verlag, 1997.
- ↑ Vieille, N. Stochastic games: Recent results / In: Handbook of Game Theory. — Elsevier Science, 2002 — P. 1833—1850.