The Price of Uncertainty
Abstract
In this work, 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. We show that in certain cases, even extremely small fluctuations can have the ability to 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Sep 01, 2013
- Source ID
- 10.1145/2509413.2509415
Entities
People
- Avrim Blum
- Maria-florina Balcan
- Yishay Mansour
Organizations
- Air Force Office of Scientific Research
- Carnegie Mellon University
- Division of Computing and Communication Foundations
- Georgia Tech
- Israel Science Foundation
- Israeli Centers for Research Excellence
- Office of Naval Research
- Seventh Framework Programme
- Tel Aviv University