  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.
