Back to Search
Start Over
Non-atomic one-round walks in congestion games.
- Source :
-
Theoretical Computer Science . Apr2019, Vol. 764, p61-79. 19p. - Publication Year :
- 2019
-
Abstract
- Abstract 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) !). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 764
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 135077655
- Full Text :
- https://doi.org/10.1016/j.tcs.2018.06.038