以前の記事の続きです。先にこれ読んだ方がわかりやすいと思います！
ナッシュ均衡点の導出方法３：Lemke-Howson algorithm
これまでに2つのナッシュ均衡点の導出方法を紹介しましたが、どちらも全てのナッシュ均衡点を導出することができるというメリットはありましたが、かなり時間がかかってしまうというデメリットがありました。逆にこれから紹介するLemke-Howson algorithmは1つしかナッシュ均衡点は求められませんが、それなりに速いというものです。では解説していきましょう！
以前の記事ではラベルを用いてナッシュ均衡点を求める方法を解説しました。実は今回のアルゴリズムでも同じことを行うのですが、少しだけアプローチが異なります。ではまずアルゴリズムを見てみましょう！
立体的なすごろくをイメージしてください。\(P, Q\)の2つ最適応答多面体に2人のプレイヤーがそれぞれスタート位置である頂点にコマを置いています。そして交互に辺を渡って隣接する別の頂点にコマを動かします。すると必ずどこかでcompletely labeledとなる頂点の組み合わせに出会います。それがナッシュ均衡点の組であるのでそれを出力します。
そしてスタート位置はどこに設定するのがよいのか？実は必ず\(P, Q\)の頂点となる\((0, 0), (0, 0)\)からスタートすればうまくいくのです。ではさらに具体的に見ていきましょう。
まず最適応答多面体が以下のようになったとします。左が3次元、右が2次元なので利得行列が\(3 \times 2\)だったんでしょうね。先に動くのは3次元の多面体（これはどっちでもいい）で、スタート地点は先ほど言ったとおり\((0, 0), (0, 0)\)です。
では緑の多面体において頂点を移動させてみましょう。
このようになりました。このとき前の図では\(1, 2, 3\)の面で囲まれた頂点にいましたが、いまは\(2, 3, 5\)で囲まれた頂点にいます。このとき面1が消えてしまったので1をdropしたと言います。そして新たに手に入れた5をcatchしたと呼びましょう。
次は赤い多面体の番です。実はこちらは進める方向は決まっています。緑の多面体が5をcatchしたので赤い多面体は5をdropする方向に進まなければなりません。つまり次のようになります。
これで新たに3をcatchすることができました。同様に緑の多面体で3をdropする方向に進んでみましょう。
次は4をcatchしたので赤い多面体で4をdropします。
2をcatchしたので、赤い多面体で2をdropします。
ここで1をcatchしました。次に赤い多面体で1をdropする方向へ進むはずですが、dropできるのは2か3だけなので1をdropすることはできません。実はここですごろくは終わりなのです！つまり、いまコマがいる頂点の組がナッシュ均衡点となります！
一番最初にdropした数字が1だったのですが、どちらかの多面体がその1をcatchした瞬間に終了となります。そしてその時の頂点の座標を正規化した値がナッシュ均衡点の混合戦略となるのです。
例えばこの例では終了したときの座標が\((1/9, 2/9, 1/3)\)と\((2/5, 1/5)\)であったとすると、比が同じのまま、和が1となるように正規化した\((1/6, 1/3, 1/2)\)と\((2/3, 1/3)\)がナッシュ均衡点の戦略となります。
以上がLemke-Howson algorithmの流れです。実際はもう少し考えるべきことはあります。例えば
- dropした値はいつかはcatchできるのか？ループすることはないのか？？
- なぜスタート地点は\((0, 0)\)じゃなければならないのか？
- どんな戦略系ゲームに対してもこれでナッシュ均衡点を求めることができるのか？
などなどです。
1に関しては（3の場合を除いてですが）必ずループしないと証明されています。2に関しては実は\((0, 0)\)以外からでもナッシュ均衡点となる頂点の組から始めてもうまくいきます。しかし、ナッシュ均衡点を求めるためにこのアルゴリズムを用いるのでナッシュ均衡点からスタートするというのはナンセンスですね。
3に関しては実はNOなんです。戦略系ゲームによってはdegenerateと呼ばれるゲームがあります。直感的には利得行列が正則でない（それぞれの行が独立ではない）ような時です。こんなときは利得行列が独立となるように一工夫する必要があります。それに関しては要望があったら、記事にしたいと思いますので、もし知りたい方は連絡してください(*^^*)
おわりに
いやー、長く複雑でしたな（笑）
これで皆さんはきっとナッシュ均衡点マスターです！いろんな人に自慢していってください（笑）
コメント