Stability vs.Optimality in Selfish Ring Routing  

作　　者：Bo CHEN Xujin CHEN Jie HU 

机构地区：[1]Warwick Business School, University of Warwick [2]Institute of Applied Mathematics,AMSS, Chinese Academy of Sciences [3]School of Mathematics and Statistics, Wuhan University

出　　处：《Acta Mathematica Sinica,English Series》2014年第5期767-784,共18页数学学报（英文版）

基　　金：Supported in part by China 973 Project(Grant No.2011CB80800);National Natural Science Foundation of China(Grant Nos.10531070,10721101,11222109 and 71101006);CAS Program for Cross & Cooperative Team of Science & Technology Innovation

摘　　要：We study asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of source-destination node-pairs over links with linear latencies. We show that there exists an optimal solution that is a 9-approximate Nash equilibrium, significantly improving the existing upper bound of 54 on the instability factor. We present fast implementation of the best response dynamics for computing a Nash equilibrium. Furthermore, we perform empirical study on the price of stability, narrowing the gap between the lower and upper bounds to 0.7436.We study asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of source-destination node-pairs over links with linear latencies. We show that there exists an optimal solution that is a 9-approximate Nash equilibrium, significantly improving the existing upper bound of 54 on the instability factor. We present fast implementation of the best response dynamics for computing a Nash equilibrium. Furthermore, we perform empirical study on the price of stability, narrowing the gap between the lower and upper bounds to 0.7436.

关 键 词：Selfish routing price of stability minimum maximum linear latency 

分 类 号：TN915.0[电子电信—通信与信息系统]