We reconsider atomic and non-atomic affine congestion games under the assumption that players are partitioned into p priority classes and resources schedule their users according to a priority-based policy, breaking ties uniformly at random. We derive tight bounds on both the price of anarchy and the price of stability as a function of p, revealing an interesting separation between the general case of p≥2 and the priority-free scenario of p=1 . In fact, while non-atomic games are more efficient than atomic ones in absence of priorities, they share the same price of anarchy when p≥2 . Moreover, while the price of stability is lower than the price of anarchy in atomic games with no priorities, the two metrics become equal when p≥2 . Our results hold even under singleton strategies. Besides being of independent interest, priority-based scheduling shares tight connections with online load balancing and finds a natural application within the theory of coordination mechanisms and cost-sharing policies for congestion games. Under this perspective, a number of possible research directions also arises.

Congestion Games with Priority-Based Scheduling

Vittorio Bilò
;
Cosimo Vinci
2020-01-01

Abstract

We reconsider atomic and non-atomic affine congestion games under the assumption that players are partitioned into p priority classes and resources schedule their users according to a priority-based policy, breaking ties uniformly at random. We derive tight bounds on both the price of anarchy and the price of stability as a function of p, revealing an interesting separation between the general case of p≥2 and the priority-free scenario of p=1 . In fact, while non-atomic games are more efficient than atomic ones in absence of priorities, they share the same price of anarchy when p≥2 . Moreover, while the price of stability is lower than the price of anarchy in atomic games with no priorities, the two metrics become equal when p≥2 . Our results hold even under singleton strategies. Besides being of independent interest, priority-based scheduling shares tight connections with online load balancing and finds a natural application within the theory of coordination mechanisms and cost-sharing policies for congestion games. Under this perspective, a number of possible research directions also arises.
2020
978-3-030-57979-1
File in questo prodotto:
File Dimensione Formato  
978-3-030-57980-7_5.pdf

non disponibili

Tipologia: Versione editoriale
Licenza: Copyright dell'editore
Dimensione 357.75 kB
Formato Adobe PDF
357.75 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/445663
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
social impact