In Congestion Games, Taxes Achieve Optimal Approximation

Dario Paccagnan () and Martin Gairing ()
Additional contact information
Dario Paccagnan: Department of Computing, Imperial College London, London SW7 2AZ, United Kingdom
Martin Gairing: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom

Operations Research, 2024, vol. 72, issue 3, 966-982

Abstract: In this work, we address the problem of minimizing social cost in atomic congestion games. For this problem, we present lower bounds on the approximation ratio achievable in polynomial time and demonstrate that efficiently computable taxes result in polynomial time algorithms matching such bounds. Perhaps surprisingly, these results show that indirect interventions, in the form of efficiently computed taxation mechanisms, yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the agents’ actions. It follows that no other tractable approach geared at incentivizing desirable system behavior can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. In short: Judiciously chosen taxes achieve optimal approximation. Three technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP -hard to approximate within a given factor depending solely on the admissible cost functions. Second, we design a polynomially computable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is optimal among all tractable mechanisms. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time algorithms with optimal approximation.

Keywords: Market Analytics and Revenue Management; congestion games; minimum social cost; hardness of approximation; optimal tolls; approximation algorithms; price of anarchy (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0526 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:3:p:966-982

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().