Improved Amenability Bounds for Local Coordination Games
For researchers studying local coordination games on networks, this provides a sharper converse bound between coordination inefficiency and graph structure.
The paper improves the quantitative relationship between low inefficiency in local coordination games and graph amenability, showing that average disagreement at most ε implies the graph is (O(ε log(1/ε)), r)-amenable, removing a square-root loss from prior work.
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.