  In this paper, we study an exponentiated multiplicative weights dynamic based
on Hedge, a well-known algorithm in theoretical machine learning and
algorithmic game theory. The empirical average (arithmetic mean) of the
iterates Hedge generates is known to approach a minimax equilibrium in zero-sum
games. We generalize that result to show that a weighted version of the
empirical average converges to an equilibrium in the class of symmetric
bimatrix games for a diminishing learning rate parameter. Our dynamic is the
first dynamical system (whether continuous or discrete) shown to evolve toward
a Nash equilibrium without assuming monotonicity of the payoff structure or
that a potential function exists. Although our setting is somewhat restricted,
it is also general as the class of symmetric bimatrix games captures the entire
computational complexity of the PPAD class (even to approximate an
equilibrium).
