CAM Colloquium, 2016-08-26 - Alexandre Bayen: Distributed Learning Dynamics Convergence in Routing Games

Abstract:           The present talk starts with a brief presentation of the state of the art in traffic monitoring, leading to a new results in routing games.  Routing games offer a simple yet powerful model of congestion in traffic networks,both in transportation and communication systems. The congestion in such systems is affected by the combined decision of the agents (drivers or routers), so modeling the decision process of the agents is important, not only to estimate and predict the behavior of the system, but also to be able to control it. This decision process is often called learning, as agents "learn" information about the system or about the other agents.We propose and study different models of learning with the following requirement: the joint learning dynamics should converge asymptotically to the Nash equilibrium of the game. In particular, we focus on two important properties:    Is the model robust to stochastic perturbations (such as measurement noise)? And does the model allow heterogeneous learning (different agents may follow different learning strategies)? We study these questions using tools from online learning theory and stochastic approximation theory. We then present experimental results obtained with an online gaming application in which distributed players can play the routing game: they connect to the web app and participate in the game, by iteratively making decisions about their routes and observing outcomes

Biography:       Alexandre Bayen is the Liao-Cho Professor of Engineering at UC Berkeley, in the department of Electrical Engineering and Computer Science and Civil & Environmental Engineering. He is the Director of the Institute of  Transportation Studies, and a Faculty Scientist at the Lawrence Berkeley National Laboratory, where he is the Director of the Transportation Initiative. He received the Engineering Degree in applied mathematics from the Ecole Polytechnique, France, in July 1998, the M.S. degree in aeronautics and astronautics from Stanford University in June 1999, and the Ph.D. in aeronautics and astronautics from Stanford University in December 2003. He was a Visiting Researcher at NASA Ames Research Center from 2000 to 2003. Between January 2004 and December 2004, he worked as the Research Director of the Autonomous Navigation Laboratory at the Laboratoire de Recherches Balistiques et Aerodynamiques, (Ministere de la Defense, Vernon, France), where he holds the rank of Major. He authored two books, over 200 peer reviewed publications. His projects Mobile Century and Mobile Millennium received the 2008 Best of ITS Award for ‘Best Innovative Practice’, at the ITS World Congress and a TRANNY Award from the California Transportation Foundation, 2009. He is a NASA Top 10 Innovators on Water Sustainability, 2010. He has received several awards including the Ballhaus Award from Stanford University, 2004; the CAREER Award from the National Science Foundation, 2009; the Presidential Early Career Award for Scientists and Engineers (PECASE) from the White House, 2010; the Okawa Research Grant Award, 2013; the Ruberti Prize from the IEEE, 2013, and the Walter Huber Prize from the ASCE, 2014. His research has been featured several hundred times in the media, including TV channels and radio stations (CBS, NBC, ABC, CNET, NPR, KGO, the BBC), and in the popular press (The Economist, The Wall Street Journal, The New York Times, The Washington Post).