Operations Research Transactions >
2019 , Vol. 23 >Issue 1: 119 - 126
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.01.014
The theory and application of nondeterministic selfish routing model
Received date: 2018-06-22
Online published: 2019-03-15
In order to describe the traffic condition in daily life more precisely, based on the classical deterministic selfish routing model, we consider the nondeterministic selfish routing model by introducing uncertainty to each edge's cost function. For the nondeterministic selfish routing model, we take three cost measurement criterions:the risk-averse type (conservatism),the risk-neutral type (rationality) and the risk-seeking type (optimism) which correspond to three different ways of thinking in daily life. Under three different cost measurement criterions, we define the stable strategy (Nash equilibrium strategy). Firstly, we prove that for each instance, the Nash equilibrium strategy always exists and is unique in essence. Secondly, we compare the three different cost measurement criterions, and find a counterintuitive phenomenon:in some instances, the cost under the risk-averse type (conservatism) is smaller than the cost under the risk-seeking type (optimism), which means high risk, low revenue and low risk, high revenue. This is on the contrary to the normal principle of high-risk-high-revenue and low-risk-low-revenue in economics. Based on this phenomenon, we define a paradox called nondeterministic paradox, and prove this paradox is actually a generalization of Braess's Paradox. Finally, we characterize the network which is paradox-free, and prove a single commodity network is nondeterministic-paradox-free if and only if it is series-parallel network.
DIAO Zhuo . The theory and application of nondeterministic selfish routing model[J]. Operations Research Transactions, 2019 , 23(1) : 119 -126 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.014
[1] Braess D. Uber ein Paradoxon aus der Verkehrsplanung[J]. Unternehmensforschung, 1968, 12:258-268.
[2] Tim Roughgarden, Eva Tardos. How bad is selfish routing[J]. Journal of the ACM, 2002, 49:236-259.
[3] Chen X J, Diao Z, Hu X D. Network characterizations for excluding Braess's Paradox[J]. Theory of Computing Systems, 2016, 59:747-780.
[4] Chen X J, Diao Z, Hu X D. Excluding Braess's Paradox in nonatomic selfish routing[C]//The 8th International Symposium on Algorithmic Game Theory, 2015, 219-230.
[5] Chen X J, Diao Z, Hu X D. Network topologies for weak Pareto optimality in nonatomic selfish routing[C]//The 22nd International Computing and Combinatorics Conference, 2016, 27-38.
[6] Igal Milchtaich. Network topology and the efficiency of equilibrium[J]. Games and Economic Behavior, 2006, 57:321-346.
[7] Ron Holzman, Nissan Law-yone. Strong equilibrium in congestion games[J]. Games and Economic Behavior, 1997, 21:85-101.
[8] Ron Holzman, Nissan Law-yone. Network structure and strong equilibrium in route selection games[J] Mathematical Social Sciences, 2003, 46:193-205.
[9] Ron Holzman, Nissan Law-yone. Strong equilibrium in network congestion games:increasing versus decreasing costs[J] International Journal of Game Theory, 2014, 44:647-666.
/
| 〈 |
|
〉 |
