CS Paper Radar

Priority Coordination Games: Hodge Decomposition and a Sharp Design Limit

Zhihao Lin, Jianglin Lan, Anh-Tu Nguyen, Yoshinobu Kawahara

cs.GT cs.MA ·submitted 2026-10-05 05:35 UTC · v1

Abstract

In decentralised priority coordination, agents announce priority levels and a shared resource serves them in decreasing order, as at an unsignalised intersection; the levels form the decision layer of a hierarchical controller. Such interactions are routinely replaced by a potential game, i.e.\ by a common objective, for analysis and design. This paper determines what that surrogate misses, using the Hodge decomposition of the incentives into a potential component, which a common objective can represent, and a harmonic component, which it cannot. For the linear payoff, both components are obtained in closed form on every conflict graph and for every deterministic tie-breaking protocol: in common units, the harmonic energy is the number of conflicts and the potential energy adds the number of adjacent pairs of conflicts. Consequently, for every rationality parameter, the best common-objective model of the agents' choice log-odds, weighted uniformly over unilateral moves, has a relative squared error of at least $1/(d_{\max}+1)$, where $d_{\max}$ is the largest number of conflicts of one agent; for an eight-vehicle intersection it is exactly one fifth, for any number of priority levels. Invisible to strict-improvement dynamics, the missed component is, under low-rationality log-linear learning with uniform revision and to leading order, the stationary probability current, and its energy sets the entropy-production rate. Payoff design cannot remove it: on the complete conflict graph of $N$ agents, under a total-order protocol and with at least three priority levels, every nonconstant rank-based payoff leaves a relative error of at least $1/N$, with equality exactly for affine payoffs.

Closest papers

Nearest neighbours by meaning across the whole index.

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs

cs.MA ·2026-09-08 ·Xiangwu Wang, Chengwei Cao, Hongyuan Tang
theory similarity 0.60
Abstract · 15 pages, 4 figures, including references and appendices

Persistent communication limits force a multi-agent system to decide which agents may coordinate throughout a rollout. Current proximity alone is insufficient: separated agents may interact later, whereas a large pair reward may remain unreachable until it is heavily discounted. We introduce Reachability-Certified Subteam Decomposition (RCSD) for finite multi-agent Markov decision processes with factorized physical dynamics, finite-range ordered pair rewards, and almost-sure motion bounds. RCSD combines a speed-limit lower bound on pairwise contact time with a reward envelope to form a current-state affinity. For any capacity-valid persistent partition, the sum of cut affinities bounds the reward-deletion error of every unchanged stationary Markov state-feedback policy. A product of team-optimal policies for the resulting cut MDP incurs at most twice this certificate in regret against the centralized optimum. Both bounds are worst-case tight. On a controlled five-agent family, RCSD-Exact reduces aggregate normalized execution regret by 56.0%, 28.8%, and 25.3% relative to uniform, distance-only, and envelope-only partitions. A separate stochastic two-dimensional study finds no bound violation over 384 exact-partition and 1,440 restricted-controller evaluations. Exact four-agent evidence favors RCSD over uniform and distance-only grouping; raw evidence for current contact is borderline and envelope-only is unresolved. Across balanced 8-20-agent strata, controller-library utility is mixed: pointwise paired intervals favor RCSD over distance and current contact, include zero for uniform, and favor envelope-only and Value-MIP over RCSD. Partition construction remains subsecond in median up to 100 agents; this last result does not include affinity formation or MDP planning.

0.37

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

Individual Rationality in Constrained Hedonic Games: Friends, Enemies, and Neutrals

cs.GT ·2026-08-14 ·Šimon Schierreich, Ildikó Schlotter
publishedtheory similarity 0.60
Abstract

We study constrained coalition formation in games induced by friends, enemies, and neutrals, under the two standard refinements of additively separable preferences: friend-oriented and enemy-oriented. We ask for partitions that are individually rational (IR), while additionally requiring exactly $k$ non-empty coalitions, each satisfying a prescribed lower and upper bound on its size. Although IR alone is trivial to satisfy for any hedonic game, the size constraints make it computationally intractable to decide whether a feasible partition exists. The two models tell strikingly different stories. Under enemy-oriented preferences, the problem collapses to size-constrained graph coloring, and its complexity follows accordingly. Under friend-oriented preferences, however, the picture is far more intricate, and is governed by the enmity structure rather than the friendships. The complexity is further shaped by two factors: how strict the imposed size requirements are, and whether relationships are symmetric or asymmetric, with several cases turning out tractable in the symmetric setting but intractable once asymmetry is allowed. Charting this boundary in terms of both classical and parameterized complexity, we provide a complete understanding of which properties of the friend/enemy structure are responsible for hardness.

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

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

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

Fair Selection of Generalized Nash Equilibria: A Comparability Perspective

cs.GT eess.SYmath.OC ·2026-11-06 ·Sophie Hall, Heinrich H. Nax, Saverio Bolognani
published similarity 0.58
Abstract · Book chapter, 25 pages, 4 figures. To appear in Socio-Inspired and Socially Aware Control for Complex Systems, Springer

Generalized Nash equilibrium (GNE) problems model self-interested agents coupled through their costs and shared constraints, and arise throughout control applications that allocate a scarce common resource. Such problems typically admit a continuum of equilibria, so any implementation must \emph{select} one. This selection is not neutral: it decides how the cost of the shared constraint is distributed among the agents, a decision often expected to be fair. The variational GNE (v-GNE), which charges all agents a uniform shadow price, is the conventional choice and is frequently advocated as fair. Through the lens of \emph{comparability} from social choice theory, we show that the GNE set itself requires no inter-agent comparability of costs, whereas the v-GNE implicitly assumes cardinal unit comparability, one of the stronger notions. We then introduce the fair GNE (f-GNE), which selects an equilibrium by explicitly optimizing a fairness metric matched to the comparability at hand, and give constructive routes to compute it for single-constraint and linear-quadratic games. An electric-vehicle charging game serves as a running example throughout this self-contained tutorial.

0.52

Stability and Perfection in Constrained Weighted Network Games

cs.GT econ.TH ·2026-11-04 ·Julien Fixary, Rémi Castera, Rida Laraki
similarity 0.57
Abstract

We introduce a general framework of constrained weighted network formation in which agents allocate resources across coalitional interactions while facing feasibility constraints. More precisely, we allow arbitrary coalitions of agents to be assigned a continuous weight, and we incorporate both coalitional capacity constraints and individual budget constraints into the model. This framework extends the weighted network formation model of Bich and Morhaim by combining continuous interaction intensities with endogenous feasibility restrictions. Within this setting, we introduce a new notion of stability -- called coalitionwise stability -- extending pairwise stability to constrained network games. Under standard continuity and componentwise quasiconcavity assumptions on payoff functions, we establish the existence of coalitionwise stable networks. We then investigate refinements of stability inspired by the notion of perfect equilibrium introduced by Selten, and by the notion of perfect pairwise stability developed by Bich and Teteryatnikova for network games. The presence of feasibility constraints fundamentally alters the geometry of the feasible set, which no longer possesses a product structure. As a consequence, trembling-hand type refinements become substantially more delicate, since perturbations of some interactions may render other interactions infeasible. Nevertheless, we introduce constrained analogues of both the trembling-hand and perturbative notions of perfect stability considered by Bich and Teteryatnikova, and study their existence and their relationship. In particular, we show the equivalence between these trembling-hand and perturbative formulations under some componentwise monotonicity assumption.

0.21