Non-atomic one-round walks in polynomial congestion games

In this paper we study the approximation ratio of the solutions achieved after an ϵ-approximate one-round walk in non-atomic congestion games. Prior to this work, the solution concept of one-round walks had been studied for atomic congestion games with linear latency functions only [Christodoulou et al. 2006,Bilò et al. 2011]. We focus on polynomial latency functions, and, by exploiting the primal-dual technique [Bilò 2012], we prove that the approximation ratio is exactly ((1+ϵ)(p+1))p+1 for every polynomial of degree p. Then, we show that, by resorting to static (resp. dynamic) resource taxation, the approximation ratio can be lowered to (1 + ϵ)p+1(p +1)p (resp. (1 + ϵ)p+1(p + 1)!).