Abstract:

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.

Key words: selfish routing, nondeterministic, optimism-reason-conservative, seriesparallel network