Equilibria in routing games with connected autonomous vehicles may not be strong, as exclusive clubs may form

Anastasia Psarou; Natello Descormier; Rafał Kucharski

cs.GTOct 14, 2025

Equilibria in routing games with connected autonomous vehicles may not be strong, as exclusive clubs may form

Authors: Anastasia Psarou, Natello Descormier, Rafał Kucharski

Organizations: Jagiellonian University, Faculty of Mathematics and Informatics, Kraków, Poland · École polytechnique, Institut Polytechnique de Paris, Palaiseau, France

Abstract

User Equilibrium (UE) is the standard representation of the so-called routing game in which drivers adjust their route choices to arrive at their destinations as fast as possible. Asking whether UE is strong has, so far, been meaningless for human drivers, who do not form coalitions because of technical and behavioral constraints. Here, we demonstrate that this will not necessarily hold for Connected Autonomous Vehicles (CAVs), which can communicate and collaborate to form routing coalitions by exploiting adaptive signal control. Within game-theoretical formulations of Nash Equilibria, we provide a methodological framework and report the novel phenomena through a carefully designed toy-network example, in which we identify so-called clubs emerging in different CAV penetration rates and adaptive traffic-light configurations. We detail one such club where three CAVs deviate from the UE and benefit (arrive faster). The formation of such a club has negative consequences for other users (who are not invited to join and must now travel longer) and for the system (making it suboptimal and disequilibrated), thereby triggering adaptation dynamics. These findings raise questions about equity in future mixed-autonomy traffic systems.

Figures & tables

Figure 1: CAV coalition formation. In our demonstration, we depart from User Equilibrium (top left) on a simple Two Route Network, where each driver decides to go straight (Route 0), as traveling Route 1 would be slower for each of them. When 10 out of 15 vehicles become autonomous vehicles, they reconsider their choices. None of them would benefit by individually deviating to Route 1 (bottom left); however, vehicles 1, 5, and 6 discover that by deviating together, they can arrive faster (bottom center). Not only on average, but also individually. This benefit for the few invited club members is at the cost of other users and system performance (bottom right).

Panel of Figure 2 — Figure 2: Illustration of the club dynamics graph $\mathcal{G}^{I}$ with $I=\{1,5\}$ , from which two coalitions are identified using Algorithm 1 . Either player 1 or 5 can act as the leader and identify that forming the club $I=\{1,5\}$ would reduce their travel times. In the first branch, players 0 and 4 are consequently invited to deviate, resulting in the terminal coalition $\{0,1,5,4\}$ , which corresponds to a Strong Nash equilibrium. In the second branch, player 6 is invited to join, and the club $I=\{1,5,6\}$ is formed. Then, both players 0 and 7 would like to join it, given that it is formed (eq. 5 ). However, when both of them join, it is no longer attractive to player number 7. This leads to a single terminal node, the coalition $\{0,1,5,6\}$ . Subsequently, in both formed coalitions, HDV 13 may adapt and improve their travel time by individually deviating. After joining, both coalitions remain stable.

Figure 3: SUMO snapshot of the traffic network employed in this work. The deviating club traveling on Route 1 is shown in red.

$x$	$g_{0}$	$g_{1}$	$g_{5}$	$g_{6}$	$g_{7}$	$\bar{g}$	State
$x^{0}$	-27	-58	-59	-59	-51	-48.3	$NE$
$\mathds{1}_{\{1,5,6\}}$	-77	-52	-52	-57	-59	-56.6
$\mathds{1}_{\{1,5,6,7\}}$	-77	-52	-53	-57	-52	-55.8
$\mathds{1}_{\{0,1,5,6,7\}}$	-53	-53	-53	-57	-71	-55.1
$\mathds{1}_{\{0,1,5,6\}}$	-53	-53	-53	-57	-60	-54.4
$\mathds{1}_{\{0,1,5,6\},13}$	-54	-57	-52	-56	-60	-59.9	stable

Table 1: Payoffs for selected joint actions. Shaded entries correspond to club members. The column

\bar{g}

reports the average payoff over all 10 CAVs.

Figure 4: Clubs are identified (red markers) in a total of 244 cases under different combinations of adaptive green-phase durations of adaptive traffic lights, two CAV penetration rates of 66.6% (15 players, 10 CAVs, 5 HDVs) and 43.5% (23 players, 10 CAVs, 13 HDVs), and two adaptive threshold values

q_{1}^{\mathrm{thr}}

= 2 and 3. This suggests that club formation is not an isolated occurrence but may arise under a range of traffic conditions and adaptive traffic light settings. The x-axis represents the green-light duration when fewer than

q_{1}^{\mathrm{thr}}

AVs choose Route 1, and the y-axis represents the green-light duration when

q_{1}^{\mathrm{thr}}

or more AVs choose Route 1.

Figure 5: Travel times of 10 CAVs in NE

x^{0}

(a) and in four considered club compositions

\mathds{1}_{\{1,5,6\}},\mathds{1}_{\{1,5,6,7\}},\mathds{1}_{\{0,1,5,6,7\}},\mathds{1}_{\{0,1,5,6\}},\mathds{1}_{\{0,1,5,6\},13}

(b-f). Travel times are normalized across the 5 plots, such that the travel time of all players in

x^{0}

is 1. Black (respectively red) arrows show how much time each player would lose (respectively gain) by changing route unilaterally from a given joint action. The absence of red arrows is therefore equivalent to the joint action being a Nash equilibrium (a), (e), and (f). Club members (deviating to Route 1) are marked with white circles, and those not invited (remaining at Route 0) with black ones. Blue arrows connect cases where a player can gain time by changing route unilaterally to the state resulting from this change (vertices of graph

\mathcal{G}

Figure 6: System-wide average travel times. a) Travel times (payoffs) experienced by various groups of players (HDVs, CAVs, and all) before (left) and after coalition

\{1,5,6\}

is formed (right). b) Average travel times experienced on respective routes. Values normalized to travel times in UE.

Figure 7: System states across various joint actions. Each dot denotes a joint action and its coordinates are the average travel times on Route 0 (x-axis) and Route 1 (y-axis), normalized such that the travel time of all vehicles in $x^{0}$ is 1. The pink diagonal represents equal travel times on both routes. On panel a) dots are colored proportionally to the split of vehicles between routes. On panel b), colors denote various equilibrium states: red when it is not Nash, yellow for Nash, and green for strong Nash. We identified several joint actions where we can identify a club (marked with black circles on b); however, some of the joint actions were not in Nash Equilibrium (red), including clubs $\{1,5\},\{1,5,6\},\{1,5,6,7\},\{0,1,5,6,7\}$ and only two actions were Strong Nash (green), corresponding to clubs $\{0,1,5,6\},\{0,1,5,4\}$

Figure 8: Changes in HDV travel times when they deviate to Route 1 after the coalition

\{0,1,5,6\}

is formed. Only HDV 13 gains by switching to Route 1. The rest of the HDVs have increased travel times when they deviate alone to Route 1.

Nash Equilibrium

Nash equilibrium studies stable strategy profiles in which no player can benefit by changing their action alone.

See all 62 papers

Randomized routing strategies of fleets of CAVs may prove market efficient
Jul 16, 2026Grzegorz Jamróz, Łukasz Gorczyca, Rafał KucharskiIntelligent Transportation Systems Vehicle Routing
Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Competitive mediator games and urban CAV routing markets
Aug 10, 2026Grzegorz JamrózMechanism Design Game Theory
Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Agent-Based Evolutionary Dynamics for Mixed Autonomy Weaving Ramps
Sep 29, 2026Sheryl Paul, Kexin Wang, Ruolin Li +1Intelligent Transportation Systems Agent-Based Modeling
University of Southern California, Los Angeles, CA, USA.

Jul 16, 2026J/K move · Enter open · S save

Randomized routing strategies of fleets of CAVs may prove market efficient

Grzegorz Jamróz, Łukasz Gorczyca, Rafał Kucharski

Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland

Intelligent Transportation Systems Vehicle Routing Autonomous Driving Planning

Open paper AskPDF arXiv

In future cities every driver may own a vehicle which could be either independently driven (HDV), or autonomously routed and piloted (CAV). The autonomous operations could be handled by a few competing companies. What is the market structure which would make this market aligned with city goals? In this paper we discuss a variant of the emerging market of collectively routed fleets of CAVs, where revenue for fleet operators is proportional to market share. We provide benchmark scenarios to compare the routing algorithms. We present several routing algorithms and demonstrate that, when the attitudes of human drivers towards CAVs exhibit significant diversity, randomised CAV routing, resulting in unpredictable travel times for HDVs, is more efficient than routing proportional to system optimum/user equilibrium. Based on this, we propose to improve the design of the market by augmenting the market-share objective with mean systemwide travel time in order to limit antisocial randomised strategies of fleet operators and drive the competition towards social welfare oriented cooperation.

Abstract

Nash Equilibrium

Explore similar work

Randomized routing strategies of fleets of CAVs may prove market efficient

Competitive mediator games and urban CAV routing markets

Agent-Based Evolutionary Dynamics for Mixed Autonomy Weaving Ramps