확률 게임

게임 이론에서 로이드 샤플리가 1950년대 초 선보인 확률형 게임은 한 명 이상의 플레이어가 펼치는 확률적 전환이 반복되는 게임이다.^[1] 그 게임은 일련의 단계로 진행된다. 각 스테이지가 시작될 때 경기는 어떤 상태에 있다. 플레이어는 행동을 선택하고 각 플레이어는 현재 상태와 선택한 행동에 따라 보상을 받는다. 그런 다음 게임은 이전 상태와 플레이어가 선택한 행동에 따라 분포가 달라지는 새로운 무작위 상태로 이동한다. 절차는 새로운 상태에서 반복되며 극은 한정된 또는 무한정 많은 스테이지에 대해 계속된다. 플레이어에 대한 총 보수는 스테이지 보상의 할인된 합계 또는 스테이지 보상의 평균보다 낮은 한도로 간주되는 경우가 많다.

확률형 게임은 마르코프 의사결정 프로세스를 여러 상호 작용하는 의사결정자에게 일반화하며, 전략형 게임은 플레이어들의 선택에 따라 환경이 변화하는 역동적인 상황에 맞춰 일반화한다.^[2]

2인용 게임

지시된 그래프의 확률형 2인용 게임은 알려지지 않은 (수리적) 환경에서 작동하는 이산 시스템의 모델링 및 분석에 널리 사용된다. 시스템과 그 환경의 가능한 구성은 정점으로 표시되며, 전환은 시스템, 그 환경 또는 "자연"의 작용에 해당한다. 그러면 시스템의 실행은 그래프의 무한 경로에 해당된다. 따라서 한 선수(시스템)는 '선행'의 확률 극대화를, 다른 선수(환경)는 정반대를 지향하는 적대적 목표를 가진 두 선수로 볼 수 있다.

많은 경우, 이 확률의 평형값이 존재하지만, 두 선수 모두를 위한 최적의 전략은 존재하지 않을 수 있다.

We introduce basic concepts and algorithmic questions studied in this area, and we mention some long-standing open problems. Then, we mention selected recent results.

Theory

The ingredients of a stochastic game are: a finite set of players ${\displaystyle I}$; a state space ${\displaystyle M}$ (either a finite set or a measurable space ${\displaystyle (M,{\mathcal {A}})}$); for each player ${\displaystyle i\in I}$, an action set ${\displaystyle S^{i}}$ (either a finite set or a measurable space ${\displaystyle (S^{i},{\mathcal {S}}^{i})}$); a transition probability ${\displaystyle P}$ from ${\displaystyle M\times S}$, where ${\displaystyle S=\times _{i\in I}S^{i}}$ is the action profiles, to ${\displaystyle M}$, where ${\displaystyle P(A\mid m,s)}$ is the probability that the next state is in ${\displaystyle A}$ given the current state ${\displaystyle m}$ and the current action profile ${\displaystyle s}$; and a payoff function ${\displaystyle g}$ from ${\displaystyle M\times S}$ to ${\displaystyle R^{I}}$, where the ${\displaystyle i}$-th coordinate of ${\displaystyle g}$, ${\displaystyle g^{i}}$, is the payoff to player ${\displaystyle i}$ as a function of the state ${\displaystyle m}$ and the action profile ${\displaystyle s}$.

게임은 어떤 초기 $상태{\displaystyle {}_{}}$ m ${\displaystyle 1_{}}$에서 시작된다$.$ $stage{\displaystyle }$ t$${\$displaystyle$ $m_{t$$},$ 플레이어는 $먼저{\displaystyle {}_{}}$ m ${\displaystyle t_{}}$ ${\$$displaystyle m_{t}},$ ${\displaystyle {그리고}_{}^{}}$ 동시에 동작 ${\displaystyle {}^{}}$를 선택하고$,$ $동작$ ${\displaystyle {프로파일}_{}}$ $t{\displaystyle {}_{}}$=${\displaystyle }$( ${\displaystyle {}_{}^{}{}_{}}$) ${$${\displaystyle {}_{}^{}}$}{$i}}}$을 관찰한다.$displaystyle s_{t}=(s_{t}^{i})_{i}}$, and then nature selects ${\displaystyle m_{t+1}}$ according to the probability ${\displaystyle P(\cdot \mid m_{t},s_{t})}$. A play of the stochastic game, ${\displaystyle m_{1},s_{1},\ldots ,m_{t},s_{t},\ldot$$s }$은$($는) g $1{\displaystyle {}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$… ${\displaystyle g_{1},g_{2},\ldots },$여기서 ${\displaystyle g_{}}$ = ${\displaystyle g({}_{}}$ ${\displaystyle t_{}}$ s ${\displaystyle t_{}}$) ${\displaystyle g_{t}=g(m_{t},s_{t})}$의 지급 스트림을 정의한다$.$

The discounted game ${\displaystyle \Gamma _{\lambda }}$ with discount factor ${\displaystyle \lambda }$ (${\displaystyle 0<\lambda \leq 1}$) is the game where the payoff to player ${\displaystyle i}$ is ${\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}}$. The ${\displaystyle n}$-stage game is the game where the payoff to player ${\displaystyle i}$ is ${\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}$.

The value ${\displaystyle v_{n}(m_{1})}$, respectively ${\displaystyle v_{\lambda }(m_{1})}$, of a two-person zero-sum stochastic game ${\displaystyle \Gamma _{n}}$, respectively ${\displaystyle \Gamma _{\lambda }}$, with finitely many states and actions exists, and Truman Bewley and Elon Kohlberg (1976) proved that ${\displaystyle v_{n}(m_{1})}$ converges to a limit as ${\displaystyle n}$ goes to infinity and that ${\displaystyle v_{\lambda }(m_{1})}$ converges to the same limit as ${\displaystyle \lambda }$ goes to ${\displaystyle 0}$.

The "undiscounted" game ${\displaystyle \Gamma _{\infty }}$ is the game where the payoff to player ${\displaystyle i}$ is the "limit" of the averages of the stage payoffs. Some precautions are needed in defining the value of a two-person zero-sum ${\displaystyle \Gamma _{\infty }}$ and in defining equilibrium payoffs of a non-zero-sum ${\displaystyle \Gamma _{\infty }}$. The uniform value ${\displaystyle v_{\infty }}$ of a two-person zero-sum stochastic game ${\displaystyle \Gamma _{\infty }}$ exists if for every ${\displaystyle \varepsilon >0}$ there is a positive integer ${\displaystyle N}$ and a strategy pair ${\displaystyle \sigma _{\varepsilon }}$ of player 1 and ${\displaystyle \tau _{\varepsilon }}$ of player 2 such that for every ${\displaystyle \sigma }$ and ${\displaystyle \tau }$ and every ${\displaystyle n\geq N}$ the expectation of ${\displaystyle {\bar {g}}_{n}^{i}}$ with respect to the probability on plays defined by ${\displaystyle \sigma _{\varepsilon }}$ and ${\displaystyle \tau }$ is at least ${\displaystyle v_{\infty }-\varepsilon }$, and the expectation of ${\displaystyle {\bar {g}}_{n}^{i}}$ with respect to the probability on plays defined by ${\displaystyle \sigma }$ and ${\displaystyle \tau _{\varepsilon }}$ is at most ${\displaystyle v_{\infty }+\varepsilon }$. Jean-François Mertens and Abraham Neyman (1981) proved that every two-person zero-sum stochastic game with finitely many states and actions has a uniform value.^[3]

If there is a finite number of players and the action sets and the set of states are finite, then a stochastic game with a finite number of stages always has a Nash equilibrium. The same is true for a game with infinitely many stages if the total payoff is the discounted sum.

The non-zero-sum stochastic game ${\displaystyle \Gamma _{\infty }}$ has a uniform equilibrium payoff ${\displaystyle v_{\infty }}$ if for every ${\displaystyle \varepsilon >0}$ there is a positive integer ${\displaystyle N}$ and a strategy profile ${\displaystyle \sigma }$ such that for every unilateral deviation by a player ${\displaystyle i}$, i.e., a strategy profile ${\displaystyle \tau }$ with ${\displaystyle \sigma ^{j}=\tau ^{j}}$ for all ${\displaystyle j\neq i}$, and every ${\displaystyle n\geq N}$ the expectation of ${\displaystyle {\bar {g}}_{n}^{i}}$ with respect to the probability on plays defined by ${\displaystyle \sigma }$ is at least ${\displaystyle v_{\infty }^{i}-\varepsilon }$, and the expectation of ${\displaystyle {\bar {g}}_{n}^{i}}$ with respect to the probability on plays defined by ${\displaystyle \tau }$ is at most ${\displaystyle v_{\infty }^{i}+\varepsilon }$. Nicolas Vieille has shown that all two-person stochastic games with finite state and action spaces have a uniform equilibrium payoff.^[4]

The non-zero-sum stochastic game ${\displaystyle \Gamma _{\infty }}$ has a limiting-average equilibrium payoff ${\displaystyle v_{\infty }}$ if for every ${\displaystyle \varepsilon >0}$ there is a strategy profile ${\displaystyle \sigma }$ such that for every unilateral deviation by a player ${\displaystyle i}$, the expectation of the limit inferior of the averages of the stage payoffs with respect to the probability on plays defined by ${\displaystyle \sigma }$ is at least ${\displaystyle v_{\infty }^{i}-\varepsilon }$, and the expectation of the limit superior of the averages of the stage payoffs with respect to the probability on plays defined by ${\displaystyle \tau }$ is at most ${\displaystyle v_{\infty }^{i}+\varepsilon }$. Jean-François Mertens and Abraham Neyman (1981) proves that every two-person zero-sum stochastic game with finitely many states and actions has a limiting-average value,^[3] and Nicolas Vieille has shown that all two-person stochastic games with finite state and action spaces have a limiting-average equilibrium payoff.^[4] In particular, these results imply that these games have a value and an approximate equilibrium payoff, called the liminf-average (respectively, the limsup-average) equilibrium payoff, when the total payoff is the limit inferior (or the limit superior) of the averages of the stage payoffs.

Whether every stochastic game with finitely many players, states, and actions, has a uniform equilibrium payoff, or a limiting-average equilibrium payoff, or even a liminf-average equilibrium payoff, is a challenging open question.

A Markov perfect equilibrium is a refinement of the concept of sub-game perfect Nash equilibrium to stochastic games.

Stochastic games have been combined with Bayesian games to model uncertainty over player strategies.^[5] The resulting "stochastic Bayesian game" model is solved via a recursive combination of the Bayesian Nash equilibrium equation and the Bellman optimality equation.

Applications

Stochastic games have applications in economics, evolutionary biology and computer networks.^[6][7] They are generalizations of repeated games which correspond to the special case where there is only one state.

See also

• Stochastic process

Notes

Further reading

• Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag. ISBN 0-387-94805-8.
• Neyman, A. & Sorin, S. (2003). Stochastic Games and Applications. Dordrecht: Kluwer Academic Press. ISBN 1-4020-1492-9.
• Yoav Shoham; Kevin Leyton-Brown (2009). Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press. pp. 153–156. ISBN 978-0-521-89943-7. (suitable for undergraduates; main results, no proofs)

External links

• Lecture on Stochastic Two-Player Games by Antonin Kucera