2019/11/18 by Rahul Chandan, Chandan, Rahul, Dario Paccagnan +3
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Electrical engineering #Game Theory and Applications #Game Theory and Voting Systems #Multiagent Systems (cs.MA) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1911.07823
openalex created_date 2019/05/03 · openalex publication_date 2019/11/18 · openalex updated_date 2026/07/28
The price of anarchy (PoA) is a popular metric for analyzing the inefficiency of self-interested decision making. Although its study is widespread, characterizing the PoA can be challenging. A commonly employed approach is based on the smoothness framework, which provides tight PoA values under the assumption that the system objective consists in the sum of the agents' individual welfares. Unfortunately, several important classes of problems do not satisfy this requirement (e.g., taxation in congestion games), and our first result demonstrates that the smoothness framework does *not* tightly characterize the PoA for such settings. Motivated by this observation, this work develops a framework that achieves two chief objectives: i) to tightly characterize the PoA for such scenarios, and ii) to do so through a tractable approach. As a direct consequence, the proposed framework recovers and generalizes many existing PoA results, and enables efficient computation of incentives that optimize the PoA. We conclude by highlighting the applicability of our contributions to incentive design in congestion games and utility design in distributed welfare games.