拡張形式のゲーム

ゲーム理論において、展開形式ゲームとは、（名前が示すように）プレイヤーの可能な動きの順序、各決定ポイントでの選択、各プレイヤーが決定を下す際に他のプレイヤーの動きについて持つ（おそらく不完全な）情報、すべての可能なゲーム結果に対する各プレイヤーの利得など、いくつかの重要な側面を明示的に表現できるゲームの仕様です。展開形式ゲームでは、不完全な情報を「自然な動き」としてモデル化された偶然のイベントの形で表現することもできます。展開形式の表現は、問題のゲームをより完全に記述する点で通常形式とは異なりますが、通常形式はゲームを利得マトリックスに単純に要約します。

一部の著者は、特に入門書では、展開型ゲームを、ペイオフ（不完全または不完全な情報なし）を持つゲームツリーとして最初に定義し、その後の章で他の要素を改良として追加します。この記事の残りの部分では、動機付けとなる例を挙げてこの穏やかなアプローチに従いますが、ここでは、（最終的に）構築された有限展開型ゲームを最初に示します。この一般的な定義は、1928 年のフォン ノイマンの以前の定義を拡張したHarold W. Kuhnによって 1953 年に導入されました。Hart (1992) の発表に従うと、nプレーヤー展開型ゲームは次の要素で構成されます。

• n人の（合理的な）プレイヤーの有限集合
• ゲームツリーと呼ばれる根付いた木
• ゲームツリーの各末端（葉）ノードにはn組の報酬があり、これは各プレイヤーがプレイする可能性のあるすべてのゲームの最後に1つの報酬があることを意味する。
• ゲーム ツリーの非終端ノードをn +1 個のサブセットに分割したもので、各 (合理的な) プレーヤーに 1 つずつ、および Chance (または Nature) と呼ばれる架空のプレーヤー用の特別なサブセットが含まれます。各プレーヤーのノードのサブセットは、「プレーヤーのノード」と呼ばれます。(したがって、完全情報のゲームには Chance ノードの空セットがあります。)
• チャンス プレーヤーの各ノードには、その出力エッジにわたる確率分布があります。
• 合理的なプレイヤーのノードの各セットは、情報セットにさらに分割され、次の意味で、プレイヤーが移動を行うときに特定の選択を区別できなくなります。
  • 同じ情報セットの任意の2つのノードの出力エッジ間には1対1の対応があり、したがって、情報セットのすべての出力エッジの集合は同値クラスに分割され、各クラスは、ある時点でのプレーヤーの動きの可能な選択肢を表します。
  • ルートから終端ノードまでのツリー内の各（有向）パスは、各情報セットを最大1回交差できる。
• 上記のパラメータで指定されたゲームの完全な説明は、プレイヤーの間では周知の事実である

したがって、プレイは、ルートからターミナル ノードまでのツリーのパスです。チャンスに属する任意の非ターミナル ノードでは、確率分布に従って出力ブランチが選択されます。任意の合理的なプレーヤーのノードでは、プレーヤーはエッジの同値クラスの 1 つを選択する必要があります。これにより、正確に 1 つの出力エッジが決定されますが、(一般に) プレーヤーはどのエッジが使用されているかはわかりません。(その時点までの他のすべてのプレーヤーの選択と自然の動きの実現を知っている外部の観察者は、エッジを正確に決定できます。)したがって、プレーヤーの純粋な戦略は、選択で構成されます。つまり、(自分の) すべての情報セットに対して、正確に 1 つの出力エッジ クラスを選択します。完全情報のゲームでは、情報セットはシングルトンです。チャンス ノードを持つゲームでペイオフをどのように解釈すべきかは、あまり明らかではありません。各プレーヤーには、すべてのゲーム結果に対して定義されたフォン ノイマン-モルゲンシュテルンの効用関数があると想定されます。この想定は、すべての合理的なプレーヤーが、その期待効用によって事前ランダムな結果を評価することを意味します。

上記の説明では、ゲームがプレイされる数学的構造を正確に定義していますが、「プレイヤーは意思決定を行う際に同じ情報セット内のノードを区別できない」など、ゲームのプレイ方法に関するステートメントを形式化するというより技術的な議論は省略されています。これらは、認識論的様相論理を使用して正確にすることができます。詳細については、Shoham & Leyton-Brown (2009、第 13 章) を参照してください。

ゲームツリー（組合せゲーム理論と人工知能で定義される）上の完全情報2人用ゲームは、結果（勝ち、負け、引き分け）を伴う展開形ゲームとして表現できる。このようなゲームの例としては、三目並べ、チェス、無限チェスなどがある。^{[1] [2]}バックギャモンのような期待ミニマックスツリー上のゲームには不完全情報はないが（すべての情報セットはシングルトン）、偶然の動きがある。たとえば、ポーカーには偶然の動き（配られるカード）と不完全情報（他のプレイヤーが秘密に持っているカード）の両方がある。（Binmore 2007、第2章）

完全な拡張形式表現では以下を指定します。

1. ゲームのプレイヤー
2. すべての選手が移動する機会を得られる
3. 各プレイヤーがそれぞれの動きで何ができるか
4. 各プレイヤーが各動きについて知っていること
5. あらゆる可能な動きの組み合わせに対して各プレイヤーが受け取る報酬

右側のゲームには、プレイヤー 1 と 2 の 2 人のプレイヤーがいます。すべての非終端ノードの数字は、その決定ノードがどのプレイヤーに属しているかを示します。すべての終端ノードの数字は、プレイヤーへの報酬を表します (例: 2,1 は、プレイヤー 1 への報酬 2 とプレイヤー 2 への報酬 1 を表します)。グラフのすべてのエッジのラベルは、エッジが表すアクションの名前です。

最初のノードはプレイヤー 1 に属し、プレイヤー 1 が最初に動くことを示しています。ツリーに従ったプレイは次のようになります。プレイヤー 1 はUとDのどちらかを選択します。プレイヤー 2 はプレイヤー 1 の選択を観察し、次にU'とD' のどちらかを選択します。報酬はツリーで指定されたとおりです。ツリーの 4 つの終端ノードによって表される 4 つの結果は、(U,U')、(U,D')、(D,U')、(D,D') です。各結果に関連付けられた報酬は、それぞれ (0,0)、(2,1)、(1,2)、(3,1) です。

プレイヤー 1 がD をプレイする場合、プレイヤー 2 は利益を最大化するために U' をプレイするため、プレイヤー 1 は 1 のみを受け取ります。しかし、プレイヤー 1 がU をプレイする場合、プレイヤー 2 はD' をプレイすることで利益を最大化し、プレイヤー 1 は 2 を受け取ります。プレイヤー 1 は 1 よりも 2 を好むため、U をプレイし、プレイヤー 2 はD' をプレイします。これがサブゲームの完全均衡です。

ゲームをこのように表現する利点は、プレイの順序が明確になることです。ツリーでは、プレーヤー 1 が最初に動き、プレーヤー 2 がその動きを観察することが明確に示されています。ただし、一部のゲームでは、プレイはこのように行われません。1 人のプレーヤーが常に別のプレーヤーの選択を観察するわけではありません (たとえば、動きが同時に起こったり、動きが隠されたりすることがあります)。情報セットは、次のような決定ノードのセットです。

1. セット内のすべてのノードは 1 人のプレイヤーに属します。
2. ゲームが情報セットに到達すると、移動しようとしているプレイヤーは情報セット内のノードを区別できません。つまり、情報セットに複数のノードが含まれている場合、そのセットが属するプレイヤーはセット内のどのノードに到達したかわかりません。

拡張形式では、情報セットは、そのセット内のすべてのノードを接続する点線で示されますが、場合によっては、そのセット内のすべてのノードの周りに描かれたループで示されます。

ゲームに複数の要素を持つ情報集合がある場合、そのゲームは不完全情報を持つと言われます。完全情報を持つゲームでは、ゲームのどの段階でも、すべてのプレイヤーがゲームの前に何が起こったかを正確に知っています。つまり、すべての情報集合は単一の集合です。^{[1] [2]}完全情報を持たないゲームは不完全情報を持ちます。

右側のゲームは、プレイヤー 2 がプレイするときにプレイヤー 1 が何をするかを知らないことを除いて、上記のゲームと同じです。最初に説明したゲームには完全な情報がありますが、右側のゲームには完全情報がありません。両方のプレイヤーが合理的であり、両方のプレイヤーが両方とも合理的であることを知っており、どのプレイヤーが知っていることはすべて、どのプレイヤーも知っていることがわかっている場合（つまり、プレイヤー 1 は、プレイヤー 2 がプレイヤー 1 が合理的であることを知っていることを知っており、プレイヤー 2 もこれを知っている、などと無限に続く） 、最初のゲームのプレイは次のようになります。プレイヤー 1 は、 U をプレイすると、プレイヤー2 がD' をプレイすることを知っているため（プレイヤー 2 にとって、ペイオフ 1 はペイオフ 0 よりも好ましいため）、プレイヤー 1 は 2 を受け取ります。しかし、プレイヤー 1 がD をプレイすると、プレイヤー 2 はU' をプレイし（プレイヤー 2 にとって、ペイオフ 2 はペイオフ 1 よりも好ましいため）、プレイヤー 1 は 1 を受け取ります。したがって、最初のゲームでは、均衡は ( U、D' ) になります。これは、プレイヤー 1 は 1 よりも 2 を受け取ることを好み、U をプレイし、プレイヤー 2 はD' をプレイするためです。

2 番目のゲームでは、それほど明確ではありません。プレイヤー 2 はプレイヤー 1 の動きを観察できません。プレイヤー 1 は、プレイヤー 2 が実際にはD をプレイしているのにU をプレイしたと思わせ、プレイヤー 2 がD' をプレイしてプレイヤー 1 が 3 を受け取るようにしたいと考えています。実際、2 番目のゲームでは、プレイヤー 1 がD をプレイし、プレイヤー 2 がU'をプレイし、プレイヤー 2 がプレイヤー 1 が間違いなくD をプレイするという信念を抱いている完全なベイズ均衡が存在します。この均衡では、すべての戦略は、保持されている信念を前提として合理的であり、すべての信念はプレイされた戦略と一致しています。情報の不完全性がゲームの結果をどのように変えるかに注目してください。

このゲームをより簡単にナッシュ均衡について解くには、^[3]通常の形式に変換することができます。^[4]これは同時/順次ゲームなので、プレイヤー1とプレイヤー2はそれぞれ2つの戦略を持ちます。^[5]

• プレイヤー1の戦略: {U , D}
• プレイヤー2の戦略: {U' , D'}

動きの組み合わせごとに固有の報酬を持つ 2 x 2 のマトリックスが作成されます。通常の形式のゲームを使用すると、ゲームを解決し、両方のプレーヤーの優位な戦略を特定できるようになります。

• プレイヤー1が上（U）をプレイする場合、プレイヤー2は下（D'）をプレイすることを好みます（ペイオフ1>0）
• プレイヤー1がダウン（D）をプレイした場合、プレイヤー2はアップ（U'）をプレイすることを好みます（ペイオフ2>1）
• プレイヤー2が上（U'）をプレイする場合、プレイヤー1は下（D）をプレイすることを好みます（ペイオフ1>0）
• プレイヤー2がダウン（D'）をプレイする場合、プレイヤー1はダウン（D）をプレイすることを好む（3>2）

これらの好みはマトリックス内でマークすることができ、両方のプレイヤーが好みを持っているボックスはナッシュ均衡を提供します。この特定のゲームには、(D,U') の単一の解があり、報酬は (1,2) です。

無限の行動空間と不完全な情報を持つゲームでは、必要に応じて、上記の弧の後ろの（非ノード）エンドポイントを接続する点線を挿入するか、弧自体を破線にすることによって、非シングルトン情報セットが表されます。上記のスタックルベルク競争では、2 番目のプレーヤーが最初のプレーヤーの動きを観察していなかった場合、ゲームはスタックルベルク モデルに適合しなくなり、クールノー競争になります。

プレイヤーがゲームの報酬が正確にいくらなのか、対戦相手がどんなタイプなのかを知らない場合があります。この種のゲームは不完全情報です。拡張形式では、いわゆるハルサニ変換を使用して、完全だが不完全な情報を持つゲームとして表現されます。この変換により、ゲームに自然の選択または神の選択という概念が導入されます。雇用主が求職者を雇うかどうかを検討しているゲームを考えてみましょう。求職者の能力は、高いか低いかの 2 つのいずれかです。能力レベルはランダムです。低い能力が確率 1/3 で、高い能力が確率 2/3 で発生します。この場合、自然を、それらの確率に従って求職者の能力を選択する別のプレイヤーとしてモデル化するのが便利です。ただし、自然には報酬はありません。自然の選択は、ゲーム ツリーでは塗りつぶされていないノードによって表されます。自然の選択ノードから来るエッジには、それが表すイベントが発生する確率がラベル付けされます。

左側のゲームは、完全情報（すべてのプレイヤーと利得は全員に知られている）のゲームだが、不完全情報（雇用主は自然の動きが何であったかを知らない）のゲームである。最初のノードは中央にあり、埋められていないため、自然が最初に動く。自然は同じ確率でプレイヤー 1 のタイプ（このゲームでは、プレイされるサブゲームの利得を選択することに等しい）t1 または t2 を選択する。プレイヤー 1 はこれらについて異なる情報セットを持っている。つまり、プレイヤー 1 はそれらがどのタイプであるかを知っている（必ずしもそうである必要はない）。しかし、プレイヤー 2 は自然の選択を観察しない。彼らはプレイヤー 1 のタイプを知らないが、このゲームではプレイヤー 1 の行動を観察している。つまり、完全情報がある。実際、ここで上記の完全情報の定義を変更するのが適切である。ゲームのすべての段階で、すべてのプレイヤーは他のプレイヤーが何をプレイしたかを知っている。秘密情報の場合、すべてのプレイヤーは自然が何をプレイしたかを知っています。情報セットは前と同じように破線で表されます。

このゲームでは、自然がプレイヤー 1 のタイプとして t1 を選択した場合、プレイされるゲームは、プレイヤー 2 がそれを知らないことを除いて、最初に説明したゲームと同じになります (そして、これが彼らの情報セットを切り抜けるという事実自体が、サブゲームの状態から不適格になります)。分離する 完全なベイズ均衡が1 つあります。つまり、異なるタイプが異なることを行う均衡です。

両方のタイプが同じアクション (プーリング) をプレイすると、均衡は維持できません。両方がD をプレイする場合、プレイヤー 2 は、情報セット内のいずれかのノードに確率 1/2 で存在するという信念しか形成できません (これは、いずれかのタイプが表示される可能性であるため)。プレイヤー 2 は、 D' をプレイすることで報酬を最大化します。ただし、D' をプレイする場合、タイプ 2 はU をプレイすることを好みます。これは均衡にはなりません。両方のタイプがUをプレイすると、プレイヤー 2 は、確率 1/2 でいずれかのノードに存在するという信念を再び形成します。この場合、プレイヤー 2 はD'をプレイしますが、タイプ 1 はD をプレイすることを好みます。

タイプ 1 がU をプレイし、タイプ 2 がD をプレイした場合、プレイヤー 2は観察したアクションに関係なくD' をプレイしますが、タイプ 1 はD を優先します。したがって、唯一の均衡は、タイプ 1 がD をプレイし、タイプ 2 がU をプレイし、プレイヤー 2 がDを観察した場合はU' をプレイし、 U を観察した場合はランダム化することです。プレイヤー 1 は、自分のアクションを通じて、プレイヤー 2 に自分のタイプ を伝えています。

正式には、展開形の有限ゲームとは次のような構造です 。 ${\displaystyle \Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\ {A(H)\}_{H\in \mathbf {H} },a,\rho ,u\rangle }$

• ${\displaystyle {\mathcal {K}}=\langle V,v^{0},T,p\rangle }$は、ノードの集合、一意の初期ノード、終端ノードの集合（決定ノードの集合とする）、およびゲームのルールが表現される直前の先行関数を持つ有限木である。${\displaystyle V}$${\displaystyle v^{0}\in V}$${\displaystyle T\subset V}$${\displaystyle D=V\setminus T}$${\displaystyle p:V\rightarrow D}$
• ${\displaystyle \mathbf {H} }$情報パーティションと呼ばれるパーティションです。${\displaystyle D}$
• ${\displaystyle A(H)}$は、すべてのアクションのセット上のパーティションを形成する各情報セットに対して利用可能なアクションのセットです。${\displaystyle H\in \mathbf {H} }$${\displaystyle {\mathcal {A}}}$
• ${\displaystyle a:V\setminus \{v^{0}\}\rightarrow {\mathcal {A}}}$は、各ノードを単一のアクションに関連付けるアクションパーティションであり、次の条件を満たします。${\displaystyle v}$${\displaystyle a(v)}$

${\displaystyle \forall H\in \mathbf {H} ,\forall v\in H}$の場合、の制約はの後継ノードの集合と一対一になります。 ${\displaystyle a_{v}:s(v)\rightarrow A(H)}$${\displaystyle a}$${\displaystyle s(v)}$${\displaystyle s(v)}$${\displaystyle v}$

• ${\displaystyle {\mathcal {I}}=\{1,...,I\}}$はプレイヤーの有限集合、は（と呼ばれる特別なプレイヤー）ネイチャー、 は情報集合 のプレイヤー分割です。がノード で移動する単一のプレイヤーであるとします。${\displaystyle 0}$${\displaystyle (\mathbf {H} _{i})_{i\in {\mathcal {I}}\cup \{0\}}}$${\displaystyle \mathbf {H} }$${\displaystyle \iota (v)=\iota (H)}$${\displaystyle v\in H}$
• ${\displaystyle \rho =\{\rho _{H}:A(H)\rightarrow [0,1]|H\in \mathbf {H} _{0}\}}$自然の行​​動の確率の集合であり、
• ${\displaystyle u=(u_{i})_{i\in {\mathcal {I}}}:T\rightarrow \mathbb {R} ^{\mathcal {I}}}$ペイオフプロファイル関数です。

プレイヤーが特定の決定ノードで選択できるアクションの数は無限にある場合があります。これを表すために使用される手段は、問題の決定ノードから突き出ている 2 つのエッジを結合するアークです。アクション スペースが 2 つの数値間の連続体である場合、下限と上限の制限数値は、通常、報酬を表す変数とともに、アークの下部と上部にそれぞれ配置されます。結果として生じる可能性のある無限の数の決定ノードは、アークの中央に配置された 1 つのノードによって表されます。同様の手段は、アクション スペースを表すために使用されます。アクション スペースは無限ではありませんが、各アクションのエッジで表すのが非実用的であるほど大きいです。

左側のツリーは、無限のアクション スペース ( 0 から 5000 までの任意の実数) または非常に大きなアクション スペース (おそらく 0 から 5000 までの任意の整数) を持つゲームを表しています。これは別の場所で指定されます。ここでは前者であると仮定し、具体的には、スタックベルク競争を行っている 2 つの企業を表していると仮定します。企業への報酬は左側に表され、⁠ ⁠${\displaystyle q_{1}}$と⁠ ⁠ は${\displaystyle q_{2}}$企業が採用する戦略、⁠ ⁠${\displaystyle c_{1}}$と⁠ ⁠${\displaystyle c_{2}}$は定数 (ここでは各企業の限界費用) です。このゲームのサブゲーム完全ナッシュ均衡は、各報酬関数のフォロワー (企業 2) の戦略変数 ( ⁠ ⁠ )に関する第 1 偏導関数^{[引用必要]}を取り、その最善の応答関数を見つけることで見つけることができます。リーダーについても同様のプロセスを実行できますが、利益を計算する際に、企業 2 が上記の応答を行うことがわかっているため、これを最大化問題に代入できます。次に、1 次導関数を取得して⁠ ⁠を解くことができ、 が得られます。これを企業 2 の最適応答関数に代入すると、サブゲーム完全ナッシュ均衡が実現します。 ${\displaystyle q_{2}}$${\displaystyle q_{2}(q_{1})={\tfrac {5000-q_{1}-c_{2}}{2}}}$${\displaystyle q_{1}}$${\displaystyle q_{1}^{*}={\tfrac {5000+c_{2}-2c_{1}}{2}}}$${\displaystyle q_{2}^{*}={\tfrac {5000+2c_{1}-3c_{2}}{4}}}$${\displaystyle (q_{1}^{*},q_{2}^{*})}$

• 決定性公理
• 完璧な情報
• 組み合わせゲーム理論
• 自己確認の均衡
• 連続ゲーム
• シグナリング
• ソリューションコンセプト

• Hart, Sergiu (1992)。「拡張型および戦略型のゲーム」。Aumann , Robert、Hart, Sergiu (編)。経済応用のためのゲーム理論ハンドブック。第 1 巻。Elsevier。ISBN 978-0-444-88098-7。
• ビンモア、ケネス（2007年）。『Playing for real: a text on game theory』オックスフォード大学出版局、米国。ISBN 978-0-19-530057-4。
• Dresher M. (1961)。戦略ゲームの数学：理論と応用（第 4 章：拡張形式のゲーム、pp74～78）。Rand Corp. ISBN 0-486-64216-X 
• Fudenberg D およびTirole J. (1991) ゲーム理論 (第 3章拡張形式ゲーム、pp67–106)。MIT 出版。ISBN 0-262-06141-4 
• レイトン・ブラウン、ケビン、ショーハム、ヨアブ（2008）、ゲーム理論の基礎：簡潔で学際的な入門、サンラファエル、カリフォルニア州：モーガン＆クレイプール出版社、ISBN 978-1-59829-593-188 ページの数学入門書。第 4 章と第 5 章を参照してください。多くの大学でWayback Machineから 2000-08-15 にアーカイブされたオンライン無料書籍です。
• Luce RDおよびRaiffa H. (1957)。ゲームと意思決定: 序論と批判的調査。(第 3 章: 拡張形式と標準形式、pp39–55)。Wiley New York。ISBN 0-486-65943-7 
• Osborne MJ とRubinstein A. 1994. ゲーム理論コース (第 6 章 完全情報を伴う拡張ゲーム、pp. 89–115)。MIT 出版。ISBN 0-262-65040-1 
• ショーハム、ヨアブ、レイトンブラウン、ケビン（2009）、マルチエージェントシステム：アルゴリズム、ゲーム理論的、論理的基礎、ニューヨーク：ケンブリッジ大学出版局、ISBN 978-0-521-89943-7計算の観点から見た包括的なリファレンス。第 5 章を参照してください。オンラインで無料でダウンロードできます。

• ホルスト・ヘルリッヒ (2006)。選択の公理。スプリンガー。ISBN 978-3-540-30989-5。6.1「ゲーム理論における災難」および7.2「測定可能性（決定性公理）」では、有限ケースの定義を無限数の選択肢（または動き）に拡張する際の問題について説明しています。

歴史論文

• ノイマン、J. (1928)。 「Zur Theorie der Gesellschaftsspiele」。数学アンナレン。100：295～320。土井：10.1007/BF01448847。S2CID  122961988。
• ハロルド・ウィリアム・クーン（2003年）。ゲーム理論の講義。プリンストン大学出版。ISBN 978-0-691-02772-2。1952 年にプリンストンで行われたクーンの講義を収録（以前は公式には出版されていなかったが、コピーとして流通していた）