Do all Wardrop Equilibria have the same social cost?

Question

I'm currently studying non-atomic congestion games, and i've come accross the following definition of the price of anarchy:

Let $f$ be a Wardrop equilibrium and let $f^*$ be a system optimal flow. Then, the price of anarchy is defined as

$$\rho(G) =\frac{C(f)}{C(f^*)}$$

where $G$ is a non-atomic congestion game, $C(f) = \sum_{e\in E} c_e(f_e)f_e$ is the social cost of an edge flow $f$ and $f_e =\sum_{i\in K}f_i(e)$ is the total load on edge $e$ (i.e. from all commodity flows).

Note that the above definition does not include a supremum over all possible Wardrop equilibria. While it is clear that all system optimal flows $f^*$ have the same social cost (they are defined as flows that minimize the social cost $C$), it is not at all clear that all Wardrop equilibria $f$ have the same social cost $C(f)$.

I found the following document, where the same definition is used in page 25: https://publications.rwth-aachen.de/record/50519/files/Olbrich_Lars.pdf. The author claims that all Wardrop equilibria have the same social cost, and claims that this follows from the following characterization of Wardrop equilibria:

Assuming continuous and non-decreasing cost functions $c_e, \; e\in E$ a feasible flow is a Wardrop equilibrium if and only if it solves the following convex optimization problem:

$$\min_{f\in\mathcal{F}} \sum_{e\in E} \int_0^{f_e} c_e(t) \; dt$$

where $\mathcal{F}$ is the set of all nonnegative feasible edge flows.

I sadly don't see how this would imply that all Wardrop equilibria have the same social cost. I would appreciate some help here.

Answer 1

I think the main point here is the convexity. Wikipedia says:

The following are useful properties of convex optimization problems:

• every local minimum is a global minimum
• the optimal set is convex

So every Wardrop equilibrium has the same value of this convex potential function, and the convex combination of Wardrop equilibria is again a Wardrop equilibrium. As you move around in this convex set, the edge costs can’t change, since that would lead to an increase in the potential function. So all Wardrop equilibria have the same edge costs. They may not have the same flow along all edges (unless the cost functions aren’t just non-decreasing but strictly increasing), but flow can only switch among edges with the same cost, which doesn’t change the social cost.

Here are some resources I found that helped me in understanding this:

• The original paper with the convex potential function by Martin Beckmann, C. Bart McGuire and Christopher B. Winsten: Studies in the Economics of Transportation

• José R. Correa and Nicolás E. Stier-Moses: Wardrop Equilibria

• Wardrop User Equilibrium and Beckmann Formulation

• Prices of Anarchy and Stability