Paccagnan, Dario and Gairing, Martin
(2021)
In Congestion Games, Taxes Achieve Optimal Approximation.
In: EC '21: The 22nd ACM Conference on Economics and Computation, 2021-7-18 - 2021-7-23, Budapest, Hungary.
|
Text
2105.07480v1.pdf - Author Accepted Manuscript Download (1MB) | Preview |
Abstract
In this work, we consider the problem of minimising the social cost in atomic congestion games. For this problem, we provide tight computational lower bounds along with taxation mechanisms yielding polynomial time algorithms with optimal approximation. Perhaps surprisingly, our 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 resource costs. Second, we design a tractable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is worst-case optimal. 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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | A preliminary version of this work appeared at the 22nd ACM Conference on Economics & Computation (EC'21) |
| Uncontrolled Keywords: | cs.GT, cs.GT, cs.CC, math.OC |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 02 Jun 2021 15:08 |
| Last Modified: | 18 Jan 2023 22:37 |
| DOI: | 10.1145/3465456.3467601 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3124802 |
Dimensions
Dimensions
