Communications of the ACM
Home/Magazine Archive/July 2012 (Vol. 55, No. 7)/Technical Perspective: Why Study the Price of Anarchy.../Full Text
Research highlights
Technical Perspective: Why Study the Price of Anarchy?
On May 16, 2012, ACM'S Special Interest Group on Algorithms and Computation Theory) (SIGACT) and the European Association for Theoretical Computer Science (EATCS) announced the recipients of the 2012 Göedel prize to be awarded for the papers:
- "Worst-case Equilibira," by Elias Koutsoupias and Christos H. Papadimitriou,
- "How Bad Is Selfish Routing?" by Tim Roughgarden and Éva Tardos, and
- "Algorithmic Mechanism Design," by Noam Nisan and Amir Ronen.
This happy event will take place this month at the International Colloquium on Automata, Languages and Programming in Warwick, England. So it is most fitting that this new paper by Tim Roughgarden appears in this issue of Communications.
In 1999, Elias Koutsoupias and Christos Papadimitriou initiated the study of "How much worse off are we due to selfishness?" They compared the worst case pure Nash equilibria to the optimal solution (in terms of some target function, usually, social welfare). This ratio was later called the price of anarchy. Study of the price of anarchy gave birth to an entirely new field of study.
Roughgarden uses a technique of "smooth games" to give bounds, not only on the price of anarchy with respect to pure Nash equilibria, but also for much more general (and convincing) settings.
One of the areas where negative effects of selfish behavior were observed was in the context of Wardrop equilibria in the analysis of traffic networks (essentially, Nash equilibria where there are infinitely many infinitesimally small agents). Roughgarden and Tardos showed tight bounds on the price of anarchy for non-atomic routing with linear latency functions. The worst case example was known as the Braess paradox (D. Braess, 1968), but Roughgarden and Tardos showed that this was tight.
There are two troubling issues regarding the price of anarchy:
- The pure Nash equilibria does not always exist. Mixed strategy (randomized) Nash equilibria are guaranteed to exist.
- Computing the Nash equilibria is, in general, difficult. To quote Papadimitriou quoting Kamal Jain: "If your laptop can't find it then neither can the market." So, why study the price of anarchy of a concept that may not exist in practice?
In the following paper, Roughgarden studies "smooth games" to give bounds, not only on the price of anarchy with respect to pure Nash equilibria, but also for much more general (and convincing) settings. He extends the class of games for which this technique was known to work, and extends the class of equilibria for which this technique gives good bounds.
In particular, this technique is shown to work for so-called "regret-minimization" dynamics, which are quite natural and believable as representing what really happens. The resulting bounds hold for regret-minimization dynamics, which means that they hold for so-called coarse correlated equilibria, which implies that they hold for correlated equilibria, from which it follows that they hold for mixed Nash equilibria, and thus for pure Nash equilibria, when they exist.
Another important contribution of Roughgarden's in the following paper is so show there exist interesting families of games for which smooth analysis gives the best possible price of anarchy bounds (with respect to pure Nash equilibria, and thus with respect to all classes that include pure Nash equilibria: mixed, correlated, coarse correlated, and no-regret dynamics). For such classes of games, smoothed analysis gives the total answer, no other technique is needed.
A caveat to the complete generality of such smoothness techniques are other natural dynamics such as best response dynamics and so-called sink equilibria for which smooth analysis may be insufficient to determine the price of anarchy.
Christodoulou and Koutsoupias used similar smoothness techniques to study the (special case) of congestion games, in the context of mixed and correlated equilibria, for both the price of anarchy (STOC 2005) and for the price of stability (ESA 2005). Smoothness techniques were implicitly used in many earlier papers to price of anarchy results. Many of the previous price of anarchy results can be more easily understood by reading the following paper than by reading the original.
©2012 ACM 0001-0782/12/0700 $10.00
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
No entries found