The Price of Stochastic Anarchy

Christine Chung, Katrina Ligett, Kirk Pruhs, Aaron Roth
[PDF]


We study the price of anarchy of the load balancing game on unrelated machines with respect to its stochastically stable states (as opposed to its Nash equilibria). Stochastic stability is a solution concept from evolutionary game theory that avoids many of the pitfalls of Nash equilibria: Unlike Nash, the stochastically stable states of a game are always the result of natural dynamics of computationally bounded and decentralized agents, and are resilient to deviations from perfect play (noise). In potential games, the stochasticly stable states are a subset of the Nash equilibria, and so distinguish between the equilibria that are resilient to imperfect play from those that are brittle. In such games, the price of stochastic anarchy can therefore be viewed as a smoothed analysis of the price of anarchy (which I discuss a bit here.) In particular, even for only two players and two machines, the price of anarchy of the load balancing game on unrelated machines is unbounded, but the price of stochastic anarchy is 2. We give (non-matching) upper and lower bounds on the price of stochastic anarchy in the general n-player m-machine case.