Cooperative game approaches to measuring network reliability considering paradoxes
Cooperative game approaches to measuring network reliability considering paradoxes
复制标题
DOI：
10.1016/j.trc.2010.05.010
复制
发表时间：
2011-04
影响因子：
8.3
通讯作者：
W. Y. Szeto
中科院分区：
文献类型：
--
作者：
W. Y. Szeto
传统上，测量传输网络可靠性的博弈论方法依赖于一方面寻求最小成本路由的用户与另一方面寻求通过破坏网络中的链路来最大化用户的总预期网络成本的一个或多个邪恶实体或恶魔之间进行的博弈的结果。由于恶魔被认为是不合作的，这种方法已被批评，它不能产生最坏情况下的解决方案的可靠性分析，采用博弈论方法的初衷相矛盾。本文提出了两种确定出行费用可靠性的合作博弈模型：Stackelberg-Nash模型和部分合作Nash模型。分析了它们之间的关系，并研究了它们的性质。本文还研究了在什么条件下，经典的非合作恶魔行为可以导致最坏情况的解决方案。数值研究表明：（1）恶魔联盟的数量对网络总期望费用和网络/OD旅行费用可靠性的影响;（ii）矛盾现象，即如果向网络添加道路，则所有旅行者在预期网络旅行成本和/或网络旅行成本可靠性方面可能更糟，以及（iii）经典博弈论方法高估网络/OD出行成本可靠性的可能性。
Traditionally, game-theoretic approaches to measuring transport network reliability have relied on the outcome of a game played between on the one hand users who seek minimum cost routes, and on the other hand, one or more evil entities or demons that seek to maximize the total expected network cost to the users by damaging links in the network. As the demons are assumed to be non-cooperative, this approach has been criticized that it cannot produce the worst-case solution for reliability analysis, contradicting the original purpose of adopting game-theoretic approaches. In this paper, two cooperative game formulations, the Stackelberg–Nash formulation and the partial-cooperative Nash formulation, are proposed to determine travel cost reliability. Their relationships are analyzed and their properties are examined. This paper also investigates under what condition(s) the classical non-cooperative demon behavior can lead to the worst-case solution. Numerical studies are provided to demonstrate: (i) the effects of the number of coalitions formed by demons on total network expected cost and network/Origin–Destination (OD) travel cost reliability; (ii) the paradoxical phenomenon that if one adds a road to a network then all the travelers may be worse off in terms of expected network travel cost and/or network travel cost reliability, and (iii) the possibility of the classical game-theoretic approach of overestimating network/OD travel cost reliability.