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 tig
- PDF / 366,333 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 189 Views
Department of Mathematics and Physics, University of Salento, Lecce, Italy [email protected] Department of Computer Science, Gran Sasso Science Institute, L’Aquila, Italy [email protected]
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.
1
Introduction
In priority-based scheduling, requests issued by some users are favoured over others, differently than what happens in fair policies, such as round-robin or first-in first-out, where all users are treated equally. Priority-based scheduling is effectively used in a variety of domains, ranging from manufacturing processes to socio-economic activities. Simple examples are the largest-job-first algorithm and the boarding strategies of airline companies. To the best of our knowledge, despite this widespread diffusion, the impact of priority-based scheduling has been considered only marginally in state-of-theart game-theoretical models. In this work, we try to fill this gap by investigating congestion games with priority-based scheduling.
This work was partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets”. c Springer Nature Switzerland AG 2020 T. Harks and M. Klimm (Eds.): SAGT 2020, LNCS 12283, pp. 67–82, 2020. https://doi.org/10.1007/978-3-030-57980-7_5
68
V. Bil` o and C. Vinci
In a congestion game [40], there is a finite set of players competing for the usage of a finite set of resources and all players require the same effort on every resource. We assume that players are partitioned into p priority classes and that, on every resource, all players of priority class c are scheduled before any player of class c > c (the lower the class, the higher the priority), while players of the same class are scheduled in a random order. Hence, the cost that player i experiences on resource r is a function of two parameters: (i) the position that i occupies in the schedule of r, and (ii) the latency function of r, i.e., how fast r processes its requests. Paramete
Data Loading...
