Invariant Price of Anarchy Bounds via Multiplicative Smoothness

The Price of Anarchy (PoA) measures efficiency loss due to decentralized decision-making. Most analyses assume Cardinal Full-Comparability (CFC), where utilities are interpersonally comparable. Without that assumption, utilities are unique only up to agent-specific affine transformations, making standard PoA bounds representation-dependent. In this paper, Shilov, Nax, and Bolognani propose a new framework under Cardinal Non-Comparability (CNC) using multiplicative smoothness—a product-form condition aligned with Nash welfare. This yields PoA bounds that are invariant under such transformations and extend naturally to coarse correlated equilibria, covering no-regret learning outcomes.

The authors apply their framework to single-choice welfare games, deriving bounds via a multiplicative retention envelope and geometric closure. The key insight is that the true cost of decentralization depends critically on whether utilities are comparable; their CNC-invariant bounds provide a more principled way to interpret efficiency losses. This work has significant implications for mechanism design, online learning, and economic theory, offering a robust analytical tool for systems where interpersonal comparisons are not justified.