簡潔なゲーム
アルゴリズムゲーム理論におけるゲーム
3人のプレイヤーI、II、IIIがそれぞれ{T,B}、{L,R}、{l,r}という戦略に直面するゲームを考えてみましょう。さらなる制約がなければ、このようなゲームを記述するには 3*2 3 =24個の効用値が必要になります。
L、l 左、右 R、l R、r
T 4、6、2​​​​ 5、5、5​​​​ 8、1、7​​​​ 1、4、9​​​​
B 8、6、6​​​​ 7、4、7​​​​ 9、6、5​​​​ 0、3、0​​​​
各戦略プロファイルでは、最初のプレーヤーのユーティリティ (赤) が最初にリストされ、次に 2 番目のプレーヤー (緑)、3 番目のプレーヤー (青)のユーティリティが続きます。

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

簡潔なゲームの種類

グラフィックゲーム

各プレイヤーの効用は、自分の行動と他のプレイヤー 1 人の行動にのみ依存するとします。たとえば、I は II に依存し、II は III に依存し、III は I に依存します。このようなゲームを表すには、合計で 12 個の効用値のみを含む 2x2 効用表が 3 つだけ必要になります。
L R
T 9 8
B 3 4
l r
L 6 8
R 1 3
T B
l 4 4
r 5 7

グラフィカルゲームとは、各プレイヤーの効用がごく少数の他のプレイヤーの行動に依存するゲームです。 が、各プレイヤーに影響を与えるプレイヤーの最大数（つまり、ゲームグラフの入次数）である場合、ゲームを記述するために必要な効用値の数は となり、これは小さな に対しては大きな改善となります。 d {\displaystyle d} n s d + 1 {\displaystyle ns^{d+1}} d {\displaystyle d}

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

スパースゲーム

以下のように、ほとんどのユーティリティが 0 の場合、簡潔な表現を簡単に作成できます。
L、l 左、右 R、l R、r
T 0、0、0​​​​ 2、0、1​​​​ 0、0、0​​​​ 0、7、0​​​​
B 0、0、0​​​​ 0、0、0​​​​ 2、0、3​​​​ 0、0、0​​​​

スパースゲームとは、ほとんどの効用値がゼロであるゲームです。グラフィカルゲームは、スパースゲームの特殊なケースと見なすことができます。

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

対称ゲーム

3人のプレイヤー全員が同じ戦略（全員を紫色で塗りつぶす）を持ち、戦略集合{T,B}に直面していると仮定する。#TPと#BPは、それぞれTとBを選択したプレイヤーの仲間の数とする。このゲームを記述するには、6つの効用値のみが必要である。
#TP=2
#BP=0 		#TP=1
#BP=1 		#TP=0
#BP=2
T 5 2 2
B 1 7 2

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

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

匿名ゲーム

プレイヤーはそれぞれ異なっていても、他のプレイヤーを区別しない場合は、ゲームを表すために 18 個のユーティリティ値をリストする必要があります (各プレイヤーに対して上記の「対称ゲーム」で示した表のような 1 つの表)。
#TP=2
#BP=0 		#TP=1
#BP=1 		#TP=0
#BP=2
T 8、8、2​​​​ 2、9、5​​​​ 4、1、4​​​​
B 6、1、3​​​​ 2、2、1​​​​ 7、0、6​​​​

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

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

ポリマトリックスゲーム

問題のゲームがポリマトリックスゲームであった場合、それを記述するには24個の効用値が必要になります。簡単のため、プレイヤーIの効用値のみを検討します（他のプレイヤーそれぞれについて、同様の表がさらに2つ必要になります）。
L R
T 4、6​​ 8、7​​
B 3、7​​ 9、1​​
l r
T 7、7​​ 1、6​​
B 8、6​​ 6、4​​
l r
L 2、9​​ 3、3​​
R 2、4​​ 1、5​​

戦略プロファイル (B,R,l) を選択した場合、プレイヤー I の効用は 9+8=17、プレイヤー II の効用は 1+2=3、プレイヤー III の効用は 6+4=10 になります。

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

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

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

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

サーキットゲーム

ここで、プレイヤーの様々な戦略をブール値「0」と「1」で表し、XをプレイヤーIの選択、YをプレイヤーIIの選択、ZをプレイヤーIIIの選択とします。各プレイヤーに回路を割り当てます。

プレイヤーI: X ∧ (Y ∨ Z)
プレイヤーII: X ⊕ Y ⊕ Z
プレイヤーIII: X ∨ Y

これらは以下のユーティリティ テーブルについて説明します。

0 , 0 0、1​​ 1 , 0 1、1​​
0 0、0、0​​​​ 0、1、0​​​​ 0、1、1​​​​ 0、0、1​​​​
1 0、1、1​​​​ 1、0、1​​​​ 1、0、1​​​​ 1、1、1​​​​

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

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

その他の表現

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

均衡点を見つける複雑さの要約

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

表現 サイズ ( O (...)) 純粋なNE 混合北東 CE 最適なCE
正規形ゲーム n s n {\displaystyle ns^{n}} NP完全 PPAD完全 P P
グラフィックゲーム n s d + 1 {\displaystyle ns^{d+1}} NP完全 PPAD完全 P NP困難
対称ゲーム s （ n + s − 2 s − 1 ） {\displaystyle s{\tbinom {n+s-2}{s-1}}} NP完全 対称ナッシュ均衡の計算は2人プレイの場合PPAD困難である。非対称ナッシュ均衡の計算はNP完全である。 P P
匿名ゲーム s n （ n + s − 2 s − 1 ） {\displaystyle sn{\tbinom {n+s-2}{s-1}}} NP困難 P P
ポリマトリックスゲーム n 2 s 2 {\displaystyle n^{2}s^{2}} 強くNP完全 PPAD完全（ゼロ和多項式） P NP困難
サーキットゲーム Σ 2 P {\displaystyle \Sigma _{2}^{\rm {P}}} -完了
混雑ゲーム PLS完全 P NP困難


注記

  1. ^ パパディミトリウ、クリストス H. (2007)。 「ナッシュ均衡を見つけることの複雑さ」。ニサンでは、ノーム。ラフガーデン、ティム。タルドス、エヴァ。他。 （編）。アルゴリズムゲーム理論。ケンブリッジ大学出版局。 29–52ページ。ISBN  978-0-521-87282-9。
  2. ^ abcde Papadimitriou, Christos H.; Roughgarden, Tim (2008). 「マルチプレイヤーゲームにおける相関均衡の計算」J. ACM . 55 (3): 1– 29. CiteSeerX 10.1.1.335.2634 . doi :10.1145/1379759.1379762. S2CID  53224027.  
  3. ^ Goldberg, Paul W.; Papadimitriou, Christos H. (2006). 「平衡問題における縮約可能性」 .第38回ACMコンピューティング理論シンポジウム議事録. シアトル, ワシントン州, 米国: ACM. pp.  61– 70. doi :10.1145/1132516.1132526. ISBN  1-59593-134-1. 2010年1月25日閲覧。
  4. ^ Gottlob, G.; Greco, G.; Scarcello, F. (2005). 「純粋ナッシュ均衡：難しいゲームと簡単なゲーム」. Journal of Artificial Intelligence Research . 24 ( 195–220 ): 26–37 . arXiv : 1109.2152 . doi :10.1613/jair.1683.
  5. ^ ab Daskalakis, Constantinos; Fabrikant, Alex; Papadimitriou, Christos H. (2006). 「ゲームの世界は平坦：簡潔なゲームにおけるナッシュ均衡の複雑性」.オートマトン、言語、プログラミング. コンピュータサイエンス講義ノート. 第4051巻. pp.  513– 524. CiteSeerX 10.1.1.111.8075 . doi :10.1007/11786986_45. ISBN   978-3-540-35904-3。
  6. ^ Chen, Xi ; Deng, Xiaotie ; Teng, Shang-Hua (2006). 「スパースゲームは難しい」.インターネットとネットワーク経済学. pp. 262–273. doi :10.1007/11944874_24. ISBN  978-3-540-68138-0。
  7. ^ Cheng, Shih-Fen; Reeves, Daniel M.; Vorobeychik, Yevgeniy; Wellman, Michael P. (2004).対称ゲームにおける均衡に関するノート. AAMAS-04 ゲーム理論と意思決定理論ワークショップ.
  8. ^ ab Brandt, Felix; Fischer, Felix; Holzer, Markus (2009). 「対称性と純粋ナッシュ均衡の計算量」J. Comput. Syst. Sci . 75 (3): 163– 177. doi : 10.1016/j.jcss.2008.09.001 .
  9. ^ パパディミトリウ, クリストス・H.; ラフガーデン, ティム (2005). 「マルチプレイヤーゲームにおける均衡計算」.第16回ACM-SIAM離散アルゴリズムシンポジウム議事録. ブリティッシュコロンビア州バンクーバー: 産業応用数学協会. pp.  82– 91. ISBN  0-89871-585-7. 2010年1月25日閲覧。
  10. ^ ダスカラキス、コンスタンティノス;パパディミトリウ、クリストス H. (2007)。 「匿名ゲームにおけるコンピューティング平衡」。arXiv : 0710.5582v1 [cs]。
  11. ^ ハウソン, ジョセフ・T. (1972年1月). 「ポリマトリックスゲームの均衡」.マネジメントサイエンス. 18 (5): 312– 318. doi :10.1287/mnsc.18.5.312. ISSN  0025-1909. JSTOR  2634798.
  12. ^ Rubinstein, Aviad (2015-01-01). 「ナッシュ均衡の近似不可能性」.第47回ACM計算理論シンポジウム議事録. STOC '15. ニューヨーク、ニューヨーク州、米国: ACM. pp.  409– 418. arXiv : 1405.3322 . doi :10.1145/2746539.2746578. ISBN 9781450335362. S2CID  14633920。
  13. ^ Apt, Krzysztof ; Simon, Sunil; Wojtczak, Dominik (2021年10月4日). 「重み付き有向グラフ上の調整ゲーム」.オペレーションズ・リサーチ数学. 47 (2): 995–1025 . arXiv : 1910.02693 . doi :10.1287/moor.2021.1159. S2CID  203836087.
  14. ^ Cai, Y.、Candogan, O.、Daskalakis, C.、Papadimitriou, C. (2016)。ゼロサム ポリマトリックス ゲーム: ミニマックスの一般化。https://people.csail.mit.edu/costis/zerosum_final3.pdf
  15. ^ O. パーソン https://pypi.org/project/polymatrix/
  16. ^ Rahn, Mona および Schafer, Guido (2015) ポリマトリックス調整ゲームにおける効率的な均衡 https://arxiv.org/pdf/1504.07518.pdf
  17. ^ フェイゲンバウム, ジョアン; コラー, ダフネ; ショア, ピーター (1995). インタラクティブ計算量クラスのゲーム理論的分類. 離散数学および理論計算機科学. 2010年1月25日閲覧。
  18. ^ ランス・フォートナウ、ラッセル・インパグリアッツォ、バレンタイン・カバネッツ、クリストファー・ウマンス (2005). 「簡潔なゼロサムゲームの計算複雑性について」第20回IEEE計算複雑性会議議事録. IEEEコンピュータ協会. pp.  323– 332. ISBN  0-7695-2364-1. 2010年1月23日閲覧。
  19. ^ シェーネベック、グラント、ヴァダン、サリル (2006). 「簡潔に表現されたゲームにおけるナッシュ均衡の計算複雑性」第7回ACM電子商取引会議議事録. 米国ミシガン州アナーバー: ACM. pp.  270– 279. doi :10.1145/1134707.1134737. ISBN  1-59593-236-4. 2010年1月25日閲覧。
  • アルゴリズムゲーム理論：純粋ナッシュの計算複雑性
「https://en.wikipedia.org/w/index.php?title=Succinct_game&oldid=1329678206#polymatrix」より取得