CS Paper Radar

Fragmented Obedient Equilibria in Routing Games

Zhengyang Wang, Achilleas Anastasopoulos

cs.GT ·submitted 2026-10-29 02:44 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Competitive mediator games and urban CAV routing markets

cs.GT cs.MAecon.THmath.OC ·2026-08-10 ·Grzegorz Jamróz
survey similarity 0.66
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

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

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

Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents

cs.GT cs.CCcs.DS ·2026-09-16 ·Paul W. Goldberg, Alexandros Hollender, Giannis Tyrovolas
theory similarity 0.61
Abstract

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

0.19

Strategy recovery for Mean-Payoff Games is as hard as solving them from scratch

cs.GT cs.DS ·2026-10-18 ·Dani Dorfman, Uri Zwick
published similarity 0.61
Abstract · To appear in SOSA 2027

Mean-Payoff Games (MPGs) form an interesting family of deterministic, infinite-duration, zero-sum, turn-based games played by two players on a finite weighted directed graph. The goal of the players is to minimize, respectively maximize, the $\textit{limiting average}$ of the costs of the edges on an infinite path constructed by the two players. The complexity of solving MPGs is a long-standing open question. The decision problem associated with these games is known to be in $\text{NP}\cap \text{co-NP}$, and even $\text{UP}\cap \text{co-UP}$, yet the problem is not known to be in $\text{P}$. This is one of the simplest combinatorial problems with such a status. A full solution of an MPG gives the $\textit{value}$ of each vertex of the game, along with a pair of $\textit{optimal strategies}$ for the two players. (Each player has a succinct $\textit{positional}$ optimal strategy.) The problem of finding optimal strategies for the players given the values of all vertices is known as the $\textit{strategy recovery}$ problem. We describe a simple reduction from the problem of solving MPGs to the strategy recovery problem for MPGs. This shows that the strategy recovery problem for MPGs is essentially as hard as solving MPGs from scratch, i.e., without knowing the values. The reduction uses simple $\textit{game transformations}$ and simple $\textit{self-reducibility}$ and $\textit{peeling}$ arguments. This answers a question of Andersson and Miltersen. Mamino obtained a similar result for $\textit{stochastic}$ games with a limiting average objective, but his technique does not extend to deterministic games such as MPGs. We go one step further and show that finding an optimal strategy for one of the players of an MPG remains hard even if an optimal strategy of the second player, and hence all the values, are known.

0.19

A Resource Allocation Tournament

cs.GT math.OCecon.TH ·2026-10-22 ·Adam Nathaniel, Refael Hassin
similarity 0.61
Abstract

We introduce and analyze a round-robin simultaneous resource allocation contest, motivated by sports leagues and other competitive environments where agents must distribute limited resources across multiple encounters. Players allocate resources in advance to matches against all opponents, and match outcomes are determined by relative allocations. We study two payoff schemes: total points, where players accumulate rewards for each win, and winner-takes-all, where only the tournament winner is rewarded. For three players, we provide complete equilibrium characterizations under both schemes. For four or more players, we show that the total points payoff admits Blotto-type equilibria, while the winner-takes-all payoff requires numerical and algorithmic analysis. To address this, we develop a best-response dynamics algorithm with stochastic inertia and use it to approximate equilibria in games with four and five players.

0.26

Scaling Chance-Constrained Correlated Equilibrium Computation for Exclusive Resource-Assignment Games

cs.GT ·2026-09-11 ·Jaehan Im, Ufuk Topcu, David Fridovich-Keil
similarity 0.60
Abstract

The chance-constrained correlated equilibrium concept provides a robust coordination technique for self-interested agents whose costs are uncertain to a central coordinator, but the number of joint actions considered in its computation grows exponentially with the number of agents. We propose an exact-one resource-assignment restriction for games in which agents compete for shared resources and simultaneous use of a resource is undesirable or unsafe. The restriction allows each resource to be assigned to exactly one agent, reducing the number of joint actions considered from O(2^(nr)) to O(n^r) for n agents and r resources. The resulting problem is solved over the restricted joint action set while retaining all incentive constraints associated with unilateral deviations. We show that the feasible set of the restricted problem is exactly the convex hull of the chance-constrained pure Nash equilibria contained in the exact-one assignment set, yielding a necessary and sufficient condition for nonemptiness. We further derive a sufficient condition under which all chance-constrained pure Nash equilibria of the unrestricted game are retained by the restriction. Numerical experiments in a vertiport departure-corridor coordination scenario demonstrate a 99.81% reduction in median computation time relative to the unrestricted formulation while achieving equivalent coordination performance.

0.31