Title: The Dynamics of Equilibria

Abstract

Many natural games have both high and low cost Nash equilibria: their Price of Anarchy is high and yet their Price of Stability is low. In
such cases, one could hope to "move" behavior from a high cost equilibrium to a low cost one by a "public service advertising campaign" encouraging players to follow the low-cost equilibrium. If every player follows the advice then we are done (since it's an equilibrium). However, the assumption that everyone follows instructions is unrealistic. A more natural assumption is that some players will follow them, while other players will not. In this paper we consider the question of to what extent can such an advertising campaign cause behavior to switch from a bad equilibrium to a good one even if only a fraction of people actually follow the given advice, and do so only temporarily. Unlike in the "price of altruism" model, we assume everyone will ultimately act in their own interest.

We analyze this question for several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, and party affiliation games (which include consensus and cut games). We show that for some of these games (such as fair cost sharing), a random alpha fraction of the population following the given advice is sufficient to get a guarantee  within any O(1/alpha) factor of the price of stability for any alpha > 0. However, for some games (such as party affiliation games), there is a strict threshold (in this case, alpha < 1/2 yields almost no benefit, yet alpha > 1/2 is enough to reach near-optimal behavior), and for some games, such as scheduling, no value alpha < 1 is sufficient.

This is based on work joint with Avrim Blum and Yishay Mansour.