Stackelberg thresholds in network routing games or the value of altruism

• 成果类型: Article; Proceedings Paper
• 署名作者: Sharma, Yogeshwer; Williamson, David P.
• 署名单位: Cornell University; Cornell University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2009.06.006
• 发表日期: 2009
• 页码: 174-190
• 关键词: Game theory; Nash equilibrium; Stackelberg equilibrium; Centrally controlled flow; Altruistic flow; Stackelberg threshold; Price of anarchy

摘要

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. (C) 2009 Elsevier Inc. All rights reserved.