Untitled Deck Flashcards
(16 cards)
What is the Stable Matching Problem?
A problem of matching n jobs with n candidates based on their ordered preference lists.
What algorithm is used to solve the Stable Matching Problem?
Propose-and-Reject algorithm (Gale-Shapley algorithm).
What is the objective of the Stable Matching Problem?
To create a matching where no individual can benefit by switching jobs.
What happens every morning in the Propose-and-Reject algorithm?
Each job proposes to its most preferred candidate who has not yet rejected it.
What does each candidate do every afternoon in the Propose-and-Reject algorithm?
Collects offers and responds ‘maybe’ to the most preferred offer and rejects others.
What does a rejected job do every evening in the Propose-and-Reject algorithm?
Crosses off the candidate who rejected its offer from its list.
What is the output of the Propose-and-Reject algorithm in the example provided?
{(Approximation Inc., Anita), (Basis Co., Bridget), (Control Corp., Christine)}.
What is a significant application of the Stable Matching Algorithm?
The residency match program for pairing medical graduates with residency slots.
Why were medical residency programs introduced?
To provide a source of cheap labor for hospitals.
What issue arose with the number of residency slots and medical graduates?
The number of residency slots exceeded the number of medical graduates.
What was the impact of hospitals competing for residency candidates?
Hospitals began making residency offers earlier to attract graduates.
Fill in the blank: The Propose-and-Reject algorithm is also known as the _______.
Gale-Shapley algorithm.
True or False: The Propose-and-Reject algorithm guarantees a stable matching.
True.
What is the significance of having no ‘exploding offers’ in the Propose-and-Reject algorithm?
It ensures that a job cannot withdraw an offer once made.
How does the Propose-and-Reject algorithm ensure stability in matchings?
By preventing any pair of individuals from preferring each other over their current matches.
List the steps of the Propose-and-Reject algorithm.
- Jobs propose to preferred candidates
- Candidates respond to offers
- Rejected jobs update their preference lists
- Repeat until no offers are rejected.
