A Network Game of Dynamic Traffic

Zhigang Cao, Bo Chen, Xujin Chen, Changjun WangarXiv 2017 · arXiv

TL;DR

This paper introduces a realistic dynamic traffic network game where selfish agents make routing decisions on-the-fly at every intersection under deterministic queuing. The authors constructively prove the existence of a Subgame Perfect Equilibrium (SPE) and show that traditional static-path Nash Equilibria form a proper subset of these dynamic outcomes. Crucially, they solve a long-standing open challenge by proving that traffic queues remain bounded over time for key network topologies, ensuring a bounded Price of Anarchy.

What Problem Does This Paper Address?

Traditional traffic routing models (like classic selfish routing) often assume static flows, failing to capture real-world dynamic phenomena like traffic jams, queuing, and on-the-fly rerouting. While dynamic flow models have gained traction recently, most existing literature forces agents to commit to a single path at the origin or relies on permanent, global player priorities to break ties.

This paper tackles a more realistic and complex scenario: a discrete-time network game with atomic agents who can dynamically alter their routing choices at every intersection they encounter. Traffic is regulated via local edge priorities and a First-In-First-Out (FIFO) queuing rule. The authors investigate fundamental game-theoretic questions for this model: Does an equilibrium always exist? How do on-the-fly decisions alter the space of equilibrium outcomes compared to upfront path choices? And importantly, do traffic queues blow up to infinity, or do they remain bounded?

Methods

The authors model the system as an extensive-form game ($\Gamma$) to capture the sequential, intersection-by-intersection decision-making process of the agents. To analyze this complex setup, they also define a simplified normal-form game ($\Gamma^n$), where agents select their entire path simultaneously at the start.

The core methodological contributions include:

  1. Iterative Dominating Path Profile Algorithm: A greedy, algorithmic approach used to constructively prove the existence of an SPE. The algorithm iteratively finds paths for agents such that earlier agents cannot be overtaken by later ones, regardless of what the later agents do.
  2. Inductive Bridge Construction: A method to iteratively assemble upfront Nash Equilibria into a full extensive-form SPE, allowing the authors to mathematically map the relationship between the two game formulations.
  3. Network Cut Analysis: Mathematical induction applied to network cuts to track how populations move through subnetworks, establishing bounds on queue lengths.

Datasets

Not discussed in the paper. This is a purely theoretical and mathematical economics paper; no empirical datasets or simulation benchmarks were utilized.

Key Insights and Ideas

  • Edge Priorities are Essential for Stability: A major "aha" moment is that placing tie-breaking priorities on edges (road segments) rather than globally on players is what guarantees the existence of an equilibrium. The authors demonstrate via a counterexample that if priorities are player-based, "Rock-Paper-Scissors" style loops emerge, and an SPE may not exist.
  • Flexibility Breeds More Options: Because agents can change paths mid-route in the extensive game ($\Gamma$), the set of equilibrium outcomes is strictly larger than in the rigid, upfront-choice game ($\Gamma^n$).
  • Natural Hierarchy and Global FIFO: At equilibrium, agents naturally sort themselves into chronological "batches" based on arrival times. Earlier batches are completely insulated from the choices of later batches (Hierarchical Independence). Furthermore, a global FIFO property naturally emerges across the entire network, even though FIFO is only enforced locally at individual queues.

Key Results

  • Guaranteed SPE: The paper provides the first constructive proof that a pure-strategy Subgame Perfect Equilibrium always exists in dynamic atomic routing games with edge priorities.
  • Proper Containment: The authors prove that the set of Nash Equilibria (NE) outcomes from upfront path selection is a proper subset of the SPE outcomes from dynamic routing.
  • Strong Equilibria: Every NE in the upfront game is shown to be a strong NE, meaning no coalition of players can collude to improve everyone's travel time. This implies the outcomes are weakly Pareto optimal.
  • Bounded Queue Lengths: The authors resolve a significant open problem by proving that equilibrium queue lengths are bounded by a finite number depending only on the network size, provided the inflow rate doesn't exceed the network's capacity. This is proven for series-parallel networks in $\Gamma^n$ and for networks where the in-degree does not exceed the out-degree at any nonterminal vertex in $\Gamma$. Consequently, the Price of Anarchy (PoA) is bounded.

Limitations and Future Work

  • Topology Restrictions: The proof for bounded queue lengths is limited to specific network structures (series-parallel or networks where in-degree $\le$ out-degree). Whether queues remain bounded in completely general networks is still an open question.
  • Single Origin-Destination: The model assumes all agents share a single origin and destination. Extending these proofs to multi-origin, multi-destination networks introduces significant complexity.
  • Fixed Departure Times: Agents enter the system at pre-determined times. A valuable extension would allow agents to strategically choose when to depart to minimize their latency.

Summary updated

Abstract

We study a network congestion game of discrete-time dynamic traffic of atomic agents with a single origin-destination pair. Any agent freely makes a dynamic decision at each vertex (e.g., road crossing) and traffic is regulated with given priorities on edges (e.g., road segments). We first constructively prove that there always exists a subgame perfect equilibrium (SPE) in this game. We then study the relationship between this model and a simplified model, in which agents select and fix an origin-destination path simultaneously. We show that the set of Nash equilibrium (NE) flows of the simplified model is a proper subset of the set of SPE flows of our main model. We prove that each NE is also a strong NE and hence weakly Pareto optimal. We establish several other nice properties of NE flows, including global First-In-First-Out. Then for two classes of networks, including series-parallel ones, we show that the queue lengths at equilibrium are bounded at any given instance, which means the price of anarchy of any given game instance is bounded, provided that the inflow size never exceeds the network capacity.
BibTeX
@misc{cao2017network,
  author = {Zhigang Cao and Bo Chen and Xujin Chen and Changjun Wang},
  title = {{A Network Game of Dynamic Traffic}},
  year = {2017},
  eprint = {1705.01784},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.01784},
}

Loading related content...

Figure