  A central question in algorithmic game theory is to measure the inefficiency
(ratio of costs) of Nash equilibria (NE) with respect to socially optimal
solutions. The two established metrics used for this purpose are price of
anarchy (POA) and price of stability (POS), which respectively provide upper
and lower bounds on this ratio. A deficiency of these metrics, however, is that
they are purely existential and shed no light on which of the equilibrium
states are reachable in an actual game, i.e., via natural game dynamics. This
is particularly striking if these metrics differ significantly, such as in
network design games where the exponential gap between the best and worst NE
states originally prompted the notion of POS in game theory (Anshelevich et
al., FOCS 2002). In this paper, we make progress toward bridging this gap by
studying network design games under natural game dynamics.
  First we show that in a completely decentralized setting, where agents
arrive, depart, and make improving moves in an arbitrary order, the
inefficiency of NE attained can be polynomially large. This implies that the
game designer must have some control over the interleaving of these events in
order to force the game to attain efficient NE. We complement our negative
result by showing that if the game designer is allowed to execute a sequence of
improving moves to create an equilibrium state after every batch of agent
arrivals or departures, then the resulting equilibrium states attained by the
game are exponentially more efficient, i.e., the ratio of costs compared to the
optimum is only logarithmic. Overall, our two results establish that in network
games, the efficiency of equilibrium states is dictated by whether agents are
allowed to join or leave the game in arbitrary states, an observation that
might be useful in analyzing the dynamics of other classes of games with
divergent POS and POA bounds.

Data Structures and Algorithms