CS代考 CS 70 Discrete Mathematics and Probability Theory Fall 2021 – cscodehelp代写

CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Stable Matching
Consider the set of jobs J = {1, 2, 3} and the set of candidates C = {A, B, C} with the following preferences.
Jobs Candidates
1 A>B>C 2 B>A>C 3 A>B>C
Candidates Jobs
A 2>1>3 B 1>3>2 C 1>2>3
Run the traditional propose-and-reject algorithm on this example. How many days does it take and what is the resulting pairing? (Show your work.)
Stable Matching III
1. True or False?
(a) If a candidate accidentally rejects a job she prefers on a given day, then the algorithm ends with a rogue couple.
(b) The Propose-and-Reject Algorithm never produces a candidate-optimal matching.
(c) If the same job is last on the preference list of every candidate, the job must end up with its least preferred candidate.
CS 70, Fall 2021, DIS 2A 1
Propose-and-Reject Proofs
Asyou¡¯veseenfromlecture,thejobs-proposingPropose-and-RejectAlgorithmproducesanemployer- optimal stable matching. Let¡¯s see if the candidate have any way of improving their standing. Suppose exactly one of the candidates has the power to arbitrarily reject one proposal, regardless of which job she has on her string (if any). Construct an example that illustrates the following: for any n ¡Ý 2, there exists a stable matching instance for which using this power helps every candidate, i.e. every candidate gets a better job than she would have gotten under the jobs-proposing Propose-and-Reject Algorithm.