We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player noncooperative games. These are extensions of the formulations known for two-player games We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended for large games. Hence, the multilinear feasibility program is an alternative method to find a Nash equilibrium in multi-player games, and outperforms many common algorithms. The mixed-integer formulations are generalisations of known mixed-integer programs for two-player games, however unlike two-player games, these mixed-integer programs do not give better performance than existing algorithms.
翻译:我们提出了多线性和混合内联多线性多线性程序,以在多玩者不合作的游戏中找到纳什平衡。这是两个玩家游戏中已知的配方的延伸。我们比较了甘比特的配方和通用算法,并得出结论,一个多线性可行性程序找到纳什平衡的速度比我们比较它的任何方法都快,包括四联反应平衡方法,这在大型游戏中都是推荐的。因此,多线性可行性程序是多玩家游戏中找到纳什平衡的替代方法,并且优于许多通用算法。混合内联式配方是两种玩家游戏已知混合内联程序的一般化方法,尽管与两个玩家游戏不同,但这些混合内联式的算法并不比现有的算法产生更好的效果。