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

Sep 29, 2026cs.MA

Agent-Based Evolutionary Dynamics for Mixed Autonomy Weaving Ramps

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.

Sheryl Paul, Kexin Wang, Ruolin Li +1

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

Agent-Based Model Sewing

Ask PDF

Apr 22, 2026cs.RO

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

Connected autonomous vehicles (CAVs), which represent a significant advancement in autonomous driving technology, have the potential to greatly increase traffic safety and efficiency through cooperative decision-making. However, existing methods often overlook the individual needs and heterogeneity of cooperative participants, making it difficult to transfer them to environments where they coexist with human-driven vehicles (HDVs).To address this challenge, this paper proposes an adaptive potential game (APG) cooperative driving framework. First, the system utility function is established on the basis of a general form of individual utility and its monotonic relationship, allowing for the simultaneous optimization of both individual and system objectives. Second, the Shapley value is introduced to compute each vehicle's marginal utility within the system, allowing its varying impact to be quantified. Finally, the HDV preference estimation is dynamically refined by continuously comparing the observed HDV behavior with the APG's estimated actions, leading to improvements in overall system safety and efficiency. Ablation studies demonstrate that adaptively updating Shapley values and HDV preference estimation significantly improve cooperation success rates in mixed traffic. Comparative experiments further highlight the APG's advantages in terms of safety and efficiency over other cooperative methods. Moreover, the applicability of the approach to real-world scenarios was validated through field tests.

Shiyu Fang, Xiaocong Zhao, Xuekai Liu +4

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

Automated Vehicles Cooperation Agentic Optimization

Ask PDF

Jul 23, 2026cs.RO

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

Safe and efficient navigation in mixed-traffic environments remains a critical challenge for Autonomous Vehicles (AVs), primarily due to the complex interdependence between the AV's decisions and the unpredictable reactions of human drivers. This paper introduces a comprehensive decision-making framework that formulates the driving interaction as a Generalized Nash Equilibrium Problem (GNEP). Unlike decoupled optimization approaches, this framework explicitly models shared safety and geometric constraints, ensuring that the feasibility of the AV's strategy is dynamically linked to the opponent's actions. To solve this non-convex problem in real-time, we propose a dedicated solver based on Particle Swarm Optimization (PSO). The complete architecture was validated on a test track using a real autonomous Renault Zoé interacting with a human driver. Experimental results demonstrate the system's ability to handle critical scenarios by generating comfortable, human-like trajectories. Benchmarks confirm the solver's operational feasibility, achieving convergence in under 50 ms.

Nouhed Naidja, Mohamed-Cherif Rahal, Steve Pechberti +3

L2S · Institut VEDECOM, Versailles, France · Laboratoire des Signaux et Syst`emes (L2S) +1

Automated Vehicles Autonomous Driving Traffic Mechanics Particle Swarm Optimization Nash Equilibrium+1

Ask PDF