Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Class 15: Stable Matchings


Schedule

There is no class Thursday (Oct 20). Please use the class time to do something worthwhile and fulfilling, preferably outdoors.

Problem Set 6 (is posted now) is due 21 October (Friday) at 6:29pm.

Links

Download the full matching code: matching.py (assertions and comments removed here for space)

We didn’t get to talk about Secure Stable Mathing today, but will in a future class. (For now, feel free to read the links, of coure.)

How Game Theory Helped Improve New York City’s High School Application Process, New York Times, 5 December 2014.

National Resident Matching Program (how medical school graduates are matched to residency programs)

Can anyone else see my rank order list (ROL)?
Your rank order list is confidential. Program rank order lists can be seen only by the program director and coordinator, the institutional official and administrator, and NRMP staff (unless you give your username and password to someone else, which is a violation of the Match agreement). (Frequently Asked Question on NRMP)

Secure Stable Matching: Jack Doerner (UVA BSCS and Studio Art, 2015), David Evans, abhi shelat. Secure Stable Matching at Scale. In 23rd ACM Conference on Computer and Communications Security (CCS). Vienna, Austria. 24-28 October 2016.

Stable Matching

Definition. $M = { (a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n) }$ is a stable matching between two sets $A = { a_1, \cdots, a_n }$ and $B = { b_1, \cdots, b_n }$ with respective preference orderings $\prec_A$ and $\prec_B$ if there is no pair $(a_i, b_j)$ where $bi \prec{a_i} b_j$ and $aj \prec{b_j} a_i$.

How do we know there is always a stable matching between any two equal-size sets?

##

Gale-Shapley Algorithm

def gale_shapley(A, B):
    pairings = {} # dictionary b: a pairings
    unpaired = set(a for a in A.keys()) # unpaired a's
    proposals = {a: 0 for a in A.keys()} # keep track of who gets next proposal

    while unpaired:
        a = unpaired.pop()
        ap = A[a] # a's preference list
        assert proposals[a] < len(ap)
        choice = ap[proposals[a]]
        proposals[a] += 1
        if choice in pairings: # a's choice already has a match
            amatch = pairings[choice]
            bp = B[choice]
            if bp.index(a) < bp.index(amatch):
                pairings[choice] = a
                unpaired.add(amatch) # lost match
            else:
                unpaired.add(a)
        else:
            pairings[choice] = a
    return [(a, b) for (b, a) in pairings.items()]
A = {"Anna": ["Kristoff", "Olaf"], "Elsa": ["Olaf", "Kristoff"]}
B = {"Kristoff": ["Anna", "Elsa"], "Olaf": ["Elsa", "Anna"]}
gale_shapley(A, B)

Modeling the Gale-Shapley program as a state machine

$S = $

$G = $

$q_0 = $

Prove termination. The Gale-Shapley program, modeled by the state machine, eventually returns.

#

#

Prove correctness. The Gale-Shapley program returns a stable matching of the two input sets and preferences.