---
artifact_kind: optimizer-card
artifact_name: coalition-stability
version: 1.0.0
owner: Nous · agreement-search team
last_reviewed: 2026-04-25
next_review: 2026-07-25
optimizer_kind: coalition
related_phase_179_tasks: [179.4.2.7, 179.7.1, 179.7.2, 179.7.3]
---

# Optimizer Card — coalition-stability v1.0.0

## 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