Entropy Bounds for Local Coordination and Graph Amenability

Abstract

We study local pure coordination games on finite graphs. In these games, each vertex must choose one of two symmetric actions using only local information, and the cost is the average disagreement across edges. Hutchcroft, Rospuskova, and Tamuz showed that if such local coordination can be achieved with low cost, then the underlying graph must be amenable, or hyperfinite, but their quantitative bound has a square root loss. We improve this loss in the unbiased binary setting. The main idea is to associate with each player's local output a probability measure that records, along an ordered list of information sources, the mutual information with that output. For binary outputs, two players who usually agree have nearby associated measures, with a bound given by the binary entropy of their disagreement probability. Combining this estimate with a grand coupling theorem yields an improved amenability bound of order $\epsilon \log (1/\epsilon )$, where $\epsilon$ is the average disagreement. We also show that the square root loss in the earlier general theorem is essentially unavoidable for non-binary coordination profiles. Thus the binary assumption is not merely technical: it is what makes the improved entropy bound possible.