Multi-agent communication & games · Optimization & optimizers / Open question
Reliable Teams with Fewer Connections
An agent team needs enough communication to avoid redundant or conflicting work, but dense graphs are costly and links can fail. A fixed game model turns topology choice into a measurable efficiency question. Efficiency payoff: Reduce communication links while retaining a coordination guarantee under failures.
Seed catalog · Showing the bundled record.
Problem statement
In a finite coverage game, agent i chooses , resource values satisfy , and welfare is . On a directed information graph G, use local utilities . Find minimum-cost G whose worst coarse-correlated-equilibrium welfare remains at least after deletion of any f links; derive polynomial-time approximation guarantees or conditional hardness bounds in .
Assumptions and scope
- Each action set is nonempty; values, link costs and alpha are rational input data. N_i is the set of agents whose actions i observes, excluding i itself. Link failures are fixed before play, not adaptively chosen each round.
- A distribution mu is a coarse correlated equilibrium when E_mu[u_i(a)] is at least E_mu[u_i(a_i',a_-i)] for every agent and every fixed unilateral action a_i'. Such equilibria exist in finite games even when pure equilibria do not.
- Charge the sum of retained directed-link costs. The robust requirement is uniform over failed-link sets of size at most f and all CCEs of each resulting game. A bicriteria algorithm must explicitly report any loss in alpha as well as its cost approximation factor.
What would settle it?
A proved cost-approximation ratio with a welfare certificate for the robust graph-design problem, or an explicit complexity-theoretic lower bound. Exhaustive graph enumeration and a CCE linear program define a baseline, not an efficient solution; preserving one favorable equilibrium is weaker than the target.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Minimal communication networks preserving full-information performance and optimal utility design for pure Nash equilibria already have results. This editorial extension fixes a coverage game and asks for costed failure robustness over CCEs, relevant to no-regret play. Its novelty and best achievable approximation ratio need a dedicated algorithmic audit beyond the source-level check. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Collins, Hill and Brown — Achieving Robust Performance Using Minimal Communication in Resource Allocation Games ↗partial theory · source checked 2026-11-19
Primary abstract checked: efficient minimal-network construction preserving a full-information guarantee in its resource-allocation setting, with pure/strict Nash analysis. Basic sparse topology design is not an unexplored problem.
- Singh and Brown — Deriving the Pure Price of Anarchy for Networked Resource Allocation Games ↗partial theory · source checked 2026-11-19
Abstract checked: LP-based optimal utility design for arbitrary information networks and pure Nash equilibria. The proposed topology extension changes the robustness requirement and equilibrium notion to link failures and coarse correlated equilibria.