Neil Olver
Associate Professor
Department of Mathematics, LSE
N.Olver@lse.ac.uk
Publications - agt
Filter by type:
We consider a dynamic model of traffic that has received a lot of attention in the past few years. Infinitesimally small agents aim to travel from a source to a destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form based on the deterministic queueing model whenever the inflow into a link exceeds its capacity.
Are equilibria in this model meaningful as a prediction of traffic behavior? For this to be the case, a certain notion of stability under ongoing perturbations is needed. Real traffic consists of discrete, atomic “packets”, rather than being a continuous flow of non-atomic agents. Users may not choose an absolutely quickest route available, if there are multiple routes with very similar travel times. We would hope that in both these situations — a discrete packet model, with packet size going to 0, and $\epsilon$-equilibria, with $\epsilon$ going to 0 — equilibria converge to dynamic equilibria in the flow over time model. No such convergence results were known.
We show that such a convergence result does hold in single-commodity instances for both of these settings, in a unified way. More precisely, we introduce a notion of “strict” $\epsilon$-equilibria, and show that these must converge to the exact dynamic equilibrium in the limit as $\epsilon \to 0$. We then show that results for the two settings mentioned can be deduced from this with only moderate further technical effort.
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 modeled via queues, which form whenever the inflow into a link exceeds its capacity. Despite lots of interest, some very basic questions remain open in this model. We resolve a number of them:
• We show uniqueness of journey times in equilibria.
• We show continuity of equilibria: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions.
• We demonstrate that, assuming constant inflow into the network at the source, equilibria always settle down into a “steady state” in which the behavior extends forever in a linear fashion.
One of our main conceptual contributions is to show that the answer to the first two questions, on uniqueness and continuity, are intimately connected to the third. Our result also shows very clearly that resolving uniqueness and continuity, despite initial appearances, cannot be resolved by analytic techniques, but are related to very combinatorial aspects of the model. To resolve the third question, we substantially extend the approach of Cominetti et al., who show a steady-state result in the regime where the input flow rate is smaller than the network capacity.
Hypercongestion—the phenomenon that higher traffic densities can reduce throughput—is well understood at the link level, but has also been observed in a macroscopic form at the level of traffic networks; for instance, in morning rush-hour traffic into a downtown core. In this paper, we show that macroscopic hypercongestion can occur as a purely emergent effect of dynamic equilibrium behaviour on a network, even if the underlying link dynamics (we consider Vickrey bottlenecks with spaceless vertical queues) do not exhibit hypercongestion.
Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.
Game Theory and Mechanism Design are by now standard tools for studying and designing massive decentralized systems. Unfortunately, designing mechanisms that induce socially efficient outcomes often requires full information and prohibitively large computational resources. In this work we study simple mechanisms that require only local information. Specifically, in the setting of a classic scheduling problem, we demonstrate local mechanisms that induce outcomes with social cost close to that of the socially optimal solution. Somewhat counter-intuitively, we find that mechanisms yielding Pareto dominated outcomes may in fact enhance the overall performance of the system, and we provide a justification of these results by interpreting these inefficiencies as externalities being internalized. We also show how to employ randomization to obtain yet further improvements. Lastly, we use the game-theoretic insights gained to obtain a new combinatorial approximation algorithm for the underlying optimization problem.
We consider a priority-based selfish routing model, where agents may have different priorities on a link. An agent with a higher priority on a link can traverse it with a smaller delay or cost than an agent with lower priority. This general framework can be used to model a number of different problems. The structural properties that lead to inefficiencies in routing choices appear different in this priority-based model compared to the classical model. In particular, in parallel link networks with nonatomic agents, the price of anarchy is exactly one in the priority-based model; that is, selfish behaviour leads to optimal routings. In contrast, in the standard model the worst possible price of anarchy can be achieved in a simple two-link network. For multi-commodity networks, selfish routing does lead to inefficiencies in the priority-based model. We present tight bounds on the price of anarchy for such networks. Specifically, in the nonatomic case the worst-case price of anarchy is exactly $(d + 1)^{d+1}$ for polynomial latency functions of degree $d$ (hence 4 for linear cost functions). For atomic games, the worst-case price of anarchy is exactly $3+2\sqrt{2}$ in the weighted case, and exactly 17/3 in the unweighted case. An upper bound of $O(2^dd^d)$ is also shown for polynomial cost functions in the atomic case, although this is not tight. Our framework (and results) also generalise to include models similar to congestion games.