Optimal Taxes in Atomic Congestion Games

28^th October 2020, 13:00
Dario Paccagnan
Imperial College London

Abstract

Throughout modern society, human users interact with large-scale engineered systems, e.g., road-traffic networks, electric power grids, wireless communication networks. As the performance of such systems greatly depends on the decisions made by the users - often leading to undesirable system behavior - a natural question arises: how can we design incentives to promote efficient use of the existing infrastructure? In this talk, we answer this question in relation to the well-studied class of atomic congestion games, used to model a variety of problems, including traffic routing. More precisely, we show how to design tractable tolling mechanisms that minimize the system inefficiency (price of anarchy) exploiting solely local information. When specializing our approach to the polynomial case, we obtain tight values for the optimal price of anarchy and corresponding tolls, uncovering an unexpected link with load balancing games. We also derive optimal tolling mechanisms that are constant with the congestion level, generalizing the results of Caragiannis et al. [ACM Transactions on Algorithms, 2010 ] to polynomial congestion games and beyond. Surprisingly, optimal tolling mechanism designed using only local information perform closely to existing mechanism that utilize global information [Bilo and Vinci, ACM Transactions on Economics and Computation, 2019 ], while the marginal cost mechanism, known to be optimal in the continuous-flow model, has lower efficiency than that encountered levying no toll. All results are tight for pure Nash equilibria, and extend to coarse correlated equilibria.

Authors: Dario Paccagnan, Rahul Chandan, Bryce L. Ferguson, Jason R. Marden