# Intrinsic Robustness of the Price of Anarchy

@article{Roughgarden2015IntrinsicRO, title={Intrinsic Robustness of the Price of Anarchy}, author={Tim Roughgarden}, journal={Journal of the ACM (JACM)}, year={2015}, volume={62}, pages={1 - 42} }

The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior. Remarkably good bounds on this measure are known for a wide range of application domains. However, such bounds are meaningful only if a game's participants successfully reach a Nash equilibrium. This drawback motivates inefficiency bounds that apply more generally to weaker notions of equilibria… Expand

#### Figures and Topics from this paper

#### 163 Citations

The Price of Anarchy of Affine Congestion Games with Similar Strategies

- Computer Science, Mathematics
- ICTCS
- 2018

Affine congestion games are a well-studied model for selfish behavior in distributed systems, such as transportation and communication networks, and small values of θ model the behavioral attitude of players who are partially oblivious to congestion and are not willing to significantly deviate from what is their best strategy in absence of congestion. Expand

From pointwise convergence of evolutionary dynamics to average case analysis of decentralized algorithms

- Mathematics, Computer Science
- 2014

This work proposes a quantitative framework where the predictions of different equilibria are weighted by their probability to arise under evolutionary dynamics given random initial conditions, and introduces a concurrent convergent deterministic discrete-time dynamic for general linear congestion games and performing stability analysis on it. Expand

Tight inefficiency bounds for perception-parameterized affine congestion games

- Computer Science
- Theor. Comput. Sci.
- 2019

A new model of congestion games that captures several extensions of the classical congestion game introduced by Rosenthal in 1973 is introduced, to parameterize both the perceived cost of each player and the social cost function of the system designer. Expand

A pr 2 01 4 Selfishness Level of Strategic Games ∗

- 2014

We introduce a new measure of the discrepancy in strategic games between the social welfare in a Nash equilibrium and in a social optimum, that we call selfishness level. It is the smallest fraction… Expand

Optimizing the price of anarchy in concave cost sharing games

- Computer Science
- 2017 American Control Conference (ACC)
- 2017

The main result of this paper is a characterization of the optimal local agent objective functions for concave cost sharing games, and it is demonstrated that the Shapley value objective function is the unique local and anonymous agent objective function that achieves the minimum price of anarchy. Expand

Analysis of Price of Total Anarchy in Congestion Games via Smoothness Arguments

- Computer Science
- IEEE Transactions on Control of Network Systems
- 2017

In a traffic network with heterogeneous players, it is shown that the upper bound of POTA is the same as that in a network with homogeneous players as time goes to infinity, and the results are applied to a traffic routing problem based on the real traffic data of Singapore. Expand

PRICE OF ANARCHY IN ATOMIC CONGESTION GAMES WITH STOCHASTIC DEMANDS AND AFFINE COSTS

- 2019

We consider atomic congestion games with stochastic demands. The game captures the fact that players may end up not being able to participate. Participation happens independently and with exogenous… Expand

Incentives in dynamic markets

- Business
- 2017

Abstract In this thesis, we consider a variety of combinatorial optimization problems within a common theme of uncertainty and selfish behavior. In our first scenario, the input is collected from… Expand

Tight Welfare Guarantees for Pure Nash Equilibria of the Uniform Price Auction

- Economics, Computer Science
- Theory of Computing Systems
- 2018

A tight upper and lower bound on the inefficiency of equilibria is shown, showing that the Price of Anarchy is bounded by 2.1885, resolving one of the open questions posed in previous works on multi-unit auctions. Expand

On the efficiency of the walrasian mechanism

- Economics, Computer Science
- EC
- 2014

The main result is that the welfare of every pure Nash equilibrium of the Walrasian mechanism is at least one quarter of the optimal welfare, when players have gross substitute valuations and do not overbid. Expand

#### References

SHOWING 1-10 OF 155 REFERENCES

Strong price of anarchy

- Economics, Computer Science
- SODA '07
- 2007

This work defines the strong price of anarchy to be the ratio of the worst case strong equilibrium to the social optimum, and shows that a strong equilibrium always exists, except for a well defined subset of network creation games. Expand

Regret minimization and the price of total anarchy

- Computer Science, Economics
- STOC
- 2008

It is proved that despite the weakened assumptions, in several broad classes of games, this "price of total anarchy" matches the Nash price of anarchy, even though play may never converge to Nash equilibrium. Expand

Strong Price of Anarchy, Utility Games and Coalitional Dynamics

- Economics, Computer Science
- SAGT
- 2014

A framework for studying the effect of cooperation on the quality of outcomes in utility games, a coalitional analog of the smoothness framework of non-cooperative games, and novel strong price of anarchy results for any monotone utility-maximization game are given. Expand

On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games

- Computer Science
- ESA
- 2005

It is shown that for the sum social cost, which corresponds to the average cost of the players, every linear congestion game has Nash and correlated price of stability at most 1.6, and the same bound holds for symmetric games as well. Expand

The price of anarchy in games of incomplete information

- Economics, Computer Science
- EC '12
- 2012

We define smooth games of incomplete information. We prove an "extension theorem" for such games: price of anarchy bounds for pure Nash equilibria for all induced full-information games extend… Expand

Strong and Pareto Price of Anarchy in Congestion Games

- Economics, Computer Science
- ICALP
- 2009

It is shown that in asymmetric games the strong and Pareto prices of anarchy coincide exactly with the known value $\frac{5}{2}$ for standard Nash, but are strictly smaller for symmetric games. Expand

The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds

- Mathematics, Computer Science
- WINE
- 2010

A formal duality is shown between certain equilibrium concepts, including the correlated and coarse correlated equilibrium, and analysis frameworks for proving bounds on the price of anarchy for such concepts, and a characterization of the set of distributions over game outcomes to which "smoothness bounds" always apply. Expand

Altruism and Its Impact on the Price of Anarchy

- Economics, Computer Science
- TEAC
- 2014

The authors' bounds show that for atomic congestion games and cost-sharing games, the robust price of anarchy gets worse with increasing altruism, while for valid utility games, it remains constant and is not affected by altruism. Expand

Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction

- Economics, Computer Science
- 2010 IEEE 51st Annual Symposium on Foundations of Computer Science
- 2010

This paper is the first to prove bounds on the price of anarchy, and to give any bounds in the Bayesian setting, and exhibits a combinatorial structure of Nash equilibria and uses this structure to bound the priceof anarchy. Expand

Price of anarchy for greedy auctions

- Computer Science, Economics
- SODA '10
- 2010

A simple deterministic mechanism for general combinatorial auctions that obtains an O(√m) approximation at every Bayes-Nash equilibrium (BNE) is exhibited. Expand