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—in the interest of mathematical simplicity—assert that the number of engaged men equals precisely the number of engaged women.)

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:

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


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


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?

  1. People. Design a class that implements the Person interface.

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

  3. Termination. Prove that your courtship method terminates on all valid inputs, or give an example that causes courthship to run forever.

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