Multi-agent communication & games · Statistical learning theory / Open question
The Price of Strategic Collaboration
Agents may contribute too little or duplicate work because of incentives and incomplete knowledge. This model makes the cost of coordinating them through information a precise worst-case quantity.
Seed catalog · Showing the bundled record.
Problem statement
For symmetric with , define . Agents know W but not their uniformly permuted task locations; a platform knowing those locations privately recommends efforts through a persuasive scheme . Determine , closing the gap .
Assumptions and scope
- The platform commits before observing the random permutation and may use any finite set of effort recommendations in [0,1]. Each agent sees only its own private recommendation; the network and prior are common knowledge.
- Persuasiveness means that, conditional on a recommendation, expected received quality is at least one and the agent cannot lower its own effort while preserving that conditional expectation. Equality is required for positive recommendations. This is not ex-post feasibility on every realization.
- Use the individually rational optimum in the denominator, not the unrestricted social optimum or full-information Nash cost. Edge weights may be arbitrarily small; unit-weight and positive-minimum-weight graph classes already have tight different exponents.
What would settle it?
A sharper worst-case exponent, ideally a matching Omega(n^3/4) construction or an improved universal signaling upper bound with a matching lower bound. Account for all persuasive schemes, not only binary/ternary ones, in an impossibility proof.
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
Haghtalab et al. explicitly pose the general-weight gap and conjecture a three-quarters lower bound. Their sharper cost upper bound is O(n^3/4 sqrt(OPT^IR)); the two-thirds lower bound already holds with positive edge weights one half. This is a specified strategic collaboration game, not a claim that actual LLM agents obey these incentives. This is an editorial reformulation of a published open problem. 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
- Haghtalab, Qiao and Yang — Platforms for Efficient and Incentive-Aware Collaboration ↗problem statement · source checked 2026-11-19
HTML Sections 2 and 4, Theorem 1.2 checked: general weighted graphs have an O(n^3/4) approximation to OPT^IR versus an Omega(n^2/3) lower bound; matching the exponent is explicitly open. Persuasiveness uses conditional expected quality and minimum feasible effort, not ex-post feasibility.
- Blum et al. — One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning ↗partial theory · source checked 2026-11-19
Primary abstract checked: stable and envy-free collaboration equilibria and their sample-collection burden relative to social optimum. The later information-design model changes what agents know, not their task-sharing matrix.