Cost Design in Atomic Routing Games
03 Oct 2022 | publication Yue Yu, Shenghui Chen, David Fridovich-Keil,and Ufuk TopcuAmerican Control Conference, 2023
- Motivation
- Atomic Routing Games
- Forward Game Solution
- Inverse Cost Design
- Numerical Result
- Implementation Note
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
On a directed graph characterized by
Then let
Each player
Forward Game Solution
We assume the cost of each player
where
We introduce the notion of Nash equilibrium in an atomic routing game as a joint flow
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
This problem can be approximately solved by converting to a nonlinear least-squares problem (see detailed derivation in Lemma 2 of our paper):
We assume the matrix
Inverse Cost Design
We now introduce the cost design problem in atomic routing games. The task is to design the value of a vector
To solve this problem, we propose an algorithm that iteratively
- Forward game solution: solves an equilibrium
with the current cost parameters using . - Inverse cost design: updates
by projected gradient descent until the solution converges to a desired equilibrium or reaches the maximum number of iterations.
The key step in inverse cost design is to differentiate through the approximate Nash equilibrium conditions.
After a step of gradient descent, we project the new cost parameters to defined spaces in order to satisfy the uniqueness assumption posed.
Numerical Result

Implementation Note
We implemented the algorithms in Julia using the JuMP interface. The nonlinear optimization in the