Question 3 Answer the following questions: 1. Give an example of rankings for three applicants 1,2, 3 and three jobs A, B, C. For which the Gale-Shapley algorithm (as presented in class) stops after three steps. 2. Consider the following rankings of applicants 1,2,3 and jobs A, B, C. Write all possible stable matchings for these rankings. You do not need to prove that they are stable. 1st 2nd 3rd 1 А В С Applicants 2 B A C |1st 2nd 3rd А 2 1 3 B1 2 3 C| 1 2 3 Jobs 3|А В С 3. Using the rankings from the previous part, identify which stable matching is the output of the Gale-Shapley algorithm as presented in class.
Question 3 Answer the following questions: 1. Give an example of rankings for three applicants 1,2, 3 and three jobs A, B, C. For which the Gale-Shapley algorithm (as presented in class) stops after three steps. 2. Consider the following rankings of applicants 1,2,3 and jobs A, B, C. Write all possible stable matchings for these rankings. You do not need to prove that they are stable. 1st 2nd 3rd 1 А В С Applicants 2 B A C |1st 2nd 3rd А 2 1 3 B1 2 3 C| 1 2 3 Jobs 3|А В С 3. Using the rankings from the previous part, identify which stable matching is the output of the Gale-Shapley algorithm as presented in class.
A First Course in Probability (10th Edition)
10th Edition
ISBN:9780134753119
Author:Sheldon Ross
Publisher:Sheldon Ross
Chapter1: Combinatorial Analysis
Section: Chapter Questions
Problem 1.1P: a. How many different 7-place license plates are possible if the first 2 places are for letters and...
Related questions
Concept explainers
Equations and Inequations
Equations and inequalities describe the relationship between two mathematical expressions.
Linear Functions
A linear function can just be a constant, or it can be the constant multiplied with the variable like x or y. If the variables are of the form, x2, x1/2 or y2 it is not linear. The exponent over the variables should always be 1.
Question
Please do all the questiosn if possible, that would be very helpful and apprecaited.
Transcribed Image Text:Question 3 Answer the following questions:
1. Give an example of rankings for three applicants 1,2,3 and three jobs
A, B, C. For which the Gale-Shapley algorithm (as presented in class)
stops after three steps.
2. Consider the following rankings of applicants 1,2,3 and jobs A, B,C.
Write all possible stable matchings for these rankings. You do not need to
prove that they are stable.
1st 2nd 3rd
1 А В С
Applicants 2 BAC
|1st 2nd 3rd
А 2 1 3
B1 2 3
C| 1 2 3
Jobs
АВ С
3. Using the rankings from the previous part, identify which stable matching
is the output of the Gale-Shapley algorithm as presented in class.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 4 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, probability and related others by exploring similar questions and additional content below.Recommended textbooks for you
A First Course in Probability (10th Edition)
Probability
ISBN:
9780134753119
Author:
Sheldon Ross
Publisher:
PEARSON
A First Course in Probability (10th Edition)
Probability
ISBN:
9780134753119
Author:
Sheldon Ross
Publisher:
PEARSON