Seminar: "Two birds with one stone: optimal approximation for integral routing and congestion pricing" - Prof. Dario Paccagnan (Imperial College London)
Seminar organized within the project DISMA Excellence Project 2018-2022.
"Two birds with one stone: optimal approximation for integral routing and congestion pricing"
Prof. Dario Paccagnan (Imperial College London)
Wednesday January 12, 2021 at 9:30
Politecnico di Torino, DISMA, Aula Buzano (third floor)
Abstract: Motivated by fleet management in autonomous mobility, we consider the classical problem of minimizing total congestion in integral multicommodity routing, for which we provide the first polynomial time algorithm with optimal approximation. Perhaps surprisingly, we show that efficiently computed taxation mechanisms also yield the same optimal approximation achieved by the best polynomial time algorithm, even if the latter has dictatorial 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 minimizing the total congestion is NP-hard to approximate within a given expression depending solely on the class of admissible resource costs. Second, we design a tractable taxation mechanism whose efficiency (price of anarchy) matches the hardness factor. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits these same performances, allowing us to devise polynomial time algorithms with optimal approximation. Joint work with: Martin Gairing (University of Liverpool).
Flyer of the event: the flyer of the event can be downloaded here