🔢 mathematics

Improved Amenability Bounds for Local Coordination Games

This paper improves the quantitative relationship between local coordination and graph amenability in binary unbiased local coordination games by proving that low average disagreement implies the graph is $(O(\varepsilon\log(1/\varepsilon)),r)$ -amenable, thereby sharpening the previously known square-root loss bound.

Original authors: Ron Peretz, Dean Kraizberg

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ron Peretz, Dean Kraizberg

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Neighborhood Agreement" Problem

Imagine a massive city where everyone needs to agree on a simple rule, like "drive on the left" or "take Tuesday off." However, there's a catch: nobody can talk to everyone. You can only chat with your immediate neighbors (your friends, your block, your street).

The goal is for the whole city to eventually agree on the same rule. But because you can only talk locally, you might end up with one neighborhood driving on the left and the next one driving on the right. This creates "inefficiency" or "disagreement" at the borders.

The paper asks a deep question: If the city manages to get almost everyone to agree (low disagreement), what does that tell us about the shape of the city's map?

The Old Theory: The "Square Root" Guess

Previous researchers (Hutchcroft, Rospuskova, and Tamuz) discovered a surprising link. They found that if a city has very low disagreement, the city's map must be "amenable."

What is "Amenable"?
Think of "amenable" as a map that can be easily chopped up into small, tidy neighborhoods. If a map is amenable, you can cut a few roads (edges) to isolate small clusters where everyone inside agrees perfectly. The only disagreements happen on the few roads you cut.

The old researchers proved:

If disagreement is low (let's call it $\epsilon$ ), the map is amenable.
However, the "cost" of chopping up the map was roughly the square root of the disagreement ( $\sqrt{\epsilon}$ ).

The Analogy:
Imagine you have a messy room (the graph). You want to tidy it up by putting things into small boxes (neighborhoods).

The old theory said: "If the room is only slightly messy (low $\epsilon$ ), you can tidy it up, but you might still have to throw away a lot of stuff (the $\sqrt{\epsilon}$ loss)."
The authors of this paper asked: "Can we do better? Can we tidy it up with less waste?"

The New Discovery: The "Entropy" Upgrade

The authors of this paper say yes, we can do much better, but only if the choices are binary (like "Left" vs. "Right" or "Yes" vs. "No").

They improved the math to show that if the disagreement is low ( $\epsilon$ ), the map is amenable with a cost of roughly $\epsilon \times \log(1/\epsilon)$ .

Why is this a big deal?
In math, $\epsilon \times \log(1/\epsilon)$ is much smaller than $\sqrt{\epsilon}$ when $\epsilon$ is tiny.

Old Way: If 1% of neighbors disagree, the map structure is "okay" but not great.
New Way: If 1% of neighbors disagree, the map is extremely well-structured and easy to divide into perfect little neighborhoods.

How Did They Do It? The "Information Detective"

The authors didn't just use standard math; they used a clever trick involving Information Theory and Game Theory.

The Old Method (Variance): The previous team looked at the "distance" between neighbors' choices. It was like measuring how far apart two people are standing.
The New Method (Shapley Values & Entropy): The authors looked at uncertainty.
- Imagine every person in the city has a secret code (random variable) that helps them decide.
- They created a "game" where they asked: "How much does knowing my neighbor's secret code reduce my own uncertainty?"
- They used a concept called Shapley Values (a way to fairly split credit in a team) to measure how much each piece of information contributed to the decision.
- Instead of measuring "distance," they measured entropy (a measure of confusion or surprise).

The Metaphor:
Imagine two neighbors, Alice and Bob.

Old View: If Alice says "Left" and Bob says "Right," they are far apart.
New View: If Alice says "Left" and Bob says "Right," how surprised should we be? If they disagree often, there is high "entropy" (chaos). If they agree most of the time, the entropy is low.

By using this "entropy" measurement, the authors proved that when neighbors agree well, the underlying map must be very easy to slice into small, tidy pieces.

The "Binary" Catch

There is one important condition for this new, sharper result: The choices must be binary and unbiased.

Binary: You can only choose A or B (like Heads/Tails).
Unbiased: You don't prefer A or B beforehand; it's a 50/50 coin flip.

The paper proves that if you allow more than two choices (like choosing between 3 or 4 colors), the old "square root" rule applies again, and you can't get the sharper result. But for simple "Yes/No" or "Left/Right" scenarios, the new, tighter bound holds.

Summary of the Result

The Problem: How does local agreement (neighbors agreeing) reflect the global shape of a network?
The Old Answer: Good local agreement implies the network is "sliceable" (amenable), but the math was a bit loose ( $\sqrt{\epsilon}$ ).
The New Answer: For simple "Yes/No" choices, good local agreement implies the network is extremely sliceable. The math is much tighter ( $\epsilon \log(1/\epsilon)$ ).
The Tool: They replaced "distance" measurements with "information/uncertainty" measurements (using Shapley values and entropy) to get a clearer picture.

In short, the paper shows that when people in a network agree well on simple choices, the network itself is much more organized and "friendly" (amenable) than we previously thought.

Technical Summary: Improved Amenability Bounds for Local Coordination Games

Problem Statement
This paper investigates pure coordination games played on finite social networks, extending the framework established by Hutchcroft, Rospuskova, and Tamuz [1]. In this setting, players (vertices of a graph $G$ ) must choose between two alternatives, $\{+1, -1\}$ , with the goal of matching their neighbors' choices. Players possess only local information, determined by random variables within a radius- $r$ neighborhood $B_r(i)$ .

The central problem addresses the relationship between the efficiency of local coordination and the geometric structure of the underlying network. Specifically, if the average disagreement (inefficiency) between neighbors is low (bounded by $\epsilon$ ), does this imply that the graph possesses a specific geometric property known as amenability (or hyperfiniteness)? Amenability, in this context, means the graph can be partitioned into connected components of radius at most $r$ by removing only an $\epsilon'$ -fraction of edges.

Previous work [1] established that low inefficiency implies amenability but with a significant quantitative loss: if the average disagreement is $\epsilon$ , the graph is $(\sqrt{8\epsilon}, r)$ -amenable. The authors of [1] conjectured that this square-root loss could be improved, particularly in the binary unbiased setting.

Methodology
The paper adopts the probabilistic abstraction used in [1], where each player's action $X_i$ is a random variable measurable with respect to independent inputs $Z_j$ within their radius- $r$ neighborhood. The actions are unbiased ( $E[X_i]=0$ ) and binary-valued.

The core methodological innovation lies in shifting from a variance-based analysis to an information-theoretic analysis:

Information Games: Instead of analyzing the variance of outputs, the authors associate a Transferable Utility (TU) game with each player's local output $X_i$ . The value of a coalition $S$ in this game is defined by the mutual information between the player's output and the inputs in $S$ : $u_i(S) := I(X_i; Z_S)$ .
Shapley Values: The authors utilize the Shapley values of these mutual-information games to define a probability measure (influence distribution) $\mu_i$ on the set of vertices. This measure represents the "influence" of each input variable on the player's output.
Entropy-Based Bounds: A key technical lemma (Lemma 3.2) establishes that the total variation distance between the Shapley distributions of two neighboring players is bounded by the binary entropy of their disagreement probability: $\|\text{Sh}(u_1) - \text{Sh}(u_2)\|_{TV} \leq h(p)$ , where $p = \Pr[X_1 \neq X_2]$ and $h(p)$ is the binary entropy function. This replaces the square-root dependence found in the variance-based approach.
Coupling: The authors employ a grand coupling theorem (Theorem 3.3) to simultaneously couple the Shapley distributions of all players. This coupling generates "leaders" for each player such that the probability of two neighbors having different leaders is controlled by the total variation distance of their distributions.

Key Contributions and Results
The primary contribution is a sharpened quantitative converse between local coordination and graph amenability for binary, unbiased variables.

Main Theorem (Theorem 2.5): If the average disagreement between neighbors is at most $\epsilon$ (where $0 < \epsilon \leq 1/2$ ), then the graph $G$ is $(2h(\epsilon), r)$ -amenable.
Quantitative Improvement: Since $h(\epsilon) \approx \epsilon \log(1/\epsilon)$ for small $\epsilon$ , this result improves the bound from $O(\sqrt{\epsilon})$ (in [1]) to $O(\epsilon \log(1/\epsilon))$ .
Tightness of Previous Bounds: The paper includes Lemma 2.4, which demonstrates that the square-root bound in the general case (without the binary restriction) is tight up to constants. This proves that the improvement to an entropy-based bound is specific to the binary unbiased setting and cannot be achieved for general random variables.

Significance and Claims
The paper claims to resolve the conjecture posed by Hutchcroft, Rospuskova, and Tamuz regarding the improvement of the amenability bound in the binary setting. By utilizing the Shapley values of a mutual-information game, the authors achieve a "sharper quantitative converse" between local coordination and graph structure.

The significance of this work is twofold:

Theoretical Precision: It provides a more precise characterization of the geometric constraints required for efficient local coordination in binary games, reducing the "loss" in the amenability parameter from a square-root dependence to a near-linear dependence (with a logarithmic factor).
Methodological Shift: It demonstrates the efficacy of replacing variance-based arguments with entropy-based arguments in the context of coordination games, leveraging the specific properties of binary entropy to bound total variation distances more tightly.

The authors explicitly state that this improvement relies on the restriction to $\{-1, 1\}$ -valued unbiased variables; without this restriction, the square-root bound remains optimal. The paper does not propose new applications or future experimental directions but focuses strictly on refining the theoretical bounds within the existing framework of local coordination games.