Shenghui Chen CS PhD @UTAustin

Cost Design in Atomic Routing Games

Yue Yu, Shenghui Chen, David Fridovich-Keil,and Ufuk Topcu
American Control Conference, 2023

Motivation

Transportation is crucial in our daily lives. Picture an intersection with four cars, each wanting to reach the opposite side of the road. The instinctive choice for each car would be the shortest path, directly crossing the intersection. However, this would lead to congestion at the center of the intersection. What’s a better solution for a socially optimal interaction? In reality, a roundabout is often implemented as an alternative. It slows down vehicles and enhances transportation efficiency by requiring each car to take a slightly longer route. (See comparison in the animation below.)

Before Design After Design

In this paper, we study the problem of designing the right cost structure that encourages players to choose the roundabout—a more desirable social interaction—instead of direct crossings.

Atomic Routing Games

Routing games are the fundamental mathematical models for predicting the collective behavior of selfish players in transportation networks. A routing game is a multi-player game on a directed graph.

A directed graph G contains a set of nodes [n] and a set of directed links [m] where each link is an ordered pair of “tail” node to “head” node. We characterize the connection among nodes in the graph G by the incidence matrix ERn×m where

(1)[E]ij={1,if node i is the tail of link j,1,if node i is the head of link j,0,otherwise.

On a directed graph characterized by E, an atomic routing game considers pN players where each player i[p] has an origin node oi[n] and a destination node di[n] in graph G. Let riRn denote the the origin-destination vector of player i such that

(2)[ri]j={1,if j=oi,1,if j=di,0,otherwise.

Then let si=Γ(ri,di)Rn1 denote the reduced origin-destination vector obtained by deleting the di-th element in ri. We also define the notion of reduced incidence matrix for player i by Ei:=Γ(E,di). Hence, we define the feasible flow set for player i by PiRm as

(3)Pi={yRm|Eiy=si,y0},i[p].

Each player i[p] chooses a path from its origin node oi to its destination node di. We represent the path chosen by player i via a flow vector xiRm, where [xi]k[0,1] denotes the probability for player i to use link k on the chosen path. By the definition above, if vector xi is a valid path connecting nodes oi and di, then it belongs to a feasible flow set. In other words, xiPi if and only if xi is a unit flow that originates at node oi, ends at node di, and is preserved at any other node.

Forward Game Solution

We assume the cost of each player i[p] is in the form of

(4)bi+12Ciiy+jiCijxj,

where biRm is the nominal link cost independent of the players’ choices, and CijRm×m for all i,j[p] are matrices of cost adjustments introduced due to interactions with other players.

We introduce the notion of Nash equilibrium in an atomic routing game as a joint flow x:=[xixp] where i[p],

(5)xiargminyPi(bi+12Ciiy+jiCijxj)y.

In the paper, we show how to compute this Nash equilibrium by solving a set of piecewise linear equations. However, since the nonsmooth piecewise linear equations are difficult to solve in general, we propose an approximate solution with smooth nonlinear equations instead. To this end, we first introduce an entropy-regularized Nash equilibrium below as an apprximation solution concept.

Forward Game Solution: Entropy-regularized Nash equilibrium
A joint flow x:=[xixp] is an approximate Nash equilibrium if all players i[p] choose flow vectors xi as follows:
(6)i[p]{minxi(bi+12Ciixi+jiCijxj)xi+λxiln(xi)s.t.Eixi=sixi0
where λR0 is an entropy weight.


This problem can be approximately solved by converting to a nonlinear least-squares problem (see detailed derivation in Lemma 2 of our paper):

Forward Game Solution: Nonlinear Least Squares
x,v=Ent-NE(b,C) iff x,v solves the nonlinear least squares problem
(7: Ent-NE)minx,vxexp(1λ(E[1,p]vbCx)1pm)2+E[1,p]xs2


We assume the matrix C bears a specific structure that can ensure the uniqueness of the solution (see Assumption 1 and Theorem 1 in our paper).

Inverse Cost Design

We now introduce the cost design problem in atomic routing games. The task is to design the value of a vector b and a matrix C such that the entropy-regularized Nash equilibrium x optimizes certain performance function ψ(x),

minx,v,b,Cψ(x)=12xx^2s.t.x,v=Ent-NE(b,C)(8)bB,CC.

To solve this problem, we propose an algorithm that iteratively

  • Forward game solution: solves an equilibrium x with the current cost parameters b,C using 7: Ent-NE.
  • Inverse cost design: updates b,C by projected gradient descent until the solution converges to a desired equilibrium x^ or reaches the maximum number of iterations.

Flowchart

The key step in inverse cost design is to differentiate through the approximate Nash equilibrium conditions.

Inverse Cost Design: Implicit Differentiation
We focus on the derivation of bψ(x); similar logic applies to Cψ(x).
(9)bψ(x)=bxxψ(x)=b[xv][xψ(x)0p(n1)]
Let ξ=[xv], we need to compute bξ and xψ(x). The latter is straight-forward to compute since ψ(x) only depends on x. To derive the former, we first let
(10)F(ξ,b,C):=[xexp(1λ(E[1,p]vbCx)1pm)sE[1,p]x],
and by the implicit function theorem, we have if ξF(ξ,b,C) is nonsingular, then
(11)bξ=(ξF(ξ,b,C))1bF(ξ,b,C)
which can be done since ξ and b are variables of the function F. We adopt ^bψ(x) in practice, where we use the Moore-Penrose pseudoinverse of a matrix whose inverse may not exist. Check Theorem 2 in our paper for more details.


After a step of gradient descent, we project the new cost parameters to defined spaces in order to satisfy the uniqueness assumption posed.

Inverse Cost Design: Projections
The projection maps ΠB:RmRm and ΠD:Rm×mRm×m are given by
ΠB(b)=argminzBzb,(12)ΠD(C)=argminXDXCF,
and we choose spaces
B:={bRpm|0pmbδ1pm},(13)D:={CRpm×pm|C+C0,CFρ,Cii=Cii,i[p]},
where parameters δ and ρ control the amount of variation allowed for b and C, respectively.


Numerical Result

Implementation Note

We implemented the algorithms in Julia using the JuMP interface. The nonlinear optimization in the 7: Ent-NE is solved by IPOPT. In this work, we hand-derived all the gradients, but they can also be easily computed with the auto-grad tools, e.g., Zygote. Check out our code on github for more details.