List

We consider a priority-based selﬁsh routing model, where agents may have diﬀerent priorities on a link. An agent with a higher priority on a link can traverse it with a smaller delay or cost than an agent with lower priority. This general framework can be used to model a number of diﬀerent problems. The structural properties that lead to ineﬃciencies in routing choices appear diﬀerent in this priority-based model compared to the classical model. In particular, in parallel link networks with nonatomic agents, the price of anarchy is exactly one in the priority-based model; that is, selﬁsh behaviour leads to optimal routings. In contrast, in the standard model the worst possible price of anarchy can be achieved in a simple two-link network. For multi-commodity networks, selﬁsh routing does lead to ineﬃciencies in the priority-based model. We present tight bounds on the price of anarchy for such networks. Speciﬁcally, in the nonatomic case the worst-case price of anarchy is exactly $(d + 1)^{d+1}$ for polynomial latency functions of degree $d$ (hence 4 for linear cost functions). For atomic games, the worst-case price of anarchy is exactly $3+2\sqrt{2}$ in the weighted case, and exactly 17/3 in the unweighted case. An upper bound of $O(2^dd^d)$ is also shown for polynomial cost functions in the atomic case, although this is not tight. Our framework (and results) also generalise to include models similar to congestion games.