Self-interested routing in queueing networks

• 成果类型: Article
• 署名作者: Parlaktürk, AK; Kumar, S
• 署名单位: Stanford University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1040.0251
• 发表日期: 2004
• 页码: 949-966
• 关键词: queueing networks; Routing; Scheduling; Nash equilibrium; mechanism design; STABILITY

摘要

We study self-interested routing in stochastic networks, taking into account the discrete stochastic dynamics of such networks. We analyze a two-station multiclass queueing network in which the system manager chooses the scheduling rule and individual customers choose routes in a self-interested manner. We show that this network can be unstable in Nash equilibrium under some scheduling rules. We also design a nontrivial scheduling rule that negates the performance degradation resulting from self-interested routing and achieves a Nash equilibrium with performance comparable to the first-best solution.