Entropy Bounds for Local Coordination and Graph Amenability
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.01963
curl -X POST /api/v1/records/arxiv/2606.01963/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.01963/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'