Improved Price of Anarchy via Predictions
Authors:
Open Access
- 12 July 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 529-557
Abstract
A central goal in algorithmic game theory is to analyze the performance of decentralized multiagent systems, like communication and information networks. In the absence of a central planner who can enforce how these systems are utilized, the users can strategically interact with the system, aiming to maximize their own utility, possibly leading to very inefficient outcomes, and thus a high price of anarchy. To alleviate this issue, the system designer can use decentralized mechanisms that regulate the use of each resource (e.g., using local queuing protocols or scheduling mechanisms), but with only limited information regarding the state of the system. These information limitations have a severe impact on what such decentralized mechanisms can achieve, so most of the success stories in this literature have had to make restrictive assumptions (e.g., by either restricting the structure of the networks or the types of cost functions). In this paper, we overcome some of the obstacles that the literature has imposed on decentralized mechanisms, by designing mechanisms that are enhanced with predictions regarding the missing information. Specifically, inspired by the big success of the literature on "algorithms with predictions", we design decentralized mechanisms with predictions and evaluate their price of anarchy as a function of the prediction error, focusing on two very well-studied classes of games: scheduling games and multicast network formation games.Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF-2047907)
This publication has 26 references indexed in Scilit:
- Decentralized utilitarian mechanisms for scheduling gamesGames and Economic Behavior, 2015
- Improving the Price of Anarchy for Selfish Routing via Coordination MechanismsAlgorithmica, 2013
- Improved Lower Bounds on the Price of Stability of Undirected Network Design GamesTheory of Computing Systems, 2012
- Coordination mechanismsTheoretical Computer Science, 2009
- An upper bound on the price of stability for undirected Shapley network design gamesInformation Processing Letters, 2009
- Coordination mechanisms for selfish schedulingTheoretical Computer Science, 2009
- Network Design with Weighted PlayersTheory of Computing Systems, 2008
- The Price of Stability for Network Design with Fair Cost AllocationSIAM Journal on Computing, 2008
- The price of anarchy of serial, average and incremental cost sharingEconomic Theory, 2007
- Dynamic Steiner Tree ProblemSIAM Journal on Discrete Mathematics, 1991