Tobias Harks

Lukas Graf, Tobias Harks, Michael Markl

Stochastic effects significantly influence the dynamics of traffic flows. Many dynamic traffic assignment (DTA) models attempt to capture these effects by prescribing a specific ratio that determines how flow splits across different routes based on the routes' costs. Other models take a game-theoretic perspective and describe the equilibria resulting from the individual traffic participants' decisions instead of prescribing flow splits, however they usually neglect stochastic effects. In this paper, we propose a new unifying framework for DTA that incorporates the interplay between the routing decisions of each single traffic participant, the potentially stochastic nature of predicting the future state of the network, and the physical flow dynamics. Our framework consists of an edge loading operator modeling the physical flow propagation and a routing operator modeling the routing behavior of traffic participants. The routing operator is assumed to be set-valued and, thus, capable to model complex (deterministic) equilibrium conditions as well as stochastic equilibrium conditions assuming that measurements for predicting traffic are noisy. As our main results, we derive several quite general equilibrium existence and uniqueness results which not only subsume known results from the literature but also lead to new results. Specifically, for the new stochastic prediction equilibrium, we show existence and uniqueness under natural assumptions on the probability distribution over the predictions.

Aloïs Duguet, Tobias Harks, Martin Schmidt et al.

We consider mixed-integer linear-quadratic generalized Nash equilibrium problems, i.e., games in which each player solves a mixed-integer program subject to linear constraints in her own and rivals' strategies as well as an objective which is quadratic in her own strategies and bilinear in her own and rivals' strategies. For this class of games, we study the question of the existence of rational equilibria assuming rational input data. We distinguish four subclasses according to the presence of player-quadratic terms in the objective and rival-dependent constraints. As our main result, we completely settle the rationality question for all four subclasses, i.e., we show that only player-linear games without player-quadratic terms and without rival-dependent constraints admit rational equilibria -- if the game admits equilibria at all. All other three classes contain instances with irrational equilibria only.

Tobias Harks, Mona Henle, Max Klimm et al.

We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources and, after observing the realized loads, an adversary (single-follower) attacks the resources with maximum loads, causing additional costs for the leaders. For the resulting strategic game among the leaders, we show that pure Nash equilibria may fail to exist and therefore, we consider approximate equilibria instead. As our first main result, we show that the existence of a $K$-approximate equilibrium can always be guaranteed, where $K \approx 1.1974$ is the unique solution of a cubic polynomial equation. To this end, we give a polynomial time combinatorial algorithm which computes a $K$-approximate equilibrium. The factor $K$ is tight, meaning that there is an instance that does not admit an $α$-approximate equilibrium for any $α<K$. Thus $α=K$ is the smallest possible value of $α$ such that the existence of an $α$-approximate equilibrium can be guaranteed for any instance of the considered game. Secondly, we focus on approximate equilibria of a given fixed instance. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible $α$ among all $α$-approximate equilibria of the given instance.

Lukas Graf, Tobias Harks, Kostas Kollias et al.

We study a dynamic traffic assignment model, where agents base their instantaneous routing decisions on real-time delay predictions. We formulate a mathematically concise model and define dynamic prediction equilibrium (DPE) in which no agent can at any point during their journey improve their predicted travel time by switching to a different route. We demonstrate the versatility of our framework by showing that it subsumes the well-known full information and instantaneous information models, in addition to admitting further realistic predictors as special cases. We then proceed to derive properties of the predictors that ensure a dynamic prediction equilibrium exists. Additionally, we define $\varepsilon$-approximate DPE wherein no agent can improve their predicted travel time by more than $\varepsilon$ and provide further conditions of the predictors under which such an approximate equilibrium can be computed. Finally, we complement our theoretical analysis by an experimental study, in which we systematically compare the induced average travel times of different predictors, including two machine-learning based models trained on data gained from previously computed approximate equilibrium flows, both on synthetic and real world road networks.