特殊路由博弈的调和率研究

doi:10.3969/j.issn.1000-3428.2011.11.093

计算机工程 ›› 2011, Vol. 37 ›› Issue (11): 269-271. doi: 10.3969/j.issn.1000-3428.2011.11.093

特殊路由博弈的调和率研究

余孝军^1,2

(1. 贵州财经学院数学与统计学院，贵阳 550004；2. 贵州省经济系统仿真重点实验室，贵阳 550004)

收稿日期:2011-01-29 出版日期:2011-06-05 发布日期:2011-06-05
作者简介:余孝军(1974－)，男，副教授、博士，主研方向：博弈理论，交通行为分析与建模
基金资助:
贵州省科学技术基金资助项目(黔科合2010J2131)；贵州省教育厅自然科学基金资助项目(黔教科2010029)

Research on Anarchy Price of Special Routing Game

YU Xiao-jun ^1,2

(1. School of Mathematics and Statistics, Guizhou College of Finance and Economics, Guiyang 550004, China; 2. Guizhou Key Laboratory of Economic System Simulation, Guiyang 550004, China)

Received:2011-01-29 Online:2011-06-05 Published:2011-06-05

摘要/Abstract

摘要： 运用算法博弈理论探讨含刻板用户的一般网络的调和率问题。建立刻画含刻板用户的Wardrop路由博弈的变分不等式模型，运用解析推导方法得到对应路由博弈调和率的上界。该上界值依赖于路段出行时间函数类和刻板用户的比例。给出多项式路段出行成本函数情况下含刻板用户的Wardrop路由博弈调和率的上界，并与以往文献中的结论进行了比较。

关键词: 刻板用户, 调和率, 路由博弈, 变分不等式, 系统最优

Abstract: The upper bound of the price of anarchy for general network with oblivious users is investigated by algorithmic game theory. The variational inequality model is established to describe the selfish routing with oblivious users. The upper bound of price of anarchy is derived by analytic derivation. It shows that the upper bounds depend on the link travel time functions and the ratio of the oblivious users in the network. The upper bound of price of anarchy with the polynomial link travel time functions of selfish routing with oblivious users is obtained; the relation between this result and the results in the previous literature is compared.

Key words: oblivious user, anarchy price, routing game, variational inequality, system optimum

中图分类号:

TP311

余孝军. 特殊路由博弈的调和率研究[J]. 计算机工程, 2011, 37(11): 269-271.

TU Xiao-Jun. Research on Anarchy Price of Special Routing Game[J]. Computer Engineering, 2011, 37(11): 269-271.

http://www.ecice06.com/CN/Y2011/V37/I11/269

参考文献

[1] Koutoupias E, Papaimitriou C. Worst-case Equilibria[C]// Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science. Trier, Germany: [s. n.], 1999: 404-413. [2] Roughgarden T, Tardos E. How Bad Is Selfish Routing?[J]. Journal of the ACM, 2002, 49(2): 236-259. [3] Yang Hai, Huang Haijun. Mathematical and Economic Theory of Road Pricing[M]. Oxford, UK: Elsevier, 2005. [4] 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. [5] Ferrante A, Parente M. Mixed Nash Equilibria in Selfish Routing Problems with Dynamic Constraints[J]. Theoretical Computer Science, 2008, 393(1-3): 37-53. [6] 杨春勇, 陈少平. 基于改进蚁群算法的网络负载均衡路由优化[J]. 计算机工程, 2010, 36(8): 4-6. [7] 隆婷, 陈志刚, 赵明, 等. 机会路由中激励合作机制的博弈分析[J]. 计算机工程, 2010, 36(12): 126-128. [8] Ledyard J. Public Goods: A Survey of Experimental Research[M]// Kagel J, Roth A. Handbook of Experimental Economics. New Jersey, USA: Princeton University Press, 1997: 111-194. [9] Levine D K. Modeling Altruism and Spitefulness in Experiments[J]. Review of Economic Dynamics, 1998, l(3): 593- 622. [10] Chen Po-an, Kempe D. Altruism, Selfishness, and Spite in Traffic Routing[C]//Proceedings of the 9th ACM Conference on Electronic Commerce. Chicago, Illinois, USA: ACM Press, 2008: 140-149. [11] Karakostas G, Kim T, Viglas A, et al. Selfish Routing with Oblivious Users[EB/OL]. (2007-09-23). http//www.cas.mcmaster. ca/~gk/papers/oblivi. [12] 侯海洋. 一类包含刻板用户的Wardrop路由博弈[J]. 应用数学学报, 2008, 31(4): 577-583. [13] Harker P T. Multiple Equilibrium Behaviors on Networks[J]. Transportation Science, 1988, 22(1): 39-46. [14] Kinderlehrer D, Stampacchia G. An Introduction to Variational Inequalities and Their Applications[M]. New York, USA: Academic Press, 1986. [15] 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.

选择文件类型/文献管理软件名称

选择包含的内容

特殊路由博弈的调和率研究

Research on Anarchy Price of Special Routing Game

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王子珩, 姜忠鼎. 支持多模态交互的桌面增强显示系统[J]. 计算机工程, 2022, 48(7): 177-188.
[2]	许福, 郝亮, 陈飞翔, 李冬梅, 崔晓晖. 面向开源代码复用的程序比对分析方法[J]. 计算机工程, 2020, 46(1): 222-228,242.
[3]	张婉莹, 曹晓梅, 陈伟. 白盒模糊测试中环境交互问题的解决方案[J]. 计算机工程, 2020, 46(1): 216-221.
[4]	张树涛, 谭海波, 陈良锋, 吕波. 一种高效的分布式爬虫系统负载均衡策略[J]. 计算机工程, 2019, 45(11): 62-67.
[5]	杨正龙, 高建华. 基于蜕变测试的面向用户搜索引擎性能分析[J]. 计算机工程, 2019, 45(10): 52-56,63.
[6]	王晨旭, 王晓晨, 余敦辉, 吴珊. 基于动态解耦的软件众包任务分解算法[J]. 计算机工程, 2019, 45(8): 120-124,134.
[7]	王晨旭, 余敦辉, 张万山, 张兴盛. 基于核心度排序的软件众包模块分配算法[J]. 计算机工程, 2019, 45(7): 66-70.
[8]	倪鸿, 刘鑫. 基于神威·太湖之光的非结构网格众核优化技术[J]. 计算机工程, 2019, 45(6): 45-51.
[9]	钱雪忠,姚琳燕. 面向稀疏高维大数据的扩展增量模糊聚类算法[J]. 计算机工程, 2019, 45(6): 75-81.
[10]	王晶,张云泉,梁军. 基于ARM V8平台的向量算法库实现与优化[J]. 计算机工程, 2019, 45(6): 82-88.
[11]	张亚. 舰船一体化网络系统故障注入平台设计[J]. 计算机工程, 2019, 45(6): 273-279.
[12]	邓路佳,刘平山. 基于GMM-FMs的广告点击率预测研究[J]. 计算机工程, 2019, 45(5): 122-126.
[13]	赵林柳,吕鑫,陶飞飞. 基于Top-k的高效用模式挖掘算法[J]. 计算机工程, 2019, 45(5): 169-174,181.
[14]	谭宏楠,石京燕,邹佳恒,杜然,姜晓巍,孙震宇. 应用于JUNO实验的容器技术研究[J]. 计算机工程, 2019, 45(4): 1-5.
[15]	孙伟娟,王宁. 基于一致性支持度的实体top-k扩展算法[J]. 计算机工程, 2019, 45(4): 181-188.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

特殊路由博弈的调和率研究

Research on Anarchy Price of Special Routing Game

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价