We consider the efficiency of taxation in congestion games with polynomial latency functions along the line of research initiated by Caragiannis et al. [ACM Transactions on Algorithms, 2010], who focused on both pure and mixed Nash equilibria in games with affine latencies only. By exploiting the primal-dual method [Bilò, Proceedings of the 10th Workshop on Approximation and Online Algorithms, 2012], we obtain interesting upper bounds with respect to a variety of different solution concepts ranging from approximate pure Nash equilibria up to approximate coarse correlated equilibria, and including also approximate one-round walks starting from the empty state. Our findings show a high beneficial effect of taxation that increases more than linearly with the degree of the latency functions. In some cases, a tight relationship with some well-studied polynomials in Combinatorics and Number Theory, such as the Touchard and the Geometric polynomials, arises. In these cases, we can also show matching lower bounds, albeit under mild assumptions; interestingly, our upper bounds are derived by exploiting the combinatorial definition of these polynomials, while our lower bounds are constructed by relying on their analytical characterization.

Dynamic taxes for polynomial congestion games

Bilò Vittorio;Vinci Cosimo
2019-01-01

Abstract

We consider the efficiency of taxation in congestion games with polynomial latency functions along the line of research initiated by Caragiannis et al. [ACM Transactions on Algorithms, 2010], who focused on both pure and mixed Nash equilibria in games with affine latencies only. By exploiting the primal-dual method [Bilò, Proceedings of the 10th Workshop on Approximation and Online Algorithms, 2012], we obtain interesting upper bounds with respect to a variety of different solution concepts ranging from approximate pure Nash equilibria up to approximate coarse correlated equilibria, and including also approximate one-round walks starting from the empty state. Our findings show a high beneficial effect of taxation that increases more than linearly with the degree of the latency functions. In some cases, a tight relationship with some well-studied polynomials in Combinatorics and Number Theory, such as the Touchard and the Geometric polynomials, arises. In these cases, we can also show matching lower bounds, albeit under mild assumptions; interestingly, our upper bounds are derived by exploiting the combinatorial definition of these polynomials, while our lower bounds are constructed by relying on their analytical characterization.
File in questo prodotto:
File Dimensione Formato  
3355946.pdf

non disponibili

Tipologia: Versione editoriale
Licenza: Copyright dell'editore
Dimensione 534.89 kB
Formato Adobe PDF
534.89 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/445653
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 12
social impact