Стохастична гра в теорії ігор повторювана гра з випадковими переходами станів розігрується одним і більше гравцями Істор

Стохастична гра в теорії ігор — повторювана гра з випадковими переходами станів, розігрується одним і більше гравцями .

Історія

Стохастичні гри були винайдені на початку 1950-х років . Найповнішим їх описом є збірка статей під редакцією А. Ноймана і С. Соріна . Елементарніша книга Дж. Філар і К. Вріз містить загальний виклад теорії марківських процесів прийняття рішень та стохастичних ігор двох осіб. Ними було використано термін конкурентні марковські процеси прийняття рішень (англ. Competitive MDPs) для обозначения стохастических игр одного и двух лиц.

Етапи

Гра розігрується протягом ряду етапів. На початку кожного етапу гра знаходиться в деякому стані. Гравці вибирають свої дії і отримують виграші, залежні від поточного стану і дій. Після цього система переходить випадковим чином в інший стан, розподіл ймовірності переходів залежить від попереднього стану і дій гравців. Ця процедура повторюється протягом скінченного або нескінченного числа кроків. Загальний виграш гравців часто визначається як дисконтована сума виграшів на кожному етапі або нижня межа середніх виграшів за скінченне число кроків.

При скінченному числі гравців, скінченних множинах дій і станів гра з скінченним числом повторень завжди має рівновагу Неша. Це справедливо також для ігор з нескінченним числом повторень, якщо виграші учасників являють собою дисконтовану суму.

показав, що всі стохастичні ігри двох осіб з скінченними множинами станів і дій мають наближену рівновагу Неша, якщо функції виграшу являють собою нижню межу середніх значень виграшу за скінченне число кроків . Питання про існування таких рівноваг в іграх з великою кількістю учасників залишається відкритим.

Застосування

Стохастичні ігри знаходять застосування в економіці і еволюційній біології. Вони являють собою узагальнення повторюваних ігор , які відповідають ситуації, коли є тільки один стан.

Див. також

Ланцюг Маркова

Посилання

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.

[1] Shapley, L.S. Stochastic games // Proc. Nat. Acad. Science. — 1953. — vol. 39. — P. 1095—1100.

[2] Stochastic Games and Applications / A. Neyman, S. Sorin, eds. — Kluwer Academic Press, 2003.

[3] Filar, J., Vrieze, K. Competitive Markov Decision Processes. — Springer-Verlag, 1997.

[4] Vieille, N. Stochastic games: Recent results / In: Handbook of Game Theory. — Elsevier Science, 2002 — P. 1833—1850.