Organizations: Jagiellonian University, Faculty of Mathematics and Informatics, Kraków, Poland · École polytechnique, Institut Polytechnique de Paris, Palaiseau, France
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).
Figure 2: Illustration of the club dynamics graph GI 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
g0
g1
g5
g6
g7
gˉ
State
x0
-27
-58
-59
-59
-51
-48.3
NE
\mathds1{1,5,6}
-77
-52
-52
-57
-59
-56.6
\mathds1{1,5,6,7}
-77
-52
-53
-57
-52
-55.8
\mathds1{0,1,5,6,7}
-53
-53
-53
-57
-71
-55.1
\mathds1{0,1,5,6}
-53
-53
-53
-57
-60
-54.4
\mathds1{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 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 q1thr = 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 q1thr AVs choose Route 1, and the y-axis represents the green-light duration when q1thr or more AVs choose Route 1.
Figure 5: Travel times of 10 CAVs in NE x0 (a) and in four considered club compositions \mathds1{1,5,6},\mathds1{1,5,6,7},\mathds1{0,1,5,6,7},\mathds1{0,1,5,6},\mathds1{0,1,5,6},13 (b-f). Travel times are normalized across the 5 plots, such that the travel time of all players in x0 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 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 x0 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.
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.
Grzegorz Jamróz, Łukasz Gorczyca, Rafał Kucharski
Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Inspired by possible future markets of autonomous routing and driving (ARAD), we introduce competitive mediator games and their equilibria which generalize the (coarse) correlated equilibria, which have become a popular research area recently as they not only can be more socially efficient than Nash equilibria but also are limits of algorithmic no-regret multi-agent learning dynamics. We discuss the basic properties of competitive mediator games and prove that in the generic setting of anonymous congestion(routing) games with market-share maximizing mediators all competitive mediator equilibria are monopolies whenever one of the mediators is weakly preferred to other mediators by all users. We apply and interpret these results in the context of new markets of competing ARAD service providers. We also provide a comprehensive overview of these markets and discuss the future mechanism design thereof.
Grzegorz Jamróz
Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
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.