Question

1. [Stable Matching] a. [Roommate] Let us assume there are 4 roommates who applied for housing at CSUSB and we want to find the best way to pair them. Consider these preference lists: A: B, C, D B: C, A, D C: A, B, D D: A, B, C Can you find a stable matching? Show work. b. [Colleges Choosing] Find the stable matching using Gale-Shapley algorithm for the following preference lists: College preference lists CSUSB: Tahani, Juan, Maria, Kevin MU: Maria, Kevin, Juan, Tahani UCR: Maria, Tahani, Juan, Kevin UOP: Maria, Juan, Tahani, Kevin Student preference lists Maria: UCR, UOP, MU, CSUSB Kevin: UCR, CSUSB, UOP, MU Juan: CSUSB, MU, UCR, UOP Tahani: CSUSB, UOP, MU, UCR

Answer 1

pst 2nd god A B C DM B: A Dout C: A B D. D : A B C favourite less favourite Ans: No perfect matching is stable » A-B, C-D A-C, B-D A-D , B-C B-C A-B A-C unstable unstable unstable »

GALE - SHAPLEY (Preference list Colleges or for and universities students) INITIALIZE M to empty matching WHILE ( some college c is unmatched and - hasn't proposed to every student) s t first student on a's list to whom c has not yet proposed IF (s is unmatched) - Add c-s to matching M ELSE IF (s prefers c to current partner c Replece c'es with cus in M ELSE s rejects a Here c = college so student

ct: Date Stable Matching CSUB - Tahani UCR - Maria MU - Juan Uop - Kevin