2. Apart from twosided matching markets, onesided matching problems (aka assign ment problems), where only one side of the market has preferences, can also often be found. In course assignment problems students often need to be assigned to tutor groups at different times of the week. The material discussed in these tutor groups is identical within a week and tutors do not have preferences, but students do have pref erences for different times in their weekly schedule. This is an example of a onesided onetomany matching problem. In order to solve this type of onesided problem, we can implement the following algorithm: STEP 0: Each agent 7; reports her preferences >,- on objects. All agents are marked active. 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)