On Coordination Ratio of a Mixed Routing Game
-
摘要: 运用算法博弈论探讨了固定需求下由刻板用户和利他用户组成的混合路由博弈的调和率问题.首先,建立了刻画这类混合路由博弈的变分不等式模型;然后,运用解析推导的方法得到了该类路由博弈调和率的上界,并以现有文献中的结论为特例.Abstract: The upper bound of the coordination ratio for a mixed routing game associated with oblivious users and altruistic users with fixed demand was investigated by algorithmic game theory. Firstly, the variational inequality model was established to describe this mixed routing game. Then, the upper bound of coordination ratio was derived by analytic derivation. The results took the results in existence literatures as its special case.
-
Key words:
- oblivious users /
- altruistic users /
- routing game /
- variational inequality /
- coordination ratio
-
[1] 丁协平.局部凸H-空间内的约束多目标对策[J]. 应用数学和力学, 2003, 24(5): 441-449.(DING Xie-ping. Constrained multiobjective games in locally convex H-spaces[J]. Applied Mathematics and Mechanics(English Edition), 2003, 24(5):499-508.) [2] 丁协平.局部FC一致空间内凝聚映象的极大元和广义对策及应用(I)[J].应用数学和力学, 2007, 28(12):1392-1399.(DING Xie-ping. Maximal elements and generalized games involving condensing mappings in locally FC-uniform spaces and applications(I)[J].Applied Mathematics and Mechanics(English Edition), 2007, 28(12):1561-1568.) [3] 俞建. 博弈论与非线性分析[M]. 科学出版社, 2008.(YU Jian. Game Theory and Non-Linear Analysis[M]. Science Press, 2008.(in Chinese)) [4] Lin Z. Essential components of the set of weakly ParetoNash equilibrium points for multiobjective generalized games in two different topological space[J]. Journal of Optimization Theory and Applications,2005, 124(2): 387-405. [5] Koutoupias E, Papaimitriou C. Worstcase equilibria[C]// Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science.NCS 1563, 1999: 404-413. [6] Roughgarden T, Tardos E. How bad is selfish routing?[J].Journal of the ACM,2002, 49(2): 236-259. [7] Yang H, Huang H J.Mathematical and Economic Theory of Road Pricing[M]. Oxford: Elsevier, 2005. [8] Roughgarden T, Tardos E. The price of anarchy is independent of the network topology[J].Journal of Computer and System Science,2003, 67(2): 341-364. [9] Correa J R, Schulz A S, Stier-Moses N S. Selfish routing in capacitated networks[J].Mathematics of Operations Research,2004, 29 (4): 961-976. [10] 刘天亮, 欧阳恋群, 黄海军. ATIS作用下的混合交通行为网络与效率损失上界[J]. 系统工程理论与实践, 2007, 27(4): 154159.(LIU Tian-liang, OUYANG Lian-qun, HUANG Hai-jun. Mixed travel behavior in networks with ATIS and upper bound of efficiency loss[J].Systems Engineering-theory & Practice,2007, 27(4):154-159.(in Chinese)) [11] Han D R, Yang H. The multiclass, multicriterion traffic equilibrium and the efficiency of congestion pricing[J].Transportation Research Part E,2008, 44(5): 753-773. [12] Guo X L, Yang H. User heterogeneity and bi-criteria system optimum[J].Transportation Research Part B,2009, 43(4):379-390. [13] Yu X J, Huang H J. Efficiency loss of mixed equilibrium behaviors with polynomial cost functions[J].Promet Traffic & Transportation,2010, 22(5): 325-331. [14] Chen P A, Kempe D. Altruism, selfishness, and spite in traffic routing[C]// Proceedings of the 9th ACM Conference on Electronic Commerce.Chicago, Illinois, USA, 2008: 140-149. [15] Karakostas G, Kim T, Viglas A, Xia H. On the degradation of performance for traffic networks with oblivious users[J].Transportation Research Part B,2011, 45(2): 364-371. [16] 侯海洋. 一类包含刻板用户的Wardrop路由博弈[J]. 应用数学学报, 2008, 31(4): 577-583.(HOU Hai-yang. A class of selfish routing with oblivious agents[J].Acta Mathematicae Applicatae Sinica,2008,31(4):577583.(in Chinese)) [17] 黄海军.城市交通网络平衡分析理论与实践[M]. 北京:人民交通出版社,1994.(HUANG Haijun.Urban Transportation Network Equilibrium Analysis Theory and Practice [M].Beijing: China Communication Press,1994.(in Chinese)) [18] Yu X J, Huang H J.Inefficiency of the uniform altruism traffic assignment[C]// Proceeding of the Second International Conference on Intelligent Computation Technology and Automation.Zhangjiajie, Hunian, China, 2009: 629-632.
点击查看大图
计量
- 文章访问数: 1329
- HTML全文浏览量: 99
- PDF下载量: 1262
- 被引次数: 0