CS Paper Radar

Competitive mediator games and urban CAV routing markets

Grzegorz Jamróz

cs.GT cs.MAecon.THmath.OC ·submitted 2026-08-10 17:42 UTC · v1
survey

Abstract

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.

Comment
42 pages, 6 figures, 1 table

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.66
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

Multi-Agent Reinforcement Learning in Markets with Congestion

cs.GT ·2026-09-13 ·Qixuan Zai, Randall Berry
similarity 0.65
Abstract

This paper investigates multi-agent reinforcement learning (MARL) in settings where firms compete for customers using congestible resources. We consider Bertrand competition in which firms compete by announcing prices and customers choose among firms based on both price and congestion. The relationship between price, congestion and the quantity of customers willing to accept service is governed by an unknown inverse demand curve, which firms must learn through experience. Each firm is modeled as a self-interested learning agent that chooses its price to maximize profit. A growing literature has shown that independently learning MARL agents can develop tacitly collusive behavior. We examine how such behavior emerges in markets with congestible resources. Our results provide insight into how learning dynamics, state representation, and strategic interaction jointly shape competition, with implications for both economic learning and the design of learning-enabled markets.

0.31

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

cs.GT ·2026-11-11 ·Luis G. Jaimes, Ayesha S. Dina
similarity 0.63
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.

0.22

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.62
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

Learning-Augmented Coordination Mechanisms

cs.GT ·2026-10-27 ·George Christodoulou, Vasilis Christoforidis, Alkmini Sgouritsa, Ioannis Vlachos
top venue similarity 0.62
Abstract · This paper has been accepted to the 40th Conference on Neural Information Processing Systems (NeurIPS 2026). Abstract abridged due to arXiv …

The inefficiency of decentralized resource allocation is classically measured by the Price of Anarchy (PoA) and the Price of Stability (PoS). The most widely studied and foundational class of these models are atomic and non-atomic congestion games, for which a robust theory quantifying the inefficiency of equilibria is well-established. To mitigate the effects of selfish behavior, we employ Coordination Mechanisms, which modify resource costs to incentivize socially improved equilibria. However, standard Coordination Mechanisms assume unknown, adversarial demand, restricting positive results mainly to specialized networks such as parallel links. We address this limitation by studying learning-augmented coordination mechanisms, where the mechanism is endowed with a potentially inaccurate prediction of the demand. We study general atomic and non-atomic congestion games with polynomial latency functions of degree $d$. Our main positive result is a learning-augmented coordination mechanism tuned by a confidence parameter $β$ which achieves a "best of both worlds" type of result: approximately optimal performance for an accurate prediction without sacrificing the worst-case guarantee of a good equilibrium (PoS). We further establish bounds on PoA-Robustness (worst equilibrium performance under cost modification). Our construction relies on transforming approximate equilibria of the original game into exact equilibria of the modified game using an approximate potential function. We complement our positive results with impossibility results. We first show that requiring all equilibria to have optimal social cost under an accurate prediction precludes bounded robustness. We also show a strong error tolerance limit in non-atomic games: even infinitesimal prediction errors can cause the performance of a mechanism with optimal consistency to revert to the original PoA.

0.30

Decentralized Optimal Equilibrium Learning Over Dynamic Networks

cs.GT cs.AIcs.LG ·2026-09-13 ·Seref Taha Kiremitci, Muhammed O. Sayin
published similarity 0.61
Abstract · Extended version of S. T. Kiremitci and M. O. Sayin, "Decentralized optimal equilibrium learning over dynamic networks," to appear in the Pr…

This paper studies decentralized learning of socially optimal equilibria in finite normal-form games over dynamic communication networks. Each agent observes only its own realized payoffs, does not know the game a priori, and can communicate only with time-varying neighbors using low-bandwidth messages. We propose networked decentralized optimal equilibrium learning dynamics in which agents generate randomized semantic content/discontent signals from local payoff comparisons and exchange time-stamped time-stacked tables rather than raw actions, payoff information or local estimates/parameters. The method combines table fusion with temporal majority reconstruction to mitigate dynamic communication while preserving fully decentralized operation. We establish finite-time logarithmic regret guarantees, with an in-phase exploration perturbation, for optimal equilibrium selection under utilitarian and proportional-fair social welfare objectives. Simulation results further show that the proposed approach can effectively select socially desirable equilibria over dynamic communication networks.

0.23

Learning and Steering in Incomplete-Information Games

cs.GT cs.AIcs.LGeess.SY+1 ·2026-11-05 ·Asrın Efe Yorulmaz, Tamer Başar
similarity 0.61
Abstract · 57 pages, 5 figures

In many modern multi-agent systems, a mediator seeks to influence strategic decision dynamics using only outcome-level feedback and without knowing agents' utilities. In this work, we study how a mediator can learn an unknown game and steer adaptive agents toward outcomes that maximize her utility using only trajectory feedback. The mediator knows the game form and her own objective, but not the agents' utilities. Moreover, she commits to nonnegative payments and provides recommendations and contexts, but receives only a single realized terminal outcome rather than full-information feedback. We develop halving-type algorithms that learn utility differences in normal-form games and conditional continuation-value differences in extensive-form games, achieving a sample complexity of $\widetilde O(\varepsilon^{-2})$ that matches worst-case lower bounds up to logarithmic factors. We then combine these learning procedures with a Lagrangian formulation in an online Learn-Compute-Steer algorithm that interleaves learning, equilibrium computation, and steering toward mediator-optimal extensive-form correlated equilibria (EFCE). With high probability, the Learn-Compute-Steer algorithm achieves a directness gap and an optimality gap of $\widetilde O(T^{-1/4})$, while time-average payments are of $\widetilde O(T^{-1/8})$.

0.23

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.61
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