The price of uncertainty

ABSTRACT

We study the degree to which small fluctuations in costs in well-studied potential games can impact the result of natural best-response and improved-response dynamics. We call this the Price of Uncertainty and study it in a wide variety of potential games (including fair cost-sharing games, set-cover games, routing games, and job-scheduling games), finding a number of surprising results. In particular, we show that in certain cases, even extremely small fluctuations can cause these dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large degrees of fluctuation.

We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show again a contrast between different games. In certain cases (e.g., fair cost-sharing, set-covering, job-scheduling) even a single Byzantine player can cause best-response dynamics to transition to states of substantially higher cost, whereas in others (e.g., the class of beta-nice games which includes routing, market-sharing and many others) these dynamics are much more resilient.

REFERENCES

• 1: Heiner Ackermann , Heiko Roglin , Berthold Vocking, On the Impact of Combinatorial Structure on Congestion Games, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.613-622, October 21-24, 2006 [doi>10.1109/FOCS.2006.55]
• 2: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 3: Baruch Awerbuch , Yossi Azar , Amir Epstein , Vahab Seyed Mirrokni , Alexander Skopalik, Fast convergence to nearly optimal solutions in potential games, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386832]
• 4: Moshe Babaioff , Robert Kleinberg , Christos H. Papadimitriou, Congestion games with malicious players, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250926]
• 5: M.-F. Balcan, A. Blum, and Y. Mansour. The price of uncertainty (full version). http://www.cs.cmu.edu/~ninamf/papers/pou-full.pdf.
• 6: Niv Buchbinder , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative Cost Sharing Games Via Subsidies, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_30]
• 7: G. Christodoulou, V.S. Mirrokni, and A. Sidiropoulos. Convergence and approximation in potential games. In Proc. 23rd STACS, 2006.
• 8: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 9: B. de Finetti. La prevision: Ses lois logiques, ses sources subjectives. Annales de l'Institut Henri Poincare, 7:1--68, 1937.
• 10: Eyal Even-Dar , Alex Kesselman , Yishay Mansour, Convergence time to Nash equilibrium in load balancing, ACM Transactions on Algorithms (TALG), v.3 n.3, p.32-es, August 2007 [doi>10.1145/1273340.1273348]
• 11: M.X. Goemans, L. Li, V.S. Mirrokni, and M. Thottan. Market sharing games applied to content distribution in ad-hoc networks. IEEE Journal on Selected Areas in Communication, 24:1020--1033, 2006.
• 12: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM (JACM), v.45 n.6, p.983-1006, Nov. 1998 [doi>10.1145/293347.293351]
• 13: E. Koutsoupias and C.H. Papadimitriou. Worst-case equilibria. In Proc. 16th STACS, pages 404--413, 1999.
• 14: D. Monderer and L.S. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
• 15: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, When selfish meets evil: byzantine players in a virus inoculation game, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146391]
• 16: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 17: R.W. Rosenthal. A class of games possessing pure-strategy nash equilibria. Int. Journal Game Theory, 2(1), 1973.
• 18: Aaron Roth, The Price of Malice in Linear Congestion Games, Proceedings of the 4th International Workshop on Internet and Network Economics, December 17-20, 2008, Shanghai, China [doi>10.1007/978-3-540-92185-1_20]
• 19: L.J. Savage. The Foundations of Statistics. John Wiley and Sons, 1954.
• 20: A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2002.
• 21: A. Tversky and D. Kahneman. The framing of decisions and the psychology of choice. Science, 211:453--458, 1981.
• 22: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 23: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics, Theory

Keywords:
algorithmic game theory, best response dynamics, social cost