CS Paper Radar

Coverage-Aware Routing with Approximate Equilibrium Guarantees for Location-Diversity Vehicular Crowdsensing

Luis G. Jaimes, Ayesha S. Dina

cs.GT ·submitted 2026-11-11 17:51 UTC · v1

Abstract

Vehicular crowdsensing uses the sensors of everyday vehicles to monitor cities, but traffic concentrates on few roads, leaving much of the network unsensed. Location-diversity incentives pay vehicles more to travel where few others go, but our earlier mechanism sets how far each vehicle deviates without optimizing collective coverage in route selection. We add this step in two stages. First, a non-cooperative game with diversity-weighted rewards yields each vehicle's equilibrium deviation. Second, the platform recommends to each vehicle a feasible route whose deviation is within a tolerance of this value, chosen to improve coverage. The coverage gain is monotone submodular, so a greedy router with local search attains at least half of the optimal gain over generated candidates. If every active vehicle has a candidate within a tolerance that is small relative to the aggregate deviation, the recommended routes form an $\varepsilon$-Nash equilibrium, with $\varepsilon$ first order in the tolerance, or second order under a stronger condition. On London and Monaco road networks, the router achieves 99.4% and 98.9% of the optimal reduction in the coverage penalty on small instances and exceeds closest-length selection by up to 27.9 points. Under heterogeneous costs, uniform deviation needs compensation averaging 42% of the budget to give every vehicle nonnegative utility; the equilibrium targets need almost none. They also yield more coverage per unit of added travel in most settings and up to 22.6 more points at small budgets, an advantage that depends on placement and reverses at large budgets, where detour limits bind.

Closest papers

Nearest neighbours by meaning across the whole index.

Fragmented Obedient Equilibria in Routing Games

cs.GT ·2026-10-29 ·Zhengyang Wang, Achilleas Anastasopoulos
similarity 0.64
Abstract

We study routing games in which competing mediators recommend routes to fixed nonatomic populations. Each mediator chooses a randomized flow allocation to minimize its population's expected travel cost, subject to users having no conditional expected gain above a tolerance $ε$ from disregarding their recommendations. We define a fragmented obedient equilibrium (FOE) by combining user obedience with mediator optimality, and establish existence under a lower-hemicontinuity assumption on the obedient policy correspondences. Under affine edge latencies and independent mediator sampling, we derive an exact reformulation in first and second flow moments that preserves best responses and equilibrium profiles. Every feasible moment pair admits a finitely supported realizing policy. When the network has at most four routes, each mediator's best-response problem is an exact semidefinite program. A numerical illustration on the Braess network shows that relaxing obedience can reduce FOE costs, while gaps relative to the social optimum and optimal obedient pooling can persist.

0.23

Competitive mediator games and urban CAV routing markets

cs.GT cs.MAecon.THmath.OC ·2026-08-10 ·Grzegorz Jamróz
survey similarity 0.63
Abstract · 42 pages, 6 figures, 1 table

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.

0.38

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

cs.GT math.OCcs.MA ·2026-09-30 ·Anran Hu, Zhexin Wang, Yufei Zhang, Xuan Di
similarity 0.63
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.

0.18

Collective Autonomous Vehicle Routing Needs Social Awareness for Coexistence with Human Drivers

cs.MA cs.AI ·2026-10-09 ·Anastasia Psarou, Mikolaj Rams, Blazej Torbus, Rafal Kucharski
similarity 0.63
Abstract

Collective Autonomous Vehicle (AV) route choices in real-world traffic networks can create externalities for Human-Driven Vehicles (HDVs), as routes that benefit AVs may increase travel times for other road users. To address this, we introduce a social component, the marginal cost, to the selfish travel time AV reward. Marginal cost captures an AV's impact on other road users by comparing their travel times with those in a counterfactual simulation in which the AV is removed. We study AV route choice in mixed-autonomy traffic settings using Multi-Agent Reinforcement Learning (MARL), where AVs learn routing policies through repeated interactions with the traffic environment. Experiments on the real-world networks of Ingolstadt and Provins show that incorporating marginal cost into the AV reward not only limits the increase in HDV travel times and shortens AV travel times relative to selfish AV routing, but also improves overall system performance. In Ingolstadt, selfish routing of 40\% AVs increases the travel times of other vehicles by 1.7\%, and this drops to 1.1\% when the social reward is included. Interestingly, not only does overall system performance improve, but the AVs are also better off when acting socially.This effect is consistent across tested cities, penetration rates, and replications, yet when the weight of the social component in the reward increases, the system fails to reach the desired performance. For a more scalable approach to social AV routing in mixed-autonomy traffic, we compute the marginal cost only for the AVs whose route choices most affect the traffic system. This reduces the number of counterfactual simulations and achieves similar performance at a significantly lower computational cost. Our results suggest that AV routing should go beyond selfish rewards and, for the benefit of all traffic participants, include a social component in its objective.

0.29

On the Fragility of Worst-Case Nash Equilibria in Atomic Congestion Games

cs.GT ·2026-09-10 ·Colton Hill, Brandon Collins, Philip N. Brown
similarity 0.62
Abstract

Aggregate performance in smart mobility systems depends heavily on the emergent behavior of selfish, resource-sharing agents that participate within the systems. As a result, recent work has focused on how a system designer can leverage incentives to influence behavior so that system cost (e.g., traffic congestion) is minimized. These results show that worst-case equilibria can be quite inefficient compared to system-optimal allocations. However, it is unclear to what extent agents are ``satisfied'' with their decisions in these worst-case scenarios. We demonstrate that in any incentivized atomic congestion game, agents' aggregate satisfaction at equilibrium (relative to their actions in an optimal allocation) is correlated with the efficiency of the corresponding system cost, in the sense that if agents are very satisfied with their equilibrium choices, the equilibrium must be relatively efficient. Further, we show that worst-case Nash equilibria are fragile, as every agent is indifferent between their action in a worst-case equilibrium and their action in a system-optimal allocation. In summary, at equilibrium, either agents are highly satisfied with their decisions or their decisions are highly inefficient, but both cannot be true simultaneously. This work adds to recent results for other classes of games which indicate that worst-case equilibrium efficiency guarantees only occur when agents are indifferent about their decisions.

0.27

How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?

cs.GT cs.AIcs.DSmath.OC ·2026-10-31 ·Yu Cheng, Tianle Jiang
similarity 0.62
Abstract

We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost. We compare the social costs of $ε$-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-$d$ polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any $ε$-NE, with matching instances for every $ε$. For small $ε$, the largest possible relative reduction and increase in general congestion games are both $Θ(\sqrt{dε})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $Θ(hε)$, while the largest possible relative increase is known to be $ε$. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.

0.13

Sharing the Road: LLM-Based Bargaining in Mixed-Autonomy Traffic

cs.MA ·2026-11-06 ·Lingxiao Zhou, Di Chen, Jia Li
similarity 0.59
Abstract

Mixed-autonomy traffic involves heterogeneous driving populations competing for shared road space. Previous studies have shown the existence and emergence of collective rationality using game-theoretic and reinforcement learning approaches, which rely on explicitly specified behavioral assumptions or reward functions for driving agents. However, how bargaining behaviors between driving agents evolve and lead to collective outcomes based on richer agent characteristics and language-based reasoning remains less understood. To fill this gap, we develop a bargaining framework based on large language models (LLMs) in which population-level autonomous vehicle (AV) and human-driven vehicle (HV) agents negotiate road-space allocations under heterogeneous objectives and private information. Through controlled experiments varying traffic composition, agent objectives, and traffic-domain knowledge, we examine bargaining behavior, coordination, and resource utilization. Results show that negotiated allocations respond to relative traffic density without strictly following proportional sharing, while density-balanced states exhibit greater coordination difficulty. Fairness-oriented objectives substantially improve agreement rates but do not necessarily yield equally high road-space utilization. Furthermore, domain knowledge affects bargaining outcomes differently across objective configurations, shaping both coordination and the role-dependent effects of fairness. These findings demonstrate the potential of LLM-based bargaining for modeling and designing interactions among driving agents in mixed-autonomy traffic.

0.04

Agent-Based Evolutionary Dynamics for Mixed Autonomy Weaving Ramps

cs.MA ·2026-09-29 ·Sheryl Paul, Kexin Wang, Ruolin Li, Jyotirmoy V. Deshmukh
theory similarity 0.58
Abstract · 6 pages, 9 figures. Accepted for publication at the 6th IFAC Workshop on Cyber-Physical Human Systems (CPHS 2026), December 11-12, 2026, Red…

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.

0.42