12 4/10: More Java (Stable Marriage)
Due: 4/10. Language: Java.
Daisy, Daisy, give me your answer, do.
I’m half crazy, all for the love of you.
It won’t be a stylish marriage! I can’t afford a carriage,
But you’ll look sweet, upon the seat of a bicycle built for two.
Marriage as a societal institution has been with us for many years, though in times of social flux or upheaval the stability of the institution is often subject to question, if not shaken outright. God made light, heavens and earth; He filled the seas with great whales; He created Man and Woman and commanded them to "be fruitful and multiply." First there was Adam and Eve... sometime later Abraham and Sarah, Isaac and Rebekah, and a long time afterwards Henry VIII and his succession of marriages, Elizabeth Taylor and Richard Burton (twice! or was it three times...), and so on to the current day. Without question, love is as powerful an emotion as it was in the good old days, but how love is manifested in marriage is as varied as the number of marriages that have taken place.
It is generally not recognized that, despite the emotive aspects of love and romance, marriage is fun- damentally an engineering problem. As such, it is amenable to a careful mathematical and computational analysis, emplying principles of programming and finite combinatorics. In this problem set, we will use the paradigm of message-passing programming, combined with the idea of encoding state information in procedures, to provide, for the first time in human history, a definitive solution to the problem of stability in marriage.
Let’s assume, for the sake of an argument, that you are a village matchmaker given the task of marrying 100 men and 100 women. Each of the men has ranked the women from 1 to 100 in the order of his preference; each woman, not to be outdone, has similarly ranked the 100 men. As a matchmaker, it is clear that in producing 100 couples, you will not be able to give each person his first choice: for example, if Alan is the first choice of all the women, only one will get him, and all other women will be left with their second (or worse) choices.
Rather than insist that everyone get their first choice, you are instead charged with creating 100 stable marriages. A set of marriages is said to be stable if there exists no man m and woman w such that m likes w better than his wife, and w likes m better than her husband. The notion is called "stability" as m’s and w’s marriages are unstable, since (albeit sordid and tawdry) m and w could optimize their sorry lot in life by leaving their mates and running off together.
The algorithm
We first describe in English an algorithm to find stable
marriages. Each person has a preference list of members of the
opposite sex. The first time a person proposes, it is to their number
one choice, the second time to their number two choice, and so on. We
will assume, without loss of non-sexist generality, that men always
propose to women (although there is no reason that it couldn’t happen
the other way around), and that the proposals occur in
rounds. At any moment in time, each person is either
engaged or unengaged, and of course initially everyone
is unengaged. (Assuming heterosexual alliances only, we can
further—
At the start of a round, each unengaged man is ordered by you, the matchmaker, to propose to the woman he loves most but as yet to whom he has not proposed. Each woman responds according to her status as given in the following case analysis:
Unengaged, received no proposals: Sit tight, life is bound to improve. Your prince will be arriving shortly.
Unengaged, received one proposal: Accept the proposal (the man and woman are now engaged).
Unengaged, received more than one proposal: Accept the proposal you like the best based on your preference list, telling the other suitors to buzz off (Wonder Man and woman now engaged).
Engaged, received no proposals: Declare your eternal and undying love to your sweetie.
Engaged, received one proposal: If you like the man who proposed more than your current main squeeze, dump your fiance and reengage yourself to this more inviting gentleman. You and the proposer are now engaged; Mr. Dumped is now unengaged. Otherwise, say "I’m flattered but I’m not interested," and declare your undying love for your intended.
Engaged, received more than one proposal: Choose the proposal you like best by looking at your preference list, and act as if you are currently engaged and this gentleman alone has proposed.
At the end of a round and the ensuing musical chairs, some men are engaged and others are not. If everyone is engaged, stop: the current pairs are the marriages that the matchmaker seeks. Otherwise, do another round.
Of course, no assurances have been made that the marriages produced are stable, or even that everyone is engaged at the end. For example, is it possible that a man proposes 100 times, exhausting his proposal list, and gets rejected every time? We’ll address these questions later on; for the moment, let’s assume that the method works correctly.
An Object Representation of People
Do you really believe that people are just computers, brain meat is nothing but a central processing unit, and the thoughts, hopes, and dreams that keep our life alive are nothing but software being executed? Of course not. (However, I’m sad to say, there are computer scientists and cognitive psychologists who do.) Nonetheless, for the purposes of this problem set, we will model certain salient features of people by objects:
Here is the interface, and some examples, for a person.
A Person implements: |
|
name : -> String |
The name of this person |
|
intended : -> [Maybe Person] |
This person's intended significant other, if any. |
|
preferences : -> [Listof Person] |
People this person would marry, in order of preference. |
|
possibles : -> [Listof Person] |
People this person has not proposed to, but is still interested in, in |
order of preference. |
|
loadPreferences : [Listof Person] -> Void |
Effect: set this person's prefences to the given list. |
|
reset : -> Void |
Effect: Reinitialize this person's intended (none), possibles (empty), and |
preferences (empty). |
|
propose : -> Boolean |
Effect: Propose to the most desired person not already proposed to. |
Produces true if proposal is accepted, false if rejected. |
|
iLoveYou : Person -> Boolean |
This message represents a proposal from the given person to this |
person. |
Effect: set the intended to the given person, if accepted. |
Produce true if accepted, false otherwise. |
|
iChangedMyMind : Person -> Void |
This message represents a break up from the given person to this |
person. |
Effect: set the intended to none. |
Assume: this person is the given person's intended and vice versa. |
|
iLikeMore : Person Person -> Boolean |
Does this person like the first person more than the second? |
|
isCouple : Person -> Boolean |
Are this person and the given person engaged to each other? |
People. Design a class that implements the Person interface.
Match making. Design the following method:
courtship : [Listof People] [Listof People] -> [Listof [Pairof String String]]
Effect: Marry all of the given proposers and proposees, producing
a stable configuration.
Produces a list of couple's name, proposer first.
The courtship method should be an implementation of the stable marriage algorithm described above.
Implement any additional methods or classes needed to implement the stable marriage algorithm.
Termination. Prove that your courtship method terminates on all valid inputs, or give an example that causes courthship to run forever.
Correctness. Prove that your courtship method always produces a stable marriage for any valid inputs, or give an example that results in an unstable configuration.