Eventi del

13 2022 12:30 - 13:45
Stanza 3-E4-SR03 / Zoom

In congestion games, taxes achieve optimal approximation

Dario Paccagnan (Imperial College London)

Abstract: Motivated by fleet management in autonomous mobility, we consider the classical problem of minimizing the social cost in atomic congestion games, including integral multi-commodity routing as a special case. In this context we show, perhaps surprisingly, that efficiently computed taxation mechanisms yield the same performance achievable by the best centralized polynomial time algorithm, even when the latter has full control over the players' 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, each settling a previously open problem  First, we show that computing the minimum social cost is NP-hard to approximate within an explicitly 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. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise the first polynomial time algorithm with optimal approximation.

 

Per ulteriori informazioni o per ricevere il link Zoom dell'evento, per favore scrivere a elisur.magrini@unibocconi.it