John Glen Wardrop
John Glen Wardrop (1922–1989), born in Warwick, England, was an English mathematician and transport analyst who developed what became known as Wardrop's first and second principles of equilibrium in the field of traffic assignment.
He studied at Downing College, Cambridge, and worked in Operational Research at British Bomber Command during the Second World War. He then helped to set up, and later headed, the Traffic Section of the Road Research Laboratory near Slough (Part of the Directorate of Scientific and Industrial Research within the UK Civil Service) where he published his work on equilibrium. He subsequently followed Dr Reuben Smeed to University College London, becoming Reader Emeritus in Traffic Studies.
Wardrop equilibria
In studies about traffic assignment, network equilibrium models are commonly used 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 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, 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 them all which routes to take. 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.
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.
References
- Wardrop, J. G.; Whitehead, J. I. (1952). "Correspondence. Some Theoretical Aspects of Road Traffic Research". Proceedings of the Institution of Civil Engineers. 1 (5): 767–768. doi:10.1680/ipeds.1952.11362.
- Wardrop, J. G. (1952). "Some Theoretical Aspects of Road Traffic Research". Proceedings of the Institution of Civil Engineers. 1 (3): 325–362. doi:10.1680/ipeds.1952.11259.
- Obituary, John Glen Wardrop Transportation 16 pp. 1-2 (1989)