Improved Amenability Bounds for Local Coordination Games

Dean Kraizberg; Ron Peretz

arxiv: 2606.01963 · v2 · pith:BALH5VMBnew · submitted 2026-06-01 · 💻 cs.GT · cs.IT· math.IT· math.PR

Improved Amenability Bounds for Local Coordination Games

Ron Peretz , Dean Kraizberg This is my paper

Pith reviewed 2026-06-28 12:33 UTC · model grok-4.3

classification 💻 cs.GT cs.ITmath.ITmath.PR

keywords local coordination gamesgraph amenabilityShapley valuesmutual informationsocial networksdisagreement bounds

0 comments

The pith

If average disagreement is at most ε in a binary unbiased local coordination game, the underlying graph must be (O(ε log(1/ε)), r)-amenable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper improves a prior quantitative link between local coordination and graph structure. Previous results showed that low average disagreement forces the graph to be amenable, but with a square-root loss in the amenability parameter. The new argument replaces that loss with a nearly linear bound that includes only a logarithmic factor. The proof associates the players' local outputs with a mutual-information game and applies Shapley values to extract the improved dependence on ε.

Core claim

In the binary unbiased setting, if the average disagreement among players is at most ε, then the graph is (O(ε log(1/ε)), r)-amenable. This sharpens the earlier square-root loss while remaining inside the local pure coordination framework.

What carries the argument

Shapley values of a mutual-information game defined on the players' local outputs.

If this is right

The quantitative converse between local coordination efficiency and amenability becomes nearly linear instead of square-root.
Amenability parameters can now be bounded directly in terms of observed disagreement without the previous ε^{1/2} degradation.
The result continues to apply only inside the binary unbiased local pure coordination model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The Shapley-value technique might yield similar improvements if the unbiased or binary restrictions are later removed.
The same mutual-information game could be examined on infinite or random graphs to test whether the log factor is necessary.

Load-bearing premise

The bound holds only in the binary unbiased case and depends on the existing definitions of local pure coordination games.

What would settle it

A finite graph and a local coordination strategy whose average disagreement is ε yet whose amenability parameter exceeds any constant times ε log(1/ε).

Figures

Figures reproduced from arXiv: 2606.01963 by Dean Kraizberg, Ron Peretz.

read the original abstract

We study local pure coordination games on finite social networks, continuing the framework of Hutchcroft, Rospuskova, and Tamuz. They showed that low inefficiency in local coordination forces the underlying graph to be amenable, with a square-root loss in the amenability parameter. We improve this loss in the binary unbiased setting. Using Shapley values of a mutual-information game associated with the players' local outputs, we prove that if the average disagreement is at most $\varepsilon$, then the graph is $(O(\varepsilon\log(1/\varepsilon)),r)$-amenable. This gives a sharper quantitative converse between local coordination and graph amenability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This sharpens the amenability loss from square-root to O(ε log(1/ε)) via Shapley values on a mutual-information game, but stays inside the binary unbiased case and the prior Hutchcroft framework.

read the letter

The main takeaway is a concrete tightening of the quantitative link between low disagreement and amenability. Where the earlier result gave a square-root loss, this one gets O(ε log(1/ε)) by associating a mutual-information game to the players' local outputs and extracting the bound through Shapley values. That step is the actual novelty and it looks like a direct, non-circular application within the existing definitions.

The paper does what it sets out to do: it improves the loss term without introducing new free parameters or changing the game class. The argument stays faithful to the binary unbiased setting and the local pure coordination framework, so the advance is incremental but cleanly executed on its own terms.

The main limitation is the restriction to binary unbiased payoffs. Nothing in the abstract suggests the method extends immediately to other action spaces or biased cases, so the scope remains narrow. Soundness depends on the details of the Shapley-value calculation and the mutual-information construction; those steps are plausible from the high-level description but would need checking in the full proof for any overlooked dependencies.

This is for people already following quantitative results on amenability and coordination games on graphs. A specialist tracking the tightest bounds in that niche would find the log-factor improvement useful. Outside that group the paper does not open new directions or applications.

It is worth sending to peer review so the Shapley argument can be verified and the authors can clarify whether the technique has any room to generalize.

Referee Report

0 major / 2 minor

Summary. The manuscript improves the quantitative converse between inefficiency in local pure coordination games and graph amenability. Building on Hutchcroft, Rospuskova, and Tamuz, it shows that in the binary unbiased setting, average disagreement at most ε implies the graph is (O(ε log(1/ε)), r)-amenable. The proof associates a mutual-information game to the players' local outputs and applies Shapley values to obtain the sharper bound.

Significance. If the result holds, the sharper O(ε log(1/ε)) loss strengthens the link between local coordination and amenability, with potential implications for equilibrium analysis on networks. The application of Shapley values to a mutual-information game is a methodological contribution that may extend to other settings in algorithmic game theory.

minor comments (2)

[Abstract] Abstract: the phrase '(O(ε log(1/ε)),r)-amenable' uses r without a parenthetical reminder of its meaning; a one-sentence gloss would improve immediate readability even though the definition appears later.
[Introduction] The restriction to the binary unbiased case is stated clearly, but a short remark in the introduction on why the Shapley-value argument does not immediately extend would help readers assess the scope.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central derivation associates a mutual-information game with players' local outputs and applies Shapley values to obtain the improved O(ε log(1/ε)) amenability bound from average disagreement ≤ ε. This is an explicit mathematical argument that builds on the external Hutchcroft-Rospuskova-Tamuz framework for local pure coordination games and does not reduce any load-bearing step to a self-definition, fitted input renamed as prediction, or self-citation chain. The result is stated only for the binary unbiased case and presents an independent quantitative improvement rather than a tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is necessarily incomplete; no free parameters or invented entities are mentioned, and the sole explicit reliance is on the prior framework.

axioms (1)

domain assumption Definitions and framework of local pure coordination games from Hutchcroft, Rospuskova, and Tamuz
The paper explicitly continues their framework for the notions of disagreement, amenability, and the game setup.

pith-pipeline@v0.9.1-grok · 5629 in / 1191 out tokens · 33376 ms · 2026-06-28T12:33:13.324854+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 5 canonical work pages

[1]

Arxiv Preprint

Tom Hutchcroft, Olga Rospuskova, and Omer Tamuz.Local Coordination and the Geometry of Social Networks, 2026. Arxiv Preprint. url=https://arxiv.org/abs/2602.12571

Pith/arXiv arXiv 2026
[2]

Owen.Sobol’ Indices and Shapley Value

Art B. Owen.Sobol’ Indices and Shapley Value. SIAM/ASA Journal on Uncertainty Quantifi- cation, 2(1):245–251, 2014. doi=10.1137/130936233

work page doi:10.1137/130936233 2014
[3]

On shapley value for measur- ing importance of dependent inputs,

Art B. Owen and Cl´ ementine Prieur.On Shapley Value for Measuring Importance of De- pendent Inputs. SIAM/ASA Journal on Uncertainty Quantification, 5(1):986–1002, 2017. doi=10.1137/16M1097717. 9

work page doi:10.1137/16m1097717 2017
[4]

Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 56(4), 2020

Endre Cs´ oka, Viktor Harangi and B´ alint Vir´ ag.Entropy and expansion. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 56(4), 2020. doi=10.1214/19-aihp1044

work page doi:10.1214/19-aihp1044 2020
[5]

Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields.Journal of the ACM, 49(5):616–639, 2002

Jon Kleinberg and ´Eva Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields.Journal of the ACM, 49(5):616–639, 2002. doi=10.1145/585265.585268

work page doi:10.1145/585265.585268 2002
[6]

Arxiv Preprint

Omer Angel and Yinon Spinka.Pairwise Optimal Coupling of Multiple Random Variables, 2019. Arxiv Preprint. url=https://arxiv.org/abs/1903.00632

arXiv 2019
[7]

Cover and Joy A

Thomas M. Cover and Joy A. Thomas.Elements of Information Theory. Second edition. Wiley- Interscience, 2006

2006
[8]

Yeung.Information Theory and Network Coding

Raymond W. Yeung.Information Theory and Network Coding. Springer, 2008

2008
[9]

Shapley.A Value forn-Person Games

Lloyd S. Shapley.A Value forn-Person Games. In Harold W. Kuhn and Albert W. Tucker, editors,Contributions to the Theory of Games II, Annals of Mathematics Studies, Vol. 28, pp. 307–317. Princeton University Press, 1953

1953
[10]

Cambridge University Press, 2014

Ryan O’Donnell.Analysis of Boolean Functions. Cambridge University Press, 2014

2014
[11]

Peking University Press, 1993

Rong Long.Martingale Spaces and Inequalities. Peking University Press, 1993

1993
[12]

G. H. Hardy, J. E. Littlewood, and G. P´ olya.Inequalities. Second edition. Cambridge University Press, 1952

1952
[13]

D. L. Burkholder. Martingale Transforms.Annals of Mathematical Statistics, 37(6):1494–1504,
[14]

and Stigum, B

doi=10.1214/aoms/1177699141. Appendix Bound on the Total variation Distance of Shapley measures in Variance Game The proof of Theorem 2.5, presented in the previous section, relies on redefining the underlying TU game. This allows us to bypass the main obstacle arising from the variance game vX(S) = Var E[X|Z S] . we show here another proof of the improve...

work page doi:10.1214/aoms/1177699141

[1] [1]

Arxiv Preprint

Tom Hutchcroft, Olga Rospuskova, and Omer Tamuz.Local Coordination and the Geometry of Social Networks, 2026. Arxiv Preprint. url=https://arxiv.org/abs/2602.12571

Pith/arXiv arXiv 2026

[2] [2]

Owen.Sobol’ Indices and Shapley Value

Art B. Owen.Sobol’ Indices and Shapley Value. SIAM/ASA Journal on Uncertainty Quantifi- cation, 2(1):245–251, 2014. doi=10.1137/130936233

work page doi:10.1137/130936233 2014

[3] [3]

On shapley value for measur- ing importance of dependent inputs,

Art B. Owen and Cl´ ementine Prieur.On Shapley Value for Measuring Importance of De- pendent Inputs. SIAM/ASA Journal on Uncertainty Quantification, 5(1):986–1002, 2017. doi=10.1137/16M1097717. 9

work page doi:10.1137/16m1097717 2017

[4] [4]

Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 56(4), 2020

Endre Cs´ oka, Viktor Harangi and B´ alint Vir´ ag.Entropy and expansion. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 56(4), 2020. doi=10.1214/19-aihp1044

work page doi:10.1214/19-aihp1044 2020

[5] [5]

Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields.Journal of the ACM, 49(5):616–639, 2002

Jon Kleinberg and ´Eva Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields.Journal of the ACM, 49(5):616–639, 2002. doi=10.1145/585265.585268

work page doi:10.1145/585265.585268 2002

[6] [6]

Arxiv Preprint

Omer Angel and Yinon Spinka.Pairwise Optimal Coupling of Multiple Random Variables, 2019. Arxiv Preprint. url=https://arxiv.org/abs/1903.00632

arXiv 2019

[7] [7]

Cover and Joy A

Thomas M. Cover and Joy A. Thomas.Elements of Information Theory. Second edition. Wiley- Interscience, 2006

2006

[8] [8]

Yeung.Information Theory and Network Coding

Raymond W. Yeung.Information Theory and Network Coding. Springer, 2008

2008

[9] [9]

Shapley.A Value forn-Person Games

Lloyd S. Shapley.A Value forn-Person Games. In Harold W. Kuhn and Albert W. Tucker, editors,Contributions to the Theory of Games II, Annals of Mathematics Studies, Vol. 28, pp. 307–317. Princeton University Press, 1953

1953

[10] [10]

Cambridge University Press, 2014

Ryan O’Donnell.Analysis of Boolean Functions. Cambridge University Press, 2014

2014

[11] [11]

Peking University Press, 1993

Rong Long.Martingale Spaces and Inequalities. Peking University Press, 1993

1993

[12] [12]

G. H. Hardy, J. E. Littlewood, and G. P´ olya.Inequalities. Second edition. Cambridge University Press, 1952

1952

[13] [13]

D. L. Burkholder. Martingale Transforms.Annals of Mathematical Statistics, 37(6):1494–1504,

[14] [14]

and Stigum, B

doi=10.1214/aoms/1177699141. Appendix Bound on the Total variation Distance of Shapley measures in Variance Game The proof of Theorem 2.5, presented in the previous section, relies on redefining the underlying TU game. This allows us to bypass the main obstacle arising from the variance game vX(S) = Var E[X|Z S] . we show here another proof of the improve...

work page doi:10.1214/aoms/1177699141