Гра стохастична

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Історія[ред.ред. код]

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

Етапи[ред.ред. код]

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

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

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

Застосування[ред.ред. код]

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


Див. також[ред.ред. код]

Посилання[ред.ред. код]

  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.


Теорія ігор

Типи ігор

антагоністичні · диференціальні · матричні · на виживання · рефлексивні · азартні · без побічних платежів · безкоаліційні · біматричні · вироджені · динамічні · з вибором моменту часу · кооперативні · на графі · на одиничному квадраті · опуклі · позиційні · прості · рекурсивні · стохастичні 

Ситуації

Безвиграшна ситуація · Парадокс Бертрана (економіка) · Ситуація рівноваги 

Стратегія

змішана · оптимальна · поведінки · чиста 

Теореми

Максіміна принцип · Мінімаксу теорема

Ігри

Дилема в'язня · РВ-ПП