グラフィカルゲーム理論

ゲーム理論では、ゲームを記述する一般的な方法として、標準形式と拡張形式があります。グラフィカル形式は、参加者間の相互作用を使用してゲームを コンパクトに表現するもう 1 つの方法です。

それぞれの戦略を持つプレイヤーがいるゲームを考えてみましょう。プレイヤーをグラフのノードとして表します。グラフでは、各プレイヤーは自分と隣のプレイヤーのみに依存する効用関数を持ちます。効用関数が依存する他のプレイヤーの数が少ないほど、グラフの表現は小さくなります。 ${\displaystyle n}$${\displaystyle m}$

グラフィカル ゲームはグラフで表されます。グラフでは、各プレーヤーがノードで表され、2 つのノードとの間にはエッジが存在する場合、 その効用関数は、他のプレーヤーが選択する戦略に依存します。 の各ノードには関数 があり、 は頂点 の次数です。 は、プレーヤーの効用を、そのプレーヤーの戦略と近隣プレーヤーの戦略の関数として指定します。 ${\displaystyle G}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle G}$${\displaystyle u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow \mathbb {R} }$${\displaystyle d_{i}}$${\displaystyle i}$${\displaystyle u_{i}}$${\displaystyle i}$

各プレイヤーが可能な戦略を持つ一般的なプレイヤーゲームの場合、正規形表現のサイズは になります。このゲームのグラフィカル表現のサイズは です。ここで はグラフの最大ノード次数です。 の場合、グラフィカルなゲーム表現ははるかに小さくなります。 ${\displaystyle n}$${\displaystyle m}$${\displaystyle O(m^{n})}$${\displaystyle O(m^{d})}$${\displaystyle d}$${\displaystyle d\ll n}$

各プレイヤーの効用関数が他のプレイヤー 1 人にのみ依存する場合:

• 
  記述されたゲームのグラフィック形式

グラフの最大次数は 1 であり、ゲームはサイズ の関数 (テーブル)として記述できます。したがって、入力の合計サイズは になります。 ${\displaystyle n}$${\displaystyle m^{2}}$${\displaystyle nm^{2}}$

ゲームでナッシュ均衡を見つけるには、表現のサイズに応じて指数関数的な時間がかかります。ゲームのグラフィカル表現がツリーである場合、均衡は多項式時間で見つけることができます。一般的なケースでは、ノードの最大次数が 3 以上であるため、問題はNP 完全です。

• マイケル・カーンズ (2007) 「グラフィック ゲーム」。ヴァジラニにて、ヴィジェイV.ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。
• Michael Kearns、Michael L. Littman、Satinder Singh (2001)「ゲーム理論のグラフィカルモデル」