In game theory and operations research, a Wardrop equilibrium is a concept developed by John Glen Wardrop for the prediction of traffic patterns in transportation networks that are subject to congestion. The idea of traffic equilibrium originated as early as 1924, with Frank Knight. The concepts are related to the idea of Nash equilibrium in game theory developed separately. However, in transportation networks, there are many players, making the analysis complex. In 1952, Wardrop stated two principles that formalize different notions of equilibrium, and introduced the alternative behaviour postulate of the minimization of the total travel costs.
Wardrop's first principle Wardrop's first principle of route choice, now known as "user equilibrium", "selfish Wardrop equilibrium" or just "Wardrop equilibrium", which is identical to the notion postulated by Knight, became accepted as a sound and simple behavioural principle to describe the spreading of trips over alternate routes because of congested conditions. It states:The journey times in all routes actually used are equal and less than those that would be experienced by a single vehicle on any unused route.The traffic flows that satisfy this principle are usually referred to as "user equilibrium" (UE) flows, since each user chooses the route that is the best. Specifically, a user-optimized equilibrium is reached when no user may lower his transportation cost through unilateral action. A variant is the stochastic user equilibrium (SUE), in which no driver can unilaterally change routes to improve his/her perceived, rather than actual, travel times.
Wardrop's second principle Wardrop's second principle, now known as "system optimal" or "social Wardrop equilibrium" states that at equilibrium, the average journey time is at a minimum. That implies that all users behave cooperatively in choosing their routes to ensure the most efficient use of the whole system. For example, this would be the case if an omnipotent central authority could command users to take specific routes. Traffic flows satisfying Wardrop's second principle are generally deemed system optimal (SO). Economists and modellers have argued that it can be achieved with marginal cost road pricing, or by a central routing authority dictating route choices. The potential fall in efficiency from social to selfish equilibria is an example of the price of anarchy.
Computation Wardrop did not provide algorithms for solving Wardrop equilibria, he simply defined them as desiderata. The first mathematical model of network equilibrium was formulated by Beckmann, McGuire and Winsten in 1956. As with Nash equilibria, simple solutions to selfish equilibrium can be found through iterative simulation, with each agent assigning its route given the choices of the others. This is very slow computationally. The Frank–Wolfe algorithm improves on this by exploiting dynamic programming properties of the network structure, to find solutions with a faster form of iteration. Creating new and faster algorithms for both selfish and social Wardrop equilibria remains an active research topic in the 2010s.
See also Congestion game
References
