# 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

- 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

- The algorithm terminates with everyone engaged

8

Q

Correctness of Gale/Shapley (2/2)

A

- 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

- The algorithm produces a stable matching

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:

- (r, h)M r and h find each other acceptable
- Each resident is matched to at most one hospital
- 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