Dynamic taxes for polynomial congestion games

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 which 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.