Question

In: Accounting

Stable matching: Determine a list of preferences for four men and four women where one proposer...

Stable matching: Determine a list of preferences for four men and four women where one proposer receives his or her lowest-ranked choice, and the rest of the proposers receive their penultimate choice. (please show how)

Solutions

Expert Solution

The Stable Marriage Problem: An Application of Induction in Understand-

ing Algorithms

A matchmaker must match up n men and n women. Each man has an ordered preference list of the n women,

and each woman has a similar list of the n men. Is there a good algorithm to pair1

them up?

Consider for example n = 3 men represented by numbers 1, 2, and 3 and three women A, B, and C, with the

following preference lists:

Men Women

1 A B C

2 B A C

3 A B C

Women Men

A 2 1 3

B 1 2 3

C 1 2 3

There are many possible pairings for this example, two of which are {(1,A), (2,B), (3,C)} and {(1,B), (2,C),

(3,A)}. How do we decide which pairing to choose? Let us look at an algorithm for this problem that is

simple, fast, and widely-used.

The Propose-And-Reject Algorithm2

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

the proposals (she now has him on a string) and “never” to all the rest.

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,

each woman marries the man she has on a string.

How is this algorithm used in the real world?

1Notice here that the focus is on actually doing the matching not in helping people discover their preferences. Preference-

discovery is a separate problem. We are assuming that all n of these men already know all n of these women quite well and

vice-versa. The only question is who will get married to whom.

2This algorithm, also known as the Gale-Shapley Algorithm, is based on a stereotypical model of courtship where the men

propose to the women, and the women accept or reject these propo.The Residency Match

Perhaps the most well-known application of the Propose-And-Reject Algorithm is the residency match pro-

gram, which pairs medical school graduates and residency slots (internships) at teaching hospitals. Grad-

uates and hospitals submit their ordered preference lists, and the stable pairing produced by a computer

matches students with residency programs.

The road to the residency match program was long and twisted3 Medical residency programs were first

introduced about a century ago. Since interns offered a source of cheap labor for hospitals, soon the number

of residency slots exceeded the number of medical graduates, resulting in fierce competition. Hospitals tried

to outdo each other by making their residency offers earlier and earlier. By the mid-40s, offers for residency

were being made by the beginning of junior year of medical school, and some hospitals were contemplating

even earlier offers — to sophomores! The American Medical Association finally stepped in and prohibited

medical schools from releasing student transcripts and reference letters until their senior year. This sparked

a new problem, with hospitals now making “short fuse" offers to make sure that if their offer was rejected

they could still find alternate interns to fill the slot. Once again the competition between hospitals led to an

unacceptable situation, with students being given only a few hours to decide whether they would accept an

offer.

Finally, in the early 50s, this unsustainable situation led to the centralized system called the National Res-

idency Matching Program (N.R.M.P.) in which the hospitals ranked the residents and the residents ranked

the hospitals. The N.R.M.P. then produced a pairing between the applicants and the hospitals, though at

first this pairing was not stable. It was not until 1952 that the N.R.M.P. switched to the Propose-And-Reject

Algorithm, resulting in a stable pairing.

Most recently, Lloyd Shapley and Alvin Roth won the Nobel Prize4

in Economic Sciences 2012, by extend-

ing the Propose-And-Reject Algorithm we study in this lecture!

3The same can actually be said about actual courtship processes in the United States. A readable reference for this is the book

“From front porch to back seat: courtship in twentieth-century America” by Beth Bailey.

In brief, historically courtship processes in the USA were built around an emphasis on the preference-discovery phase. Lots of

cultural institutions existed to encourage mixing, and core ideals of hospitality and politeness were invoked to prevent early binding.

Socially, people existed in exactly three categories: single, engaged to be married (a brief transitional period), and married. “Dates”

complemented and then largely supplanted the older “calling” tradition as technology and living arrangements changed. But there

was no exclusivity for single people. Marriage ages were relatively stable and in the mid-twenties.

The war created a huge shock to the system. With many men killed or wounded, a fear of being left alone accelerated the process

(arguably helped along by consumerism and the rising cult of female domesticity). Everything seemed to shift to younger and

younger ages. “Going steady” (sticking to a single partner exclusively in terms of going on dates) emerged and while it prompted

severe criticism from the older generation (who, quite reasonably, argued that going steady violated the most basic principle of

preference-discovery — to actually interact with different people at the same time and then also help set them up with others

through introductions — and furthermore, only exposed vulnerable young people to “temptation”), it became socially acceptable

as people raced to lock-in a partner. The marriage age plummeted until the median hit 18 years old by the early 1960s.

In the subsequent decades, the marriage age crept back up slowly. However, for a long time, the actual ages of “going steady”

(early-binding) and having a single partner for dates stayed stable and in most cases, began below even 18 years old. There is some

evidence that perhaps now, this trend is reversing and the social hold of “going steady” is being broken among youth


Related Solutions

In a study investigating the difference in food preferences between men and women, researchers asked subjects...
In a study investigating the difference in food preferences between men and women, researchers asked subjects to indicate whether they like or disliked certain foods. One question was about lamb. Twenty percent of a sample of 75 men disliked lamb, while 38% of a sample of 100 women indicated that they disliked lamb. Test the claim that there is a difference in the proportions of men and women who dislike lamb. Indicate the correct set of statistical hypotheses for this...
[12] In an experiment on human behavior, a psychologist asks four men and four women to...
[12] In an experiment on human behavior, a psychologist asks four men and four women to enter a room and sit at a rectangular table. This table has three seats on each of the longer sides of the table, and one seat at each end of the table. The seats at the end of the table are considered to be the dominant seats. (A diagram may help you to visualize this). a. If the people choose their seats randomly, determine...
A recent study of gender preferences among car shoppers found that men and women equally favor...
A recent study of gender preferences among car shoppers found that men and women equally favor economy cars. A marketing analyst doubts these results. He believes that a person’s gender influences whether or not he/she purchases an economy car. He collects data on 400 recent car purchases cross-classified by gender and type of car (economy car versus noneconomycar). The results are shown as follows: ECONOMY CAR NON-ECONOMY CAR FEMALE 50 60 MALE 120 170 a. State null and alternative hypotheses...
A researcher wants to determine if there is a significant difference between men and women in...
A researcher wants to determine if there is a significant difference between men and women in terms of guilty/non guilty pleas submitted by a sample of 50 defendants. Knowing that there are 25 women and 25 men in this sample and that 15 men entered guilty pleas [and 10 no guilty pleas] and 5 women entered guilty pleas [and 20 no guilty pleas]… [Hint: Calculated Chi-Sq. = 8.33] Formulate the null and research/alternative hypotheses. Create a contingency table with 2...
Stability vs., Pareto Efficiency in the marriage market (i.e., a one-to-one matching market with strict preferences)....
Stability vs., Pareto Efficiency in the marriage market (i.e., a one-to-one matching market with strict preferences). (a) Show that stable matchings are Pareto efficient. That is, for any stable matching µ between a group of men M and a group of women W, there is no matching µ 0 such that µ 0 (a) µ(a) for all agents, and the preference is strict for at least one agent. (b) Is any Pareto efficient matching stable? Prove or give a counter-example.
A physical therapist wants to determine the difference in the proportion of men and women who...
A physical therapist wants to determine the difference in the proportion of men and women who participate in regular sustained physical activity. a. What sample size should be obtained if she wishes the estimate to be within two percentage points with 99​% ​confidence, assuming that she uses the estimates of 22.9​% male and 19.1​% female from a previous year? b. What sample size should be obtained if she wishes the estimate to be within two percentage points with 99​% ​confidence,...
A physical therapist wants to determine the difference in the proportion of men and women who...
A physical therapist wants to determine the difference in the proportion of men and women who participate in regular sustained physical activity. What sample size should be obtained if she wishes the estimate to be within two percentage points with 90​% ​confidence, assuming that ​(a) she uses the estimates of 21.7​% male and 19.5​% female from a previous​ year? n=__ ​(Round up to the nearest whole​ number.) ​(b) she does not use any prior​ estimates? n=___ ​(Round up to the...
A physical therapist wants to determine the difference in the proportion of men and women who...
A physical therapist wants to determine the difference in the proportion of men and women who participate in regular sustained physical activity. What sample size should be obtained if he wishes the estimate to be within two percentage points with 99 % confidence, assuming that (a) hehe uses the estimates of 22.4 % male and 18.5 % female from a previous year? (b) he does not use any prior estimates?
A physical therapist wants to determine the difference in the proportion of men and women who...
A physical therapist wants to determine the difference in the proportion of men and women who participate in regular sustained physical activity. What sample size should be obtained if he wishes the estimate to be within three percentage points with 99​% ​confidence, assuming that ​(a) he uses the estimates of 21.3​% male and 19.6​% female from a previous​ year? ​(b) he does not use any prior​ estimates? ​(a) n equals nothing ​(Round up to the nearest whole​ number.)
A physical therapist wants to determine the difference in the proportion of men and women who...
A physical therapist wants to determine the difference in the proportion of men and women who participate in regular sustained physical activity. What sample size should be obtained if he wishes the estimate to be within two percentage points with 99​% ​confidence, assuming that ​(a) he uses the estimates of 22.6​% male and 18.9​% female from a previous​ year? n=____ ​(b) he does not use any prior​ estimates? n=____
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT