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
Bilo V.;Vinci C.
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
