Stackelberg Thresholds in Network Routing Games or The Value of Altruism

 

Yogeshwer Sharma

Cornell University

Monday  April 23, 2007
4:00 PM, 5130 Upson Hall

Abstract:

In a network routing game, users carrying infinitesimal flow route their flow selfishly in order to minimize the latency of their flow. This is a nice model of noncooperative agents, but the resulting solution after selfish routing may have cost greater than the cost of the optimum solution. We look at a well-known way to improve the quality of the selfish routing, called Stackelberg strategies.

In a Stackelberg strategy, a central authority is allowed to route certain fraction of flow in whatever way they like in order to improve the quality of the solution resulting after remaining selfish

(uncontrolled) flow has routed itself. We investigate the question of what minimum fraction of flow must be centrally controlled in order that it makes a difference, that is what is the minimum fraction of flow that must be (centrally) controlled such that the cost of the resulting solution is *strictly* less than the cost of the Nash equilibrium. We call this minimum fraction the Stackelberg threshold.

In this talk, I will present a result which finds the Stackelberg threshold for a given network.

Joint work with David Williamson.

____________________________

Abstract From the Paper:

Noncooperative network routing games are a natural model of users trying to *selfishly* route flow through a network in order to minimize their own delays. It is well known that the solution resulting from this selfish routing (called the Nash equilibrium) can have social cost strictly higher than the cost of the optimum solution. One way to improve the quality of the resulting solution is to *centrally

control* a fraction of the flow. A natural problem for the network administrator then is to route the centrally controlled flow in such a way that the overall cost of the solution is minimized after the remaining fraction has routed itself selfishly.

This problem falls in the class of well-studied Stackelberg routing games. We consider the scenario where the network administrator wants the final solution to be (strictly) better than the Nash equilibrium. In other words, she wants to control enough flow such that the cost of the resulting solution is strictly less than the cost of the Nash equilibrium.

We call the minimum fraction of users that must be centrally routed to improve the quality of the resulting solution the *Stackelberg threshold*. We give a closed form expression for the Stackelberg threshold for parallel links networks with linear latency functions. The expression is in terms of Nash equilibrium flows and optimum flows. It turns out that the Stackelberg threshold is the minimum of Nash flows on links which have more optimum flow than Nash flow.

Using our approach to characterize the Stackelberg thresholds, we are able to give a simpler proof of an earlier result which finds the minimum fraction required to be centrally controlled to induce an optimum solution.