Imperial College London
Portrait Picture

DrDarioPaccagnan

Faculty of Engineering, Department of Computing

Senior Lecturer
 
 
 
//

Contact

 

d.paccagnan Website

 
 
//

Location

 

Electrical EngineeringSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Paccagnan:2020:10.1109/tac.2019.2961995,
author = {Paccagnan, D and Chandan, R and Marden, JR},
doi = {10.1109/tac.2019.2961995},
journal = {IEEE Transactions on Automatic Control},
pages = {4616--4631},
title = {Utility design for distributed resource Allocation - Part I: characterizing and optimizing the exact price of anarchy},
url = {http://dx.doi.org/10.1109/tac.2019.2961995},
volume = {65},
year = {2020}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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.
AU  - Paccagnan,D
AU  - Chandan,R
AU  - Marden,JR
DO  - 10.1109/tac.2019.2961995
EP  - 4631
PY  - 2020///
SN  - 0018-9286
SP  - 4616
TI  - Utility design for distributed resource Allocation - Part I: characterizing and optimizing the exact price of anarchy
T2  - IEEE Transactions on Automatic Control
UR  - http://dx.doi.org/10.1109/tac.2019.2961995
UR  - https://ieeexplore.ieee.org/document/8941319
UR  - http://hdl.handle.net/10044/1/81185
VL  - 65
ER  -
Download