Three boys, Alan, Bill, and Charlie, and three girls, Alice, Betsy, and Clara, are planning dates for the senior prom. Their preferences over possible partners are given in this table:

For example, Alan likes Alice best, Betsy second, and Clara third, while Alice likes Bill best, Alan second, and Charlie third.
(a) Suppose that partners are assigned by the deferred acceptance algorithm, where the boys ask the girls. On the first round, Alice will be asked by ________and ________. Betsy will be asked by ________. Clara will be asked by ________. Who does Alice refuse on the first round? ________ what happens on the second round? ________Clara what is the final assignment of partners? Alice is matched with ________, Betsy with ________, and Clara with ________. Verify that this assignment is stable.
(b) Suppose that instead they assign partners by the deferred acceptance algorithm, with the girls asking the boys. What is the final assignment of partners? Alice is matched with ________, Betsy is matched with ________, and Clara is matched with ________. Verify that this assignment is stable.
(c) In this example, which group is in general better off, the proposing sex or ________ to sex? The proposers (It turns out that this result is true in general. See David Gale and Lloyd Shapley:€College Admissions and the Stability of Marriage€, American Mathematical Monthly volume 69, pages 9-14, 1962.)
(d) Suppose that partners are assigned by the deferred acceptance algorithm, with the boys proposing. Alice knows everybody€™s preferences and believes that everybody else will act according to their true preferences. Can she get a better outcome by a bit of deception? Suppose that Alice chooses Charlie over Alan, what will happen in the second round? ________. What will be the final outcome? ________. Will Alice be better off than if she had played €œhonestly€ and picked Alan over Charlie? ________

Transcribed Image Text:

First Choice Third Choice econd Choice Person Alan Bill Charlie Alice Betsy Alice Betsy Alice Clara Clara Clara Betsy Alice Betsy Clara Bill Alan Alan Alan Bill Charlie Charlie Charlie Bill