Frontiers in Economics and Computation - UK

This seminar series features research in Economics and Computation, Game Theory, Optimisation in a broad sense

Join Mailing List   -   Twitter


Continuity, Uniqueness and Long-Term Behaviour of Nash Flows Over Time

  • Abstract. 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. 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 behaviour 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, rather surprisingly, intimately connected to the third.

    Manuscript: ArXiv '21 (Appeared at FOCS 2021)


Neil Olver (LSE)

25 May '22

  • Bio. Neil Olver is an Associate Professor in the Department of Mathematics at LSE. He works broadly in combinatorial optimization and its intersections with algorithmic game theory and probability. A focus of his work is on designing provably good algorithms for fundamental network optimization problems, motivated by applications such as road traffic and telecommunication networks. He was previously faculty at the Vrije Universiteit Amsterdam, an Instructor in Applied Mathematics at MIT, and a PhD student at McGill University. He has received a number of grants for his work, including VIDI and VENI grants from the Dutch Research Council.