๐Ÿฅฎ mooncakes.io

    moonmatch

    Matching markets for MoonBit: two-sided stable matching with machine-checkable stability certificates.

    matching-markets
    stable-marriage
    gale-shapley
    top-trading-cycles
    Download zip
    Version
    0.1.0
    License
    Apache-2.0
    Repository
    Last updated
    last month
    Downloads
    28

    No dependencies

    #MoonMatch

    CI

    Matching-market engine for MoonBit: Gale-Shapley stable matching, hospital/residents with quotas, and top trading cycles โ€” every outcome ships with a machine-checkable stability certificate, so "this allocation is stable" is a verified fact, not a claim.

    ๐Ÿšง WIP โ€” 2026 MoonBit Hackathon (September edition) entry, developed in the open.

    #Why

    Roommate pairing, school-seat assignment, shift swaps, organ exchanges: these are all matching markets, and the 2012 Nobel Prize (Roth & Shapley) says the algorithm you choose changes who wins. The registry already has naive DA/TTC implementations (see the landscape table below โ€” checking for them honestly is what shaped this library). What none of them provide is the part this library is built around: every outcome ships with an independently auditable stability certificate โ€” a brute-force blocking-pair scan, and an exportable witness blob a stranger can verify without trusting or re-running any code here.

    #Status

    #The CLI, in one honest demo

    check runs no algorithm โ€” it takes somebody else's answer and audits it:

    $ moon run cli -- check "1,0,2|0,1,2|0,1,2" "2,1,0|0,2,1|0,1,2" "0,1,2"
P0 -> R0
P1 -> R1
P2 -> R2
certificate: UNSTABLE, 4 blocking pair(s): (P0, R1) (P1, R0) (P2, R0) (P2, R1)

    #Certificates you can hand to a stranger

    cert exports the DA answer together with one witness per tempting pair ("P1 courted R0; R0 really holds P2, who it ranks above P1"). verify then checks a delivered blob without running any matching algorithm: each witness is one "who appears first in this list" scan, and the verification path shares no rank tables, queues or helpers with the mechanisms โ€” so accepting a certificate is not the same as trusting us.

    $ moon run cli -- cert "1,0,2|0,1,2|0,1,2" "2,1,0|0,2,1|0,1,2"
certificate: {"proposer_prefs":[[1,0,2],[0,1,2],[0,1,2]],"receiver_prefs":[[2,1,0],[0,2,1],[0,1,2]],"claim":[1,2,0],"witnesses":[{"proposer":1,"receiver":0,"holder":2},{"proposer":1,"receiver":1,"holder":0}]}

$ moon run cli -- verify '{"proposer_prefs":...,"witnesses":[]}'
verify: REJECTED: proposer 1 prefers receiver 0 to its partner, but no witness vouches for the refusal

    If a witness lies about the market's true holder, the rejection names the exact blocking pair it was hiding (witness for (proposer 0, receiver 1)is a lie: ...). A quickcheck property verifies on random markets that verify and the independent brute-force scan always agree.

    #Performance, measured (not promised)

    moon run --release benchmarks measures every hot path on square random markets from a fixed-seed LCG โ€” same inputs, same numbers, every run โ€” using the official moonbitlang/core/bench harness (its batching and winsorised statistics, not our stopwatch). Medians of 10 runs on the author's laptop, microseconds:

    ndeferred_acceptanceblocking_pairs scancertificateverifytop_trading_cycles
    10043941111833
    30033277338775176
    10003,43912,5482248,6181,184

    Two honest footnotes. First: the audits (blocking_pairs, verify) are ฮ˜(nยทm) by design โ€” they re-check everything independently of the mechanisms, and that duplication is exactly what makes the certificate worth something. Second: this table caught a real bug in itself โ€” the first version of verify was quadratic in certificate size (23.8 ms at n=1000, 100ร— the cost of generating the same certificate); it now buckets witnesses during the honesty pass (8.6 ms), and the remaining gap is the deliberate independent scanning.

    #Where this sits in the Mooncakes registry

    Keyword sweeps are cheap to get wrong, so every neighbour below was verified at README/interface level, twice. (An earlier version of this table described moonbit-auction as "one-sided bidding only" โ€” a deeper look found a whole src/matching subtree, and the correction is part of this project's story.) As of 2026-09-23:

    NeighbourWhat it actually hasWhat it does not have
    pk9993/moonbit-auction/src/matchingDA, TTC, TTC-with-chains, capacitated matching; audit_matching counts duplicate proposers, invalid references, capacity overflowany stability check โ€” the repo has no blocking-pair logic at all; no exportable certificate
    bobzhang/loop_invariants_graph/gale_shapley_stable_matching (2026-09-22)square-table DA + is_stable -> Bool, with loop-invariant documentationone-to-one only (no HR quotas, no TTC); the check is in-library trust, not an artifact a third party can audit
    hutingyu-nuist/moonballotIRV vote tabulationtwo-sided matching of any kind
    SUIKKKA/shiftweaveshift-scheduling constraint rulesgame-theoretic stability

    The gap MoonMatch occupies is the column on the right: stability as a verifiable artifact โ€” exportable witness certificates, an outsider-only verification path, capacity-aware HR certificates, and TTC IR/Pareto audits, none of which any registry package provides.

    #Quick example

    // proposers and receivers are row indices; each row ranks the other
    // side best-to-worst and must be a complete permutation
    let market = Preferences::new(
      [[0, 1], [1, 0]], // proposers' rankings
      [[0, 1], [0, 1]], // receivers' rankings
    )
    let m = market.deferred_acceptance()
    m.is_stable() // true โ€” verified by a blocking-pair scan, not trusted

    #License

    Apache-2.0

    CertError

    source
    pub suberror CertError {
      InvalidWitness(Int, Int)
      WitnessNotDominating(Int, Int)
      HolderMismatch(Int, Int, Int, Int)
      MissingWitness(Int, Int)
    } derive(
    Debug    )

    A certificate that fails to prove what it claims. Each variant names the exact pair at fault, so rejection is actionable, not just a red light.
    impl Show for CertError

    CertError::output

    source
    fn CertError::output(self : CertError, logger : &Logger) -> Unit

    CertError::to_repr

    source

    CertError::to_string

    source
    fn CertError::to_string(self : CertError) -> String

    CertificateError

    source
    pub suberror CertificateError {
      ClaimLength(Int, Int)
      PartnerOutOfRange(Int, Int)
      ReceiverHeldTwice(Int)
    } derive(
    Debug    )

    A claimed proposer->receiver table contradicts the market: wrong length, an out-of-range partner, or a receiver claimed twice.

    CertificateError::output

    source
    fn CertificateError::output(self : CertificateError, logger : &Logger) -> Unit

    CertificateError::to_repr

    source

    CertificateError::to_string

    source
    fn CertificateError::to_string(self : CertificateError) -> String

    MarketError

    source
    pub suberror MarketError {
      Empty
      RowNotPerm(Int)
      EndowmentLength(Int, Int)
      EndowmentNotPerm
    } derive(
    Debug    )

    A malformed exchange market.
    impl Show for MarketError

    MarketError::output

    source
    fn MarketError::output(self : MarketError, logger : &Logger) -> Unit

    MarketError::to_repr

    source

    MarketError::to_string

    source
    fn MarketError::to_string(self : MarketError) -> String

    ProfileError

    source
    pub suberror ProfileError {
      Empty
      RowLength(Side, Int, Int, Int)
      NotPermutation(Side, Int)
    } derive(
    Debug    )

    A malformed market description. Every Preferences value is built through Preferences::new, the single invariant gate; no downstream algorithm re-checks these conditions.

    ProfileError::output

    source
    fn ProfileError::output(self : ProfileError, logger : &Logger) -> Unit

    ProfileError::to_repr

    source

    ProfileError::to_string

    source
    fn ProfileError::to_string(self : ProfileError) -> String

    QuotaError

    source
    pub suberror QuotaError {
      QuotaLength(Int, Int)
      NonPositiveQuota(Int, Int)
    } derive(
    Debug    )

    Per-hospital capacity problems for the hospital/residents mechanism. Kept separate from ProfileError because quotas are a second gate: the Preferences themselves stay legal, only the capacity table can contradict the market shape.
    impl Show for QuotaError

    QuotaError::output

    source
    fn QuotaError::output(self : QuotaError, logger : &Logger) -> Unit

    QuotaError::to_repr

    source

    QuotaError::to_string

    source
    fn QuotaError::to_string(self : QuotaError) -> String

    HRAssignment

    source
    pub struct HRAssignment {
      preferences : Preferences
      quotas : Array[Int]
      proposer_to_receiver : Array[Int]
      receiver_holders : Array[Array[Int]]
    } derive(Eq, 
    Debug    )

    The outcome of a hospital/residents run: residents see one hospital (or -1), hospitals see a list of residents up to their quota.

    HRAssignment::blocking_pairs

    source
    fn HRAssignment::blocking_pairs(self : HRAssignment) -> Array[(Int, Int)]

    Blocking pairs under capacity: a resident prefers some hospital to their current post (or to being unmatched), and that hospital either has a free seat or ranks the resident above its current worst holder. An empty result means the assignment is stable; like the one-to-one certificate this scan shares no logic with the mechanism.

    HRAssignment::equal

    source

    HRAssignment::is_stable

    source
    fn HRAssignment::is_stable(self : HRAssignment) -> Bool

    HRAssignment::not_equal

    source
    fn HRAssignment::not_equal(x : HRAssignment, y : HRAssignment) -> Bool

    HRAssignment::to_repr

    source

    Market

    source
    pub struct Market {
      prefs : Array[Array[Int]]
      endowment : Array[Int]
    } derive(Eq, 
    Debug    )

    A one-sided exchange (housing) market: n agents each start out owning exactly one of n indivisible goods. Unlike two-sided matching there is no counterparty consent โ€” ownership itself is the currency โ€” which is why the solution concept changes from "stable" to "in the core", and Top Trading Cycles is the mechanism that implements it (Shapley & Scarf 1974).

    Market::equal

    source
    fn Market::equal(Market, Market) -> Bool

    Market::is_individually_rational

    source
    fn Market::is_individually_rational(self : Market, alloc : Array[Int]) -> Bool

    Individual rationality: no agent finishes with a good ranked below the one it brought in. A theorem about TTC โ€” asserted here as an audit that runs different code from the mechanism.

    Market::new

    source
    fn Market::new(prefs : Array[Array[Int]], endowment : Array[Int]) -> Market raise MarketError

    Build an exchange market: every agent must rank all n goods (complete strict orders), and the endowment must assign every good to exactly one agent.

    The row check deliberately delegates to the two-sided gate (check_rows) and only translates the error: one source of truth for "is this a complete ranking", two honest vocabularies for two kinds of market.

    Market::not_equal

    source
    fn Market::not_equal(x : Market, y : Market) -> Bool

    Market::pareto_dominators

    source
    fn Market::pareto_dominators(self : Market, alloc : Array[Int]) -> Array[Array[Int]]

    Exhaustive Pareto audit: every allocation that makes at least one agent strictly better off and no agent worse off. Enumerates all n! assignments โ€” exponential on purpose: it is the dumb-but-trust- me reference the quickcheck properties compare TTC against, and is only sane for tiny markets (n <= 6).

    Market::to_repr

    source

    Market::top_trading_cycles

    source
    fn Market::top_trading_cycles(self : Market) -> Array[Int]

    Top Trading Cycles: each waiting agent points at its favourite good still in the market; every ownership-pointer cycle trades at once and its members leave. At least one cycle exists per round (the pointing graph is a function on the waiting set), so this terminates in at most n rounds, and the outcome is in the core โ€” verifiable below rather than taken on trust.

    Matching

    source
    pub struct Matching {
      preferences : Preferences
      proposer_to_receiver : Array[Int]
      receiver_to_proposer : Array[Int]
    } derive(Eq, 
    Debug    )

    The outcome of running a mechanism on a Preferences: for each agent on each side, whom they are matched to, or -1 when unmatched.

    Matching::blocking_pairs

    source
    fn Matching::blocking_pairs(self : Matching) -> Array[(Int, Int)]

    Brute-force blocking-pair scan: every (proposer, receiver) pair that would rather leave this matching for each other. A matching is stable iff the result is empty.

    This deliberately does not reuse anything from the mechanism that produced the matching: the certificate is only worth having if it is computed independently (O(n * m) rank-table scans).

    Matching::certificate

    source
    fn Matching::certificate(self : Matching) -> StabilityCert

    Produce the certificate for this matching: one witness per pair (p, r) that p prefers over its partner, naming r's actual holder. For a stable matching every witness is honest; for an unstable one, the dishonest witness is exactly the blocking pair, and verify will say so. A tempting pair whose receiver is unmatched gets no witness -- correctly, since nothing can vouch for it.

    Matching::equal

    source
    fn Matching::equal(Matching, Matching) -> Bool

    Matching::is_stable

    source
    fn Matching::is_stable(self : Matching) -> Bool

    True when no blocking pair exists โ€” the defining property of a stable matching (Shapley & Flood 1962; Roth 1985 for the general case).

    Matching::not_equal

    source
    fn Matching::not_equal(x : Matching, y : Matching) -> Bool

    Matching::to_repr

    source

    Preferences

    source
    pub struct Preferences {
      proposer_prefs : Array[Array[Int]]
      receiver_prefs : Array[Array[Int]]
    } derive(Eq, 
    Debug    )

    A two-sided strict-preference market: n proposers, m receivers, agents identified by their row index (0-based).

    Row i of proposer_prefs ranks every receiver best-to-worst; row i of receiver_prefs ranks every proposer best-to-worst. Complete lists are mandatory because the theorems behind these algorithms (stability always exists; deferred acceptance returns the proposer-optimal stable matching) are stated for complete profiles โ€” silently tolerating a gap would change the theorem being implemented.

    Preferences::deferred_acceptance

    source
    fn Preferences::deferred_acceptance(self : Preferences) -> Matching

    Gale-Shapley deferred acceptance: every unmatched proposer keeps proposing down its list; receivers hold the best offer so far and reject the rest. At most n * m proposals, so it terminates fast, and the result is stable โ€” independently verifiable below with Matching::blocking_pairs rather than taken on trust.

    Preferences::equal

    source
    fn Preferences::equal(Preferences, Preferences) -> Bool

    Preferences::hospital_residents

    source
    fn Preferences::hospital_residents(self : Preferences, quotas : Array[Int]) -> HRAssignment raise QuotaError

    Deferred acceptance with many-to-one receivers (Roth & Sotomayor 1990, the algorithm behind US resident matching): identical to deferred_acceptance when every quota is 1; otherwise a hospital holds its best quota offers instead of just one.

    Preferences::matching_from

    source
    fn Preferences::matching_from(self : Preferences, proposer_to_receiver : Array[Int]) -> Matching raise CertificateError

    Rebuild a Matching from a claimed proposer->receiver table so any outsider โ€” auditor, CLI, test โ€” can run is_stable on a certificate it was handed rather than on one the library just produced. Matching values are deliberately read-only outside this package; this validating door is how they are made. -1 means unmatched.

    Preferences::new

    source
    fn Preferences::new(proposer_prefs : Array[Array[Int]], receiver_prefs : Array[Array[Int]]) -> Preferences raise ProfileError

    Build a market from raw ranking tables, rejecting empty markets, ragged rows, and rows that are not complete permutations of the other side's indices.

    Preferences::not_equal

    source
    fn Preferences::not_equal(x : Preferences, y : Preferences) -> Bool

    Preferences::to_repr

    source

    Side

    source
    pub(all) enum Side {
      Proposer
      Receiver
    } derive(Eq, 
    Debug    )

    Which side of the market a preference row belongs to.

    Side::equal

    source
    fn Side::equal(Side, Side) -> Bool

    Side::not_equal

    source
    fn Side::not_equal(x : Side, y : Side) -> Bool

    Side::to_repr

    source

    StabilityCert

    source
    pub struct StabilityCert {
      proposer_prefs : Array[Array[Int]]
      receiver_prefs : Array[Array[Int]]
      claim : Array[Int]
      witnesses : Array[Witness]
    } derive(Eq, ToJson, 
    Debug    , 
    FromJson    )

    A claimed market + matching + the witness table covering every tempting pair. Values are only meaningful together with verify.

    StabilityCert::equal

    source

    StabilityCert::from_json

    source

    StabilityCert::from_json_string

    source
    fn StabilityCert::from_json_string(s : String) -> StabilityCert raise

    Parse a delivered certificate (raises @json.ParseError or @json.JsonDecodeError on junk input, propagated undecorated).

    StabilityCert::not_equal

    source
    fn StabilityCert::not_equal(x : StabilityCert, y : StabilityCert) -> Bool

    StabilityCert::to_json

    source

    StabilityCert::to_json_string

    source
    fn StabilityCert::to_json_string(self : StabilityCert) -> String

    Serialize for delivery to a third party.

    StabilityCert::to_repr

    source

    StabilityCert::verify

    source
    fn StabilityCert::verify(self : StabilityCert) -> Unit raise

    Check a delivered certificate without recomputing anything. Raises the first defect found (or returns quietly, which IS the verdict: the market is stable under this matching). The only ranking knowledge used is prefers_before, shared with nothing in the mechanism files.

    Witness

    source
    pub struct Witness {
      proposer : Int
      receiver : Int
      holder : Int
    } derive(Eq, ToJson, 
    Debug    , 
    FromJson    )

    One line of evidence: proposer proposer courts receiver, and holder vouches that receiver ranks holder above proposer.

    Witness::equal

    source
    fn Witness::equal(Witness, Witness) -> Bool

    Witness::from_json

    source

    Witness::not_equal

    source
    fn Witness::not_equal(x : Witness, y : Witness) -> Bool

    Witness::to_json

    source
    fn Witness::to_json(Witness) -> Json

    Witness::to_repr

    source

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    ยฉ 2026 mooncakes.io