We study the price of anarchy of selfish routing with variable traffic rates and when the path cost is a nonadditive function of the edge costs. Nonadditive path costs are important, for example, in networking applications, where a key performance metric is the achievable throughput along a path, which is controlled by its bottleneck (most congested) edge. We prove the following results.
โข In multicommodity networks, the worst-case price of anarchy under the p path cost with 1 < p โค โ can be dramatically larger than under the standard 1 path cost. โข In single-commodity networks, the worst-case price of anarchy under the p path cost with 1 < p < โ is no more than with the standard 1 path norm. (A matching lower bound follows trivially from known results.) This upper bound also applies to the โ path cost if and only if attention is restricted to the natural subclass of equilibria generated by distributed shortest path routing protocols. โข For a natural cost-minimization objective function, the price of anarchy with endogenous traffic rates (and under any p path cost) is no larger than that in fixed-demand networks. Intuitively, the worstcase inefficiency arising from the "tragedy of the