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)!).

Non-atomic one-round walks in congestion games

Vinci C.
2019-01-01

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)!).
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397518304547-main.pdf

solo utenti autorizzati

Tipologia: Versione editoriale
Note: Articolo accessibile in Open Archive editoriale, al seguente link: https://www.sciencedirect.com/science/article/pii/S0304397518304547
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 549.11 kB
Formato Adobe PDF
549.11 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/484286
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact