Utility design improves worst case outcomes in networked multi-agent games
Deriving the Pure Price of Anarchy for Networked Resource Allocation Games
Computer Science and Game TheoryMultiagent Systems
Summary
When many agents work together but only have partial communication with each other, it’s tricky to design incentives so they achieve the best overall outcome. The authors study how to assign local rewards to these agents to steer them toward good results, measured by how bad the worst stable outcome can be compared to the ideal. They provide a way to find the best local reward designs for any network setup using a mathematical program. Surprisingly, sometimes cutting off all communication among agents leads to the best behavior. Their approach also finds good solutions for many kinds of problems including coverage tasks.
What this means in practice
- •For network schedulers: Assign localized utility functions to communication-limited devices to guarantee stable system performance despite network constraints.
- •For resource allocation teams: Design incentive rules for agents sharing resources over arbitrary networks to optimize worst-case efficiency in coverage and coordination tasks.
Authors
Vartika Singh, Philip N. Brown
Abstract
This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.