Combined single-path routing and flow control in many-user region: a case for nash efficiency

We consider the problem of combined single- path routing and flow control, which is nonconvex and NP-hard to solve exactly. We focus on the "many-user" region, i.e. large networks that have far more users than bottleneck links, which is close to real network scenarios. We first show that by allowing a proportionally small number of users to use multipath routing, while keeping the remaining majority using single-path routing, results in a solution that achieves multipath optimality. Therefore it is conceptually plausible that in the many-user region a local algorithm can achieve solutions arbitrarily close to the optimal solution. To show this is indeed correct, we focus on the solutions brought out by the simplest local algorithm, the Nash algorithm. We first examine a special type of network and show that the Nash equilibrium exists and the Nash algorithm always converges. It is then shown that the \´price of anarchy\´, that is the gap between the worst Nash equilibrium and the social optimum, is bounded when the number of users goes to infinity. For general networks, it is not known whether there exists a Nash equilibrium. We introduce the concept of approximate Nash equilibrium, show its existence, and prove that it will be arbitrary close to the social optimum when the number of users is sufficiently large.