確率ゲーム

ゲーム理論において、確率ゲーム（またはマルコフゲーム）は、1950年代初頭にロイド・シャプレーによって提唱され^{[1] 、1人以上のプレイヤーによって行われる}確率的遷移を伴う繰り返しゲームである。ゲームは段階的に行われる。各段階の開始時、ゲームはある状態にある。プレイヤーは行動を選択し、各プレイヤーは現在の状態と選択した行動に応じた報酬を受け取る。次に、ゲームは新しいランダムな状態に移行し、その分布は前の状態とプレイヤーが選択した行動に依存する。この手順は新しい状態で繰り返され、有限または無限の数の段階にわたってゲームが続行される。プレイヤーへの総報酬は、段階報酬の割引合計、または段階報酬の平均の 極限下側であることが多い。

確率ゲームはマルコフ決定プロセスを複数の相互作用する意思決定者に一般化し、戦略型ゲームをプレイヤーの選択に応じて環境が変化する動的な状況に一般化します。^[2]

有向グラフ上の確率的 2 人用ゲームは、未知の (敵対的な) 環境で動作する離散システムのモデリングと分析に広く使用されています^[要出典]。システムとその環境の可能な構成は頂点として表され、遷移はシステム、その環境、または「性質」のアクションに対応します。システムの実行は、グラフ内の無限パスに対応します。したがって、システムとその環境は、敵対的な目的を持つ 2 人のプレーヤーとして考えることができます。一方のプレーヤー (システム) は「良い」実行の確率を最大化することを目指し、もう一方のプレーヤー (環境) は反対のことを目標とします。

多くの場合、この確率の均衡値は存在しますが、両方のプレイヤーにとって最適な戦略は存在しない可能性があります。

この分野で研究されている基本的な概念とアルゴリズムの問​​題を紹介し、長年未解決となっているいくつかの問題について言及します。その後、最近の結果をいくつか紹介します。

確率的ゲームの要素は、プレイヤーの有限集合、状態空間（有限集合または測定可能な空間）、各プレイヤー のアクション集合 （有限集合または測定可能な空間）、から への遷移確率（ここではアクション プロファイル ）、は現在の状態と現在のアクション プロファイルが与えられた場合に次の状態が である確率、 からへのペイオフ関数（ここでは の- 番目の座標、は状態とアクション プロファイルの関数としてのプレイヤー へのペイオフ）です。 ${\displaystyle I}$${\displaystyle S}$ ${\displaystyle (S,{\mathcal {S}})}$${\displaystyle i\in I}$${\displaystyle A^{i}}$${\displaystyle (A^{i},{\mathcal {A}}^{i})}$${\displaystyle P}$${\displaystyle S\times A}$${\displaystyle A=\times _{i\in I}A^{i}}$${\displaystyle S}$${\displaystyle P(S\mid s,a)}$${\displaystyle S}$${\displaystyle s}$${\displaystyle a}$${\displaystyle g}$${\displaystyle S\times A}$${\displaystyle R^{I}}$${\displaystyle i}$${\displaystyle g}$${\displaystyle g^{i}}$${\displaystyle i}$${\displaystyle s}$${\displaystyle a}$

ゲームは、ある初期状態から始まります。 ステージ では、プレイヤーはまず を観察し、同時にアクションを選択し、アクション プロファイルを観察し、確率 に従って自然が選択します。 確率ゲーム のプレイは、のペイオフ ストリームを定義します。 ${\displaystyle s_{1}}$${\displaystyle t}$${\displaystyle s_{t}}$${\displaystyle a_{t}^{i}\in A^{i}}$${\displaystyle a_{t}=(a_{t}^{i})_{i}}$${\displaystyle s_{t+1}}$${\displaystyle P(\cdot \mid s_{t},a_{t})}$${\displaystyle s_{1},a_{1},\ldots ,s_{t},a_{t},\ldots }$${\displaystyle g_{1},g_{2},\ldots }$${\displaystyle g_{t}=g(s_{t},a_{t})}$

割引係数( ) を持つ割引ゲームは、プレイヤーの利得が であるゲームです。段階ゲームは、プレイヤーの利得が であるゲームです。 ${\displaystyle \Gamma _{\lambda }}$${\displaystyle \lambda}$${\displaystyle 0<\lambda \leq 1}$${\displaystyle i}$${\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}}$${\displaystyle n}$${\displaystyle i}$${\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}$

有限個の状態と行動を持つ2人ゼロ和確率ゲーム の値が存在し、 Truman Bewleyと Elon Kohlberg (1976)は、 が無限大に近づくにつれて が極限に収束し、 がに近づくにつれて が同じ極限に収束することを証明しました。 ${\displaystyle v_{n}(s_{1})}$${\displaystyle v_{\lambda }(s_{1})}$${\displaystyle \Gamma_{n}}$${\displaystyle \Gamma _{\lambda }}$${\displaystyle v_{n}(s_{1})}$${\displaystyle n}$${\displaystyle v_{\lambda }(s_{1})}$${\displaystyle \lambda}$${\displaystyle 0}$

「割引なし」ゲーム とは、プレイヤーへの報酬がステージ報酬の平均の「極限」であるゲームである。2人ゼロサムゲームの値の定義と、非ゼロサムゲームの均衡報酬の定義には、いくつかの注意が必要である。2人ゼロサム確率ゲームの一様値が存在するのは、すべての に対して、正の整数とプレイヤー1とプレイヤー2の 戦略ペアが存在し、すべてのおよびおよびすべてのに対して、およびで定義されるプレイの確率に関する の期待値が少なくとも であり、および で定義されるプレイの確率に関する の期待値が 最大で である場合である。Jean -François MertensとAbraham Neyman (1981) は、有限個数の状態とアクションを持つすべての2人ゼロサム確率ゲームは一様値を持つことを証明した。^[3]${\displaystyle \Gamma _{\infty }}$${\displaystyle i}$${\displaystyle \Gamma _{\infty }}$${\displaystyle \Gamma _{\infty }}$${\displaystyle v_{\infty }}$${\displaystyle \Gamma _{\infty }}$${\displaystyle \varepsilon >0}$${\displaystyle N}$${\displaystyle \sigma _{\varepsilon }}$${\displaystyle \tau _{\varepsilon }}$${\displaystyle \sigma }$${\displaystyle \tau }$${\displaystyle n\geq N}$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \sigma _{\varepsilon }}$${\displaystyle \tau }$${\displaystyle v_{\infty }-\varepsilon }$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \sigma }$${\displaystyle \tau _{\varepsilon }}$${\displaystyle v_{\infty }+\varepsilon }$

プレイヤーの数が有限で、アクション セットと状態のセットが有限である場合、有限数のステージを持つ確率ゲームには常にナッシュ均衡が存在します。合計の報酬が割引合計である場合、ステージ数が無限のゲームでも同じことが言えます。

非ゼロ和確率ゲームが一様均衡ペイオフを持つとは、任意の に対して正の整数 と戦略プロファイルが存在し、プレイヤーによる任意の一方的逸脱 に対して となる戦略プロファイル、つまり、すべてのに対して となる戦略プロファイルが あり、任意の によって定義されるプレイの確率に関する の期待値は少なくとも であり、によって定義されるプレイの確率に関する の 期待値は最大で であることを意味します。Nicolas Vieille は、有限の状態空間と行動空間を持つすべての 2 人確率ゲームが一様均衡ペイオフを持つことを示しました。^[4]${\displaystyle \Gamma _{\infty }}$${\displaystyle v_{\infty }}$${\displaystyle \varepsilon >0}$${\displaystyle N}$${\displaystyle \sigma }$${\displaystyle i}$${\displaystyle \tau }$${\displaystyle \sigma ^{j}=\tau ^{j}}$${\displaystyle j\neq i}$${\displaystyle n\geq N}$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \sigma }$${\displaystyle v_{\infty }^{i}-\varepsilon }$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \tau }$${\displaystyle v_{\infty }^{i}+\varepsilon }$

非ゼロ和確率ゲームが極限平均均衡ペイオフを持つとは、任意の に対して、プレイヤー による任意の一方的逸脱に対して、 によって定義されるプレイの確率に関するステージ ペイオフの平均の極限劣位の期待値が少なくとも であり、 によって定義されるプレイの確率に関するステージ ペイオフの平均の極限優位の期待値が 最大で であるような戦略プロファイルが存在する場合です。Jean -François MertensとAbraham Neyman (1981) は、有限の数の状態と行動を持つすべての 2 人ゼロ和確率ゲームが極限平均値を持つことを証明しています。^[3]また Nicolas Vieille は、有限の状態空間と行動空間を持つすべての 2 人確率ゲームが極限平均均衡ペイオフを持つことを示しています。^[4]特に、これらの結果は、総報酬がステージ報酬の平均の限界劣位（または限界優位）であるとき、これらのゲームには価値と近似均衡報酬（それぞれ限界平均（または限界超平均）均衡報酬と呼ばれる）があることを示唆している。 ${\displaystyle \Gamma _{\infty }}$${\displaystyle v_{\infty }}$${\displaystyle \varepsilon >0}$${\displaystyle \sigma }$${\displaystyle i}$${\displaystyle \sigma }$${\displaystyle v_{\infty }^{i}-\varepsilon }$${\displaystyle \tau }$${\displaystyle v_{\infty }^{i}+\varepsilon }$

有限数のプレイヤー、状態、アクションを持つすべての確率ゲームが均一な均衡報酬を持つのか、それとも極限平均均衡報酬を持つのか、あるいは極限平均均衡報酬を持つのかは、難しい未解決の問題です。

マルコフ完全均衡は、サブゲーム完全ナッシュ均衡の概念を確率ゲームに改良したものです。

確率的ゲームはベイジアンゲームと組み合わせて、プレイヤーの戦略に関する不確実性をモデル化してきました。^[5]結果として得られる確率的ベイジアンゲームモデルは、ベイジアンナッシュ均衡方程式とベルマン最適性方程式の再帰的組み合わせによって解かれます。

確率ゲームは経済学、進化生物学、コンピュータネットワークに応用されている。 ^{[6] [7]確率ゲームは}繰り返しゲーム を一般化したものであり、状態が1つしかない特殊なケースに対応する。

• 確率過程

• Filar, J. & Vrieze, K. (1997)。競争的マルコフ決定プロセス。スプリンガー・フェルラーク。ISBN 0-387-94805-8。
• Neyman, A. & Sorin, S. (2003).確率ゲームとその応用. ドルドレヒト: Kluwer Academic Press. ISBN 1-4020-1492-9。
• Yoav Shoham、Kevin Leyton-Brown (2009)。マルチエージェントシステム：アルゴリズム、ゲーム理論、論理的基礎。ケンブリッジ大学出版局。pp. 153–156。ISBN 978-0-521-89943-7。（学部生向け、主な結果、証明なし）

• アントニン・クセラによる確率的2人用ゲームに関する講義