Michal Feldman
ABSTRACT
We present an analysis framework for bounding the price of anarchy (POA) in games that have many players, as in many of the games most pertinent to computer science applications. We use this framework to demonstrate that, in many of the models in which the POA has been studied, the POA in large games is much smaller than the worst-case bound. Our framework also differentiates between mechanisms with similar worst-case performance, such as simultaneous uniform-price auctions and greedy combinatorial auctions, thereby providing new insights about which mechanisms are likely to perform well in realistic settings.
- R. J. Aumann and L. S. Shapley. Values of Non-Atomic Games. Princeton University Press, 1974.Google Scholar
- E. M. Azevedo and E. Budish. Strategy-proofness in the large. Working paper, 2011.Google Scholar
- A. C. Berry. The accuracy of the gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society, 49(1):pp. 122–136, 1941.Google ScholarCross Ref
- K. Bhawalkar and T. Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. In SODA, 2011. Google ScholarDigital Library
- K. L. Brown. Resource allocation in competitive multiagent systems. Ph.d. thesis, Stanford University, 2003.Google Scholar
- G. Christodoulou, A. Kovacs, and M. Schapira. Bayesian Combinatorial Auctions. In ICALP ’08 Proceedings of the 35th international colloquium on Automata, Languages and Programming, 2008. Google ScholarDigital Library
- R. Cole and Y. Tao. The price of anarchy of large walrasian auctions. CoRR, abs/1508.07370, 2015.Google Scholar
- B. de Keijzer, E. Markakis, G. Schäfer, and O. Telelis. Inefficiency of standard multi-unit auctions. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA), pages 385–396, 2013.Google ScholarCross Ref
- C.-G. Esseen. On the liapunoff limit of error in the theory of probability. Arkiv f ˜ A˝ ur Matematik, Astronomi och Fysik., A28:1–19, 1942.Google Scholar
- U. Feige, M. Feldman, N. Immorlica, R. Izsak, B. Lucier, and V. Syrgkanis. A unifying hierarchy of valuations with complements and substitutes. In In Proceedings of 29th AAAI Conference on Artificial Intelligence (AAAI), 2015. Google ScholarDigital Library
- M. Feldman, H. Fu, N. Gravin, and B. Lucier. Simultaneous auctions are (almost) efficient. In STOC, 2013. Google ScholarDigital Library
- A. Hassidim, H. Kaplan, Y. Mansour, and N. Nisan. Non-price equilibria in markets of discrete goods. In EC’11, 2011. Google ScholarDigital Library
- K. Iyer, R. Johari, and M. Sundararajan. Mean field equilibria of dynamic auctions with learning. In Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), San Jose, CA, USA, June 5-9, 2011, pages 339–340, 2011. Google ScholarDigital Library
- M. O. Jackson and A. M. Manelli. Approximately Competitive Equilibria in Large Finite Economies. Journal of Economic Theory, 77(2):354–376, December 1997.Google ScholarCross Ref
- E. Kalai. Large robust games. Econometrica, 72(6):1631–1665, 2004.Google ScholarCross Ref
- M. Kearns. Graphical games. In N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, editors, Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.Google ScholarCross Ref
- M. Kearns, M. M. Pai, A. Roth, and J. Ullman. Mechanism design in large games: incentives and privacy. In Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, pages 403–410, 2014. Google ScholarDigital Library
- B. Lucier and A. Borodin. Price of anarchy for greedy auctions. In SODA, 2010. Google ScholarDigital Library
- E. Markakis and O. Telelis. Uniform price auctions: Equilibria and efficiency. In SAGT, 2012.Google ScholarCross Ref
- M. M. Pai, A. Roth, and J. Ullman. An anti-folk theorem for large repeated games with imperfect monitoring. CoRR, abs/1402.2801, 2014.Google Scholar
- D. J. Roberts and A. Postlewaite. The incentives for price-taking behavior in large exchange economies. Econometrica, 44(1), 1976.Google Scholar
- R. M. Rogers and A. Roth. Asymptotically truthful equilibrium selection in large congestion games. In ACM Conference on Economics and Computation, EC ’14, Stanford, CA, USA, June 8-12, 2014, pages 771–782, 2014. Google ScholarDigital Library
- T. Roughgarden. Intrinsic robustness of the price of anarchy. In STOC, 2009. Google ScholarDigital Library
- T. Roughgarden. The price of anarchy in games of incomplete information. In EC, 2012. Google ScholarDigital Library
- D. Schmeidler. Equilibrium points of nonatomic games. Journal of Statistical Physics, 7(4):295–300, 1973.Google ScholarCross Ref
- I. Shevtsova. On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands. ArXiv e-prints, Nov. 2011.Google Scholar
- Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game Theoretic and Logical Foundat ions. Cambridge University Press, 2008. Google ScholarDigital Library
- R. M. Starr. Quasi-Equilibria in Markets with Non-Convex Preferences. Econometrica, 37(1):25–38, January 1969.Google Scholar
- J. M. Swinkels. Efficiency of large private value auctions. Econometrica, 69(1):pp. 37–68, 2001.Google ScholarCross Ref
- V. Syrgkanis. Bayesian games and the smoothness framework. CoRR, abs/1203.5155, 2012.Google Scholar
- V. Syrgkanis and E. Tardos. Composable and efficient mechanisms. In STOC, 2013. Google ScholarDigital Library
- J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.Google Scholar
Index Terms
- The price of anarchy in large games
Recommendations
The price of anarchy of finite congestion games
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingWe consider the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. For asymmetric games, the price of anarchy of maximum social cost is Θ(√N), where N is the number of players. For all other cases of symmetric or ...
Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions
We study the price of anarchy (PoA) of simultaneous first-price auctions (FPAs) for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian price of anarchy (BPoA) of these auctions are e/(e − 1) [Syrgkanis and ...
The price of anarchy in bertrand games
EC '09: Proceedings of the 10th ACM conference on Electronic commerceThe Internet is composed of multiple economically-independent service providers that sell bandwidth in their networks so as to maximize their own revenue. Users, on the other hand, route their traffic selfishly to maximize their own utility. How does ...
Comments