CSpace  > 应用数学研究所
On weak Pareto optimality of nonatomic routing networks
Chen, Xujin1,2; Diao, Zhuo3; Hu, Xiaodong1,2
AbstractThis 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.
KeywordNonatomic selfish routing Nash equilibrium Weakly Pareto optimal Multi-commodity network
Indexed BySCI
Funding ProjectNational 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 Research AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS IDWOS:000516140700001
Citation statistics
Document Type期刊论文
Corresponding AuthorDiao, Zhuo
Affiliation1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China
2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China
3.Cent Univ Finance & Econ, Sch Stat & Math, Beijing, Peoples R China
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Chen, Xujin]'s Articles
[Diao, Zhuo]'s Articles
[Hu, Xiaodong]'s Articles
Baidu academic
Similar articles in Baidu academic
[Chen, Xujin]'s Articles
[Diao, Zhuo]'s Articles
[Hu, Xiaodong]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Chen, Xujin]'s Articles
[Diao, Zhuo]'s Articles
[Hu, Xiaodong]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.