Homework 4 Solutions1a) Both traders have a monopoly. Therefore, Trader 1 is free to charge 1 to Buyer 1 andgive 0 to Seller 1, making a profit of 1 for himself. Trader 2 behaves the same way.So, the Nash Equilibrium in this case is for each trader to make a profit of 1 and forgoods to pass from Bito Sithrough Ti, i = 1, 2.1b) First of all, because each trader still has a monopoly over one buyer and one seller, eachtrader is guaranteed a profit of at least 1 by giving 0 to his seller and putting his askprice greater than or equal to 1. The only opportunity to make a profit strictly greaterthan 1 comes from dealing with B3. But if any trader chooses an ask price strictlygreater than 1, then B3will of course deal with whoever has the lower ask price. (Thisis an example of perfect competition.) In order for there to be Nash equilibrium, theask prices T1and T2set must be mutual best responses to each other, and thereforetheir ask prices must both be equal to 1.Now that we know that the ask prices of the traders will be equal to 1 in any NashEquilibrium, we also know that in any Nash Equilibrium B3will be involved in anexchange because he is the only buyer who is not indifferent between buying and notbuying (B3will have a payoff of 1 by exchanging and a payoff of 0 by not exchanging,whereas B1and B2will have payoffs of zero regardless). Therefore, the Nash Equilibriafor this example are 1) goods flow from B1to S1through T1and from B3to S2throughT2and 2) goods flow from B3to S1through T1and from B2to S2through T2, bothtraders making a profit of 1 in each case.COMMON MISTAKE: Some students claimed that there is some NashEquilibrium in which B3does not get a good. As explained above, this canNEVER happen because B3strictly prefers to buy a good once the ask pricesare set at 1. It is alright for B1or B2to not get a good because both areindifferent to whether they buy a good or not.COMMON MISTAKE: Some students argued that once the traders hadset their ask prices to 1, the traders were indifferent to which buyer theywere to trade with. This shows a misunderstanding of the model; in thetextbook, it is explained that there are two stages. The first is that traderssimultaneously set their buy and ask prices. The second is that the buyersand sellers simultaneously choose which trader(s) (if any) they want to dealwith.1c) In this case, there is only one buyer over whom T1and T2must compete, and the traderwho fails to deal with B3will get a profit of zero. As argued in 1b), in any equilibriumthe ask prices of the traders must therefore both be zero. Hence, the Nash Equilibriain this case are 1) goods flow from B3to S1and 2) goods flow from B3to S2, whereboth traders make a profit of 0 in each case.2a) The largest strongly connected component in this directed graph consists of the nodes1, 2, 5, 6, 8, 13, 14, 15, 16, since 1) for any two of these nodes there is a path from one to1the other, 2) it is not contained in any strictly larger strongly connected component,and 3) it contains more than half the nodes in the graph.COMMON MISTAKE: Note that node 9 is not included, since there is noedge from 9 to any of the nodes listed above.2b) Adding an edge from 11 to 4 (or 11 to 12) increases the size of the largest stronglyconnected component from part a) by 5 nodes: 9, 10, 11, 4, 7 (or 9, 10, 11, 12, 7). Thisis as large an increase as is possible for this graph, for the following reasons.There are only 8 nodes in the graph that were not already part of the largest stronglyconnected component from part a). It’s clear that by adding an edge it is impossibleto include both 4 and 12 simultaneously in a strongly connected component, so we canadd at most 7 nodes. If node 3 were to be added by addition of an edge, then the newedge would need to be outgoing from node 3. If the edge was from node 3 to some nodealready in the strongly connected component, only node 3 would be added. Having anedge from 3 to 9, from 3 to 10, from 3 to 11, or from 3 to 17 would not add node 3 tothe strongly connected component. The best option that is left is for the new edge tobe from 3 to 4 or 12, adding 3 nodes to the strongly connected component. Thus, wehave the choice of adding 3 nodes, or to leave node 3 out. The same is true for node17. Therefore, if there is any edge addition that leads to adding more than 3 nodes, itcan’t possibly be adding nodes 3 and 17 to the strongly connected component. Hence,at most 5 nodes can be added.Therefore, as we found an edge addition that adds 5 nodes to the graph, this gives thelargest possible increase in size of the strongly connected component from part a).COMMON MISTAKE: Some students added the 11-14 edge, which onlyincreases the size of the largest strongly connected component by threenodes.3a) In this network, the nodes that have the potential for their hub scores to change are theAi’s, and the nodes that have the potential for their authority scores to change are theBi’s and C. So we will refer to the former as hubs and the latter as authorities.In this initial round, we first update authority scores based on in-links and then updatehub scores. B1and C each have 3 incoming edges, soauth(B1) = auth(C) = 3.In the same way,auth(B2) = auth(B3) = 4Now, the hub scores are updated to be the sum of the authority scores for each authoritya given hub points to. So, as hubs A1, A2and A3all point to the same authorities,their hub scores will always be equal, and in this round are updated tohub(A1) = hub(A2) = hub(A3) = auth(B1) + auth(B2) + auth(B3) = 11For the rest,hub(A4) = auth(B2) + auth(B3) + auth(C) = 112andhub(A5) = hub(A6) = auth(C) = 3.Again, the hub scores of A5and A6will always be the same in any round because theypoint to the same authority (C).The sum of the current authority scores is 14, so the normalized authority scores forB1, B2B3and C are 3/14, 4/14, 4/14, and 3/14, respectively. The sum of the currenthub scores is 50, so the normalized hub scores for A1through A6are 11/50, 11/50,11/50, 11/50, 3/50 and 3/50, respectively.3b) For subsequent rounds, each authority score is first updated to be the sum of the hubscores of each hub pointing to a given authority, and hub scores are then updated.To make the comparisons asked for in parts c) and d), we need the normalized scoresfrom the first round and second round. Thus, we will be normalizing the scores atthe end of this second round as well. Whether we use the normalized or unnormalizedscores from part a) for our