簡潔なゲーム

アルゴリズムゲーム理論では、簡潔ゲームまたは簡潔に表現可能なゲームとは、通常の形式の表現よりはるかに小さいサイズで表現できるゲームのことである。プレイヤーの効用に制約を設けずに、各プレイヤーが複数の戦略に直面するゲームを記述するには、効用の値をリストする必要がある。単純なアルゴリズムでも、このような大きな入力の長さの時間多項式でナッシュ均衡を見つけることは可能である。簡潔ゲームは、長さnの文字列で表されるゲームで、プレイヤーの数と各プレイヤーの戦略の数がn の多項式で制限される場合、多項式型であるという^{[1] (簡潔ゲームを}計算問題として記述する正式な定義は、Papadimitriou & Roughgarden 2008 ^[2]によって与えられている)。 ${\displaystyle n}$${\displaystyle s}$ ${\displaystyle ns^{n}}$

グラフィカル ゲームとは、各プレーヤーの効用が他のごく少数のプレーヤーの行動に依存するゲームです。 が各プレーヤーの行動によって影響を受けるプレーヤーの最大数である場合 (つまり、ゲーム グラフの入次数である場合)、ゲームを記述するために必要な効用値の数は であり、 が小さい場合、これはかなりの改善です。 ${\displaystyle d}$${\displaystyle ns^{d+1}}$${\displaystyle d}$

任意の正規形ゲームは、すべての次数が 3 に制限され、各プレイヤーに 2 つの戦略があるグラフィカル ゲームに還元できることが示されています。 ^[3]正規形ゲームとは異なり、グラフィカル ゲームで純粋なナッシュ均衡を見つける問題 (存在する場合) はNP 完全です。^[4]グラフィカル ゲームで (混合の可能性のある) ナッシュ均衡を見つける問題はPPAD完全です。^{[5]グラフィカル ゲームの}相関均衡を見つけることは多項式時間で実行でき、制限されたツリー幅を持つグラフの場合、最適な相関均衡を見つけることも同様に当てはまります。^[2]

スパース ゲームとは、ほとんどのユーティリティがゼロであるゲームのことです。グラフィカル ゲームは、スパース ゲームの特殊なケースとして考えることができます。

2人プレイのゲームの場合、スパースゲームとは、2つのペイオフ（効用）行列の各行と各列に非ゼロの要素が最大で定数個あるゲームとして定義できます。このようなスパースゲームでナッシュ均衡を見つけることはPPAD困難であり、PPADがPに含まれない限り、完全な多項式時間近似スキームは存在しないことが示されている。^[6]

対称ゲームでは、すべてのプレイヤーは同一であるため、戦略の組み合わせの効用を評価する際に重要なのは、各戦略を実行するプレイヤーの数だけです。したがって、このようなゲームを説明するには、効用値のみを与える必要があります。 ${\displaystyle n}$${\displaystyle s}$${\displaystyle s{\tbinom {n+s-2}{s-1}}}$

2 つの戦略を持つ対称ゲームでは、常に純粋ナッシュ均衡が存在する - ただし、対称純粋ナッシュ均衡が存在しない場合もある。^[7]アクション数が一定である対称ゲーム (3 人以上のプレイヤーがいる可能性あり) で純粋ナッシュ均衡を見つける問題はAC ⁰にあるが、アクション数がプレイヤー数とともに増加する場合 (線形であっても)、問題は NP 完全である。^{[8]どの対称ゲームにも}対称均衡が存在する。n人のプレイヤーがk 個の戦略に直面する対称ゲームを考えると、k = であれば、対称均衡は多項式時間で見つかる可能性がある。^[9]対称ゲームで相関均衡を見つけることは、多項式時間で実行できる可能性がある。^[2]${\displaystyle O(\log n/\log \log n)}$

匿名ゲームでは、プレイヤーはそれぞれ異なる効用を持ちますが、他のプレイヤーを区別しません (たとえば、「映画館に行く」と「バーに行く」のどちらかを選択する必要があるときに、それぞれの場所がどれくらい混んでいるかだけを気にし、そこで誰に会うかは気にしません)。このようなゲームでは、プレイヤーの効用は、仲間のうち何人がどの戦略を選択したか、およびプレイヤー自身の戦略によって決まるため、効用値が必要になります。 ${\displaystyle sn{\tbinom {n+s-2}{s-1}}}$

プレイヤーの数に応じてアクションの数が増加する場合、匿名ゲームで純粋なナッシュ均衡を見つけることはNP困難です。^[8]匿名ゲームの最適な相関均衡は多項式時間で見つかる場合があります。^{[2]戦略の数が2の場合、} ε近似ナッシュ均衡を見つけるためのPTASが知られています。^[10]

ポリマトリックスゲーム（マルチマトリックスゲームとも呼ばれる）では、プレイヤーのペア（i,j）ごとに、プレイヤー i の効用の要素を表す効用行列があります。プレイヤー i の最終的な効用は、このような要素すべての合計です。このようなゲームを表すために必要な効用値の数は です。 ${\displaystyle O(n^{2}*s^{2})}$

ポリマトリックスゲームには、常に少なくとも 1 つの混合ナッシュ均衡があります。^[11]ポリマトリックスゲームでナッシュ均衡を見つける問題は PPAD 完全です。^[5]さらに、ポリマトリックスゲームで定数近似ナッシュ均衡を見つける問題も PPAD 完全です。^[12]ポリマトリックスゲームの相関均衡を見つけることは、多項式時間で行うことができます。^[2]プレイヤー間でプレイされるペアワイズゲームが純粋ナッシュ均衡を持っている場合でも、グローバルな相互作用は必ずしも純粋ナッシュ均衡を許容するわけではないことに注意してください (混合ナッシュ均衡は必ず存在します)。純粋ナッシュ均衡が存在するかどうかを確認することは、非常に NP 完全な問題です。^[13]

プレイヤー間のゼロサム相互作用のみを持つ競争的ポリマトリックスゲームは、2人プレイのゼロサムゲームの一般化です。フォン・ノイマンによって元々2人プレイのゲーム用に定式化されたミニマックス定理は、ゼロサムポリマトリックスゲームに一般化されます。^[14] 2人プレイのゼロサムゲームと同様に、ポリマトリックスゼロサムゲームには、多項式時間で計算できる混合ナッシュ均衡があり、それらの均衡は相関均衡と一致 します。しかし、2人プレイのゼロサムゲームの他のいくつかの特性は一般化されません。特に、プレイヤーはゲームの一意の値を持つ必要はなく、均衡戦略は、均衡戦略を使用したときにプレイヤーの最悪ケースの報酬が最大化されないという意味で、最大最小戦略ではありません。競争的ポリマトリックスゲームをシミュレートするための オープンソースのPythonライブラリ^{[15]が存在します。}

エッジ上に調整ゲームを持つポリマトリックスゲームはポテンシャルゲーム ^[16]であり、ポテンシャル関数法を使用して解くことができます。

簡潔なゲームを表現する最も柔軟な方法は、各プレイヤーを多項式時間制限付きチューリングマシンで表現することです。このマシンは、すべてのプレイヤーの行動を入力として受け取り、プレイヤーの効用を出力します。このようなチューリングマシンはブール回路と同等であり、ここでは回路ゲームと呼ばれるこの表現について検討します。

2人プレイのゼロサム回路ゲームの値を計算することはEXP完全問題であり、^[17]そのようなゲームの値を乗法係数まで近似することはPSPACEにあることが知られています。^[18]純粋なナッシュ均衡が存在するかどうかを判断することは完全問題です（多項式階層を参照）。^[19]${\displaystyle \Sigma _{2}^{\rm {P}}}$

簡潔なゲームには他にも多くの種類があります (多くはリソースの割り当てに関係しています)。例としては、混雑ゲーム、ネットワーク混雑ゲーム、スケジューリング ゲーム、ローカル効果ゲーム、施設配置ゲーム、アクション グラフ ゲーム、ハイパーグラフィカル ゲームなどがあります。

以下は、いくつかのゲーム表現で特定のクラスの均衡を見つけるための既知の複雑さの結果の表です。「NE」は「ナッシュ均衡」を表し、「CE」は「相関均衡」を表します。nはプレーヤーの数、s は各プレーヤーが直面する戦略の数です (すべてのプレーヤーが同じ数の戦略に直面すると仮定します)。グラフィカル ゲームでは、d はゲーム グラフの最大入次数です。参考文献については、メインの記事の本文を参照してください。

• アルゴリズムゲーム理論: 純粋ナッシュの計算複雑性