Routing Games

Motivating Example: Competing delivery companies¶

In a busy city, two rival delivery companies — QuickShip and TurboExpress — operate daily distribution routes to deliver packages to the central business district.

Each company starts from its own warehouse, located in different suburbs on opposite sides of the city. Every morning, the companies dispatch their fleets toward the central depot, but must decide how to route their vans:

• Each company can take its own dedicated service road to the depot.
• Alternatively, both companies can use a shared ring road that offers a faster connection, but becomes congested as total traffic increases.

The travel costs for each route depend on the level of congestion:

• For QuickShip (source $s_1$):

  • Dedicated service road cost: $c_{s_1}(x) = x^2$, where $x$ is the number of QuickShip vans using this road.

• For TurboExpress (source $s_2$):

  • Dedicated service road cost: $c_{s_2}(x) = \dfrac{3}{2}x$.

• For the shared ring road (available to both companies):

  • Shared road cost: $c_\text{shared}(x) = x$, where $x$ is the total number of vans from both companies using this route.

Each source has a total demand of $r = 1 / 2$ units of traffic to send to the sink.

This is shown diagrammatically in Figure 1.

Each company decides independently how to distribute its fleet across the available routes, aiming to minimise its own delivery costs. However, since the shared road’s cost depends on total usage, each company’s decision affects the other’s outcome.

This setting creates a routing game, where decentralised decisions lead to interdependent costs. We will analyse this scenario to explore the concept of Nash equilibrium in network routing, and investigate how self-interested routing can result in stable, but potentially inefficient, traffic patterns.

Theory¶

Definition: Routing Game¶

A routing game $(G,r,c)$ is defined on a graph $G=(V,E)$ with a defined set of sources $s_i$ and sinks $t_i$. Each source-sink pair corresponds to a set of traffic (also called a commodity) $r_i$ that must travel along the edges of $G$ from $s_i$ to $t_i$. Every edge $e$ of $G$ has associated to it a nonnegative, continuous and nondecreasing cost function (also called latency function) $c_e$.

Example: The Routing Game Representation of the Delivery Companies Game¶

For the routing game in Figure 1:

• $G=(V, E)$ with $V=\{s_1, s_2, a, t\}$ and $E=\{(s_1, t), (s_1, a), (s_2, a), (s_2, t), (a, t)\}$
• $r_1=r_2=1/2$
• $c_{s_1, t}(x)=x^2, c_{s_2, t}(x)=3x/2, c_{a, t}(x)=x, c_{s_1, a}(x)=c_{s_2, a}=0$

Definition: Set of Paths¶

For any given $(G,r,c)$ we denote by $\mathcal{P}_i$ the set of paths available to commodity $i$.

Definition: Feasible Flow¶

On a routing game we define a flow $f$ as a vector representing the quantity of traffic along the various paths, $f$ is a vector index by $\mathcal{P}$. Furthermore we call $f$ feasible if:

Example: Feasible Flows for the Delivery Companies Game¶

For the routing game in Figure 1:

and

The set of all possible paths is denoted by $\mathcal{P}=\bigcup_{i}\mathcal{P}_i$.

Definition: Cost function¶

For any routing game $(G,r,c)$ we define a cost function $C(f)$:

Where $c_P$ denotes the cost function of a particular path $P$: $c_P(x)=\sum_{e\in P}c_e(x)$. Note that any flow $f$ induces a flow on edges:

So we can re-write the cost function as:

Example: Cost function for the Delivery Companies Game¶

For the routing game in Figure 1:

Let $f=(\alpha,1/2-\alpha,1/2-\beta,\beta)$ as shown in Figure 2.

The cost of $f(\alpha,1/2-\alpha,1/2-\beta,\beta)$ is given by:

Definition: Optimal Flow¶

For a routing game $(G,r,c)$ we define the optimal flow $f^*$ as the solution to the following optimisation problem:

Minimise $\sum_{e\in E}c_e(f_e)f_e$:

Subject to:

Example: Optimal Flow for the Delivery Companies Games¶

In Figure 2 this corresponds to:

Minimise $C(\alpha,\beta)=\alpha^3+3/2\beta^2+\alpha^2 + 2\alpha\beta + \beta^2 - 2\alpha - 2\beta + 1$:

Subject to:

A plot of $C(\alpha,\beta)$ is shown in Figure 3.

The minimal point looks to be near the right boundary of the square, although it is unclear if it is on the boundary or not. It is in fact not on the boundary taking this fact as an assumption, identity the optimal flow using the Karush-Kuhn-Tucker conditions.

Let us first define the Lagrangian:

If $f^*$ is the minimal point then the complementary slackness implies that $\lambda_i=0$ for all $i$, since this point does not sit on any boundary which would make the corresponding constraint function $g_i(f^*)=0$.

Thus:

We note that the feasiblity constraints all hold for $f^*$ so we are left to check stationarity:

and

which gives:

Substituting this in to the first equation gives:

which has solutions:

Only one of those is positive satisfying the constraints, substituting it in to (14) gives:

thus the optimal flow is:

If we take a closer look at $f^*$ in our example, we see that traffic from the first commodity travels across two paths: $(s_1, t)$ and $(s_1, a, t)$. The cost along the first path is given by:

The cost along the second path is given by:

Thus traffic going along the second path is experiencing a higher cost. In practice, they would deviate some of their traffic from the second path to the first.

This leads to the definition of a Nash flow.

Definition: Nash Flow¶

For a routing game $(G,r,c)$ a flow $\tilde f$ is called a Nash flow if and only if for every commodity $i$ and any two paths $P_1,P_2\in\mathcal{P}\_i$ such that $f\_{P_1}>0$ then:

A Nash flow ensures that all used paths have minimal costs.

Example: Nash Flow for Delivery companies game¶

For Figure 2 if we assume that both commodities use all paths available to them:

Solving this gives: $\beta=\frac{2}{5}(1-\alpha)$ $\Rightarrow$ $x^{2} + \frac{3}{5} x - \frac{3}{5}$ this gives

Neither of these two values are within our region thus there is no Nash flow where all paths are used.

Let us assume that $\alpha=1/2$ (i.e. commodity 1 does not use $P_{s_1, a, t}$). Assuming that the second commodity uses both available paths we have:

Thus we have $\tilde f=(1/2,1/5)$ which gives a cost of $C(\tilde f)=11/40$ which is higher than the optimal cost!

What if we had assumed that $\beta=1/2$?

This would have given $\alpha^2=1/2-\alpha$ which has solutions:

Taking the second value for $\alpha$ which does lie in the feasible region. The cost of the path $P_{s_2, a, t}$ is then approximately .134 however the cost of the path $P_{s_2, t}$ is approximately .75 thus the second commodity should deviate. We can carry out these same checks with all other possibilities to verify that $\tilde f=(1/2,1/5)$ is a Nash flow.

Definition: Potential Function¶

Given a routing game $(G,r,c)$ we define the potential function of a flow as:

Example: Potential Function for the delivery company game¶

The potential function for Figure 2 is given by:

Theorem: Nash Flow minimises the potential function¶

A feasible flow $\tilde f$ is a Nash flow for the routing game $(G,r,c)$ if and only if it is a minima for $\Phi(f)$.

Definition: Marginal Cost¶

If $c$ is a differentiable cost function then we define the marginal cost function $c^*$ as:

Example: The marginal costs for the delivery company game¶

The marginal costs for Figure 2 are given by:

$c^*_{s_1, t}(x)=3x^2, c_{s_2, t}(x)=3x, c_{a, t}(x)=2x, c_{s_1, a}(x)=c_{s_2, a}=0$

The corresponding routing game $(G, r, c^*)$ is shown in Figure 4.

Theorem: Optimal Flow is a Nash Flow for Marginal Costs¶

A feasible flow $f^*$ is an optimal flow for $(G,r,c)$ if and only if $f^*$ is a Nash flow for $(G,r,c^*)$.

Exercises¶

Exercise: Braess’s Paradox¶

Determine the optimal and Nash flows for the routing games shown in Figure 5 and Figure 6.

Exercise: Nash flow via potential minimisation¶

Use Theorem: Nash Flow minimises the potential function and Appendix: Karush-Kuhn-Tucker Conditions to verify that $\tilde f=(1/2,1/5)$ is a Nash flow for Figure 2.

Nash flow from marginal cost formulation¶

Use Theorem: Optimal Flow is a Nash Flow for Marginal Costs to confirm that

is a Nash flow for Figure 2.

Programming¶

Scipy has functionality for optimising function within certain boundaries, thanks to Theorem: Nash Flow minimises the potential function this can be used to find not only optimal flows but also Nash flows.

In Appendix: Karush-Kuhn-Tucker Conditions is an example showing how to use Scipy to optimise a function. Here is another one:

import numpy as np
import scipy.optimize

def objective(f):
    alpha, beta = f
    return alpha ** 3 / 3 + 3 * beta ** 2 / 4 + (1 - alpha - beta) ** 2 / 2

def g_1(f):
    return f[0]

def g_2(f):
    return f[1]

def g_3(f):
    return 1 / 2 - f[0]

def g_4(f):
    return 1 / 2 - f[1]

constraints = [
    {'type': 'ineq', 'fun': g_1},
    {'type': 'ineq', 'fun': g_2},
    {'type': 'ineq', 'fun': g_3},
    {'type': 'ineq', 'fun': g_4},
]

res = scipy.optimize.minimize(objective, [0, 0], constraints=constraints)
res

Notable Research¶

The original paper introducing the notion of Nash flows is Wardrop, 1952. An important phenomenon in this field is Braess’s Paradox, first described in Braess, 1968, which shows that adding capacity to a network can paradoxically increase overall congestion. This effect is not purely theoretical and has been observed in real-world settings Steinberg & Zangwill, 1983Youn et al., 2008.

The inefficiencies that arise in congestion networks due to self-interested behaviour have led to the concept of the Price of Anarchy, defined as $C(\tilde f)/C(f^*)$. This concept was introduced in Roughgarden & Tardos, 2002. Various applications have been explored, including Knight & Harper, 2013, which studied the inefficiencies caused by patients selecting hospitals based on individual preferences.

Conclusion¶

In this chapter, we introduced routing games, where self-interested agents choose paths through a network to minimize their own travel costs. These individual decisions create congestion effects, making costs interdependent and leading to potentially inefficient outcomes.

We developed a formal framework for routing games, introduced the key concepts of feasible flow, optimal flow, and Nash flow, and explored how potential functions allow us to compute Nash flows via standard optimisation techniques. We also introduced the concept of marginal costs, leading to the result that optimal flows correspond to Nash flows in a modified game with marginal cost functions.

Table 1 summarises the key concepts introduced in this chapter.