Games with secure equilibria

Krishnendu Chatterjee, Thomas A. Henzinger and Marcin Jurdzinski
Theoretical Computer Science
Volume 365, Issues 1-2 , 10 November 2006, Pages 67-82
http://dx.doi.org/10.1016/j.tcs.2006.07.032

LICS2004の論文のジャーナル版．
二人非ゼロ和ゲームを考える．もちろんナッシュ均衡は存在するけど，それが複数ある場合，その中のどれをプレイヤーが好むのかという問題がある．
その場合，利得和が最大になるようなものを考えることが多く，これは相手と協力する行動となる．
この論文ではその逆で相手と敵対する行動をとるようなナッシュ均衡を考え，それをsecureな均衡と呼ぶ．
(定義は論文参照．)
定理として，ゲームにある仮定をおいたとき，利得ベクトルが極大なナッシュ均衡で，secureにもなっているものがただ1つ存在することが示されている．
このゲームに対する仮定は論文のモチベーションとなっているsystem verificationの問題を包含していて，自然といえる．