Stable matching and five representative problems

Stable matching problem

Solution pseudocode:

Initially all m in M and w in W are free 
While there is a free m 
	w highest on m’s list that m has not proposed to 
	if w is free, then match (m, w)
	else 
		suppose (m2 , w) is matched 
		if w prefers m to m2
			unmatch (m2 , w) 
			match (m, w)

python implementation:

def gale_shapley(*, A, B, A_pref, B_pref):
    """Create a stable matching using the
    Gale-Shapley algorithm.
    
    A -- set[str].
    B -- set[str].
    A_pref -- dict[str, list[str]].
    B_pref -- dict[str, list[str]].

    Output: list of (a, b) pairs.
    """
    B_rank = pref_to_rank(B_pref)
    ask_list = {a: deque(bs) for a, bs in A_pref.items()}
    pair = {}
    #
    remaining_A = set(A)
    while len(remaining_A) > 0:
        a = remaining_A.pop()
        b = ask_list[a].popleft()
        if b not in pair:
            pair[b] = a
        else:
            a0 = pair[b]
            b_prefer_a0 = B_rank[b][a0] < B_rank[b][a]
            if b_prefer_a0:
                remaining_A.add(a)
            else:
                remaining_A.add(a0)
                pair[b] = a
    #
    return [(a, b) for b, a in pair.items()]

Use case

matching internship applicant to companies. The matching should be self enforcing and have less chaos.

We want both parties to either:

• perfer thier choice of matching
• satisfied with the current selection and will not change.

In the applicant and companies example, this means: E prefers every one of its accepted applicants to A; or (ii) A prefers her current situation over working for employer E.

Five representative problems

#Algorithm

1. Interval scheduling
2. Weighted interval scheduling
3. Bipartite Matching
4. Independent Set
5. Competitive facility location

Interval scheduling

Usually is solved using some kind of greedy algorithm

Weighted interval scheduling

Usally solved using dynamic programming

Bipartite Matching

It is like stable matching but without preferences.

there is not necessarily an edge from every x ∈ X to every y ∈ Y, so the set of possible matchings has quite a complicated structure. In other words, it is as though only certain pairs of men and women are willing to be paired off, and we want to figure out how to pair off many people in a way that is consistent with this.

Usally solved using augmentation, which is the key to a subset of problem s called network flow problems.

Independent Set

For example, the maximum size of an independent set in the graph in Figure 1.6 is four, achieved by the four-node independent set {1, 4, 5, 6}.

This belongs to the class of prbolems called NP-complete problems.

Competitive facility location

Thus our game consists of two players, P1 and P2, alternately selecting nodes in G, with P1 moving first. At all times, the set of all selected nodes must form an independent set in G. Suppose that player P2 has a target bound B, and we want to know: is there a strategy for P2 so that no matter how P1 plays, P2 will be able to select a set of nodes with a total value of at least B? We will call this an instance of the Competitive Facility Location Problem.

It is considered in the class of problsm called PSPACE-complete problems. It is harder the NP-complete problems