Similar to Maximum Flow Problem. An instance of a Potential Game.

Atomic Traffic Routing

This time, there are cars (not infinitesimally small). If player chooses path , then:

  1. : traffic (=# of cars) flowing thru edge
  2. Individual cost:
  3. Potential Function:
    • This is similar to the integral of costs for each edge:

thm. (Potential function minimization derives PNE) Minimizing the following potential function will give you the PNE.

Proof. The inner summation above is Intuitively the area under the cost, as illustrated above. Then, consider an agent deviated from path to , which as a whole is a change from flow to . Then the difference in potential of these two flows is:

Thus, each user’s goal is to minimize this potential function. Therefore the minimum of the potential function is the pure strategy nash eqilibirum.

thm. (existence of PNE). Proof outline. This potential function will have one global minimum, if the cost functions are monotonically increasing (v.v. strictly increasing) and continuous, making a (v.v. strictly) convex function which has a global minimum (v.v. a single global minimum). This shows that it PNE will always exist for monotonic cost functions.

Nonatomic Traffic Routing


  • flow on edge is
  • Congestion Function i.e. time taken
  • Individual Delay for Path :
  • Total Delay for all paths:

Pigou’s Example

  • Nash Equilibrium when
    1. For all users of edge ,
    2. For all users of edge ,
    • Total delay
  • Global Optimum when:

⇒ Total delay minimized when half goes thru , other half goes thru

Braess’s Paradox

i.e. adding a new road may worsen outcome for Nash Equilibrium (but not in global minimum)

  • Consider before and after adding edge from , a superhighway with zero delay cost.
  • NE before adding blue edge:
    • on top ()
    • on bottom ()
  • NE after adding blue edge (superhighway):
    • all passes thru green path ()
    • (worse!)

For Social Planner…

Observe that congestion network is a convex optimization problem:

  • Total Delay function is a convex function
  • Constraints (=conversation of flow) are linear:
    1. inflow = outflow
    2. flow at source/target is

For Obtaining Nash Equilibirum…

thm. Routing NE Uniqueness. For every routing problem there is only one NE.

thm. Obtaining NE of Congestion Network. Minimizing the following function will yield the unique NE of any congestion network:

Proof Sketch. The following definition of will satisfy the definition of a potential function