Semidefinite Programming and Nash Equilibria in Bimatrix Games
We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium (NE) problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is … Read more