The deferred acceptance algorithm can be used to construct an assignment of men and women. In this algorithm, members of one gender are the suitors and members of the other gender the suitees. The algorithm uses a series of rounds; in each round every suitor whose proposal was rejected in the previous round proposes to his or her highest ranking suitee who has not already rejected a proposal from this suitor. The suitees reject all the proposals except that from the suitor that this suitee ranks highest among all the suitors who have proposed in this round or previous rounds. The proposal of this highest ranking suitor remains pending and is rejected in a later round if a more appealing suitor proposes in that round. The series of rounds ends when every suitor has exactly one pending proposal. All pending proposals are then accepted. a) Write the deferred acceptance algorithm in pseudocode. b) Show that the deferred acceptance algorithm terminates. c) Show that the deferred acceptance always terminates with a stable assignment
The deferred acceptance
members of one gender are the suitors and members of
the other gender the suitees. The algorithm uses a series of rounds; in each round every suitor whose proposal
was rejected in the previous round proposes to his or her
highest ranking suitee who has not already rejected a proposal from this suitor. The suitees reject all the proposals
except that from the suitor that this suitee ranks highest
among all the suitors who have proposed in this round
or previous rounds. The proposal of this highest ranking
suitor remains pending and is rejected in a later round if a
more appealing suitor proposes in that round. The series
of rounds ends when every suitor has exactly one pending
proposal. All pending proposals are then accepted.
a) Write the deferred acceptance algorithm in
pseudocode.
b) Show that the deferred acceptance algorithm
terminates.
c) Show that the deferred acceptance always terminates
with a stable assignment
Step by step
Solved in 4 steps
