Entropy Bounds for Local Coordination and Graph Amenability
Abstract
We study local coordination on finite graphs, equivalently, the ability of randomized local protocols with independent private randomness to produce highly correlated outputs at neighboring vertices. Hutchcroft, Rospuskova, and Tamuz (2026) showed that if such local coordination can be achieved with low cost, then the graph admits a low-cost leader profile, or equivalently an appropriate bounded-radius decomposition, with a square-root loss in the cost. We substantially improve this bound for unbiased binary outputs. If the average disagreement is ε, we construct a leader profile of cost O(εlog(1/ε)). The key ingredient is an information-theoretic influence measure: after fixing an ordering of the independent information sources, we assign to each binary output the increments of mutual information revealed along that ordering. For two outputs that disagree with probability p, the corresponding measures are within binary entropy h(p) in total variation. Combined with a grand coupling theorem, this yields the improved bound. We also show that a universal linear bound is impossible. We construct graphs with binary local profiles of cost O(ε) for which every leader profile has cost Ω (ε√(log(1/ε))). The construction uses weighted majority functions and can be implemented as an action-symmetric Nash equilibrium, giving a negative answer to the question of HRT whether leader equilibria are always optimal up to a constant factor. Finally, we show that the binary assumption is essential: for general real-valued outputs, the square-root dependence of the HRT theorem is sharp up to a universal constant.
Related
- Cayley-graph density of Thompson's group F: local deletions and finite-window bounds
- Local and Global Risk Bounds for Quantum Entropy Estimation under Projective-Design Measurements
- Physics-Informed Graph-Based Safe RL with Constraint-Specific Critics for Community Battery Coordination in Distribution Network
- Hermite-Fisher bounds and stability for min-entropy power inequalities
- Entropy and Translation Length in the Ray Graph
BibTeX
@misc{peretz2026entropy,
title = {{Entropy Bounds for Local Coordination and Graph Amenability}},
author = {Ron Peretz and Dean Kraizberg},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2606.01963},
eprint = {2606.01963},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.01963},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Entropy Bounds for Local Coordination and Graph Amenability
AU - Ron Peretz
AU - Dean Kraizberg
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2606.01963
UR - https://arxiv.org/abs/2606.01963
AB - We study local coordination on finite graphs, equivalently, the ability of randomized local protocols with independent private randomness to produce highly correlated outputs at neighboring vertices. Hutchcroft, Rospuskova, and Tamuz (2026) showed that if such local coordination can be achieved with low cost, then the graph admits a low-cost leader profile, or equivalently an appropriate bounded-radius decomposition, with a square-root loss in the cost. We substantially improve this bound for unbiased binary outputs. If the average disagreement is ε, we construct a leader profile of cost O(εlog(1/ε)). The key ingredient is an information-theoretic influence measure: after fixing an ordering of the independent information sources, we assign to each binary output the increments of mutual information revealed along that ordering. For two outputs that disagree with probability p, the corresponding measures are within binary entropy h(p) in total variation. Combined with a grand coupling theorem, this yields the improved bound. We also show that a universal linear bound is impossible. We construct graphs with binary local profiles of cost O(ε) for which every leader profile has cost Ω (ε√(log(1/ε))). The construction uses weighted majority functions and can be implemented as an action-symmetric Nash equilibrium, giving a negative answer to the question of HRT whether leader equilibria are always optimal up to a constant factor. Finally, we show that the binary assumption is essential: for general real-valued outputs, the square-root dependence of the HRT theorem is sharp up to a universal constant.
ER -