Stable games and their dynamics

We study a class of population games called stable games. These games are characterized by self-defeating externalities: when agents revise their strategies, the improvements in the payoffs of strategies to which revising agents are switching are always exceeded by the improvements in the payoffs of strategies which revising agents are abandoning. We prove that the set of Nash equilibria of a stable game is globally asymptotically stable under a wide range of evolutionary dynamics. Convergence results for stable games are not as general as those for potential games: in addition to monotonicity of the dynamics, integrability of the agents' revision protocols plays a key role.     

The projection dynamic and the geometry of population games

The projection dynamic is an evolutionary dynamic for population games. It is derived from a model of individual choice in which agents abandon their current strategies at rates inversely proportional to the strategies' current levels of use. The dynamic admits a simple geometric definition, its rest points coincide with the Nash equilibria of the underlying game, and it converges globally to Nash equilibrium in potential games and in stable games.     

New complexity results about Nash equilibria

We provide a single reduction that demonstrates that in normal-form games: (1) it is -complete to determine whether Nash equilibria with certain natural properties exist (these results are similar to those obtained by Gilboa and Zemel [Gilboa, I., Zemel, E., 1989. Nash and correlated equilibria: Some complexity considerations. Games Econ. Behav. 1, 80–93]), (2) more significantly, the problems of maximizing certain properties of a Nash equilibrium are inapproximable (unless ), and (3) it is -hard to count the Nash equilibria. We also show that determining whether a pure-strategy Bayes–Nash equilibrium exists in a Bayesian game is -complete, and that determining whether a pure-strategy Nash equilibrium exists in a Markov (stochastic) game is -hard even if the game is unobserved (and that this remains -hard if the game has finite length). All of our hardness results hold even if there are only two players and the game is symmetric.