Congestion Games with Priority-Based Scheduling

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.