STEP 1: Each agent 2', points to her most preferred object (possibly her own); each object points back to its owner. STEP 2: This creates a directed graph. In this graph, cycles are identied. Each agent has an outdegree (i.e., the number of directed edges departing from a vertex) equal to 1 , so that there exists at least one directed cycle in the graph. With strict preferences each agent is in at most one cycle. STEP 3: Each agent in a cycle is given the object she points at, and she is then removed from the market with her assigned house. STEP 4: If unmatched agents remain, jump to step 1 and iterate. (a) Consider a set of agents A : {1,2,3,4}, a set of objects 0 = {(1, b, c, d}, and the preference prole >~1 >'2 >'3 >4 d a, c b a d @ELC'rn @031. a. b 0 Applying the algorithm described above shows that the unique matching is p : {(1. C), (2, d), (3.6). (4. b)}- (20 P0111138) 3. Is the onesided matching algorithm strategy proof? (20 Points)