While in the typical selfish routing setting the users follow a strategy that minimizes their individual cost by taking into account the (dynamic) congestion due to the current routing pattern, an oblivious user ignores congestion altogether. Instead, he decides his routing on the basis of cheapest routes on a network without any flow whatsoever. These cheapest routes can be, for example, the shortest paths in the network without any flow. This model tries to capture the fact that routing tables for at least a fraction of the flow in large scale networks such as the Internet may be based on the physical distances or hops between routers alone. The phenomenon is similar to the case of traffic networks where a certain percentage of travelers base their route simply on the distances they observe on a map, without thinking (or knowing, or caring) about the delays experienced on this route due to their fellow travelers. In this work we study the price of anarchy of such networks, i.e., the ratio of the total latency experienced by the users in this setting over the optimal total latency if all users were centrally coordinated.

We also study the generalization of selfish routing where the users are divided into an $\alpha$ fraction that are routed according to a central coordinator's routing strategy (Stackelberg strategy), and the remaining $1-\alpha$ that determine their strategy selfishly, given the routing of the coordinated users. We analyze two such strategies from the literature, LLF and SCALE. For general topology networks, multicommodity users, and linear latency functions, we show for the first time a price of anarchy bound for SCALE, which decreases from $4/3$ to $1$ as $ \alpha$ increases from $0$ to $1$, and depends only on $\alpha$. In addition, we show that we can do away with the central coordinator, as long as we are allowed to impose taxes (tolls) on the edges in order to steer the selfish users towards an improved system cost and as long as there is at least a fraction $\alpha$ of users that pay their taxes.