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.