Network Flow
network flow
OR 215 Spring 1998
Network Flows M. Hartmann
STABLE MATCHING PROBLEMS
Stable Marriage Problem
Propose and Reject Algorithm
Bipartite Stable Matching
Application: NRMP
Linear Programming Formulation
Non-Bipartite Stable Matching
STABLE MARRIAGE PROBLEM
A certain community consists of n men and n women. Each person has a strict preference over members of the opposite sex, for example:
Bengt: Anita, Christine, Elena Anita: Peter, Reid, Bengt
Peter: Christine, Elena, Anita Christine: Reid, Bengt, Peter
Reid: Elena, Anita, Christine Elena: Bengt, Peter, Reid
Note: The preferences must be strict, i.e. Elena cannot be indifferent between Bengt and Peter.
For a given matching, a man-woman pair is unstable if they are not married to each other, but prefer each other to their current mates. A perfect matching is said to be stable if it has no unstable pairs.
• Is the matching Bengt-Christine, Peter-Anita, Reid-Elena stable?
(consider Peter-Elena)
• Is the matching Bengt-Christine, Peter-Elena, Reid-Anita stable?
PROPOSE AND REJECT ALGORITHM
We will show constructively that every set of preferences admits a stable perfect matching.
Consider the following algorithm:
• Initially, all men and women are single.
• In each iteration, a man who is single proposes to the woman he prefers most among the women to whom he has not yet proposed.
• The woman that receives the proposal accepts it if she is single or if she prefers the proposing man to her current mate.
• In the latter case, the man disavowed becomes single again, and the algorithm continues to its next iteration.
• This courtship process ends when each single man has proposed to all of the women.
EXAMPLE
Suppose we replace Bengt by Cyrus, with preferences:
Cyrus: Christine, Elena,
OR 215 Spring 1998
Network Flows M. Hartmann
STABLE MATCHING PROBLEMS
Stable Marriage Problem
Propose and Reject Algorithm
Bipartite Stable Matching
Application: NRMP
Linear Programming Formulation
Non-Bipartite Stable Matching
STABLE MARRIAGE PROBLEM
A certain community consists of n men and n women. Each person has a strict preference over members of the opposite sex, for example:
Bengt: Anita, Christine, Elena Anita: Peter, Reid, Bengt
Peter: Christine, Elena, Anita Christine: Reid, Bengt, Peter
Reid: Elena, Anita, Christine Elena: Bengt, Peter, Reid
Note: The preferences must be strict, i.e. Elena cannot be indifferent between Bengt and Peter.
For a given matching, a man-woman pair is unstable if they are not married to each other, but prefer each other to their current mates. A perfect matching is said to be stable if it has no unstable pairs.
• Is the matching Bengt-Christine, Peter-Anita, Reid-Elena stable?
(consider Peter-Elena)
• Is the matching Bengt-Christine, Peter-Elena, Reid-Anita stable?
PROPOSE AND REJECT ALGORITHM
We will show constructively that every set of preferences admits a stable perfect matching.
Consider the following algorithm:
• Initially, all men and women are single.
• In each iteration, a man who is single proposes to the woman he prefers most among the women to whom he has not yet proposed.
• The woman that receives the proposal accepts it if she is single or if she prefers the proposing man to her current mate.
• In the latter case, the man disavowed becomes single again, and the algorithm continues to its next iteration.
• This courtship process ends when each single man has proposed to all of the women.
EXAMPLE
Suppose we replace Bengt by Cyrus, with preferences:
Cyrus: Christine, Elena,
References: H.G. Abeledo and U.G. Rothblum, “Courtship and linear programming,” Linear Algebra and Its Applications 216 (1995) 111-124. H.G. Abeledo and U.G. Rothblum, “Stable matchings and linear inequalities,” Discrete Applied Mathematics 54 (1994) 1-27. A.T. Benjamin, C. Converse and H.A. Krieger, “How do I marry thee? Let me count the ways,” Discrete Applied Mathematics 59 (1995) 285-292. D. Gusfield and R.W. Irving, The Stable Marriage Problem: Structure and Algorithms (MIT Press, Cambridge, 1989). A.E. Roth, “New physicians: a natural experiment in market organization,” Science 250 (1990) 1524-1528. A.E. Roth and E. Peranson, “The effects of the change in the NRMP matching algorithm,” Journal of the American Medical Association 278 (1997) 729-732. -----------------------