# 8 - Graph Matching 4 Flashcards

1
Q

What are stable matching problems?

A
• A class of matching problems involving a stability criterion. The Stable Marriage problem
• Input: n men and n women; each person ranks all n members of the opposite sex in strict order of preference
• Output: a stable matching
2
Q

What are definitions of the Stable Marriage problem?

A
• A matching is a set of n disjoint (man,woman) pairs
• A blocking pair for a matching M is a (man,woman) pair (m,w)M such that:
• m prefers w to his partner in M, and
• w prefers m to her partner in M
• A matching is stable if it has no blocking pairs
3
Q

Example of stable marriage problem instance

A
4
Q

What is stability checking?

A
5
Q

Finding a stable matching

A
• A stable matching always exists for a given instance of the Stable Marriage problem
• A stable matching may be found in O(n2) time using the Gale/Shapley algorithm
6
Q

What is the Gale/Shapley (man oriented) algorithm?

A

Slides have short 2-slide example

7
Q

Correctness of Gale/Shapley (1/2)

A
1. The algorithm terminates with everyone engaged
* No man can be rejected by all the women
* Suppose man m was rejected by every woman
* Then all women have been engaged at some point
* But if a woman becomes engaged she is never again free
* Thus, once m is rejected by the last woman on his list, all women are engaged
* But, there are equal numbers of men and women and no man is engaged to more than one woman
* So all men are engaged, contradiction
8
Q

Correctness of Gale/Shapley (2/2)

A
1. The algorithm produces a stable matching
* It is immediate that the engaged pairs form a matching M
* Suppose m prefers w to M(m)
* Then m proposed to w at some point, and m was rejected by w
* So w was, or became, engaged to a man she prefers to m, so w prefers M(w) to m
* Thus (m,w) does not block M
* So M cannot have any blocking pairs, and hence is stable
* This establishes the correctness of the algorithm
• and also proves that a stable matching exists for every instance of the problem
9
Q

What is the man-optimal property?

A
• Note that the algorithm, as given, is non-deterministic the order in which free men propose is not specified
• Theorem:
• (i) All executions of the man-oriented Gale / Shapley algorithm yield the same stable matching M. (So the non-determinism is immaterial.)
• (ii) In this stable matching M, every man has the best partner he can have in any stable matching.
• Let M be the stable matching given by the man-oriented Gale/Shapley algorithm. We call M the man-optimal stable matching.
• Theorem: In the man-optimal stable matching, each woman has the worst partner that she can have in any stable matching.
• Similarly the woman-oriented Gale/Shapley algorithm (roles of men and women reversed) gives rise to the woman-optimal stable matching.
10
Q

Implemenation of Gale/Shapley

Deciding wether w prefers m to m’

A
• Assume that the input preference lists are represented as follows:
• mp(m, i)=w if woman w is at position i of m’s list
• wp(w, i)=m if man m is at position i of w’s list
• Construct women’s ranking lists:
• wr(w, m)=i if wp(w, i)=m
• so wr(w, m) < wr(w, m’) implies that w prefers m to m’
11
Q

Implemenation of Gale/Shapley

Locating free men efficiently

A
• Use a stack containing the free men
• Initially place all men on the stack
• The while loop iterates as long as the stack is nonempty
• Pop the stack to obtain the next free man to propose
• If a man is rejected, he is free again and is pushed onto the stack
12
Q

Analysis of Gale/Shapley algorithm

A
• Clearly the women’s ranking arrays can be found in O(n2) time
• Easy to keep track of the engaged pairs, and the next woman to whom a man will propose
• Each iteration of the while loop involves exactly one proposal
• No man ever proposes twice to the same woman
• So the total number of iterations is ≤ n2
• Therefore the complexity of the algorithm is O(n2)
• Notice that the Gale/Shapley algorithm runs in linear time in the input size
• an instance involves 2n preference lists, each of length n, hence 2n2 data values
13
Q

What is the Hospital/Residents problem (HR)? (1/2)

A
• n residents r1, r2, …, rn, m hospitals h1, h2, …, hm
• Hospital hi has capacity ci, i.e. has ci posts available
• Each resident chooses a subset of the hospitals and ranks them in strict order of preference
• h is acceptable to r if h is on r’s preference list, otherwise is unacceptable
• Each hospital ranks in strict order of preference the residents for whom it is acceptable
• A matching M in an instance of HR is an allocation of residents to hospitals such that:
1. (r, h)M r and h find each other acceptable
2. Each resident is matched to at most one hospital
3. No hospital exceeds its capacity
14
Q

Hospital/residents problem example

see slides

A
15
Q

Hospitals/Residents problem (2/2)

A
• A stable matching always exists for an instance of HR
• Such a matching may be found in linear time
• by a straightforward extension of the Gale-Shapley algorithm
• residents apply (propose) to hospitals in order of preference
• a hospital accepts a resident if it is undersubscribed
• if it is full, it compares (in constant time) the new resident to its least preferred assignee and rejects one of them accordingly
• a resident who is rejected by all hospitals remains unmatched
• An instance of HR may have many stable matchings
• but all stable matchings for a given instance have the same size and match the same set of residents
• there are resident-optimal and hospital-optimal stable matchings, analogous to man-optimal and woman-optimal