Стохастическая игра

В теории игр — стохастическая игра (или игра Маркова ), представленная Ллойдом Шепли в начале 1950-х годов. — повторяющаяся игра с вероятностными переходами, в которую играют один или несколько игроков. Игра проводится в несколько этапов. В начале каждого этапа игра находится в каком-то состоянии . Игроки выбирают действия, и каждый игрок получает выигрыш , который зависит от текущего состояния и выбранных действий. Затем игра переходит в новое случайное состояние, распределение которого зависит от предыдущего состояния и действий, выбранных игроками. Процедура повторяется в новом состоянии, и игра продолжается конечное или бесконечное число этапов. Общий выигрыш игрока часто принимается как дисконтированная сумма выигрышей на этапе или нижний предел средних выигрышей на этапе.

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

Игры для двух игроков

Стохастические игры двух игроков на ориентированных графах широко используются для моделирования и анализа дискретных систем, работающих в неизвестной (состязательной) среде. . Возможные конфигурации системы и ее окружения представлены в виде вершин, а переходы соответствуют действиям системы, ее окружения или «природы». Тогда запуск системы соответствует бесконечному пути в графе. Таким образом, систему и ее окружение можно рассматривать как двух игроков с антагонистическими целями, где один игрок (система) стремится максимизировать вероятность «хороших» результатов, а другой игрок (окружающая среда) стремится к противоположному.

Во многих случаях существует равновесное значение этой вероятности, но оптимальных стратегий для обоих игроков может не существовать.

Мы представляем основные понятия и алгоритмические вопросы, изучаемые в этой области, а также упоминаем некоторые давние открытые проблемы. Затем мы упомянем избранные недавние результаты.

Теория

Составляющими стохастической игры являются: конечный набор игроков. $I$; государственное пространство $S$ (либо конечное множество, либо измеримое пространство $(S,{\mathcal {S}})$); для каждого игрока $i\in I$, набор действий $A^{i}$(либо конечное множество, либо измеримое пространство $(A^{i},{\mathcal {A}}^{i})$); вероятность перехода $P$ от $S\times A$, где $A=\times _{i\in I}A^{i}$ это профили действий, $S$, где $P(S\mid s,a)$ это вероятность того, что следующее состояние находится в $S$ учитывая нынешнее состояние $s$ и текущий профиль действий $a$; и функция выигрыша $g$ от $S\times A$ к $R^{I}$, где $i$-я координата $g$, $g^{i}$, — выигрыш игрока $i$ как функция государства $s$ и профиль действия $a$.

Игра начинается с некоторого начального состояния $s_{1}$. На этапе $t$, игроки сначала наблюдают $s_{t}$, затем одновременно выберите действия $a_{t}^{i}\in A^{i}$, затем наблюдайте за профилем действий $a_{t}=(a_{t}^{i})_{i}$, и тогда природа выбирает $s_{t+1}$ по вероятности $P(\cdot \mid s_{t},a_{t})$. Игра в стохастическую игру, $s_{1},a_{1},\ldots ,s_{t},a_{t},\ldots$,определяет поток выплат $g_{1},g_{2},\ldots$, где $g_{t}=g(s_{t},a_{t})$.

Игра со скидкой $\Gamma _{\lambda }$ с дисконтным коэффициентом $\lambda$ ( $0<\lambda \leq 1$) — игра, в которой выигрыш игроку $i$ является $\lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}$. $n$-сценическая играэто игра, в которой выигрыш игроку $i$ является ${\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}$.

Значение $v_{n}(s_{1})$, соответственно $v_{\lambda }(s_{1})$, стохастической игры двух лиц с нулевой суммой $\Gamma _{n}$, соответственно $\Gamma _{\lambda }$, с конечным числом состояний и действий, и Трумэн Бьюли и Илон Кольберг (1976) доказали, что $v_{n}(s_{1})$ сходится к пределу как $n$ уходит в бесконечность и это $v_{\lambda }(s_{1})$ сходится к тому же пределу, что и $\lambda$ идет в $0$.

Игра «без скидки» $\Gamma _{\infty }$ это игра, в которой выигрыш игроку $i$ - это «предел» средних выигрышей на этапах. При определении ценности игры с нулевой суммой двух человек необходимы некоторые меры предосторожности. $\Gamma _{\infty }$ и при определении равновесных выигрышей игрока с ненулевой суммой $\Gamma _{\infty }$. Единое значение $v_{\infty }$ стохастической игры двух лиц с нулевой суммой $\Gamma _{\infty }$ существует, если для каждого $\varepsilon >0$ есть целое положительное число $N$ и стратегическая пара $\sigma _{\varepsilon }$ игрока 1 и $\tau _{\varepsilon }$ игрока 2 такая, что для каждого $\sigma$ и $\tau$ и каждый $n\geq N$ ожидание ${\bar {g}}_{n}^{i}$ относительно вероятности игр, определенных формулой $\sigma _{\varepsilon }$ и $\tau$ по крайней мере $v_{\infty }-\varepsilon$, и ожидание ${\bar {g}}_{n}^{i}$ относительно вероятности игр, определенных формулой $\sigma$ и $\tau _{\varepsilon }$ самое большее $v_{\infty }+\varepsilon$. Жан-Франсуа Мертенс и Абрахам Нейман (1981) доказали, что каждая стохастическая игра двух лиц с нулевой суммой и конечным числом состояний и действий имеет единообразную ценность.

Если существует конечное число игроков, а множества действий и набор состояний конечны, то стохастическая игра с конечным числом этапов всегда имеет равновесие по Нэшу . То же самое верно и для игры с бесконечным количеством этапов, если общий выигрыш равен дисконтированной сумме.

Стохастическая игра с ненулевой суммой $\Gamma _{\infty }$ имеет равновесный равновесный выигрыш $v_{\infty }$ если для каждого $\varepsilon >0$ есть целое положительное число $N$ и профиль стратегии $\sigma$ такая, что при каждом одностороннем отклонении игрока $i$, т. е. профиль стратегии $\tau$ с $\sigma ^{j}=\tau ^{j}$ для всех $j\neq i$и каждый $n\geq N$ ожидание ${\bar {g}}_{n}^{i}$ относительно вероятности игр, определенных формулой $\sigma$ по крайней мере $v_{\infty }^{i}-\varepsilon$, и ожидание ${\bar {g}}_{n}^{i}$ относительно вероятности игр, определяемых формулой $\tau$ самое большее $v_{\infty }^{i}+\varepsilon$. Николя Вьей показал, что все стохастические игры двух лиц с конечными пространствами состояний и действий имеют равномерный равновесный выигрыш.

Стохастическая игра с ненулевой суммой $\Gamma _{\infty }$ имеет предельно средний равновесный выигрыш $v_{\infty }$ если для каждого $\varepsilon >0$ есть профиль стратегии $\sigma$ такая, что при каждом одностороннем отклонении игрока $i$, ожидание предела ниже среднего среднего выигрыша на этапе относительно вероятности игр, определяемых формулой $\sigma$ по крайней мере $v_{\infty }^{i}-\varepsilon$, и ожидание предела, превосходящего средние значения выигрышей на этапе относительно вероятности игр, определяемых формулой $\tau$ самое большее $v_{\infty }^{i}+\varepsilon$. Жан-Франсуа Мертенс и Абрахам Нейман (1981) доказывают, что каждая стохастическая игра с нулевой суммой для двух человек с конечным числом состояний и действий имеет предельное среднее значение, и Николя Вьей показал, что все стохастические игры для двух человек с конечными пространствами состояний и действий имеют равновесный выигрыш в виде предельного среднего. В частности, эти результаты подразумевают, что эти игры имеют ценность и приблизительный равновесный выигрыш, называемый средним по limsup (соответственно, средним по limsup) равновесным выигрышем, когда общий выигрыш равен нижнему пределу (или верхнему пределу) игры. средние выигрыши по этапам.

Вопрос о том, имеет ли каждая стохастическая игра с конечным числом игроков, состояний и действий равномерный равновесный выигрыш, равновесный выигрыш в виде предельного среднего или даже равновесный выигрыш в пределах предела среднего, является сложным открытым вопросом.

— Идеальное равновесие Маркова это уточнение концепции идеального равновесия по Нэшу в подыграх для стохастических игр.

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

Приложения

Стохастические игры находят применение в экономике , эволюционной биологии и компьютерных сетях. Они представляют собой обобщения повторяющихся игр , соответствующие частному случаю, когда существует только одно состояние.

См. также

• Случайный процесс

Дальнейшее чтение

• Филар Дж. и Вриз К. (1997). Конкурентные марковские процессы принятия решений . Спрингер-Верлаг. ISBN  0-387-94805-8 .
• Нейман А. и Сорин С. (2003). Стохастические игры и их приложения . Дордрехт: Kluwer Academic Press. ISBN  1-4020-1492-9 .
• Йоав Шохам; Кевин Лейтон-Браун (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Издательство Кембриджского университета. стр. 153–156 . ISBN  978-0-521-89943-7 . (подходит для студентов; основные результаты, без доказательств)

Внешние ссылки

• Лекция Антонина Кучеры «Стохастические игры для двух игроков»