# Achieving Pareto Optimality in Games via Single-bit Feedback

arXiv: https://arxiv.org/abs/2509.25921 · HTML: https://mlsanity.com/paper/2509.25921/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2025.

## Built on by (most cited first, 1 of 1)

- [Decentralized Optimal Equilibrium Learning Over Dynamic Networks](https://mlsanity.com/paper/2609.17601/) (2026)

## Abstract (arXiv)

Efficient coordination in multi-agent systems often incurs high communication overhead or slow convergence rates, making scalable welfare optimization difficult. We propose Single-Bit Coordination Dynamics for Pareto-Efficient Outcomes (SBC-PE), a decentralized learning algorithm requiring only a single-bit satisfaction signal per agent each round. Despite this extreme efficiency, SBC-PE guarantees convergence to the exact optimal solution in arbitrary finite games. We establish explicit regret bounds, showing expected regret grows only logarithmically with the horizon, i.e., O(log T). Compared with prior payoff-based or bandit-style rules, SBC-PE uniquely combines minimal signaling, general applicability, and finite-time guarantees. These results show scalable welfare optimization is achievable under minimal communication constraints.