Stackelberg thresholds in network routing games or the value of altruism

Yogeshwer Sharma and David P. Williamson

Games and Economic Behavior, 2009, vol. 67, issue 1, pages 174-190

Abstract: It is well known that the Nash equilibrium in network routing games can have strictly higher cost than the optimum cost. In Stackelberg routing games, where a fraction of flow is centrally-controlled, a natural problem is to route the centrally-controlled flow such that the overall cost of the resulting equilibrium is minimized. We consider the scenario where the network administrator wants to know the minimum amount of centrally-controlled flow such that the cost of the resulting equilibrium solution is strictly less than the cost of the Nash equilibrium. We call this threshold the Stackelberg threshold and prove that for networks of parallel links with linear latency functions, it is equal to the minimum of the Nash flows on links carrying more optimum flow than Nash flow. Our approach also provides a simpler proof of characterization of the minimum fraction that must be centrally controlled to induce the optimum solution.

Keywords: Game; theory; Nash; equilibrium; Stackelberg; equilibrium; Centrally; controlled; flow; Altruistic; flow; Stackelberg; threshold; Price; of; anarchy (search for similar items in EconPapers)
Date: 2009

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6WFW ... f2e82ce5db639cce0ce1
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:eee:gamebe:v:67:y:2009:i:1:p:174-190

Access Statistics for this article

Games and Economic Behavior is edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Series data maintained by Heidi Boesdal ().