1. (40 points) a) Consider the pairwise exchange model, and draw the mutual compatibility graph for the following problem: = {(1,2), (2,3), (2,4), (4,5), (5,6)}.

b) Find the assignments prescribed by the Priority Mechanism with agent order (2, 5, 4, 6, 3, 1). Display the steps. Is it possible to match more patients to kidneys than in the solution(s) you found?

c) Given the Priority Mechanism, can patient 2 gain by not revealing that she is compatible with patient 3?