论文标题
热带互补性问题和纳什平衡
Tropical complementarity problems and Nash equilibria
论文作者
论文摘要
线性互补编程是对线性编程的概括，该编程涵盖了bimatrix游戏的NASH均衡计算。尽管后一个问题是PPAD综合的，但我们表明，与NASH平衡相关的互补问题的热带类似物可以在多项式时间内解决。此外，我们证明了Lemke-Howson算法在热带设置上携带，并在最坏情况下执行线性枢轴数量。结果的结果是一类新的（经典）bimatrix游戏，可以在多项式时间内完成NASH均衡计算。
Linear complementarity programming is a generalization of linear programming which encompasses the computation of Nash equilibria for bimatrix games. While the latter problem is PPAD-complete, we show that the tropical analogue of the complementarity problem associated with Nash equilibria can be solved in polynomial time. Moreover, we prove that the Lemke--Howson algorithm carries over the tropical setting and performs a linear number of pivots in the worst case. A consequence of this result is a new class of (classical) bimatrix games for which Nash equilibria computation can be done in polynomial time.
