不确定性自私路由模型的理论和应用
|
摘要
为了更加准确地描述现实生活中的交通情况,以经典的自私路由模型为基础,在边的费用函数上引入不确定性,从而定义了具有不确定性的自私路由模型.对于不确定性自私路由模型,采用三种费用衡量标准,风险厌恶型(保守型)、风险折衷型(理智型)、风险偏好型(乐观型),分别对应着不同人群在现实中的选择.进而定义了在不同衡量标准下所形成的稳定策略,即纳什均衡策略,并且证明了在任何一种衡量标准下,纳什均衡策略总是存在并且本质是唯一的.接着对三种费用衡量标准下的纳什均衡费用进行了比较,发现了一种反直观的现象:风险厌恶型(保守型)衡量标准下的纳什均衡费用可能严格低于风险偏好型(乐观型)衡量标准下的纳什均衡费用,即有可能会出现高风险低回报,低风险高回报的情况,这与经济学中高风险高回报,低风险低回报的原则是相违背的.以此为基础,进而提出了一种自私路由风险性悖论,并证明了这种自私路由风险回报悖论本质上是传统布雷斯悖论的推广.最后,刻画出了不会发生自私路由风险回报悖论的网络结构,证明了一个单对始终点网络不会发生自私路由风险回报悖论当且仅当它是序列-平行网络.
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 par ad ox-free, and prove a single commodity network is nondeterministic-paradox-free if and only if it is series-parallel network.
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 par ad ox-free, and prove a single commodity network is nondeterministic-paradox-free if and only if it is series-parallel network.
引文
[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.
[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.