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$$pge 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$$pge 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$$pge 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

Vinci C.
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$$pge 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$$pge 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$$pge 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
16113349 03029743
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11386/4785764
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact