Non-atomic one-round walks in 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. [1], Bilò et al. [2]). We give an explicit formula to determine the approximation ratio for non-atomic congestion games having general latency functions. In particular, we focus on polynomial latency functions, and, 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)!).