Nash Equilibria in Random Games 2006年3月7日 FOCSセミナー 加藤公一 東京大学情報理工学系研究科博士課程1年 日本ユニシス株式会社 1 紹介する論文: I. Barany, S. Vempala, A. Vetta, “Nash Equilibria in Random Games”, FOCS 2005 これを紹介しようと思った動機: ナッシュ均衡と多面体の関係 面白そう! ゲーム理論はよく知らない いい機会だから勉強しておこう! 2 背景 ゲーム理論の重要性 •経済学 •外交、軍事 •インターネットリソースの奪い合い •社会的ネットワークの効率利用 (例:Incentive Network[Kleinberg-Raghavan 05]) 計算量的な面白さ ナッシュ均衡問題はNPよりは易しいだろうと予想 されている 3 ゲーム理論の基本 2-Player Game 二人のプレーヤ(AliceとBob)が、それぞれ与えられた戦略の中から1つを 選ぶとそれぞれの利得が決まる 例:じゃんけん Aliceの利得行列:A Bobの利得行列:B グー チョキ パー グー 0 1 -1 チョキ -1 0 パー 1 -1 Bob Alice グー チョキ パー グー 0 -1 1 1 チョキ 1 0 -1 0 パー -1 1 0 一般にはA≠-B Bob Alice 非ゼロ和ゲーム 4 混合戦略とナッシュ均衡 じゃんけんのN回勝負を考える 出す手の組み合わせを考える必要がある 混合戦略 このとき、ゲームに勝つには? グー、チョキー、パーを均等に(それぞれ確率1/3で)出すこと (偏りがあれば、相手にそのウラをかかれる) ベクトル (1 / 3, 1 / 3, 1 / 3)T であらわす 両方のプレーヤが同じくらい賢くて、最善を尽くせば? 1 / 3, 1 / 3) 両方とも (1 / 3, T という戦略を選択し、何度やっても同じ結果に ナッシュ均衡 5 定式化 Alice, Bobの利得行列: A, B x, y Alice, Bobがとる混合戦略: (確率分布なので (n×n) x i 1, i じゃんけんの場合 (n次) y i 1 ) A T Aliceの利得 x Ay Bobの利得 xT By xx , y y * チョキ パー グー 0 1 -1 チョキ -1 0 1 パー 1 -1 0 B A 定義: * グー i x* y* (1 / 3,1 / 3,1 / 3)T がナッシュ均衡である T x* max arg xT Ay* , y * max arg x* Ay x y 6 未解決問題: ナッシュ均衡を1つ求めるために必要な計算量は? 予想: NP困難ではないと思われている おそらく「PとNPの間」くらいであろう [Papadimitriou 94] 現状: 知られているのは指数時間アルゴリズムのみ 以上最悪ケースの議論だが、ランダムなゲームが与えられた場合は? この論文のテーマ! 7 結論 ランダムなゲームは、十分に高い確率で 計算量 O(n3 log log n) で計算できる。 ランダムゲーム:利得行列の各要素が乱数 一様乱数と正規分布乱数の両方について示されている 最悪ケースと比べて指数ギャップ! 8 アルゴリズム(Las Vegas) 整数dを1からNまで増やしながら以下を繰り返す: サポートのサイズがdのナッシュ均衡を探す サポート:要素が0でないインデックスの集合 T 例: (0,5,6,0,7) のサポートは 2,3,5 こんな単純なアルゴリズムでなぜうまくいくのか? 9 アルゴリズムの分析 証明: 十分高い確率でサポート のサイズ=2のナッシュ均衡 が存在する 2次元の凸包を求める高速 アルゴリズムが存在 ランダムな点集合の凸包として得 られる多面体の問題に帰着される 10 ナッシュ均衡問題の幾何的解釈 xT Ay を xT Ay と見る Ay は多面体の内部を動く A (a1 ,, an ) とすると conv {a1 ,, an } x を固定すると max xT Ay を求めることは y 1 1 max x y' を求めることと同値 y 'conv A x 同様に、 y を固定すると O max xT By max x' y x 1 1 x 'conv(B) 11 ナッシュ均衡: x 0, y 0 なので、座標値非負のところだけで考えてよい Aliceの戦略 Bobの戦略 Aliceの戦略 conv ( A) Bobの戦略 conv ( B) お互いに最適解になっているときが、ナッシュ均衡 サポートの制限: 行列A, Bのいくつかの行、列を取り除いて上記の問題を考えると、 サポートを制限したときの問題に対応 サポートのサイズをdに制限したナッシュ均衡問題は、d次元の線 形計画に対応 12 なぜうまくいくか サポートのサイズをdに制限してもナッシュ均衡がある場合: 全体n次元 Aliceの戦略 Bobの最適戦略を含むd-1次元面 d次元 conv ( A) サイズdのサポートを固定した 時の混合戦略の集合 Aliceの最適戦略を含むd-1次元面 Bobの戦略 d次元 conv ( B) 対応 d個の点によって張られ るd-1次元の面 こうなる確率を組み合わせ的に調べてみると、実は十分に高いことがわかる 1 1 f ( d ) サポートのサイズd以下のナッシュ均衡が存在しない確率: n N 2 1 N1はfacet上の点の数 13 計算量は? 以下d=2とする ほとんどの点は凸包の内部になる 凸包の境界上にあるのは x O Olog n 個 (dが一般なら O log n d 1 個[Dwyer88]) [Kirkpatrick-Seidel88] 2次元で入力点数N、出力点数Mのと き、凸包計算の計算量は ON log M d=2にできたことが ここで効いてくる 凸包の計算コストは On log log n 14 計算量 サイズ2のサポートの組み合わせは n 凸包計算は 線形計画は C2 O n 2 On log log n O1 3 トータルの計算量は O n log log n 15 まとめ 2-Playerのランダムゲームは、十分に高い 確率で多項式時間でナッシュ均衡を求める ことが可能 平均計算時間のことは言っていないので注意 最悪ケースでは指数時間 16
© Copyright 2025 ExpyDoc