Risk sensitivity of price of anarchy under uncertainty

Georgios Piliouras, Evdokia Nikolova, Jeff S. Shamma

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Scopus citations

Abstract

In algorithmic game theory, the price of anarchy framework studies efficiency loss in decentralized environments. In optimization and decision theory, the price of robustness framework explores the tradeoffs between optimality and robustness in the case of single agent decision making under uncertainty. We establish a connection between the two that provides a novel analytic framework for proving tight performance guarantees for distributed systems in uncertain environments. We present applications of this framework to 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 towards uncertainty has a critical effect on system performance and should therefore be a subject of close and systematic investigation.

Original languageEnglish (US)
Title of host publicationEC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce
Pages715-732
Number of pages18
StatePublished - Jul 10 2013
Event14th ACM Conference on Electronic Commerce, EC 2013 - Philadelphia, PA, United States
Duration: Jun 16 2013Jun 20 2013

Publication series

NameProceedings of the ACM Conference on Electronic Commerce

Other

Other14th ACM Conference on Electronic Commerce, EC 2013
CountryUnited States
CityPhiladelphia, PA
Period06/16/1306/20/13

Keywords

  • Congestion games
  • Price of anarchy
  • Price of robustness
  • Robust optimization
  • Stochastic optimization

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Risk sensitivity of price of anarchy under uncertainty'. Together they form a unique fingerprint.

Cite this