CS 70 Discrete Mathematics for CSSpring 2008 David Wagner Note 7Stable Marriage — An Application of Proof Techniques toAlgorithmic AnalysisConsider a dating agency that must match up n men and n women. Each man has an ordered preferencelist of the n women, and each woman has a similar list of the n men (ties are not allowed). Is there a goodalgorithm that the agency can use to determine a good pairing?ExampleConsider for example n = 3 men (represented by numbers 1, 2, and 3) and 3 women (A, B, and C), and thefollowing preference lists:Men Women1 A B C2 B A C3 A B CWomen MenA 2 1 3B 1 2 3C 1 2 3For instance, the preference lists above mean that woman A is man 1’s top choice; woman B is his secondchoice; and so on.What properties should a good pairing have? One possible criterion for a “good” pairing is one in which thenumber of first ranked choices is maximized. Another possibility is to minimize the number of last rankedchoices. Or perhaps minimizing the sum of the ranks of the choices, which may be thought of as maximizingthe average happiness. In this lecture we will focus on a very basic criterion: stability. A pairing is unstableif there is a man and a woman who prefer each other to their current partners. We will call such a pair arogue couple. So a pairing of n men and n women is stable if it has no rogue couples.An unstable pairing from the above example is: {(1,C),(2,B), (3, A)}. The reason is that 1 and B form arogue couple, since 1 would rather be with B than C (his current partner), and since B would rather be with1 than 2 (her current partner). This is trouble: Before long, 1 and B are going to spending many late nightsdoing CS70 problem sets together. Obviously, the existence of rogue couples is not a good thing if you area matchmaker, since they will lead to instability or customer dissatisfaction. That is why we focus on stablepairings.An example of a stable pairing is: {(2,A),(1, B), (3,C)}. Note that (1, A) is not a rogue couple. It is truethat man 1 would rather be with woman A than his current partner. Unfortunately for him, she would ratherbe with her current partner than with him. Note also that both 3 and C are paired with their least favoritechoice in this matching. Nonetheless, it is a stable pairing, since there are no rogue couples.The problem facing us is to find a stable pairing, given the preference lists for all n men and all n women.CS 70, Spring 2008, Note 7 1Does a Stable Pairing Always Exist?Before we discuss how to find a stable pairing, let us ask a more basic question: do stable pairings alwaysexist? Surely the answer is yes, since we could start with any pairing and make it more and more stable asfollows: if there is a rogue couple, modify the current pairing so that they are together. Repeat. Surely thisprocedure must result in a stable pairing! Unfortunately this reasoning is not sound. To demonstrate this,let us consider a slightly different scenario, the roommates problem. Here we have 2n people who must bepaired up to be roommates (the difference being that unlike the dating scenario, a person can be paired withany of the remaining 2n− 1). The point is that nothing about the above reasoning relied on the fact that mencan only be paired with women in the dating scenario, so by the same reasoning we would expect that therewould be a stable pairing for the roommates problem as well. The following counter-example illustrates thefallacy in the reasoning:RoommatesA B C DB C A DC A B DD – – –Visually, we have the following situation:What is interesting about this problem is that there is no stable pairing (i.e., there is always a rogue couple).For example, the pairing {(A, B),(C,D)} contains the rogue couple B and C. Using the reasoning above,we might decide to pair B and C together, giving us the pairing: {(B,C),(A, D)}. But this pairing is alsounstable because now A and C are a rogue couple. In fact, in this example there is no stable pairing. Thusany proof that there must be a stable pairing in the dating problem must use the fact that there are twogenders in an essential way.In fact, we shall show that, when we have n men and n women, a stable pairing always exists. This fact issomewhat surprising, but true.The Traditional Marriage AlgorithmWe will study what is sometimes called the “Traditional Marriage Algorithm” (TMA), so-called because itis based on a 1950’s model of dating where the men propose to the women, and the women accept or rejectthese proposals. We will prove that the Traditional Marriage Algorithm always finds a stable pairing andstudy its many interesting properties.The Traditional Marriage Algorithm works like this:Every Morning: Each man goes to the first woman on his list not yet crossed off and proposes to her.Every Afternoon: Each woman says “Maybe, come back tomorrow” to the man she likes best among themen who have proposed to her (she now has him on a string) and “No, I will never marry you!” to all therest.Every Evening: Each rejected suitor crosses off the woman who rejected him from his list.The above loop is repeated each successive day until there are no more rejected suitors. On this day, eachwoman marries the man she has on a string.We wish to show that this algorithm always outputs a stable pairing. But how do we even know that it mustterminate? Let us prove something stronger: the algorithm is guaranteed to terminate in at most n2days.CS 70, Spring 2008, Note 7 2Well, for each day (except the last), at least one woman is crossed off some man’s list. Since there are nmen, each starting with a list of size n, it follows that the algorithm must terminate after n2days.To establish that the pairing output is stable, we need the following crucial lemma:Improvement Lemma: If woman W has man M on a string on the kth day, then on every subsequent dayshe has someone on the string whom she likes at least as much as M.Proof: Suppose that on day ℓ (for some ℓ ≥ k) W has some man M′on a string, where she likes M′at leastas much as M. (Possibly M = M′.) Since she has M′on a string, that means that she told M′“maybe” onday ℓ. On day ℓ + 1, M′will come back and propose to W again, since he was told “maybe” the previousday. So W has the choice of at least one man on day ℓ + 1. Let M′′be her favorite choice among all of thosewho propose to her on day ℓ + 1. She will tell M′′“maybe” on day ℓ + 1, so on day ℓ + 1 she will have M′′on a string.
View Full Document
Unlocking...