Name
Abstract | ||
|---|---|---|
Noncooperative network routing games are a natural model of users trying to selshly route o w through a network in order to minimize their own delays. It is well known that the solution resulting from this selsh 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 o w. A natural problem for the network administrator then is to route the centrally controlled o w in such a way that the overall cost of the solution is minimized after the remaining fraction has routed itself selshly . This problem falls in the class of well-studied Stackelberg routing games. We consider the scenario where the network administrator wants the nal solution to be (strictly) better than the Nash equilibrium. In other words, she wants to control enough o w such that the cost of the resulting solu- tion is strictly less than the cost of the Nash equilibrium. We call the minimum fraction of users that must be cen- trally 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 o ws and optimum o ws. It turns out that the Stackelberg threshold is the minimum of Nash o ws on links which have more optimum o w than Nash o w. Using our approach to characterize the Stackelberg thresh- olds, we are able to give a simpler proof of an earlier result which nds the minimum fraction required to be centrally controlled to induce an optimum solution. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.geb.2009.06.006 | ACM Conference on Electronic Commerce |
Keywords | Field | DocType |
centrally controlled flow,stackelberg equilibrium,nash equilibrium,game theory,price of anarchy,c72,stackelberg threshold,altruistic flow,network routing | Correlated equilibrium,Welfare economics,Economics,Mathematical economics,Epsilon-equilibrium,Best response,Symmetric equilibrium,Price of anarchy,Solution concept,Stackelberg competition,Nash equilibrium | Journal |
Volume | Issue | ISSN |
67 | 1 | Games and Economic Behavior |
Citations | PageRank | References |
25 | 1.11 | 22 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yogeshwer Sharma | 1 | 161 | 9.67 |
| David P. Williamson | 2 | 3564 | 413.34 |