SWUTC Research Project Description
Game Theory and Traffic Assignment: Refinements, Stability, and Tractability
University: University of Texas at Austin
Principal Investigator:
Stephen Boyles
Department of Civil and Environmental Engineering
(512) 471-3548
Project Monitor:
Daniel Yang
Capital Area Metropolitan Planning Organization
505 Barton Springs Road, Suite 700
Austin, TX 78704
Funding Source: USDOT and State of Texas General Revenue Funds
Total Study Cost: $79,285
Project Number: 600451-00065
Date Started: 5/1/12
Estimated Completion Date: 6/30/13
Project Summary
Project Abstract:
The most common assumption in traffic assignment models is the user equilibrium state, where all travelers minimize their travel time, accounting for others’ route choices as well. While typically solved as a nonlinear program, techniques of non-cooperative game theory can provide a more refined analysis. In particular, a common problem is distinguishing among multiple path flow equilibria (for “select link” analyses or environmental justice studies), and the game theoretic concepts of refinements and stability directly relate to this issue. By applying these techniques, the accuracy of select link and equity analyses will be improved considerably.
Project Objectives:
The three primary objectives of this study are as follows:
- Review approaches from the game theory and traffic assignment literature, and identify opportunities for these two areas to interface.
- Adapt techniques from computational game theory, game stability, and/or equilibrium refinements to the traffic assignment problem.
- Further specialize these techniques to “select link” analysis and related problems in equity assessment and environmental justice.
Task Descriptions:
Task 1. Review traffic assignment and game theory research literature to identifyopportunities.
A thorough survey of the traffic assignment and game theory research literature will be undertaken, looking for opportunities for applying results or techniques from the latter area to the former. In particular, this review will include equilibrium refinements, stability results, and specialized results for potential games and other special cases satisfied by the traffic assignment problem.
Task 2. Identify a tractable reformulation of the traffic assignment problem in game-theoretic terms.
The key obstacle in applying game theory techniques to traffic assignment is formulating the problem in a way which is computationally tractable. These decisions will include choosing the agents (specific travelers vs. origin-destination pairs as conceptual “agents”), action spaces (discrete vs. continuous), and equilibrium types (Nash vs. correlated), among others.
Task 3. Create small testbed instances to identify fundamental properties.
In this task, a set of small “toy” networks will be developed to study the game theoretic properties of traffic equilibrium using the formulation in Task 2. These networks will vary according to topology, size, and level of congestion. Later tasks will expand upon this analysis to larger-sized problems, but understanding the fundamental ideas in a highly controlled setting is a necessary foundation.
Task 4. Apply equilibrium refinements to testbed instances and compare their effects.
Building on the formulation in Task 2, a subset of the equilibrium refinements identified in Task 1 will be applied to the test instances identified in Task 3. These refinements will be compared comprehensively, including examinations of (a) their behavioral justification and interpretation; (b) their effectiveness at reducing the size of the equilibrium set; and (c) their ease of application and associated computational burden.
Task 5. Develop case study on larger network involving select link analysis.
The objective of this task is to develop a case study which is more realistic than the small examples developed in Task 3. This will include choosing a network, demand table, demographic data, and identifying several alternative “projects” for comparison. In particular, this case study will be one which highlights equity, environmental justice, or other concerns where select link analyses play a major role.
Task 6. Identify computational strategies and heuristics for the larger network.
A major impediment to applying these techniques on practical-sized problems is the computation time associated with solving economic games exactly. However, for the purposes of ranking projects, an approximate solution may be good enough to yield substantial benefits over current practice without requiring exorbitant computational resources. This task will investigate strategies such as heuristics, approximation schemes, parallelization, or other methods for developing a practical method.
Task 7. Final report.
A comprehensive final report will be written, describing all research work performed.
Implementation of Research Outcomes:
Traffic assignment is used to determine the number of users on roadway links in a network. While this problem has been widely studied in transportation literature, its use of the concept of equilibrium has attracted considerable interest in the field of game theory. The approaches used in both transportation and game theory disciplines are explored, and the similarities and dissimilarities between them are studied. In particular, treatment of multiple equilibrium solutions using equilibrium refinements and learning algorithms which convergence to equilibria under incomplete information and/or bounded rationality of players are discussed in detail.
Products developed by this research:
Presentation: Game-Theoretic Learning Models in Traffic Assignment, T. Rambha, S. Boyles and K. Yin, presented at the Annual Meeting of the Institute for Operations Research and Management Sciences, Minneapolis, MN, October 2013.
Course Materials: For CE 392C (Transportation Network Analysis) and 392DD (Dynamic Traffic Assignment) at the University of Texas at Austin.
Journal submission in preparation: Game-Theoretic Leaning Models in Traffic Assignment, T. Rambha, S. Boyles, and K. Yin, to be submitted to Networks and Spatial Economics.
Impacts/Benefits of Implementation:
This research effort found significant differences in the modeling of traffic equilibrium across various fields. While transportation engineers use the Wardrop formulation for traffic assignment; researchers in economics and algorithmic game theory study it under the class of network games/congestion games, in which each individual traveler is a player (atomic congestion games) or every origin-destination pair is a player (non-atomic congestion game). The latter formulation appears to be more useful as the Nash Equilibrium to this game is much stronger than the Wardrop formulation and its properties are currently being explored.
The research results will lead to more accurate transportation planning forecasts, which are especially relevant when doing analyses related to social equity and environmental justice. Research results are already being discussed with Daniel Yang of the Capital Area Metropolitan Planning Organization. In addition, a concept identified in this project, which is currently being explored in further research, may lead to revisiting some of the standard assumptions in traffic modeling.
Web Links:
Final Technical Report