Disciplines · Compliance

Optimizer Card — coalition-stability v1.0.0

membership, least-core allocation, side-payment generation, simplified Davis-Maschler bargaining set.

9sections3 minread

On this page

1. Identity#

  • Optimizer name: coalition-stability
  • Algorithm family: cooperative game theory — Shapley values, core membership, least-core allocation, side-payment generation, simplified Davis-Maschler bargaining set.
  • Implementation source: libs/nous/agreement-search/src/coalition-stability.ts.
  • Intended use: multi-party search where any strict subset of the parties can defect to a sub-agreement and secure a collective value that beats the grand coalition's per-party allocation. DAO governance (§179.7.2), multi-supplier procurement (§179.7.1), multi-party restorative circles (§179.7.3).

2. Scoring rule#

  • Utility aggregation: characteristic-function game v(S) = collective value coalition S can secure. Caller-supplied or derived by the kernel from a candidate pool.
  • Solution concepts emitted: Shapley values; core membership; least-core allocation; bargaining-set membership.
  • Side-payment generation: transfer vector τ such that u(c) + τ equals the least-core allocation, normalized so Σ τ = 0.
  • Handling of hard constraints: every candidate in the input pool passes through filterCandidates.
  • Handling of uncertainty: Shapley sampling (n > 7) emits 95% confidence intervals via the sample standard deviation.

3. Inputs#

  • Party set: n parties; the kernel handles n up to 7 with exact Shapley enumeration; beyond 7, Monte-Carlo sampling at caller-chosen budget.
  • Characteristic function: caller-supplied callback (S) → v(S), OR a candidate pool plus enforcement policy that derives v(S) (the default).
  • Candidate pool: filtered candidate set from the upstream search kernels.
  • Bargaining-set scan depth: caller-controlled (bargainingSetScanDepth).
  • Time / iteration budget: subgradient iterations for least-core
    • bargaining-set scan budget.
  • Randomness: seeded mulberry32 for Shapley sampling.

4. Outputs#

  • Accepted candidate contract: bestStableCandidate — the candidate whose native utility vector is closest (in L1 norm of τ) to the least-core allocation.
  • Allocation diagnostics: Shapley values (with CI for n > 7); core-empty / core-non-empty verdict; least-core ε; blocking-coalition list with excess values; bargaining-set membership of the imputation.
  • Side-payment vector: for the recommended candidate.
  • Uncertainty propagation: for Monte-Carlo sampled Shapley, the CI flows to the workbench.

5. Evaluation#

Metric Value Evaluator card Date
Shapley axiom satisfaction efficiency, symmetry, dummy-player, n/a — coalition-stability.test.ts 2026-04-25
additivity (asserted by tests)
Core-empty correctness matches reference linear-program n/a — coalition-stability.test.ts 2026-04-25
verdict on benchmark scenarios
Subgradient convergence step-size decay; converges to least- n/a — coalition-stability.test.ts 2026-04-25
core within configured tol
Side-payment minimality L1-norm minimum across pool n/a — coalition-stability.test.ts 2026-04-25
(asserted)
Bargaining-set superset of core core ⊆ bargaining-set (axiom) n/a — coalition-stability.test.ts 2026-04-25
Runtime (typical) exact for n ≤ 7; sampling-budget n/a — deterministic synchronous kernel 2026-04-25
dependent for larger n
Cost per run $0 (LLM-free) n/a 2026-04-25

6. Known limitations#

  • Exact Shapley enumeration is O(2^n); Monte-Carlo sampling required for n > 7.
  • Least-core subgradient assumes linear v(S) extrapolation between samples; non-monotone games may yield slow convergence.
  • Bargaining-set scan is exhaustive only up to bargainingSetScanDepth; deeper objection-counter chains are not searched.
  • Side-payment generation assumes transferable utility; for non-transferable-utility cases the recommended candidate is reported with transferable_utility = false and side-payment is null.

7. Guardrails#

  • Candidate safety gate: filterCandidates on every pool member.
  • Clause static validation: inside filterCandidates.
  • Redline separation: per-party redlines block coalition formation that would require the redlined party to consent; v(S) for such S is forced to the BATNA floor.
  • No external subsidy: Σ τ = 0 is enforced; the kernel cannot invent transfers from outside the party set.

8. References#

  • libs/nous/agreement-search/src/coalition-stability.ts
  • Shapley (1953), "A value for n-person games".
  • Schmeidler (1969), "The nucleolus of a characteristic function game" (least-core convergence behaviour).
  • Davis, Maschler (1965), "The kernel of a cooperative game" (bargaining-set foundation).
  • docs/research/bibliography.md §coalition-games