The Multilinear Minimax Relaxation of Bimatrix Games and Comparison with Nash Equilibria via Lemke-Howson
share
Extensive study on the complexity of computing Nash Equilibrium has resulted in the definition of the complexity class PPAD by Papadimitriou Papa2, Subsequently shown to be PPAD-complete, first by Daskalakis, Goldberg, and Papadimitriou Papa for 3 or more and even for the bimatrix case by Chen and Deng Chen. On the other hand, it is well known that Nash equilibria of games with smooth payoff functions are generally Pareto-inefficient Dubey In the spirit of Von Neumann's Minimax Theorem and its polynomial-time solvability via Linear Programming, Kalantari Kalantari has described a multilinear minimax relaxation (MMR) that provides an approximation to a convex combination of expected payoffs in any Nash Equilibrium via LP. In this paper, we study this relaxation for the bimatrix game, solving its corresponding LP formulation and comparing its solution to the solution computed by the Lemke-Howson algorithm. We also give a game theoretic interpretation of MMR for the bimatrix game involving a meta-player. Our relaxation has the following theoretical advantages: (1) It can be computed in polynomial time; (2) For at least one player, the computed MMR payoff is at least as good any Nash Equilibrium payoff; (3) There exists a convex scaling of the payoff matrices giving equal payoffs. Such a solution is a satisfactory compromise. Computationally, we have compared our approach with the state-of-the-art implementation of the Lemke-Howson algorithm Lemke. We have observed the following advantages: (i) MMR outperformed Lemke-Howson in time complexity; (ii) In about 80% of the cases the MMR payoffs for both players are better than any Nash Equilibria; (iii) in the remaining 20%, while one player's payoff is better than any Nash Equilibrium payoff, the other player's payoff is only within a relative error of 17%.
READ FULL TEXT