Improved Amenability Bounds for Local Coordination Games
2026-06-01 • Computer Science and Game Theory
Computer Science and Game TheoryInformation Theory
AI summaryⓘ
The authors study games where players on a network try to match their choices with neighbors, called local pure coordination games. They build on previous work that linked how well players coordinate to a property of the network called amenability, but improve the precision of this link in a special binary case. By using a tool from game theory called Shapley values related to how much information players share, they show that if players disagree very little on average, the network is more tightly amenable than previously known. This means they provide a better mathematical relationship between good local coordination and the network's structure.
local coordination gamefinite social networksgraph amenabilityShapley valuesmutual informationbinary settingdisagreement measurenetwork structuregame theoryquantitative bounds
Authors
Ron Peretz, Dean Kraizberg
Abstract
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.