Dynamic Traffic Models in Transportation Science

While there are many methods in within-day dynamics of on-demand mobility services, the literature on day-to-day dynamics is scarce. In this open problem session, I will present a steady state assignment game model for analyzing and designing platforms of mobility ecosystems that output passenger flows, stable pricing ranges, and platform subsidies. I will discuss challenges and opportunities to identifying an equivalent day-to-day adjustment model corresponding to that model: stable outcome space becoming an attractor, learning functions for user and operators that include cost allocations, using the path-dependency of the dynamic system to tackle the nonuniqueness of stable outcome spaces corresponding to a matching solution, deterministic and stochastic variants, and introducing policy interventions to guide ecosystems toward desired attractors.

Strategic transport planning models that predict travel demand and behavior in consideration of a congested transport system have been used for many decades. Historically, these models are aggregate and continuum flow based, meaning that human behavior and physical vehicle propagation are abstracted into a limited number of representative traveler and vehicle flows. The last few decades have seen the convergence of network flow meso/microsimulations and activity-based travel demand models into “agent-based” model systems that simulate individual synthetic travelers and vehicles instead of largely anonymous flows. Greater realism may be expected from agent-based models, given their potentially higher level of detail. However, careful structural modeling is needed to leverage these capabilities. The talk presents the possible advantages that arise from an agent-based approach and emphasizes the accompanying modeling challenges.

We study the existence of approximate pure Nash equilibria ($\alpha$-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree $d$. Previously it was known that $d$-approximate equilibria always exist, while nonexistence was established only for small constants, namely for $1.153$-PNE. We improve significantly upon this gap, proving that such games in general do not have $\tilde{\mathrm{\Theta }}(\sqrt{d})$-approximate PNE, which provides the first super-constant lower bound.

Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an $\tilde{O}(\sqrt{d})$-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions.

The circuit gadget is of independent interest and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games. For example, we demonstrate that the question of existence of $\alpha$-PNE in which a certain set of players plays a specific strategy profile is NP-hard for any , even for unweighted congestion games.

Finally, we study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players $n$. We show that $n$-PNE always exist, matched by an almost tight nonexistence bound of $\tilde{\mathrm{\Theta }}(n)$, which we can again transform into an NP-completeness proof for the decision problem.

Electric vehicles (EVs) are a great promise for the coming decades in order to allow for mobility but at the same time take measures against the climate change by reducing the emissions of classical combustion engines.

However, those new types of vehicles also come with new challenges like the limited range and the more complex and time consuming recharging process. Modelling traffic involving EVs, thus, requires a more involved model then the one used for traditional vehicles. To accommodate this, we augment the deterministic queuing model of Vickrey with energy constraints and study capacitated dynamic equilibria in this model. Here, in contrast to the traditional dynamic equilibria, we can neither assume that particles only take simple paths (leading to an infinite dimensional strategy space) nor synchronized intermediate arrival times (i.e. particles starting at the same time from the same source towards the same destination might still arrive at intermediate nodes at different times).

We will explore these difficulties and show how we can overcome them to show existence of equilibria for EVs as well as an even more general traffic models. We complement our theoretical results by a computational study in which we apply a fixed-point algorithm to compute energy- dynamic equilibria.

I will first give a brief overview on some existing DTA models assuming i) perfect and full information on travel times, flows etc. and the other extreme (ii) assuming only instantaneous (incomplete) information. After this overview I introduce a DTA model, where agents base their instantaneous routing decisions on real-time delay predictions. I formulate a mathematically concise model and derive properties of the predictors that ensure a dynamic prediction equilibrium exists.I will show that the framework subsumes the well-known full information and instantaneous information models, in addition to admitting further realistic predictors as special cases.

A largely untapped potential for improving traffic flows is rooted in the inherent uncertainty of travel times. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent provider may use this informational advantage in order to steer a traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion.

In this talk, we discuss our recent progress on this signaling problem. We characterize cases in which optimal signaling schemes are structurally simple and/or can be computed in polynomial time. Our results reveal interesting connections between optimal signaling, network structure, and support enumeration for equilibria.

Stability and instability issues in DTA have been studied actively in recent years but still many things are not well understood. This talk will give a brief introduction of existing studies dealing with stability issues in DTA, especially those on for DUE (dynamic user-equilibrium) solutions, and raise possible future research directions to tackle with this problem.

We study the existence of pure Nash equilibria in atomic congestion games with different user classes where the cost of each resource depends on the aggregated demand of each class. A set of cost functions is called consistent for this class if all games with cost functions from the set have a pure Nash equilibrium. We give a complete characterization of consistent sets of cost functions showing that the only consistent sets of cost functions are sets of certain affine functions and sets of certain exponential functions. This characterization is also extended to a larger class of games where each atomic player may control flow that belongs to different classes.

We report on work in progress on the question of finding good paths for bicycles in a traffic network with (possibly coordinated) traffic lights. While the standard dynamic shortest path problem in time-dependent networks with cyclic time windows is known to be easy, we study the related problem of finding routes that keep a small number of stops. We show that the problem is strongly NP-hard for paths and trails, whereas it is weakly NP-hard for walks. We give a pseudo-polynomial algorithm for this third option. Further we report about ongoing work on designing algorithms for the case of variable speeds and the employment of appropriate power consumption and recovery models for bicycles for the above formulated problem.

Consider a set family $𝒫$ on a common ground set $E$, together with a requirement $r(P)\in [0,1]$ for each $P\in 𝒫$. Each element $e\in E$ is equipped with a marginal probability $p(e)$ such that ${\sum }_{e\in P}p(e)\ge r(P)$ for all $P\in 𝒫$. In this talk, we investigate the question under which conditions these marginal probabilities can be turned into a probability distribution on the subsets of $E$ such that each $P\in 𝒫$ is intersected by the resulting random set with probability at least $r(P)$.

Motivated by a network security game, Dahan et al. (2001) showed the existence of such a distribution for the case that $𝒫$ is the family of maximal chains in a partial order (equivalently: the set of $s$-$t$-paths in a directed acyclic graph) and the requirements $r$ fulfill a natural conservation property. We extend this result to the case that $𝒫$ is an abstract network fulfilling a certain ordering assumption. We also give a significantly simplified argument for the original result, using a classic idea from the theory of flows over time. In particular, our results imply that equilibria for the aforementioned security game can be efficiently computed even when the underlying digraph contains cycles.

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modelled via queues, which form whenever the inflow into a link exceeds its capacity. We answer some rather basic questions about equilibria in this model: in particular uniqueness (in an appropriate sense), and continuity: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions.

To prove these results, we make a surprising connection to another question: whether, assuming constant inflow into the network at the source, do equilibria always eventually settle into a “steady state” where all queue delays change linearly forever more? Cominetti et al. proved this under an assumption that the inflow rate is not larger than the capacity of the network – eventually, queues remain constant forever. We resolve the more general question positively.

Cities and companies alike often resort to the use of detailed, dynamic, and stochastic traffic simulators to tackle their transportation optimization problems. Methods from the field of simulation-based optimization are often used. However, their use to tackle problems with time-dependent decision variables is limited. In this talk, we present recent work that formulates an analytical,, differentiable, and compute efficient dynamic traffic model, and integrates it within a Bayesian optimization (BO) framework to tackle high-dimensional dynamic transportation problems. We present validation results on small network problems, as well as a large-scale traffic signal control case study for Midtown Manhattan, New York City. We discuss how the proposed approach enhances the scalability of BO methods.

We consider the problem of minimising social cost in atomic congestion games and show, perhaps surprisingly, that efficiently computed taxation mechanisms yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the players’ actions. It follows that no other tractable approach geared at incentivising desirable system behaviour can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. In short: Judiciously chosen taxes achieve optimal approximation.

Three technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP-hard to approximate within a given factor depending solely on the admissible resource costs. Second, we design a tractable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is optimal. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time algorithms with optimal approximation.

In a Stackelberg max closure game, we are given a digraph whose vertices correspond to projects from which firms can choose and whose arcs represent precedence constraints. Some projects are under the control of a leader who sets prices in the first stage of the game, while in the second stage, the firms choose a feasible subset of projects of maximum value. For a single follower, the leader’s problem of finding revenue-maximizing prices can be solved in strongly polynomial time. In this paper, we focus on the setting with multiple followers and distinguish two situations. In the case in which only one copy of each project is available (limited supply), we show that the two-follower problem is solvable in strongly polynomial time, whereas the problem with three or more followers is NP-hard. In the case of unlimited supply, that is, when sufficient copies of each project are available, we show that the two-follower problem is already APX-hard. As a side result, we prove that Stackelberg min vertex cover on bipartite graphs with a single follower is APX-hard.

PPAD and PLS are successful classes that each capture the complexity of important game-theoretic problems: finding a mixed Nash equilibrium in a bimatrix game is PPAD-complete; and finding a pure Nash equilibrium in a congestion game is PLS-complete. Many important problems, such as solving a Simple Stochastic Game or finding a mixed Nash equilibrium of a congestion game, lie in both classes. However, it was strongly believed that their intersection does not have natural complete problems. We show that it does: any problem that lies in both classes can be reduced in polynomial time to the problem of finding a stationary point of a function. Our result has been used to show that computing a mixed equilibrium of a congestion game is also complete for the intersection of PPAD and PLS.

We study the use of machine learning techniques to solve a fundamental shortest path problem, known as the single-source many-targets shortest path problem (SSMTSP). Basically, our idea is to equip an adapted version of Dijkstra’s algorithm with machine learning predictions to solve this problem: Based on the trace of Dijkstra’s algorithm, we design a neural network that predicts the shortest path distance after a few iterations. The prediction is then used to prune the search space explored by Dijkstra’s algorithm, which significantly reduces the number of operations on the underlying priority queue. Crucially, our algorithms always compute the exact shortest path distances (even if the prediction is inaccurate) and never use more queue operations than the standard algorithm. We provide a probabilistic analysis of our new algorithm which proves a lower bound on the number of saved queue operations. Our bound quantifies these savings depending on the accuracy of the prediction and applies to arbitrary graphs with (partial) random weights. We also present extensive experimental results on random instances showing that the actual savings are oftentimes significantly larger.

Flows over time are a natural way to incorporate flow dynamics that arise in various applications such as traffic networks. In this work we introduce a natural variant of the deterministic fluid queuing model in which users aim to minimize their costs subject to arrival at their destination before a pre-specified deadline. We determine the existence and the structure of Nash flows over time and fully characterize the price of anarchy for this model. The price of anarchy measures the ratio of the quality of the equilibrium and the quality of the optimum flow, where we evaluate the quality using two different natural performance measures: the throughput for a given deadline and the makespan for a given amount of flow. While it turns out that both prices of anarchy can be unbounded in general, we provide tight bounds for the important subclass of parallel path networks. Surprisingly, the two performance measures yield different results here.

In this talk we revisit the complexity of computing a(n) (approximate) pure equilibrium in atomic congestion games. While our understanding of the complexity of pure equilibria is reasonably well, i.e, it is PLS-hard in general but we have a good picture of the landscape of tractable spacial cases, the same is not true of approximate pure equilibria. We discuss the gap between general inapproximability result of Vöcking and S. and the approximation algorithm of Caragiannis et al. for certain cost function. We briefly outline a possible approach towards closing this gap.

The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, production, traffic, evacuation, and finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, are hardly practical as they rely on parametric submodular function minimization via Megiddo’s method of parametric search. The main contribution of this paper is a considerably faster algorithm for the Quickest Transshipment Problem that instead employs a subtle extension of the Discrete Newton Method. This improves the previously best known running time of $\tilde{O}(m^4{k}^{14})$ to $\tilde{O}(m^2{k}^5+m^3{k}^3+m^{3}n)$, where $n$ is the number of nodes, $m$ the number of arcs, and $k$ the number of sources and sinks.

LP duality (the strong duality theorem of linear programming) and the minimax theorem for zero-sum games are considered “equivalent” in the sense that one can easily be proved from the other. However, the classic proof by Dantzig (1951) of LP duality from the minimax theorem is flawed. It needs an additional assumption of strict complementarity. We show that this assumption amounts to assuming the Lemma of Farkas, which implies LP duality directly. We fix this with a new, different proof. We also mention a beautiful existing direct proof of the Lemma of Farkas based on minimally infeasible systems of inequalities.

The link costs are given by strictly increasing functions $c_a(v_a)=t_a(v_a)+{\tau }_a$. User Equilibrium (UE) wherein the OD flows satisfy Wardrop’s first principle, is a solution to ${\min }_v{\int }_0^{v_a}{c}_a(z)𝑑z$ for demand-feasible link flow vectors $v\in \mathrm{\Omega }(q)$.

It is well-known that that UE is typically inefficient, in that it does not minimise the total network travel time. The flow pattern corresponding to the minimum network travel time satisfies ${\min }_v{\sum }_a{t}_a(v_a)v_a$ again constrained to demand-feasible flows.

The UE path flows equilibrate the total OD cost ${\sum }_a{c}_a{\delta }_{ap}^w$ on each path $p$ connecting OD $w$, including the cost arising from any link tolls. Applying network tolls therefore enables us to achieve the system optimum (minimum travel time) flow pattern, while satisfying UE with respect to the total costs.

We can apply tolls to achieve many other demand-feasible flow patterns e.g. for a single OD network we could ensure non-zero flow on only one path by applying sufficiently high tolls on the links we wish to remain unused. In this case the toll levels are not unique, and the set of tolled links may be non-unique. This is particularly the case if we allow “negative tolls”.

For a given network we say that we have full controllability if we can push the UE solution to be ANY feasible link flow solution $v\in \mathrm{\Omega }(q)$.
Problem 1: Minimum toll set for full controllability under fixed demand
For a given network with fixed demand, using positive or negative tolls, determine the minimum number of links to toll in order to achieve full controllability (i.e. the toll levels can be varied to achieve the different flow patterns, but the set of tolled links is fixed).
Problem 2: Minimum toll set to achieve system optimal under any demand
For a given network, determine the minimum number of links to toll (positively or negatively) so that UE gives the system optimum flow pattern at ANY level of OD demand(s).

Notes: In the simplest case there is only one OD pair. Certain network topologies may be trivial e.g. spanning tree. For which network topologies can bounds be established?

Let $G=(V,E)$ be a directed graph which corresponds to the infrastructure of a train network. We like to embed two (or multiple) trains with given origins and destinations and given departure and arrival times. Some vertices/edges may be blocked in a specific time window, for example since another fixed train uses the track at this moment.

The easier case is to embed a single train in the network which takes the times the infrastructure can be used into account. One approach to solve the problem is to construct a time expanded network, delete all vertices/edges which cannot be used and find a path in the time expanded network.

For two (or multiple) trains we have to find disjoint path so that the trains do not collide. Shiloach and Perl [1] provide an algorithm which solves this problem in directed acyclic graphs. But disjoint path in general are not enough: Due to safety reasons, the trains will block the nodes/edges longer than the time they are on them. That raises the question how to find “very disjoint” paths in a directed graph.

The discussion during the seminar leads to promising ideas, e.g. how to adapt the algorithm by Shiloach and Perl [1]. However, constructing the time expanded network blows up the instance. Thus, this idea is very time consuming and the question arise how to speed up.