Abstract
In many settings, the behavior of a system arises as a consequence of the actions of many self-interested agents optimizing their individual objectives, as opposed to the intervention of a central authority optimizing for a global objective. The concepts of the price of anarchy (POA) and the price of stability (POS) from game theory characterize system performance for the worst and best equilibria, respectively, in such settings relative to the globally optimal solution. A deficiency of these concepts, however, is that they are purely existential and do not shed light on which equilibrium states are reachable in an actual game, i.e., via natural game dynamics. This is particularly striking if these quantities differ significantly in value, such as in network design games where the exponential gap between the best and worst equilibria originally prompted the notion of POS in game theory (Anshelevich et al., FOCS 2002).
In this work, we make progress toward bridging this gap by studying network design games under natural game dynamics. On the one hand, we show that in a completely decentralized setting, where agents arrive, depart, and make improving moves in an arbitrary order, the inefficiency of the equilibrium attained can be polynomially large. On the other hand, if after every batch of (adversarial) arrivals and departures of agents, a game designer is allowed to execute a sequence of improving moves to create an equilibrium, 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 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.
This is joint work with Seffi Naor, Debmalya Panigrahi, Mohit Singh, and Seeun Umboh.