Decentralized Decision-Making among Heterogeneous Autonomous Vehicles: An $α$-Potential Game Framework

Anran Hu; Zhexin Wang; Yufei Zhang; Xuan Di

math.OCSep 30, 2026

Decentralized Decision-Making among Heterogeneous Autonomous Vehicles: An $α$ -Potential Game Framework

Authors: Anran Hu, Zhexin Wang, Yufei Zhang, Xuan Di

Organizations: Department of Industrial Engineering and Operations Research, Columbia University · Department of Mathematics, Imperial College London, London, UK · Department of Civil Engineering and Engineering Mechanics, Data Science Institute, Columbia University

Abstract

We study noncooperative multi-vehicle games among heterogeneous autonomous vehicles, where each vehicle adopts a decentralized closed-loop policy based on its own state, and optimizes an objective that depends on other vehicles through potentially asymmetric interaction weights. We develop an $α$ -potential game framework that reduces the computation of an approximate Nash equilibrium (NE) to the minimization of a single auxiliary $α$ -potential function. We explicitly construct this $α$ -potential, establish the existence of its minimizers, and characterize the equilibrium approximation error $α$ in terms of interaction asymmetry. We further introduce vehicle-specific scaling to reduce the effective interaction asymmetry, thereby tightening the equilibrium approximation and, in important cases, recovering an exact NE despite asymmetric interactions. We also derive social-efficiency guarantees for the potential-selected policies, revealing how the interaction structure shapes worst-case efficiency. Numerical experiments demonstrate the flexibility of the framework in capturing heterogeneous vehicle interactions, collision and obstacle avoidance, lane changing and overtaking under different traffic configurations, and priority-based intersection crossing.

Figures & tables

	$\displaystyle\text{find}$	$\displaystyle\tilde{p}\in[0,\infty)^{N}$
	$\displaystyle\text{s.t.}$	$\displaystyle\sum_{j\neq i}\|\tilde{p}_{i}\lambda_{ij}-\tilde{p}_{j}\lambda_{ji}\|\leq r_{\rm mid}\tilde{p}_{i},\qquad i\in[N],$
		$\displaystyle\sum_{i\in S_{\ell}}\tilde{p}_{i}=\|S_{\ell}\|,\qquad\ell=1,\ldots,m.$

Algorithm 1 Bisection for Optimizing Rescaling Parameters

Scenario (Section)	Dim.	Control	Experiment	Goal
Interaction regimes ( 5.1.1 )	1D	Velocity; acceleration	10 vehicles; weak versus strong interactions ( $\beta=0$ versus $\beta=1$ ) (Figures 1 and 2 )	Compare separation and collision avoidance
Scalability ( 5.1.1 )	1D	Velocity	30 vehicles; strong interactions ( $\beta=1$ ) (Figure 3 )	Assess scalability to a larger number of vehicles
Obstacle avoidance ( 5.1.2 )	2D	Acceleration	10 vehicles; no obstacle, or a circular obstacle of radius $0.1$ or $0.5$ (Figure 4 )	Assess trajectory responses to obstacle size
Rescaling ( 5.1.3 )	1D	Velocity; acceleration	9 vehicles with asymmetric interactions (Figure 5 ); exploitability before and after rescaling (Table 3 )	Assess size-dependent equilibrium behavior; Evaluate improvement in Nash approximation
Lane changing ( 5.2 )	2D	Velocity	3 vehicles, 2 lanes; two initial layouts with identical costs and target speeds (Figure 6 )	Compare lane changes and overtaking behavior
Intersection crossing ( 5.3 )	2D	Acceleration	8 vehicles; same initial conditions, with versus without major–minor-road differentiation (Figure 7 )	Assess road-priority effects on yielding and crossing

Table 1 : Numerical simulation scenarios.

Panel of Figure 1 — Figure 1 : Vehicle trajectories of the control-velocity model for $\beta=0$ (left) and $\beta=1$ (right)

Panel of Figure 2 — Figure 2 : Vehicle trajectories of the control-acceleration model for $\beta=0$ (left) and $\beta=1$ (right)

Panel of Figure 3 — Figure 3 : Vehicle trajectories and potential objective during training for the 30-vehicle control-velocity model.

Panel of Figure 4 — Figure 4 : Vehicle trajectories under acceleration-control without obstacle (left), with a small obstacle (middle), and with a large obstacle (right)

Vehicle	1	2	3	4	5	6	7	8	9
$\gamma_{i}$	0.115	0.117	0.095	0.395	0.319	0.347	1.805	2.235	2.353
$\tau_{i}$	10	10	10	3	3	3	0.5	0.5	0.5

Table 2 : Values of

\{\gamma_{i}\}_{i\in[9]}

and

\{\tau_{i}\}_{i\in[9]}

Panel of Figure 5 — Figure 5 : Vehicle trajectories of different types under control-velocity (left) and control-acceleration (right)

		Vehicle
Scaling	Metric	1	2	3	4	5	6	7	8	9
Before	Cost $J_{i}(\phi)$	5.336	3.774	1.458	4.974	3.830	4.736	11.168	16.183	11.832
Before	Relative exploitability (%)	64.679	49.945	12.646	18.740	22.354	23.210	3.640	0.008	0.009
After	Cost $J_{i}(\phi)$	1.637	1.712	1.642	5.258	4.497	7.148	8.930	13.070	13.290
After	Relative exploitability (%)	0.180	0.795	0.928	1.598	1.145	0.927	3.717	0.962	2.275

Table 3 : Exploitability before and after scaling.

Parameter	$k_{1}$	$k_{2}$	$k_{3}$	$k_{4}$	$k_{5}$	$k_{6}$	$k_{7}$	$k_{8}$	$k_{9}$	$q_{1}$	$q_{3}$	$c_{1}$	$c_{2}$	$d_{\mathrm{lat}}$
Value	10.0	0.1	1.0	8.0	100.0	20.0	1.0	5.0	10.0	0.1	50	0.5	1.5	0.9

Table 4 : Parameter values and initial conditions for the lane-changing experiments in Section 5.2 .

Panel of Figure 6 — Figure 6 : Lane changing in velocity control

Parameter	$q_{4}$	$q_{6}$	$q_{7}$	$q_{8}$	$q_{9}$	$q_{10}$
Value	0.1	1.0	10.0	10.0	5.0	10.0

Table 5 : Parameter values and initial conditions for the unsignalized intersection-crossing experiments.

Panel of Figure 7 — Figure 7 : Comparison of the intersection-crossing dynamics at four representative time instants. The top row shows the major–minor-road scenario, while the bottom row shows the scenario without major–minor-road differentiation. Vehicle colors indicate deviations from their target speeds.

Explore similar work

Agent-Based Evolutionary Dynamics for Mixed Autonomy Weaving Ramps
Sep 29, 2026Sheryl Paul, Kexin Wang, Ruolin Li +1Agent-Based Model Sewing
University of Southern California, Los Angeles, CA, USA.
Toward Cooperative Driving in Mixed Traffic: An Adaptive Potential Game-Based Approach with Field Test Verification
Apr 22, 2026Shiyu Fang, Xiaocong Zhao, Xuekai Liu +4Automated Vehicles Cooperation
Key Laboratory of Road and Traffic Engineering of the State, Ministry of Education, Tongji University, Shanghai, 201804, China · State Key Laboratory of Intelligent Green Vehicle and Mobility, Tsinghua University, Beijing, 100084, China · State Key Lab of Intelligent Transportation System, School of Transportation Science and Engineering, Beihang University, Beijing, 100191, China
A Real-Time Generalized Nash Equilibrium Framework for Interaction-Aware Autonomous Driving in Mixed Traffic
Jul 23, 2026Nouhed Naidja, Mohamed-Cherif Rahal, Steve Pechberti +3Automated Vehicles Autonomous Driving
L2S · Institut VEDECOM, Versailles, France · Laboratoire des Signaux et Syst`emes (L2S) +1

Sep 29, 2026, cs.MAJ/K move · Enter open · S save

Agent-Based Evolutionary Dynamics for Mixed Autonomy Weaving Ramps

Sheryl Paul, Kexin Wang, Ruolin Li, Jyotirmoy V. Deshmukh

University of Southern California, Los Angeles, CA, USA.

Agent-Based Model Sewing

Open paper AskPDF arXiv

Existing models of mixed-autonomy weaving ramps characterize how altruistic connected and automated vehicles (CAVs) can improve traffic efficiency at the population level, but provide limited insight into how such behavior emerges from decentralized vehicle interactions or how it is affected by finite populations, heterogeneous preferences, and imperfect information. We develop an agent-based model of a macroscopic weaving-ramp framework in which individual vehicles adapt their lane choices using an evolutionary game-theoretic update rule and altruism-based objectives providing a microscopic interpretation of the original Wardrop model. We prove convergence of the decentralized dynamics to the unique equilibrium predicted by the macroscopic theory. Beyond reproducing aggregate equilibrium behavior, the framework enables the study of deployment-level questions that cannot be addressed by static analysis. Simulation results demonstrate close agreement with the macroscopic predictions while revealing how convergence rates, adaptation to changing traffic conditions, heterogeneous altruism levels among CAVs, and imperfect state information influence system performance and the distribution of altruistic burden across vehicles. These results provide a bridge between equilibrium traffic theory and decentralized mixed-autonomy deployment.

Abstract

Explore similar work

Agent-Based Evolutionary Dynamics for Mixed Autonomy Weaving Ramps

Toward Cooperative Driving in Mixed Traffic: An Adaptive Potential Game-Based Approach with Field Test Verification

A Real-Time Generalized Nash Equilibrium Framework for Interaction-Aware Autonomous Driving in Mixed Traffic