井上 彰
2014/4/16 (水), 15:00-18:00
東京大学 工学部6号館 235号室
ナッシュ均衡は利己的なプレイヤーがそれぞれ戦略を選ぶときの安定な組合せのことでゲーム理論における基本的な概念である.そこで今回はナッシュ均衡を求めること、特に全てのナッシュ均衡を求めることを考える.一般にナッシュ均衡列挙問題は非常に難しい問題だが,近年KannanとTheobald[1]はランクkゲームという枠組みを考え,Adsulら[2]はランク1ゲームにおいて有用な列挙アルゴリズムを示した.Adsulらの論文では数値実験までは行われていなかったため卒論でこれの実装,数値実験を行った.
さらにYajimaとKonno[3]の双線形計画問題に関する研究を応用することで,ランク2ゲームにおけるナッシュ均衡列挙アルゴリズムを作りこちらも実装と数値実験を行った.使用した手法によって低ランク性を仮定しない一般的な列挙アルゴリズムと比べて高速に全てのナッシュ均衡を求めることができることを確認した.
参考文献
[1] R. Kannan and T. Theobald, Games of fixed rank: a hierarchy of bimatrix games, Economic Theory, 42 (2010), pp. 157–173.
[2] B. Adsul, J. Garg, R. Mehta, and M. Sohoni, Rank-1 bimatrix games: A homeomorphism and a polynomial time algorithm, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, ACM, 2011, pp. 195–204.
[3] Y. Yajima and H. Konno, Efficient algorithms for solving rank two and rank three bilinear programming problems, Journal of Global Optimization, 1 (1991), pp. 155–171.
