collections/stable_matching_utils library

Stable matching via Gale-Shapley — roadmap #448.

Given two disjoint sides — proposers and acceptors — each ranking some or all members of the other side, find a stable matching: a pairing in which no proposer/acceptor pair would both prefer each other over their current assignment. The classic application is matching applicants to positions.

This is the proposer-optimal Gale-Shapley algorithm: among ALL stable matchings, every proposer gets the best acceptor it can have in any stable matching (and, dually, every acceptor gets its worst). The algorithm always terminates in a stable result.

Edge cases handled: unequal set sizes (extra members on either side stay unmatched), incomplete preference lists (a party that does not list someone prefers to stay unmatched rather than be paired with them), and the absence of ties (preferences are strict — each list is a ranking with no duplicates). Malformed input (a preference list referencing an unknown party, or a duplicate within one list) throws ArgumentError.

Functions

stableMatching(StableMatchingPrefs prefs) → Map<String, String>

Computes a stable matching from prefs, returning proposer → acceptor for every matched proposer; unmatched proposers are absent from the map.

Typedefs

StableMatchingPrefs = ({Map<String, List<String>> acceptors, Map<String, List<String>> proposers})

Preference data for one stable-matching problem: each side maps a member to its strict ranking (index 0 = most preferred) of the other side.