Cooperative game formulations for measuring network reliability

Abstract

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 phenomena 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 network travel cost reliability respectively, and (iii) the possibility of the classical game-theoretic approach of overestimating network/OD travel cost reliability.