Abstract: Navigation apps like Google Maps and Waze have hundreds of millions of users, and they constitute an integral part of day-to-day life in major metropolitan areas. However, for such apps to be effective, this vast number of users must be routed under a high degree of uncertainty (exogenous traffic fluctuations, accidents, changing weather conditions, etc.), a fact which poses significant challenges from an algorithmic point of view.
In this talk, we will examine two complementary aspects of algorithmic traffic routing in large-scale networks. First, we will analyze the price of anarchy (PoA) incurred by traffic assignment algorithms in realistic urban conditions – the high-congestion regime observed during rush hour, versus the low-congestion conditions observed off-peak. Somewhat surprisingly, even though worst-case PoA bounds suggest a significant gap between equilibrium and socially optimum traffic assignments, we show that this gap vanishes in both heavy and light traffic, irrespective of the network topology or the number of origin-destination pairs in the network. Subsequently, in the second part of the talk, we will examine how to compute equilibrium traffic assignments efficiently under uncertainty, in both static and stochastic environments. In particular, we will discuss an adaptive exponential weights method – dubbed AdaWeight – that seamlessly interpolates between the optimal $O(1/T^2)$ and $O(1/\sqrt{T})$ convergence rates for static and stochastic networks respectively, without requiring any prior knowledge of the system or its parameters.
Bio: Panayotis Mertikopoulos is a research director at the French National Center for Scientific Research (CNRS). After graduating valedictorian from the University of Athens in 2003, he received his MSc and MPhil degrees in mathematics in 2005 from Brown University, and his PhD degree from the University of Athens in 2010. He then spent one year as a post-doctoral fellow at École Polytechnique in Paris before joining CNRS in 2011. Since then, he has held visiting scholar or part-time positions at UC Berkeley, Criteo AI Lab, and the University of Athens.
Some of his recent paper awards and distinctions include the INFORMS TST best paper award in 2022, several spotlights/long talks at NeurIPS, ICML and ICLR, and a nomination for the médaille de bronze of the CNRS in computer science in 2020.
His research interests span the interface of game theory, learning and optimization, with a special view toward their applications to machine learning, operations research, and network theory. He is especially interested in the long-run behavior of multi-agent learning and optimization algorithms and dynamics – whether they converge, at what speed, and/or what type of non-stationary, off-equilibrium behaviors may arise when they do not.