Abstract
In game theory, the price of anarchy framework studies efficiency loss in decentralized environments. Optimization and decision theory, on the other hand, explore tradeoffs between optimality and robustness in the case of single-agent decision making under uncertainty. What happens when we combine both approaches? We examine connections between the efficiency loss due to decentralization and the efficiency loss due to uncertainty and establish tight performance guarantees for distributed systems in uncertain environments. We present applications based on novel variants of atomic congestion games with uncertain costs, for which we provide tight performance bounds under a wide range of risk attitudes. Our results establish that the individual's attitude toward uncertainty has a critical effect on system performance and therefore should be a subject of close and systematic investigation.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1-27 |
| Number of pages | 27 |
| Journal | ACM Transactions on Economics and Computation |
| Volume | 5 |
| Issue number | 1 |
| DOIs | |
| State | Published - Oct 26 2016 |
Bibliographical note
KAUST Repository Item: Exported on 2020-10-01Acknowledgements: Georgios Piliouras and Jeff S. Shamma would like to acknowledge AFOSR/MURI Project FA9550-09-1-0538, AFOSR Project FA9550-09-1-0420 as well as ONR Grant N00014-09-1-0751 for their support in the funding of this research. Georgios Piliouras would also like to acknowledge the CMI Wally Baer and Jeri Weiss postdoctoral fellowship, SUTD grant SRG ESD 2015 097 and MOE AcRF Tier 2 Grant 2016-T2-1-170. Evdokia Nikolova would like to acknowledge NSF CCF Grants 1216103, 1350823, 1331863. Part of the work was completed while Georgios Piliouras was a CMI Wally Baer and Jeri Weiss postdoctoral fellow at California Institute of Technology. Part of the work was completed while Georgios Piliouras and Evdokia Nikolova were resident scientists at the Simons Institute for the Theory of Computing.