📐algorithm-stable-marriage

The groupant beside algorithms/src/stable_marriage/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Components

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

Model text

descriptant

Description and epoch memory

Two equal-sized populations with complete strict n-entry permutation rows; total 2nn entries at most 2000000. Empty populations allowed.

2026-10-30 initial epoch: chose existing matching plus explicit alternating closure for cover, and FIFO deferred acceptance plus inverse receiver ranks for marriage. Prospective cost: Validation, rank construction and at most n squared proposals cost O(n squared); ranks use O(n squared) auxiliary storage and queues/mates O(n). Budget arithmetic is checked before allocation; allocation failure is untyped. No approximation surrogate is useful for the exact witness contract.

Independent finite oracles inspect both primal/dual cover cardinalities and every stable permutation at small sizes. Original source and fixtures; citation describes the classical method. Models and partial syntax do not prove semantics; macros remain opaque and semantic AST is absent.

approximant

Forward and cost

Validate equal sizes, checked quadratic budget, then proposer and receiver rows. Build receiver inverse ranks. FIFO free proposers propose to the next untried receiver; a receiver retains its best proposal so far and requeues the rejected proposer. Return receiver index per proposer when the queue empties.

Validation, rank construction and at most n squared proposals cost O(n squared); ranks use O(n squared) auxiliary storage and queues/mates O(n). Budget arithmetic is checked before allocation; allocation failure is untyped.

Attribution: D. Gale and L. S. Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly 69(1) (1962), 9–15. Implementation and fixtures are original. No optimization or speedup is claimed.

invariant

Invariants

Each receiver holds at most one proposer; each held proposer is absent from the free queue. A proposer never repeats a proposal. Receiver held ranks strictly improve on replacement. Completeness prevents preference exhaustion by a free proposer. Final mates form a permutation without blocking pairs and are proposer-optimal among stable permutations.

Test enumeration uses independent subset/assignment predicates rather than repeating production traversal. Bounds do not prove unbounded behavior.

catalog

Typed models

Source snapshot: 245bad78eb11d5b0f2f865a72a2ccf0541a146269c3531e42fb6d355fe55e26e. Domain: Two equal-sized populations with complete strict n-entry permutation rows; total 2nn entries at most 2000000. Empty populations allowed.

Each relation is source-derived, exact as a specification; finite executable evidence is partial. Assumes deterministic std-only execution with successful allocation. No executable inverse solver or approximation error cap is claimed.

behavior-complement

Universe: two preference matrices crossed with candidate receiver vectors and errors. Absent successful behaviors include a non-permutation, a blocking pair (p,r) where both prefer each other to assigned mates, or a stable permutation giving a proposer a worse partner than another stable permutation. Invalid row lengths/permutations cannot succeed. Unequal sizes beat the budget error, which beats malformed rows; within each row, length beats duplicate/out-of-range entry. The finite exhaustive oracle supports these exact source-derived constraints without a general Rust proof.

reverse-reconstruction

For an observed permutation m, retain every pair of complete preference matrices for which m is stable and proposer-optimal: for each stable alternative s and proposer p, rank_p(m[p]) <= rank_p(s[p]). This finite relational characterization is ambiguous: with two proposers each ranking a distinct receiver first, either strict ordering in each receiver row still yields m. Observing a matching loses unproposed suffixes and proposal/rejection history. Error preimages comprise all profiles sharing the first failed validation predicate and observed indices.

proposal-budget

The sum of next-proposal cursors increases exactly once per loop and is bounded by n squared. Receiver ranks only improve; a rejected proposer can never obtain that receiver in a proposer-optimal stable solution. Complete strict preferences are required.

optimality-fiber

Fix preferences and enumerate all n! assignments; discard blocking assignments. For each proposer, the returned partner has minimum ordinal rank among the remaining assignments. Tests enumerate every profile up to n=3; this is finite evidence only.

validation-partition

Equal size is inspected before checked total entries, then proposer rows before receiver rows. Row length is inspected before entry validity, duplicates share the invalid-preference variant. Later malformed rows remain unconstrained in an early-error preimage.

tests

Bounded checks

All 46674 strict preference profiles for n=0 through 3: every assignment checked for blocking pairs and every stable alternative compared proposer by proposer. Replacement witness; row/duplicate/range/error precedence; n=1000 boundary and n=1001 rejection. Three named tests.

Debug and release run twice with normalized named outcomes. Compiled production mutants flip the cover left complement and receiver replacement comparison respectively; named oracle assertions reject them. Restored positives and strict algorithms clippy are required. External receipts bind final source/evidence hashes. No timing or full-system claim.

See executed receipts for final source hashes, named control failures and repeated test log hashes. All checks stated above completed.

evidence

Executed evidence, 2026-10-30

Source SHA-256: 245bad78eb11d5b0f2f865a72a2ccf0541a146269c3531e42fb6d355fe55e26e. Three tests passed twice in debug and twice in release with identical normalized named results across all four runs. Both restored debug suites passed. Strict algorithms all-targets Clippy and narrow rustfmt checks passed. Four syntax projections repeated byte-identically; structural scaffold passed twice with identical reports (one intentionally missing external scaffold sidecar).

• stable_marriage-debug-1.log: 1cc0bb3ad3f61e469e7d0cad8e599f68e00fa38e58b23443bcbc968bb74000f2
• stable_marriage-debug-2.log: c58528570e494e55479656404370958481b56ad9a169f8b0c3bbc1d024e635d8
• stable_marriage-release-1.log: f21c6a741c558489f5f82244bb5aa1175e88a2e4215a0475b83f29d7ef8e58ee
• stable_marriage-release-2.log: e276961b9bcd1acba127bf4fd564a3eab98d805207f4cb1a79f4c03f11d8d13b
• stable_marriage-restored.log: 35e1ef64eae39d69d913ad0b46522792295273bdd0abd535163d8cd62a88a477
• marriage-mutant.log: c2d96973907a7c62f74fd385378c46db21fc0df733de17cfcc5cf38885aa6ee6

Compiled receiver rank comparison reversal was rejected by receiver_replacement_witness: [0,1] instead of [1,0].

Raw logs remain in the external wave14 graphs run bundle. Earlier tooling attempts exposed two Clippy style findings, absent rg, and stale syntax outputs; final receipts above bind corrected sources and successful checks. No source correctness repair was required by positive oracle findings. No general proof, speedup, full-system or allocation-failure claim.

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/stable_marriage/mod.rs.groupant/