Congestion games are a well-studied model for resource sharing among
uncoordinated selfish players. Usually, one assumes that the resources in a
congestion game do not have any preferences regarding the players that can access
them. In typical load-balancing applications, however, different jobs can have
different priorities, and jobs with higher priorities get, for example, larger
shares of processor time.
We extend the classical notion of congestion game and introduce
a model in which each resource can assign priorities to the players, and players
with higher priorities can displace players with lower priorities. Not only does our
model extend classical congestion games, it can also be seen as
a model of two-sided markets with ties. Hence it unifies previous results
for these two classical models.
¶ We prove that singleton congestion games with priorities are potential games.
Furthermore, we
show that every player-specific singleton congestion game with priorities
possesses a pure Nash equilibrium that can be found in polynomial time. Finally,
we extend our results to matroid congestion games, in which the strategy spaces
of the players are matroids over the resources.