On learning Game-Theoretical models with Application to Urban Mobility
Jerome Thai
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2017-212
December 14, 2017
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-212.pdf
Modeling real-world processes as convex optimization or variational inequality problems is a common practice as it enables to leverage powerful mathematical tools for the study of such processes. For example, in economics, knowing the consumer utility function enables to adjust prices to achieve some demand level. In control, a low complexity controller requires less computation for little performance loss. In transportation science, the selfish behavior of agents (from shorted path routing) leads to an aggregate cost in the network worse than the system’s optimum, and which can be analytically quantified. Taxation schemes can be designed to incentivize system optimal drivers’ decisions.
In the first part of our work, we briefly review fundamental results in convex optimization, variational inequality theory, and game theory. We also focus on the selfish routing game, which is a popular game-theoretical framework to model the urban transportation network. In particular, we study the impact of the increasing penetration of routing apps on road usage. Its conclusions apply both to manned vehicles in which human drivers follow app directions, and unmanned vehicles following shortest path algorithms. To address the problem caused by the increased usage of routing apps, we model two distinct classes of users, one having limited knowledge of low-capacity road links. This approach is in sharp contrast with some previous studies assuming that each user has full knowledge of the network and optimizes his/her own travel time. We show that the increased usage of GPS routing provides a lot of benefits on the road network of Los Angeles, such as decrease in average travel times and total vehicle miles traveled. However, this global increased efficiency in urban mobility has negative impacts as well: increase in traffic in cities bordering highway from users taking local routes to avoid congestion.
In the second part, we explore the ability of low complexity game-theoretical models to accurately approximate real transportation systems. For example, system mischaracterizations in selfish routing can cause taxes designed for one problem instance to incentivize inefficient behavior on different, yet closely-related instances. Hence, we want to be able to measure the quality of the learned model. In the present work, we present a statistical framework for the fitting of equilibrium models based on measurements of edge flows using the (standard) empirical risk minimization principle, by choosing the fit giving the lowest expected loss (the distance between the observed and predicted outputs) under the empirical measure. Hence, for the class of models of interest, it is critical to be able to have theoretical guarantees on the quality of the fit. We then present a computational methodology for imputing the map of an equilibrium model, and propose a statistical hypothesis test for validating the trained model against the true one.
In the third part, we explore existing work for estimating link and route flows, and we propose two novel frameworks for traffic estimation. In the first framework, we focus on estimating the highway traffic, which is modeled as a discretized hyperbolic scalar partial differential equations. The system is written as a switching dynamical system, with a state space partitioned into an exponential number of polyhedra in which one mode is active. We propose a feasible approach based on the interactive multiple model (IMM), and apply the k-means algorithm on historical data to partition modes into clusters, thus reducing the number of modes. In the second framework, we develop a convex optimization methodology for the route flow estimation problem from the fusion of vehicle count and cellular network data. The proposed approach is versatile: it is compatible with other data sources, and it is model agnostic and thus compatible with user equilibrium, system-optimum, Stackelberg concepts, and other models.
Advisors: Alexandre Bayen
BibTeX citation:
@phdthesis{Thai:EECS-2017-212,
Author= {Thai, Jerome},
Title= {On learning Game-Theoretical models with Application to Urban Mobility},
School= {EECS Department, University of California, Berkeley},
Year= {2017},
Month= {Dec},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-212.html},
Number= {UCB/EECS-2017-212},
Abstract= {Modeling real-world processes as convex optimization or variational inequality problems is a common practice as it enables to leverage powerful mathematical tools for the study of such processes. For example, in economics, knowing the consumer utility function enables to adjust prices to achieve some demand level. In control, a low complexity controller requires less computation for little performance loss. In transportation science, the selfish behavior of agents (from shorted path routing) leads to an aggregate cost in the network worse than the system’s optimum, and which can be analytically quantified. Taxation schemes can be designed to incentivize system optimal drivers’ decisions.
In the first part of our work, we briefly review fundamental results in convex optimization, variational inequality theory, and game theory. We also focus on the selfish routing game, which is a popular game-theoretical framework to model the urban transportation network. In particular, we study the impact of the increasing penetration of routing apps on road usage. Its conclusions apply both to manned vehicles in which human drivers follow app directions, and unmanned vehicles following shortest path algorithms. To address the problem caused by the increased usage of routing apps, we model two distinct classes of users, one having limited knowledge of low-capacity road links. This approach is in sharp contrast with some previous studies assuming that each user has full knowledge of the network and optimizes his/her own travel time. We show that the increased usage of GPS routing provides a lot of benefits on the road network of Los Angeles, such as decrease in average travel times and total vehicle miles traveled. However, this global increased efficiency in urban mobility has negative impacts as well: increase in traffic in cities bordering highway from users taking local routes to avoid congestion.
In the second part, we explore the ability of low complexity game-theoretical models to accurately approximate real transportation systems. For example, system mischaracterizations in selfish routing can cause taxes designed for one problem instance to incentivize inefficient behavior on different, yet closely-related instances. Hence, we want to be able to measure the quality of the learned model. In the present work, we present a statistical framework for the fitting of equilibrium models based on measurements of edge flows using the (standard) empirical risk minimization principle, by choosing the fit giving the lowest expected loss (the distance between the observed and predicted outputs) under the empirical measure. Hence, for the class of models of interest, it is critical to be able to have theoretical guarantees on the quality of the fit. We then present a computational methodology for imputing the map of an equilibrium model, and propose a statistical hypothesis test for validating the trained model against the true one.
In the third part, we explore existing work for estimating link and route flows, and we propose two novel frameworks for traffic estimation. In the first framework, we focus on estimating the highway traffic, which is modeled as a discretized hyperbolic scalar partial differential equations. The system is written as a switching dynamical system, with a state space partitioned into an exponential number of polyhedra in which one mode is active. We propose a feasible approach based on the interactive multiple model (IMM), and apply the k-means algorithm on historical data to partition modes into clusters, thus reducing the number of modes. In the second framework, we develop a convex optimization methodology for the route flow estimation problem from the fusion of vehicle count and cellular network data. The proposed approach is versatile: it is compatible with other data sources, and it is model agnostic and thus compatible with user equilibrium, system-optimum, Stackelberg concepts, and other models.},
}
EndNote citation:
%0 Thesis %A Thai, Jerome %T On learning Game-Theoretical models with Application to Urban Mobility %I EECS Department, University of California, Berkeley %D 2017 %8 December 14 %@ UCB/EECS-2017-212 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-212.html %F Thai:EECS-2017-212