On weak Pareto optimality of nonatomic routing networks
文献类型：期刊论文
| 作者 | Chen, Xujin1,2 ; Diao, Zhuo3; Hu, Xiaodong1,2
|
| 刊名 | JOURNAL OF COMBINATORIAL OPTIMIZATION
 |
| 出版日期 | 2020-02-15 |
| 页码 | 19 |
| ISSN号 | 1382-6905 |
| 关键词 | Nonatomic selfish routing Nash equilibrium Weakly Pareto optimal Multi-commodity network |
| DOI | 10.1007/s10878-020-00539-7 |
| 英文摘要 | This paper establishes several sufficient conditions for the weak Pareto optimality of Nash equilibria in nonatomic routing games on single- and multi-commodity networks, where a Nash equilibrium (NE) is weakly Pareto optimal (WPO) if under it no deviation of all players could make everybody better off. The results provide theoretical and technical bases for characterizing graphical structures for nonatomic routing games to admit WPO NEs. We prove that the NE of every nonatomic routing game on a single or multi-commodity network is WPO (regardless of the choices of nonnegative, continuous, nondecreasing latency functions on network links) if the network does not have two links x, y and three paths each of which goes from some origin to some destination such that the intersections of the three paths with {x,y}are {x},{y} and {x,y} respectively. This sufficient condition leads to an alternative proof of the recent result that the NE of every 2-commodity nonatomic routing game on any undirected cycle is WPO. We verify a general property satisfied by all feasible 2-commodity routings (not necessarily controlled by selfish players) on undirected cycles, which roughly says that no feasible routing can "dominate" another in some sense. The property is crucial for proving the weak Pareto optimality associated to the building blocks of undirected graphs on which all NEs w.r.t. two commodities are WPO. |
| 资助项目 | National Natural Science Foundation of China[11531014] ; National Natural Science Foundation of China[11901605] ; Ministry of Science and Technology of China[2018AAA0101002] ; Key Research Program of Frontier Sciences, CAS[ZDBS-LY-7008] |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| 出版者 | SPRINGER |
| WOS记录号 | WOS:000516140700001 |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/50825]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Diao, Zhuo |
| 作者单位 | 1.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 3.Cent Univ Finance & Econ, Sch Stat & Math, Beijing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Chen, Xujin,Diao, Zhuo,Hu, Xiaodong. On weak Pareto optimality of nonatomic routing networks[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2020:19. |
| APA | Chen, Xujin,Diao, Zhuo,&Hu, Xiaodong.(2020).On weak Pareto optimality of nonatomic routing networks.JOURNAL OF COMBINATORIAL OPTIMIZATION,19. |
| MLA | Chen, Xujin,et al."On weak Pareto optimality of nonatomic routing networks".JOURNAL OF COMBINATORIAL OPTIMIZATION (2020):19. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。