Utility Design for Distributed Resource Allocation—Part I: Characterizing and Optimizing the Exact Price of Anarchy

DOI10.1109/TAC.2019.2961995zbMATH Open1492.91162arXiv1807.01333OpenAlexW3099868047MaRDI QIDQ5853880FDOQ5853880

Authors: Dario Paccagnan, Rahul Chandan, Jason R. Marden 

Publication date: 12 March 2021

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: Game theory has emerged as a fruitful paradigm for the design of networked multiagent systems. A fundamental component of this approach is the design of agents' utility functions so that their self-interested maximization results in a desirable collective behavior. In this work we focus on a well-studied class of distributed resource allocation problems where each agent is requested to select a subset of resources with the goal of optimizing a given system-level objective. Our core contribution is the development of a novel framework to tightly characterize the worst case performance of any resulting Nash equilibrium (price of anarchy) as a function of the chosen agents' utility functions. Leveraging this result, we identify how to design such utilities so as to optimize the price of anarchy through a tractable linear program. This provides us with a priori performance certificates applicable to any existing learning algorithm capable of driving the system to an equilibrium. Part II of this work specializes these results to submodular and supermodular objectives, discusses the complexity of computing Nash equilibria, and provides multiple illustrations of the theoretical findings.

Full work available at URL: https://arxiv.org/abs/1807.01333

Recommendations

• The price of anarchy and the design of scalable resource allocation mechanisms
• Design of price mechanisms for network resource allocation via price of anarchy
• The Price of Anarchy of generic valid utility systems
• The price of anarchy of the proportional allocation mechanism revisited
• Price-based protocols for fair resource allocation, convergence time analysis and extension to Leontief utilities
• Integer Programming and Combinatorial Optimization
• Price of Anarchy in Networks with Heterogeneous Latency Functions
• Utility Design for Distributed Resource Allocation—Part II: Applications to Submodular, Covering, and Supermodular Problems
• The price of anarchy for instantaneous dynamic equilibria

Mathematics Subject Classification ID

Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cited In (4)

• Robust utility design in distributed resource allocation problems with defective agents
• Utility Design for Distributed Resource Allocation—Part II: Applications to Submodular, Covering, and Supermodular Problems
• Robust networked multiagent optimization: designing agents to repair their own utility functions
• The price of anarchy as a classifier for mechanism design in a Pareto-Bayesian-Nash context

This page was built for publication: Utility Design for Distributed Resource Allocation—Part I: Characterizing and Optimizing the Exact Price of Anarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853880)