Methodologies for Quantifying and Optimizing the Price of Anarchy

• 成果类型: Article
• 署名作者: Chandan, Rahul; Paccagnan, Dario; Marden, Jason R.
• 署名单位: Imperial College London; University of California System; University of California Santa Barbara
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3401787
• 发表日期: 2024
• 页码: 7742-7757
• 关键词: games; COSTS; minimization; measurement; Nash equilibrium; reviews; optimization; Congestion games; game theory; multiagent systems; price of anarchy (PoA)

摘要

The use of game theory for the analysis and design of socio-technological systems has received significant attention as it enables the quantification of the system-level performance while accounting for the presence of individual decision makers. In this context, a popular metric for analyzing the system-level performance is the price of anarchy (PoA), which measures the loss in efficiency caused by distributed decision making. Over the past two decades, significant effort has been devoted to developing analytical and computational methodologies for characterizing this metric, with remarkable success. However, existing approaches for obtaining PoA bounds either require the solution of intractable programs, or provide bounds that are not tight. Motivated by this gap, our work develops a computationally efficient framework to tightly characterize the PoA in a broad class of problems. Our framework not only recovers and generalizes many existing PoA results, but it also enables the efficient computation of decision-making rules that optimize the PoA-a central component in the design of socio-technological systems.