Gairing, Martin and Paccagnan, Dario
(2023)
In Congestion Games, Taxes Achieve Optimal Approximation.
Operations Research.
pp. 743-744.
|
Text
taxes-OR-FINAL.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (1MB) | Preview |
Abstract
<jats:p> The Power of Traffic Tolls </jats:p><jats:p> The paper “In Congestion Games, Taxes Achieve Optimal Approximation” by Paccagnan and Gairing investigates the power and limitations of taxes as interventions in congestion games. Perhaps surprisingly, they find that efficiently computed taxes can achieve the same performance as the best polynomial time algorithm, even when the algorithm has full control over the agents’ actions. The authors establish three main results to support this claim. First, they prove that minimizing congestion is NP-hard to approximate within a given factor based on the latency functions. Second, they demonstrate how convex optimization tools can be used to design optimal taxes. Third, they provide a polynomial time algorithm with an approximation factor matching the hardness barrier. The upshot of their contribution can be summarized as follows: Judiciously designed taxes achieve optimal approximation, and no other tractable intervention can improve upon this result. </jats:p>
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | congestion games, minimum social cost, hardness of approximation, optimal tolls, approximation algorithms, price of anarchy |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 22 Jun 2023 08:05 |
| Last Modified: | 26 Sep 2023 09:29 |
| DOI: | 10.1287/opre.2021.0526 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3171203 |
Dimensions
Dimensions
