Shapley-Coop: Credit Assignment for Emergent Cooperation in Self-Interested LLM Agents

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Shapley-Coop is a cooperative workflow that enables self-interested LLM agents to spontaneously cooperate in open-ended environments by grounding incentive alignment and reward redistribution in Shapley value theory. It combines a structured negotiation protocol with two Chain-of-Thought reasoning modules—one prospective (heuristic externality assessment) and one retrospective (formal Shapley approximation)—to achieve both task-time coordination and post-task fair credit assignment.

Problem

Existing multi-agent LLM frameworks assume predefined roles, aligned goals, or explicit coordination rules. In open-ended environments where agents are self-interested and goals conflict, these methods fail: agents fall into social dilemmas (Nash equilibria with suboptimal collective outcomes), and even negotiation-enabled agents cannot fairly attribute credit to individual contributions. The core unsolved challenges are (1) incentive alignment across heterogeneous goals and (2) principled credit assignment without full observability.

Method

Shapley-Coop addresses both challenges through three integrated modules:

1. Structured Negotiation Protocol: Agents communicate via tagged, machine-parseable messages (<s>...</s>) covering intent notification, pricing proposals, and structured accept/reject/counter-propose responses.

2. Short-Term Shapley CoT: During task execution, each agent qualitatively estimates the collective reward achievable under full cooperation, assesses whether its current action creates positive or negative externalities for others (without computing exact Shapley values), and proposes qualitative price adjustments to align incentives in real time.

3. Long-Term Shapley CoT: Post-task, each agent retrospectively computes the full Shapley value from the observed trajectory by (a) summing the total coalition reward, (b) estimating marginal contributions ∆_i(C) = R(C∪{i}) − R(C) across subcoalitions, (c) averaging over all orderings per Equation 3, and (d) negotiating final reward redistribution based on these computed values. LLMs call external calculation functions for the combinatorial steps.

The two CoT modules together form a closed-loop pricing mechanism: short-term aligns goals prospectively; long-term enforces fairness retrospectively.

Key Contributions

• Introduces a pricing-based perspective for multi-LLM cooperation grounded in cooperative game theory (Shapley values), distinct from rule-, role-, or model-oriented prior work.
• Proposes Shapley-Coop, a complete workflow integrating structured negotiation with Short-Term and Long-Term Shapley Chain-of-Thought for simultaneous incentive alignment and credit assignment.
• Demonstrates emergent cooperation in open-ended environments without predefined roles or reward structures.
• Validates the approach on three qualitatively different environments: a social-dilemma toy game, a complex multi-step RPG, and a realistic multi-role software engineering simulation.

Results

• Escape Room (DeepSeek-v3): LLM+SC achieves 100% cooperation success with payoff allocations converging to the Shapley-optimal 4.5 each; LLM+NEG succeeds only 25% of the time; LLM-only succeeds 0%.
• Raid Battle (multi-step, 4 agents, 3 difficulty levels): LLM+SC improves contribution scores over LLM+NEG by +36% to +222% per role across levels, with healers and taunters receiving appropriate support rather than all agents free-riding on damage-dealing.
• Raid Battle credit assignment: LLM+STS shows systematic underestimation errors (e.g., 4.52–6.26% reward deficit for the primary taunter); LLM+SC substantially closes these gaps.
• ChatDev (software engineering): Reward allocations produced by Shapley-Coop deviate from WEV-grounded ground truth by <6% for most roles; hands-on roles (Programmer, Reviewer) show near-perfect alignment.

Limitations

• Shapley value approximation may not satisfy the efficiency property (exact payoffs may not sum to total reward), a known trade-off accepted for computational tractability.
• Communication overhead (token cost) from the negotiation protocol is significant and unaddressed; no quantitative cost analysis is provided.
• Dynamic repricing during collaboration is not supported; pricing is set pre-task and redistributed post-task, with no mechanism to adapt to mid-task changes in agent behavior or environment state.
• Coalition reward estimation R(C) requires counterfactual reasoning about absent agents, which LLMs approximate heuristically and may do poorly at scale or in novel tasks.
• Evaluated on only two or three scenarios per claim; scalability to larger agent counts (N >> 4) is not empirically validated.

Relevance to Agentic AI / LLM Agents

This work directly targets a critical bottleneck in deploying LLM agents in multi-agent settings: how to get agents with misaligned private objectives to cooperate without imposing top-down role constraints. By importing cooperative game theory into LLM agent coordination, Shapley-Coop provides a principled alternative to ad hoc negotiation, which is increasingly important as agentic systems move toward open-ended, market-like environments (e.g., AI-to-AI contracting, multi-provider pipelines). The Shapley Chain-of-Thought pattern—decomposing game-theoretic reasoning into LLM-executable CoT steps with external calculation hooks—is a reusable design pattern for embedding formal economic mechanisms into agent reasoning loops. The ChatDev experiment also grounds the framework in a realistic multi-agent software engineering task, demonstrating applicability to agentic coding pipelines.