This website uses third party cookies to improve your experience. If you continue browsing or close this notice, you will accept their use.

Dynamic Taxes for Polynomial Congestion Games

21 September 2017 at 12:01 PM - 1:00 PM

Room 207, Campus on Viale Romania, 32

Speaker: Cosimo Vinci, GSSI

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 [Bilo, 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.