Risk sensitivity of price of anarchy under uncertainty

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 40 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.