PaperlayerView exact revision on arXiv

Source-linked AI summary

Priority Coordination Games: Hodge Decomposition and a Sharp Design Limit

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

arXiv:2610.05832v1cs.GTcs.MA

TL;DR

Potential games are routinely used to analyze and design priority coordination, but how much of the incentives such common-objective surrogates miss is rarely computed. The paper applies the Hodge decomposition to split incentive flows into a potential component representable by a common objective and a harmonic residual. For linear payoff f(r)=−r, both energies count conflicts and every β>0 surrogate misses at least 1/(dmax + 1) of incentive energy; the sharp design limit holds on complete graphs under total order for K≥3.

  • Problem

    Potential games are routinely used to analyze and design priority coordination, but how much of the incentives such common-objective surrogates miss is rarely computed.

    Source: §I · p. 1

  • Method

    The paper applies the Hodge decomposition to split incentive flows into a potential component representable by a common objective and a harmonic residual.

    Source: §I · p. 2

  • Results

    For linear payoff f(r)=−r, both energies count conflicts and every β>0 surrogate misses at least 1/(dmax + 1) of incentive energy; the sharp design limit holds on complete graphs under total order for K≥3.

    Source: §I · p. 2

  • Takeaways & Limitations

    The harmonic component is invisible to strict-improvement dynamics but gives the leading-order stationary current and entropy-production rate under low-rationality log-linear learning.

    Source: §I · p. 2

    The sharp payoff-design bound applies to complete conflict graphs under a total-order protocol with K≥3; it can fail for K=2 and at finite K off the complete graph.

    Source: §I · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

Priority levels determine service order in a conflict graph, forming a decision layer that is often modeled as a potential game. This paper measures what that common-objective surrogate misses and studies its consequences for learning and payoff design.

I. INTRODUCTION

  • Potential games support convergence analysis and explicit stationary distributions, but priority coordination is not potential once two agents conflict.When tied agents compete to go first, the gains around a closed cycle can sum to 2 rather than zero.Source: §I · p. 1
  • The paper asks how large the missed component is, what it does to behavior, and whether payoff design can remove it.The total number of waits is the same in every profile and for every payoff, so the design question concerns distance from a potential game rather than welfare.Source: §I · p. 2
  • The Hodge decomposition separates incentives into a component representable by a common objective and a circulating harmonic remainder.The squared harmonic norm is the smallest squared error of any potential surrogate.Source: §I · p. 2
  • For the linear payoff, harmonic energy counts conflicts and potential energy adds adjacent conflict pairs; the best common-objective model misses at least 1/(dmax+1) of incentive energy.The missed component is invisible to strict-improvement paths and equilibrium service order, but under low-rationality log-linear learning it determines the leading-order stationary current and entropy-production rate.Source: §I · p. 2
  • On complete conflict graphs with a total-order protocol and at least three levels, rank-based payoff design cannot reduce the relative error below 1/N, and affine payoffs attain that bound.The result is a limit on potential-game approximation, not a recommendation of the affine payoff.Source: §I · p. 2

A. Related Work

  • Prior work studies game decompositions, approximate potentials, and learning behavior, while this paper identifies closed-form energies, links the residual to learning, and gives a sharp payoff-design bound.The authors distinguish their result from welfare-oriented utility design and note that the potential share had previously been proposed as an empirical predictor.Source: A. Related Work · pp. 2–3

B. Organisation and Notation

  • The model uses an undirected conflict graph, discrete priority levels, and a tie-breaking orientation; each agent’s payoff depends on its conflict position, and affine rank payoffs yield pairwise games.The paper’s stated organization assigns the closed-form, behavior, and design questions to successive sections.Source: B. Organisation and Notation · p. 3, §II · p. 3, A. Pairwise Games on an… · p. 3

C. Flows and Hodge Decomposition

The Hodge decomposition represents unilateral payoff changes as a flow and separates the part explained by a potential from a harmonic residual. A number-operator lemma supplies a tractable route from payoff components to energies and the paper’s three questions.

C. Flows and Hodge Decomposition

  • A game’s flow records payoff changes under unilateral moves, and its unique orthogonal decomposition separates a potential gradient from a harmonic flow.The harmonic flow vanishes exactly when the game is an exact potential game.Source: C. Flows and Hodge Decomposition · p. 4

D. Problem Statement

  • Potential and harmonic energies are squared norms of the two components, with their normalized shares summarizing how incentives are divided.The paper studies closed forms, behavioral implications for improvement dynamics and log-linear learning, and the minimum harmonic share under specified design conditions.Source: C. Flows and Hodge Decomposition · p. 4, D. Problem Statement · p. 4

E. The Number-Operator Lemma

  • The number-operator lemma yields the Hodge potential by dividing each Hoeffding component by its order, enabling closed-form energy calculations.On the product game graph, the Laplacian multiplies an m-agent component by m; the potential and harmonic components are orthogonal.Source: E. The Number-Operator Lemma · p. 4

III. CLOSED-FORM ENERGIES OF PRIORITY COORDINATION

For pairwise games, the Hodge decomposition separates reciprocal interaction incentives from opposed ones. In priority coordination with a linear payoff, this structure gives closed-form potential and harmonic energies.

III. CLOSED-FORM ENERGIES OF PRIORITY COORDINATION

  • For priority coordination with linear payoff, the harmonic energy counts conflicts while potential energy adds adjacent pairs of conflicts.This is the section’s closed-form result for every conflict graph and deterministic protocol.Source: §III · p. 5

A. Symmetric and Antisymmetric Interactions

  • Each pairwise interaction splits into symmetric and antisymmetric parts under exchange of the agents.The symmetric part captures reciprocal effects; the antisymmetric part captures gains to one agent at the other’s expense.Source: A. Symmetric and Antisymmetric… · p. 5
  • Only the symmetric interaction component can be represented by a common objective that changes incentives in the same way for both agents.The proposition states the corresponding Hodge potential and harmonic flow in kernel form.Source: A. Symmetric and Antisymmetric… · p. 5
  • The proposition gives the potential and harmonic energies for pairwise games and characterizes exact potential games by symmetric interactions on every edge.The energies depend on the interaction kernels, with edge-local contributions.Source: A. Symmetric and Antisymmetric… · p. 5
  • The proof constructs the potential from centered own and interaction terms, then obtains the harmonic component by subtracting its flow from the payoff flow.Orthogonality is used to derive the energy expression.Source: A. Symmetric and Antisymmetric… · p. 5
  • The proof uses exchange invariance of the uniform measure to relate the two ordered interaction norms and derive the stated energy constants.The authors include the short proof because those constants are used throughout.Source: A. Symmetric and Antisymmetric… · p. 5

B. Priority Games: Every Interaction is Antisymmetric

For the linear priority game, every conflict contributes harmonic energy, while adjacent conflicts add potential energy. This graph-based split gives a lower bound on the error of any common-objective surrogate and remains informative about what pricing can and cannot change.

B. Priority Games: Every Interaction is Antisymmetric

  • Each conflict contributes one unit of harmonic energy, and each adjacent pair of conflicts adds potential energy: E_harm = |E| and E_pot = |E| + |E2|.The harmonic component is the antisymmetric interaction; the potential component also includes agents’ shared incentives to escalate.Source: B. Priority Games: Every Interaction… · pp. 5–6
  • For every β > 0, the best common-objective model has relative squared error at least 1/(d_max + 1), for every nonempty conflict graph and deterministic protocol.On a d-regular graph, ρ_pot = d/(d+1); on the complete graph, ρ_pot = (N − 1)/N.Source: B. Priority Games: Every Interaction… · pp. 5–6
  • The surrogate error weights every unilateral move equally; it measures incentive mismatch, not how often errors occur along a trajectory.At high rationality, play concentrates near equilibria, so an error weighted by visited profiles can be smaller.Source: B. Priority Games: Every Interaction… · p. 6
  • Pricing can change potential energy and the potential share, but it cannot change harmonic energy; separable level pricing therefore cannot eliminate the irreducible component.When harmonic energy is positive, pricing can move ρ_pot across [ρ_min, 1).Source: B. Priority Games: Every Interaction… · p. 6
  • For pairwise games, transfers that make the game an exact potential game must cancel the harmonic flow, and their flow energy is at least E_harm.The minimum is attained by the budget-balanced side payment described in Proposition 1(b), which level pricing cannot achieve.Source: B. Priority Games: Every Interaction… · p. 6
  • Neither energy predicts pure-strategy Nash equilibrium existence or efficiency, and pricing can alter behavior while leaving harmonic energy fixed.The total number of waits is constant across profiles.Source: B. Priority Games: Every Interaction… · p. 6

C. Reading a Single Move: Mean and Fluctuation

For a single move in the linear game, the potential part is the expected number of neighbours overtaken under uniformly random levels, and the harmonic part is the fluctuation from that mean. The resulting potential share does not depend on the number of priority levels.

C. Reading a Single Move: Mean and Fluctuation

  • For a move of length ℓ, the game flow is W, the number of neighbours overtaken, and its harmonic part is W − d_iℓ/K.The potential part is d_iℓ/K, the expected number overtaken when each neighbour’s level is uniform.Source: C. Reading a Single Move: Mean and… · p. 6
  • The number W of overtaken neighbours is distributed as Bin(d_i, ℓ/K); its mean is the potential part and its fluctuation is the harmonic part.The overtaking events are independent under the uniform reference measure.Source: C. Reading a Single Move: Mean and… · p. 6
  • The potential share of the linear game does not depend on K because substituting ℓ → K − ℓ maps one energy sum onto the other.With uniformly random tie-breaking, E_pot is unchanged and E_harm is multiplied by (K − 2)/(K + 1); for K = 2, the game is exact potential.Source: C. Reading a Single Move: Mean and… · p. 7

IV. DYNAMICS AND LEARNING

Strictly improving moves terminate, and under the index protocol all pure-strategy Nash equilibria yield the same service order. Under low-rationality log-linear learning, the harmonic component instead appears in stationary probability currents and entropy production.

IV. DYNAMICS AND LEARNING

  • Every strict improvement raises both generalized ordinal potentials, and every improvement path has length at most N(K − 1).This applies to every conflict graph, protocol, and strictly decreasing payoff-from-rank function.Source: §IV · p. 7
  • Under the index protocol, all pure-strategy Nash equilibria induce the same service order, though mixed equilibria are not considered.At equilibrium, every agent below the top level has a larger index than each of its neighbours.Source: §IV · p. 7

A. Log-linear Learning: Stationary Law and Current

  • As β → 0, the occupation measure is Gibbs in the Hodge potential to first order, while the leading-order probability current is the harmonic flow.For uniform revision, J_β = βh/(N K^(N+1)) + O(β²).Source: A. Log-linear Learning: Stationary Law… · p. 7
  • Under uniform revision, the leading-order entropy-production rate is proportional to harmonic energy, which is invisible in the occupation measure to first order.For the linear priority game, σ_β = β²(K² − 1)|E|/(6N K²) + O(β³).Source: A. Log-linear Learning: Stationary Law… · pp. 7–8
  • The low-rationality result describes the noise-dominated regime; for the intersection, its stationary-law approximation is about 10% accurate when β max_i d_i ≲ 1, based on one example.The paper gives no uniform accuracy bound or large-β theorem.Source: A. Log-linear Learning: Stationary Law… · p. 8

V. GENERAL PAYOFFS: THE HODGE SPECTRUM

For continuous priorities on the complete conflict graph, the paper turns payoff design into a spectral problem. The potential share is at most (N−1)/N for nonconstant payoffs, with equality exactly for affine payoffs.

V. GENERAL PAYOFFS: THE HODGE SPECTRUM

  • Payoff design becomes a Rayleigh-quotient problem in rank increments F, and the linear payoff is stationary at potential share (N−1)/N.The increments encode how much an agent loses when dropping one rank.Source: §V · p. 8
  • Higher-order interactions are relatively more harmonic because their contribution receives a decreasing potential-energy weight.The order-m form measures incentive structure carried by interactions involving m agents.Source: §V · p. 8
  • For continuous priorities, every nonconstant payoff has potential share ρpot(f) ≤ (N−1)/N, with equality iff f is affine.The potential share is the fraction of total incentive energy captured by the potential component.Source: §V · p. 9
  • For N = 8, potential share falls from 0.875 for the linear payoff to 0.860 for −r^2 and 0.647 for winner-take-all.The loss of potential share relative to the linear payoff is bounded by the payoff’s deviation from linearity.Source: §V · p. 9

VI. FINITELY MANY PRIORITY LEVELS

For finite priority levels, the complete-graph design limit holds for every K ≥ 3, while K = 2 is a genuine exception. Finite quantisation perturbs the continuous-priority spectrum, and the design limit also constrains low-rationality irreversibility.

VI. FINITELY MANY PRIORITY LEVELS

  • For K ≥ 3 on the complete conflict graph, every nonconstant rank payoff has potential share at most (N−1)/N, with equality iff it is affine.The bound cannot be extended to K = 2: for N = 7, a strictly decreasing payoff has potential share greater than 6/7.Source: §VI · p. 9
  • For K = 2 and N = 7, increments F = (9, 8, 6, 4, 2, 1) yield potential share 53454277/62354880, exceeding 6/7.The stated counterexample shows the K ≥ 3 hypothesis cannot be dropped.Source: §VI · pp. 9–10
  • The proof’s sharp level inequality has constant K−2, which cannot be improved and is the only step requiring K ≥ 3.The remaining matrix inequality is certified analytically or by exact symbolic computation and rational matrix factorisations, without floating-point computation.Source: §VI · p. 10
  • For the complete graph, finite-quantisation energy forms reduce to polynomials in K−2, and generalized eigenvalues equal λp + O(K−2).This uses protocol-reversal symmetry; without an automorphism reversing the protocol, odd powers of 1/K can occur.Source: §VI · p. 10
  • At low rationality, no rank payoff reduces learning’s leading-order irreversibility below the linear payoff; Corollary 5 extends the limit to every β > 0.The low-rationality statement is expressed relative to total incentive energy; the all-rationality limit requires no expansion in β.Source: §VI · p. 10

VII. NUMERICAL STUDY

The numerical study independently checks the closed forms, tests the predicted learning behavior, and compares layouts and payoff-design settings. Its results support the stated limits while showing where affine-payoff optimality can fail outside the complete-graph setting.

VII. NUMERICAL STUDY

  • The study enumerated profile spaces and computed Hodge components by sparse least-squares projection, while stationary laws, currents, and entropy production came from transition matrices.These computations did not enter any proof.Source: §VII · p. 11

A. Verification of the Closed Forms

  • On 24 conflict graphs, least-squares energies matched Proposition 2’s closed forms within 4 × 10−15; finite-K eigenvalues approached Theorem 1’s values at O(K−2).The largest eigenvalue in the N = 5 example was (N−1)/N for every tested K.Source: A. Verification of the Closed Forms · p. 11

B. Log-linear Learning

  • The predicted σβ/β²–harmonic-energy line matched 284 points across four game families within 1.2×10−3 relative deviation, including non-pairwise random games.On the intersection, the prediction ratio fell from 0.99 at β = 0.1 to 0.03 at β = 8 as pure-equilibrium mass rose from 10−3 to about 0.65.Source: B. Log-linear Learning · p. 11

C. Reading a Layout

  • The measured σβ/β² for four eight-agent layouts agreed with the leading-order prediction to five digits; each removed conflict lowers leading-order entropy production equally.The star and unprotected crossing have the same potential share, 4/5, yet the crossing has 16/7 times the entropy production.Source: C. Reading a Layout · pp. 11–12

D. Beyond the Complete Graph

  • Outside the complete graph, affine payoffs were slightly beaten at finite K: on K3,3, the best tested shares were 0.7635 at K = 3 and 0.7504 at K = 7, versus 3/4 for linear.On tested cycles the linear payoff was optimal; randomized tie-breaking on KN also allowed a higher share than linear.Source: D. Beyond the Complete Graph · p. 12

VIII. CONCLUSION

  • The conclusion identifies the central design limit: the missed energy is the conflict count, and the best common-objective model errs by at least 1/(dmax+1).The paper also reports that the affine-payoff extremality can fail off the complete graph and under randomized tie-breaking at finite K.Source: §VIII · p. 12

APPENDIX I PROOF OF THEOREM 1

The appendices develop the continuous and finite-quantisation proofs through orthogonal-polynomial analysis and a staged positivity argument. For the finite case, the proof reduces the payoff form to bond variables, establishes positivity for K≥3, and identifies its kernel.

APPENDIX I PROOF OF THEOREM 1

  • Orthogonal-polynomial compatibility drives the continuous proof: binomial averaging yields Legendre polynomials, while differencing and the kernel operator lead to weighted Jacobi polynomials.The Jacobi polynomials are orthogonal under the weight associated with the kernel operator.Source: Appendix I · p. 12

B. Stage 1: splitting by interaction order

  • Every interaction order m≥3 contributes a positive-semidefinite form, leaving the two-body form as the remaining positivity problem.The higher-order argument does not depend on the payoff function.Source: B. Stage 1: splitting by interaction… · p. 13

C. Stage 2: reduction to bond variables

  • The two-body form is rewritten in bond vectors defined on a larger space than the vectors generated by payoffs, enabling positivity to be proved on that larger space.The kernel is transferred back to the payoff function after the reduction.Source: C. Stage 2: reduction to bond variables · p. 13

D. Stage 3: the level inequality

  • A sharp level inequality with constant K−2 compensates the negative term bond by bond; this is the only proof step requiring K≥3.The constant cannot be improved, and at K=2 the inequality gives no margin.Source: D. Stage 3: the level inequality · p. 14

E. Stage 4: the Perron argument and three branches

  • The final matrix condition is proved analytically for K≥5 and by exact symbolic or rational certificates for the remaining finite cases.For K=4, root isolation establishes the condition for N≥10; for K=3, the stated argument covers N≥17 before exact certificates settle remaining pairs.Source: E. Stage 4: the Perron argument and… · p. 14

F. Assembly

  • For K≥3 and N≥3, the assembled proof establishes QK ⪰0 and identifies its kernel as the constant vectors; the K=2 counterexample is verified exactly.For N=2, the result follows separately from the linear-payoff null-vector result.Source: F. Assembly · p. 14

Supplementary Material for

  • The supplementary proof distinguishes hand arguments, symbolic identities, and exact rational certificates; no proof depends on floating-point computation.The supplementary roadmap identifies steps, their uses, and how they are verified.Source: Supplementary Material for · pp. 16–17, Appendix S · p. 17

B. Step 1: proof of Lemma 2 (exact eigenvector)

The proof first shows that the linear payoff is an exact null vector of the quadratic form, then handles higher interaction orders and reduces the remaining two-body problem to bond vectors. The reduction also identifies affine payoffs through the bond-vector kernel.

B. Step 1: proof of Lemma 2 (exact eigenvector)

  • For every N≥2 and K≥2, the linear payoff is an exact null vector of QK, a fact used in the theorem’s kernel statement and certificates.The identity relies on conditional independence of opponents’ service events and the fact that positions form a permutation.Source: B. Step 1: proof of Lemma 2 (exact… · pp. 18–19

C. Step 2: proof of Proposition S5 (higher orders)

D. Step 3: bond vectors and the two-body reduction (first part of Proposition S10)

  • The two-body form becomes a quadratic form in bond vectors on a larger space, and its kernel transfers back to the payoff: it is affine exactly when the bond vectors are constant.This two-body reduction applies for every N≥2 and K≥2, although Theorem 2 requires K≥3.Source: D. Step 3: bond vectors and the… · pp. 20, 22

E. Step 4: the sum-of-squares identity

The sum-of-squares identity rewrites the bond form into nonnegative pieces plus a residual term, while the kernel argument shows that vanishing of Sq forces all bond vectors to be the same constant vector.

E. Step 4: the sum-of-squares identity

F. Step 5: the kernel of Sq

  • For N≥3 and K≥2, Sq(D)=0 forces every bond vector Dk to equal the same constant vector.All three groups of squares are needed to eliminate the remaining endpoint freedoms.Source: F. Step 5: the kernel of Sq · p. 24

G. Step 6: the sharp level inequality

The section establishes a sharp level inequality for K ≥ 3 and develops bond-coordinate positivity conditions used to prove nonnegativity across priority-level branches.

G. Step 6: the sharp level inequality

H. Step 7: a lower bound in the bond vectors alone, and step coordinates

  • Step coordinates express covariances through bond vectors and a fixed bond matrix, reducing positivity to a quadratic form on the bond space.The bond matrix uses the path Green's function gb(k,l).Source: H. Step 7: a lower bound in the bond… · p. 25

I. Step 8: a Perron argument in the space of bonds

  • If condition (T) holds on every bond, BN,K is positive semidefinite; strictness on at least one bond gives kernel span(1 ⊗ 1).The proof uses a Perron argument on the bond-space matrix.Source: §I · p. 26

J. Step 9: the branch K ≥5

  • For K ≥ 5 and (N-2)(K-4) ≥ 4, BN,K is positive semidefinite with kernel span(1 ⊗ 1).This covers N ≥ 6 for K = 5, N ≥ 4 for K = 6 or 7, and N ≥ 3 for K ≥ 8; the simpler bound does not suffice for K = 4 or K = 3.Source: J. Step 9: the branch K ≥5 · p. 26

K. Step 10: the branch K = 4 (computer-assisted root isolation)

The remaining level-count branches combine root isolation and exact certificates to establish positivity, while identifying the binary-priority boundary where the result fails.

K. Step 10: the branch K = 4 (computer-assisted root isolation)

  • For K = 4 and N ≥ 10, BN,4 is positive semidefinite with kernel span(1 ⊗ 1).For 3 ≤ N ≤ 9, condition (T) fails at some bond even with the exact eigenvalue bound; those cases are settled by exact certificates.Source: K. Step 10: the branch K = 4… · p. 27

L. Step 11: the branch K = 3 (computer-assisted)

  • For K = 3 and N ≥ 17, BN,3 is positive semidefinite with kernel span(1 ⊗ 1).For N ≤ 16 the bond form is indefinite on the full bond space but positive on the image needed for Theorem 2, so finite cases require separate treatment.Source: L. Step 11: the branch K = 3… · pp. 28–29

M. Step 12: the finitely many remaining cases (exact certificates)

N. Step 13: assembly, the case N = 2, and K = 2

O. The reciprocity law: proof of Proposition 7

The reciprocity argument characterizes how finite-level forms relate to continuous-priority forms, while the appendix derives a tie-pattern law for harmonic energy.

O. The reciprocity law: proof of Proposition 7

  • The forms are polynomials in 1/K of degree at most 2N-1, with constant term equal to the continuous-priority form, and reversal of protocol gives m≺(-x) = m≺rev(x).For protocols reversed by a graph automorphism, the expansion is instead a polynomial in K^-2; these claims concern forms, not eigenvalues, which are analytic near the continuum limit with corrections O(K^-2).Source: O. The reciprocity law: proof of… · pp. 30–31
  • The reciprocity proof assumes a total-order protocol and does not cover directed cycles or randomized tie-breaking.The appendix is independent of the earlier proof of Theorem 2 and describes finite-level deviations from continuum forms.Source: O. The reciprocity law: proof of… · pp. 30–31

APPENDIX S-B THE HARMONIC COMPONENT OF THE LINEAR GAME: TIE-PATTERN LAW AND RANDOMISED TIE-BREAKING

  • Averaging over a uniformly random tie-breaking order makes conditional harmonic energy an explicit linear function of the full tie pattern.On the complete graph with the index protocol, its conditional expectation given the number of tied pairs is affine; on other graphs, conditioning only on tied conflict edges can miss the full pattern.Source: Appendix S · pp. 31, 32, 34

A. Randomised tie-breaking

Uniform random tie-breaking preserves the potential energy but scales the harmonic energy by a factor that vanishes for two priority levels. The appendix relates this effect to the antisymmetric comparison and develops the energy and projection tools used for continuous priorities.

A. Randomised tie-breaking

  • (K −2)/(K + 1) multiplies Eharm under uniform random tie-breaking, while Epot remains as in Proposition 2; the game is an exact potential game iff K = 2.The deterministic protocol amplifies the harmonic component without creating it.Source: A. Randomised tie-breaking · p. 34
  • Antisymmetry of the comparison creates the harmonic component, while deterministic tie resolution adds to it; the tie-breaking factor vanishes at K = 2.At K = 2, random resolution of ties is a coin flip with no residual interaction.Source: A. Randomised tie-breaking · p. 34

A. Setting

  • With iid uniform continuous priorities, each agent’s payoff is f of its position, and the Hodge projection is the inverse number operator on mean-zero functions.The operator multiplies order-m components by m.Source: A. Setting · p. 35

B. The two energies (eq. (21) of the main text)

APPENDIX S-D PRICED PRIORITIES

Pricing can change equilibrium existence and learning-related quantities while leaving harmonic energy unchanged. The appendix gives equilibrium conditions, reports an eight-vehicle intersection scan, and describes exact-arithmetic checks of the proof.

APPENDIX S-D PRICED PRIORITIES

  • On a d-regular graph, c = d/K makes the game purely harmonic and uniform mixing a Nash equilibrium; for 0 < c < 1 and E ≠ ∅, no pure Nash equilibrium exists.The all-zero profile is a Nash equilibrium iff c ≥ maxi bi.Source: Appendix S · p. 37
  • Pricing can leave Eharm unchanged while pure equilibria disappear and reappear; on a triangle with cyclic protocol and K = 2, everyone bidding 1 is an equilibrium for every c < 1.The appendix notes that equilibrium existence is not predicted by either energy.Source: Appendix S · pp. 37–38
  • On the eight-vehicle intersection, the potential share moves from 4/5 at c = 0 to 0 at c = 4/3 and 0.96 at c = 4.5, while harmonic energy stays constant to 10−14.At β max |∆u| = 0.02, entropy production stays within 3 × 10−5 of the Proposition 6 prediction.Source: Appendix S · p. 38

APPENDIX S-E REPRODUCIBILITY AND INDEPENDENT AUDIT

  • Theorem 2’s proof uses computer assistance at three steps only; the remaining steps and Appendices S-B–S-D are proved by hand, with exact-arithmetic scripts and independent checks.The end-to-end check bypasses the proof and certifies Theorem 2 for a given pair; at K = 2 it reports positivity through N = 6 and failure at N = 7.Source: Appendix S · p. 38
Loading 2610.05832v1…