8 - Graph Matching 4

Question 1

What are stable matching problems?

Answer 1

• 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

Question 2

What are definitions of the Stable Marriage problem?

Answer 2

• 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

Question 3

Example of stable marriage problem instance

Answer 3

Question 4

What is stability checking?

Answer 4

Question 5

Finding a stable matching

Answer 5

• 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

Question 6

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

Answer 6

Slides have short 2-slide example

Question 7

Correctness of Gale/Shapley (1/2)

Answer 7

• 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

Question 8

Correctness of Gale/Shapley (2/2)

Answer 8

• 2. 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

Question 9

What is the man-optimal property?

Answer 9

• 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.

Question 10

Implemenation of Gale/Shapley

Deciding wether w prefers m to m’

Answer 10

• 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’

Question 11

Implemenation of Gale/Shapley

Locating free men efficiently

Answer 11

• 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

Question 12

Analysis of Gale/Shapley algorithm

Answer 12

• 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

Question 13

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

Answer 13

• 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

Question 14

Hospital/residents problem example

see slides

Question 15

Hospitals/Residents problem (2/2)

Answer 15

• 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