Center for Algorithms and Theory of Computation

CS 269S, Winter 2022: Theory Seminar


January 21, 2022, 1:00 – 1:50pm: online

In Congestion Games, Taxes Achieve Optimal Approximation

Freddy Reiber

Abstract:

We consider the problem of minimizing social cost in atomic congestion games and show, perhaps surprisingly, that efficiently computed taxation mechanisms yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the players' actions. To do this we give two contributions. 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 optimal. Finally, 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.

Paper by: Dario Paccagnan, Martin Gairing, https://arxiv.org/abs/2105.07480