← All AI/ML open problems

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.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

In a finite coverage game, agent i chooses ai∈Ai⊆[m]a_i\in A_i\subseteq[m], resource values satisfy vr∈(0,1]v_r\in(0,1], and welfare is W(a)=∑rvr1{∃i:ai=r}W(a)=\sum_r v_r\mathbf1\{\exists i:a_i=r\}. On a directed information graph G, use local utilities uiG(a)=vai1{aj≠ai ∀j∈Ni(G)}u_i^G(a)=v_{a_i}\mathbf1\{a_j\ne a_i\ \forall j\in N_i(G)\}. Find minimum-cost G whose worst coarse-correlated-equilibrium welfare remains at least αmax⁡aW(a)\alpha\max_a W(a) after deletion of any f links; derive polynomial-time approximation guarantees or conditional hardness bounds in n,m,fn,m,f.

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

  1. 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.

  2. 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.