# Price of anarchy for dynamic flows

05 Dec 2019This post is about flows from a game theory perspective. It originates from a recent talk of Tim Oosterwijk at the University of Chile about this paper.

## A model for dynamic flows

We use a model useful to study settings like urban traffic.
The flow is dynamic (that is we do not focus on
some stationary state) and there
can be congestion. It is called the *fluid queueing
model*.

The network is a graph, and there is one source node where the flow enters and one target node where the flow exits. Each edge of the network has a delay and a capacity per time unit. If more flows enters the edge than the capacity, a (FIFO) queue will form inside this edge.

Maybe a good example is a network where on every edge there is a toll. If there is no queue, going through a toll $t$ takes some $s_t$ seconds, and at most some $c_t$ cars can go through the toll at each second. If too many cars arrive, then a queue is forming, that will disappear later if not so many cars arrive.

## Objective

We consider a setting where a constant flow $u_0$ enters the network at each unit of time.

Now at each intersection of degree $d$ a particule of flow can go in either of the $d-1$ directions. Given the choice of each particule at each intersection, the flow is completely defined, and you can measure how fast it is. For example routing every particule through the same edge of small capacity would in general form a huge queue in this edge and make the flow very slow.

We can consider at least two notions of efficiency: (1) for a given
time, how much flow exits the network, and (2) for a given amount of flow
to start with, when does the last particule exits the network.
We we will consider the second one, called the *makespan*.

## Price of anarchy

We study the makespan of different strategies for routing the flow.
As often in
algorithmic game theory,
one is interested in the price of anarchy.
On a given instance this price is the ratio of the makespan of the best
routing strategy divided by the makespan of the strategy where every
particule optimizes its own travel time.
In other words, the ratio between the strategy where an oracle decides
optimally a route for every car, and the strategy where every driver
optimizes its own travel time. Note that the setting where we let the
particules (or drivers) decide is a kind of game, and we look at the
equilibrium of this game. This might be called the *selfish* solution.

The price of anarchy of the problem is the largest (the supremum to be precise) price of anarchy among every instance of the problem.

## Result

Tim and his co-authors show (among other results) an upper bound of $e/(e-1)$ on the price of anarchy for this problem, under some conditions.

## A key open problem: the monotonicity conjecture

There is a very neat and puzzling conjecture that, if true, would imply that the upper bound above always hold.

The so-called *monotonicity conjecture* states that: if one reduces the
flow that enters in the network by unit of time (but keeping the total
amount to push in the network), then the makespan of the selfish solution
increases.

This seems very natural, but it is still open, and sometimes unexpected things happen in the such games (like in Braessâ€™s paradox)