2016/09/28 by Ioannis Avramopoulos, Avramopoulos, Ioannis
Computer Science · Decision Sciences · Social Sciences · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.1609.08934
openalex publication_date 2016/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that, by using multiplicative weights in a game-theoretic thought experiment (and an important convexity result on the composition of multiplicative weights with the relative entropy function), a symmetric bimatrix game (that is, a bimatrix matrix wherein the payoff matrix of each player is the transpose of the payoff matrix of the other) either has an interior symmetric equilibrium or there is a pure strategy that is weakly dominated by some mixed strategy. Weakly dominated pure strategies can be detected and eliminated in polynomial time by solving a linear program. Furthermore, interior symmetric equilibria are a special case of a more general notion, namely, that of an "equalizer," which can also be computed efficiently in polynomial time by solving a linear program. An elegant "symmetrization method" of bimatrix games [Jurg et al., 1992] and the well-known PPAD-completeness results on equilibrium computation in bimatrix games [Daskalakis et al., 2009, Chen et al., 2009] imply then the compelling P = PPAD.