Improved Amenability Bounds for Local Coordination Games

Ron Peretz, Dean Kraizberg · 2026

Read Improved Amenability Bounds for Local Coordination Games by Ron Peretz, Dean Kraizberg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01963.txt.

Introduction

Peretz and Kraizberg sharpen entropy bounds for local coordination on graphs. In these games, each vertex picks one of two actions. Only local information can guide that choice. Cost is the average disagreement across edges. Past work tied low cost to graph amenability. Its quantitative bound lost a square root factor.

The pair improve that loss in the unbiased binary case. Each player's output gets an associated probability measure. The measure records mutual information along ordered sources. Two players who mostly agree have nearby measures. The gap is bounded by binary entropy of disagreement. A grand coupling theorem joins these estimates. The improved amenability bound is of order epsilon log. Coordination limits thus reflect graph structure more tightly.

Catalog record

CREATORRon Peretz, Dean Kraizberg
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01963

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improved Amenability Bounds for Local Coordination Games Ron Peretz, Dean Kraizberg Abstract We study local pure coordination games on finite social networks, continuing the framework of Hutchcroft, Rospuskova, and Tamuz [ 1 ] . 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 ⁡ ( ε ​ log ⁡ ( 1 / ε ) ) , r ) (O(\varepsilon\log(1/\varepsilon)),r) -amenable. This gives a sharper quantitative converse between local coordination and graph amenability. Keywords: Coordination Games, Information Games, Amenability, Social Networks. 1 Introduction This paper continues the study of pure coordination games on social networks, initiated in the recent work of Hutchcroft, Rospuskova, and Tamuz [ 1 ] . In these games, players must choose between two alternatives toward which they are initially unbiased. The only goal is that, on average, the players’ choices will match. Examples include the choice of a weekly day of rest, the side of the street on which to drive, and the paper size used for printing: a priori, the choice itself plays no significant role, but consistency among the players is crucial. The players are considered as part of a social network 1 1 1 Modeled by a graph whose vertices represent the players. , where they aim to coordinate with their neighbors. Communication is local, that is, bounded by distance, and the network itself is considered large. In such a case, total coordination is unachievable, and therefore some inefficiency in the players’ choices must occur. It is shown in [ 1 ] that a geometric property of the network, known as amenability, or hyperfiniteness in graph-theoretic terminology, is related to low inefficiency. Amenability of a network means that the graph can be divided into disjoint local neighborhoods by removing only a small fraction of the edges. Given such a decomposition, total coordination can be achieved inside each neighborhood, while the only contribution to inefficiency comes from inconsistencies between adjacent neighborhoods. Quite surprisingly, the converse also holds: high coordination implies that the network is amenable. However, the cost of the resulting decomposition is asymptotically larger. The authors conjectured that this gap can be improved, and this is precisely what we prove in the present paper. Our approach follows the probabilistic formulation used in their proof. Each player is assigned a local random variable, determined only by the information available in a bounded neighborhood, and the quality of coordination is measured by the expected disagreement along edges. A key point in our argument is that, for the improved estimate, it is necessary to work specifically with \{-1,1\} -valued, unbiased random variables. In this binary setting, disagreement has an information-theoretic meaning: if two neighboring outputs disagree with probability p , then the conditional uncertainty between them is controlled by the binary entropy h(p) . This allows us to replace the square-root type estimate in the original argument by an entropy-type estimate. This is related in spirit to the approach of [ 4 ] , where entropy is considered in place of variance, although the methods themselves are different. We build on the technical framework presented in [ 1 ] , which uses the Shapley distribution (see [ 2 ] , [ 3 ] ). This distribution measures how much a single variable affects the outcome of a function depending on several independent inputs. We modify this part of the argument by considering the Shapley values of a mutual-information game associated with the players’ local outputs. This yields an improved bound on the total variation distance between the resulting Shapley distributions, in terms of how often the two functions disagree. This, in turn, shows that the decomposition of the network can be obtained at a smaller cost in disagreements between neighboring players. 2 Preliminaries 2.1 The Model Let G=(N,E) be a finite undirected graph. The elements of N represent the players, and an edge \{i,j\}\in E means that i and j are neighbors. We write B_{r}(i):=\{j\in N:\operatorname{dist}_{G}(i,j)\leq r\} for the radius- r ball around i . We think of r as the radius to which information can travel before actions are chosen. Each player chooses an action in \{+1,-1\} . The underlying game is a pure coordination game: each player wants to match the actions of her neighbors (the payoff of player i at an action profile a=(a_{j})_{j\in N}\in\{+1,-1\}^{N} is u_{i}(a):=-\sum_{\{i,j\}\in E}|a_{i}-a_{j}|. The model presented in [ 1 ] allows players to communicate locally before choosing actions. Communication is restricted to distance r , and there are two types of messages: each player i\in N can send public and private messages observed by the players in B_{r}(i) . For our purposes, incentives and the precise message structure will not play a role. We use the probabilistic abstraction appearing in [ 1 , Theorem 5] . Namely, let (Z_{i})_{i\in N} be independent random variables associated to the vertices, and let (X_{i})_{i\in N} be a family of random variables, such that X_{i}\text{ is measurable with respect to }\sigma(Z_{j}:j\in B_{r}(i)) , and the variables are unbiased, meaning \mathbb{E}[X_{i}]=0,\ \mathbb{E}[X_{i}^{2}]=1. Thus, X_{i} is determined by information inside the radius- r ball of i . We will be interested in the average expected inefficiency, or average disagreement, of a given family X=(X_{i})_{i\in N} which is given by \frac{1}{|E|}\sum_{\{i,j\}\in E}\frac{1}{2}\mathbb{E}\left[(X_{i}-X_{j})^{2}\right]. 2.2 Amenable Graphs The geometric property governing local coordination is amenability, also called hyperfiniteness in parts of the graph theory literature. Definition 2.1 ( (\varepsilon,r) -amenability) Let G=(N,E) be a finite graph. We say that G is (\varepsilon,r) -amenable if there exists a partition of N into connected components such that each component has radius at most r , and such that the number of edges crossing between distinct parts is at most \varepsilon|E| . Equivalently, G is (\varepsilon,r) -amenable if one can delete at most an \varepsilon -fraction of the edges so that every connected component of the remaining graph has radius at most r . On such a graph there is a natural coordination strategy---all the players in a component may coordinate on the same signal from some chosen leader, which then implies that disagreements occur only along the boundary edges between different parts. In particular, this strategy 2 2 2 In fact, an unbiased leader equilibrium exists with such inefficiency [ 1 , Theorem 1] . guarantees inefficiency of at most \varepsilon . Example 2.2 Let C_{n} denote the cycle graph on the vertex set \{1,\ldots,n\} , where \{i,j\}\in E if and only if j=i+1\quad\text{ or }\quad i-1\mod(n) . One may verify that C_{n} is (\frac{1}{2r+1},r) -amenable. 2.3 Bounds of Amenability Parameter One of the main results in [ 1 ] is that low inefficiency in local coordination forces the underlying graph to be amenable. They prove that on amenable graphs one can construct efficient leader equilibria, while on non-amenable graphs low-inefficiency coordination is impossible. We shall use the following theorem as the benchmark result. Theorem 2.3 [ 1 , Theorem 5] Let G=(N,E) be a

Read the complete text