Discussion 1B

Induction Problem

A party has people. A celebrity is a person who knows nobody, but everyone knows the celebrity. If you ask questions of the form Does know ? prove that you can figure out who the celebrity is (or that there is no celebrity) using questions.

Stable Marriage

There are men and women. Each man has his own preference list of the women, and likewise for the women. The goal is to pair up the men and women according to their preferences.

Definitions

Stable Marriage Algorithm

The men go down their lists, proposing to women. When a woman receives multiple proposals, she keeps her favorite man on her string and rejects the other men, who continue down their lists. The algorithm ends when every woman receives one proposal.

Improvement Lemma - if a woman has a man on her string, then for every day after she will either have the same man or a better man on her string

Theorem - the algorithm always terminates with a male-optimal stable pairing

Worksheet

1. Stable Marriage

The algorithm takes four days (it terminates on the fifth) and the final pairing is .

2. Propose-and-Reject Proofs

a The Improvement Lemma says if a woman receives a proposal, then on each day after she will either have the same man on her string or get proposals from better men.

b Suppose for the sake of contradiction that she receives no proposal on day but receives a proposal on a previous day . Then using part a, since she receives a proposal on day she receives proposals for all subsequent days, including day . This contradicts the assumption that she receives no proposal on day .

c Let the number of days the algorithm takes be . Since the algorithm ends, every woman has a proposal on day . Since the algorithm does not end on day , there is some woman who does not have a proposal on day . Then using part b, she did not receive proposals on all days before , so she only receives one proposal (on day ).

3. Be a Judge

a False. If this were true that would mean every man gets rejected times and every woman gives rejections. This contradicts what we proved before: that there is some woman who is proposed to exactly once.

If , can this be true?

b True. Suppose they aren’t paired, so that in the final pairing we see the pairs and . In this final pairing, and form a rogue couple since they each prefer the other over their current partners. Therefore this isn’t a stable pairing.

c False. Consider the counterexample with with men and and women and . Both men have the preference list and both women have the preference list . The algorithm terminates with the pairing .

d True. If for every pair they each have the other as their least favorite partner, then any other choice of and is a rogue couple.

Induction Problem Solution

Base case

For , we ask the two questions Does know ? and Does know ?

Inductive hypothesis

Assume that at a party with people we can figure out who the celebrity is using questions.

Inductive step

Our goal is to show that at a party with people we need to use questions. First we ask Does know ? If knows , then is not a celebrity; otherwise, if does not know , then is not celebrity. In both cases, we are left with people who are potentially celebrities. So, we can use our inductive hypothesis and ask questions to learn one of the following:

  1. There’s no celebrity among the people, and since the person we excluded is not a celebrity, we know there is no celebrity among the people. We use one additional question, meaning we ask a total of questions.
  2. There’s a celebrity among the people, but we need to check whether this person is still a celebrity among the people. This requires us to ask two questions: whether the potential celebrity and the th person know each other. We use three additional questions, meaning we ask a total of questions.