Priority Coordination Games: Hodge Decomposition and a Sharp Design Limit

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

cs.GTOct 5, 2026

Priority Coordination Games: Hodge Decomposition and a Sharp Design Limit

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

Organizations: Graduate School of Information Science and Technology, The University of Osaka, Suita, Osaka 565-0871, Japan · James Watt School of Engineering, University of Glasgow, Glasgow G12 8QQ, United Kingdom · LAMIH UMR CNRS 8201 Laboratory, Université Polytechnique Hauts-de-France, 59313 Valenciennes, France · INSA Hauts-de-France, 59313 Valenciennes, France · RIKEN Center for Advanced Intelligence Project, Tokyo 103-0027, Japan

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.

Figures & tables

Panel of Figure 1 — Fig. 1: The smallest priority game: two conflicting agents, levels $\{0,1\}$ , agent $0$ served first on a tie. Vertices are profiles $s_{0}s_{1}$ ; arrows are unilateral raises, labelled with the mover’s payoff gain. (a) The game flow; (b) its potential part (blue), the common incentive to raise one’s level; (c) its harmonic part (red), a circulation recording who goes first.

Fig. 2: Running example. (a) Eight vehicles at a two-lane intersection: A1–A4 turn left from the inner lanes (solid), A5–A8 go straight on the outer lanes (dashed); circles mark the

16

pairwise crossings of the nominal paths. (b) The resulting conflict graph; arrows show the index protocol (on a tie, tail first).

Fig. 3: Closed forms against independent computation. (a) Energies of Proposition 2 against a least-squares Hodge projection. (b) Finite-

K

spectrum against Theorem 1 .

Fig. 4: Log-linear learning (Proposition 6 ), computed from the transition matrix. (a) Occupation, on

C_{5}

(

K=3

): distance between the stationary law and the Gibbs law of a Hodge potential. (b) Circulation: stationary current against the harmonic flow on every edge of the game graph of the intersection. (c) Irreversibility: entropy production against harmonic energy for four families of games; the line is the prediction, without fitted parameters; the random games are not pairwise. (d) Range of validity on the intersection: the low-

\beta

law gives way to the ordinal regime, in which mass shifts towards the set of pure-strategy Nash equilibria of Proposition 5 without being absorbed by it.

Layout	$\|E\|$	$\|E_{2}\|$	$\mathcal{E}_{\mathrm{pot}}$	$\rho_{\mathrm{pot}}$	$\sigma_{\beta}/\beta^{2}$
Fully channelised (matching)	$4$	$0$	$4$	$1/2$	$0.0741$
Single merge cycle $C_{8}$	$8$	$8$	$16$	$2/3$	$0.1481$
One arbiter (star)	$7$	$21$	$28$	$4/5$	$0.1296$
Unprotected crossing (Example 1 )	$16$	$48$	$64$	$4/5$	$0.2963$

TABLE I: Four layouts for eight agents,

K=3

. Energies in units of

2c_{K}

;

\sigma_{\beta}/\beta^{2}

measured at

\beta\max_{i}d_{i}=0.02

Figure 7

Figure 8

Figure 9

Figure 10

Fig. S1: Logical structure of the supplementary material. Boxes are the fourteen steps of the proof of Theorem 2 (Appendix S-A ); arrows point from a step to the steps that use it, and the horizontal collector above Step S-A.14 gathers everything the assembly needs: the higher orders (Step S-A.3 ), the kernel of

\mathrm{Sq}

(Step S-A.6 ), the three branches (Steps S-A.10 – S-A.12 ) and the certificates (Step S-A.13 ), which together cover every pair

(K,N)

with

K\geq 3

; Step S-A.2 feeds both the kernel statement and the image certificates. Dashed boxes are the three computer-assisted steps; all computations are exact. Section S-A.15 and Appendices S-B – S-D are independent of the proof and of one another, except that Appendix S-C uses the conservation law of Step S-A.1 .

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

$K$	all large $N$	bond-space cert.	image cert.
$3$	$N\geq 17$	–	$4\leq N\leq 16^{\ast}$
$4$	$N\geq 10$	$5\leq N\leq 9$	$N=3,4$
$5$	$N\geq 6$	$N=4,5$	$N=3$
$6,7$	$N\geq 4$	$N=3$	–
$\geq 8$	$N\geq 3$	–	–

Appendix

TABLE II: Coverage of Theorem 2 for

K\geq 3

N\geq 3

: by the large-

N

branch of Appendix B-E or by an exact rational certificate.

Step	proves	used in	verified by
S-A.1	Laplacian $\operatorname{div}\delta=K\mathsf{N}$ , conservation, order decomposition $Q_{K}=K^{N+1}\sum_{m}Q^{(m)}_{K}$ (Lemmas S1 – S3 )	every later step	by hand
S-A.2	$Q_{K}\mathbf{1}=0$ : the linear payoff is an exact null vector (Lemma 2 )	kernel statement, Step S-A.14	by hand
S-A.3	$\\|\sum_{i\in T}[u_{i}]_{T}\\|^{2}\leq 2\sum_{i}\\|[u_{i}]_{T}\\|^{2}$ , hence $Q^{(m)}_{K}\succeq 0$ for $m\geq 3$ (Proposition S5 , Lemma S6 )	reduces the theorem to $Q^{(1)}+Q^{(2)}\succeq 0$	by hand
S-A.4	bond vectors $\hat{D}_{k}(f)$ ; first- and second-order components in bond form (Propositions S8 , S9 ); $Q^{(1)}+Q^{(2)}=\mathfrak{B}_{N,K}(\hat{D}(f))$ (Proposition S10 ); injectivity on affine $f$ (Lemma S11 )	Steps S-A.5 – S-A.13 work on $\mathfrak{B}$ alone	by hand
S-A.5	Hahn–Poincaré and spread identities; the sum-of-squares identity $K^{2}\mathfrak{B}=\sum_{k}Z_{k}+\mathrm{Sq}-\mathrm{Neg}$ (Theorem S14 )	Steps S-A.6 – S-A.12	by hand
S-A.6	$\mathrm{Sq}(D)=0$ iff $D\in\operatorname{span}(\mathbf{1}\otimes\mathbf{1})$ (Lemma S15 )	kernel statement, Step S-A.14	by hand

Appendix

TABLE S1: Roadmap of the proof of Theorem 2 . “exact” means rational or symbolic arithmetic.

$K$	all large $N$	bond-space certificate	image certificate	direct
$3$	$N\geq 17$ (Thm. S32 )	–	$4\leq N\leq 16$	$N=3$
$4$	$N\geq 10$ (Thm. S26 )	$5\leq N\leq 9$	$N=3,4$	–
$5$	$N\geq 6$ (Thm. S24 )	$N=4,5$	$N=3$	–
$6,7$	$N\geq 4$ (Thm. S24 )	$N=3$	–	–
$\geq 8$	$N\geq 3$ (Thm. S24 )	–	–	–

Appendix

TABLE S2: Coverage of

\{(K,N):K\geq 3,\ N\geq 3\}

. No pair is left uncovered. The first column is analytic for

K\geq 5

(Theorem S24 ) and rests on exact symbolic computation for

K=4

and

K=3

(Steps S-A.11 – S-A.12 ).

$N$	$K=2$	$K=3$	$K=4$	$K=5$	$K=6$	$K=7$	$K=8$
3	$+.167$	$+.296$	$+.342$	$+.363$	$+.374$	$+.381$	$+.385$
4	$+.075$	$+.216$	$+.267$	$+.291$	$+.304$	$+.311$	$+.317$
5	$+.033$	$+.169$	$+.219$	$+.243$	$+.256$	$+.264$	$+.269$
6	$+.011$	$+.138$	$+.186$	$+.209$	$+.221$	$+.229$	$+.234$
7	$\mathbf{-.001}$	$+.116$	$+.161$	$+.183$	$+.195$	$+.202$	$+.207$
8	$\mathbf{-.009}$	$+.100$	$+.142$	$+.163$	$+.174$	$+.181$	$+.185$

Appendix

TABLE S3: Margin

\frac{N-1}{N}-\max_{f}\rho_{\mathrm{pot}}(f)

over non-affine payoff-from-rank functions

f

K_{N}

, computed in floating point from the pencil

(M_{\mathrm{pot}},M_{\mathrm{tot}})

(not part of any proof). When positive it is the gap

\lambda_{1}-\lambda_{2}

between the two largest generalised eigenvalues, and as

K\to\infty

it tends to

\lambda_{1}-\lambda_{2}=\frac{2}{N+2}

of Theorem 1 . The entries at

K=2

N\geq 7

(bold) are negative, in agreement with the exact witness at

N=7

; blank cells were not computed.

Fig. S2: The tie-pattern law against exhaustive enumeration (floating point; not part of any proof). (a) Complete graph, index protocol:

\mathbb{E}[H\mid A]

against the number

A

of tied pairs (points) and the affine law of Corollary S37 (lines). (b)

C_{4}

P_{4}

S_{4}

K=3

: the order-averaged energy

\mathbb{E}[\bar{H}\mid\mathcal{A}_{C}]

lies on the line of slope one given by ( S32 ); conditioning on tied conflict edges alone (

C_{4}

, grey, shifted for display) is not affine.

script	step	establishes
verify_certificates.py + certificates/ ( $25$ files)	S-A.13	the pairs of Table S2 : rebuilds each certified matrix from Theorem S14 and Step S-A.4 , checks $LDL^{\top}=A$ with positive pivots and the kernel; standard library only, imports nothing
audit_K4.py	S-A.11	the cubic of Lemma S25 , exact root counting for $\varrho\geq\varrho_{0}$ , and (T) for all bonds iff $N\geq 10$ (Theorem S26 ); also audits the hand-proved closed forms of Steps S-A.8 – S-A.9
k3_representation_proof.py , s1_closed.py , check_blocks.py , verify_M_symbolic.py	S-A.12	Lemmas S27 , S29 and S31 : the block representation, the closed forms of its entries, the row sums $\mathsf{M}\mathbf{1}$ , and the certificates for $N=17,18$
k2_witness.py	S-A.14	the $K=2$ , $N=7$ witness from the definition of the Hodge projection; $Q_{2}\mathbf{1}=0$ ; the sign change between $N=6$ and $N=7$
end_to_end.py	–	Theorem 2 for $K=3$ , $N\leq 7$ ; $K=4$ , $N\leq 5$ ; $K=5$ , $N\leq 4$ ; $K=6,7$ , $N=3$ , using no step of the proof (see below)

Appendix

TABLE S4: Scripts on which the proof of Theorem 2 depends, and the two independent checks.

Explore similar work

Sep 14, 2026cs.GT

Deriving the Pure Price of Anarchy for Networked Resource Allocation Games

This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.

Vartika Singh, Philip N. Brown

University of Colorado Colorado Springs, Colorado Springs, CO, 80918 USA · Politecnico di Torino, Italy

Game Theory Utility Maximization Submodular Functions Multi-Agent Coordination Prices Anonymization

Ask PDF

Jul 19, 2026cs.MA

The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination

The problem of fair multi-agent coordination in decentralized settings is one of the most pressing challenges for building efficient collaborative systems. Resource allocation is based on optimized collective arrangements accounting for agents' needs. Such coordination should not only be computationally efficient but also account for fairness, i.e., equitable redistribution of costs incurred by all agents. Recent literature has proposed several algorithms that efficiently determine optimal plan combinations balancing system-wide efficiency and individual discomfort of agents in a centralized setting. However, these works do not address equitable resource optimization in fully decentralized scenarios, specifically, the optimized redistribution of discomfort among coordinating agents so that none experiences a discomfort level that could lead to loss of incentive or polarization that can disrupt planned operations. In this work, we study the problem of optimizing three objectives: (i) system-wide efficiency, (ii) individuals' comfort and (iii) fairness (i.e., balancing of incurred discomfort costs) in decentralized multi-agent coordination. We design a novel model to optimize those three orthogonal objectives, without any substantial increase in communication and computational overhead. Through experiments on two real-world datasets, we validate the model and demonstrate that it can achieve fairer optimization outcomes, while satisfying agents' preferences and system goals.

Jovan Nikolic, Maciej Krzysztof Zuziak, Evangelos Pournaras

Google, Zurich, 8002 Zurich, Switzerland. · School of Computer Science, University of Leeds, Leeds, UK. · School of Energy Systems, LUT University, 53850 Lappeenranta, Finland

Multi-Agent Coordination Decentralized Autonomous Organization Decentralized Optimization Coordination Algorithmic Fairness

Ask PDF

Sep 30, 2026math.OC

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

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.

Anran Hu, Zhexin Wang, Yufei Zhang +1

Department of Industrial Engineering and Operations Research, Columbia University · Department of Mathematics, Imperial College London, London, UK · Department of Civil Engineering and Engineering Mechanics, Data Science Institute, Columbia University

Decentralized Autonomous Organization

Ask PDF

Abstract

Explore similar work

Deriving the Pure Price of Anarchy for Networked Resource Allocation Games

The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordination

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

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