Invariant Price of Anarchy and Multiplicative Smoothness

Ilia Shilov, Heinrich H. Nax and Saverio Bolognani

Papers from arXiv.org

Abstract: The Price of Anarchy (PoA) is a popular measure of the costs of decentralization in terms of efficiency losses. Almost all PoA analyses operate within a framework assuming both Cardinal Full-Comparability (CFC) and smoothness, in which case any derived bounds conveniently extend beyond pure Nash to coarse correlated equilibria and no-regret learning outcomes. However, interpersonal utility comparability is an additional assumption that generally has to be justified. Without it, cardinal utilities (e.g. defined under classical von Neumann--Morgenstern framework) are unique only up to agent-specific affine transformations, rendering both the utilitarian PoA and the classical smoothness conditions representation-dependent. In this paper, we operate under a more general Cardinal Non-Comparability (CNC) framework, under which the weighted Nash welfare is a canonical admissible aggregator. We introduce multiplicative smoothness, a product-form condition matched to the multiplicative structure of Nash welfare, and obtain PoA bounds that are CNC-invariant and extend to coarse correlated equilibria. We demonstrate applicability of our framework on single-choice welfare games, deriving the bounds through simple proof relying on multiplicative retention envelope and geometric closure. The interpretation of this bound in terms of the true cost of decentralization depends crucially on interpersonal comparability of utilities.

Date: 2026-06
References: Add references at CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2606.11397 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2606.11397

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().