3. (18 pts) I11 this problem, we look for other properties of Top Trading Cycle (TTC) algorithm that we learned in the class. I11 the original setting of house allocation problem, we don't have a social welfare function to maximize. Here, we dene a social welfare function and figure out whether TTC algorithm is welfare-maximizing. Recall from the original setting, there are in houses (In, ..., an) and 11 agents (named 1, ...,-11). Agent 2' owns h, at first. Each agent's preferences are represented by a total ordering over h1,...,h,,. (a) (1 pt) Suppose n = 4 and agents1 order of preference over houses is as following. For example, Agent 1 prefers F12 the most, and I11 the least. Agent 1 : 312 > by, > 1'14 > .311 Agent 2 : In > In; > hg > .312 Agent 3 : In > flg > hg > F14 Agent 4 : 312 > 1'11 > fig > .314 Find the allocation of houses in the TCC algorithm. We define 9(1) as the index of house (one of 1, ..n) which is allocated to agent 2' by TTC algorithm. We further define am E {1, 2, .., n} as agent is ranking of house hj in his total ordering over h1,...,hn. For the preference given in part (a), (11,2 2 4,013 = 3,a-1,4 = 2,111,] = 1. The higher am, the more agent 1' prefers house It): We dene the social welfare f of an allocation of houses, 9, as follows. Here 9 can be viewed as one-to-one correspondence between agents and houses. This social welfare function indicates how much the agents like their new houses. For example, if agent 1,2,3,4 were assigned to houses h2,h3,hl,h4, then 9(1) 2 2, 9(2) 2 3, 9(3) 2 1, 9(4) 2 4. With the example given in part (a), we have 4 \"9) = 205,96) = a1,2 + (12,3 + (13.1 + (14,4 1:] (b) (2 pts) Calculate the social welfare, g) for the example in part (a) above. Now consider arbitrary n and (rigs. (c) (5 pts) Prove that f(9) 2 2:1 (1-1-9. Note that (1-1-9- is agent i's preference for her original house. (d) (5 pts) Prove that f(9) 2 \"32. (e) (5 pts) Prove or disprove that 9 maximizes f(9) among all the possible allocations