Networks: Fall 2013 Homework 4David Easley and´Eva Tardos Due at 11:15am, Friday, October 25, 2013As noted on the course home page, homework solutions must be sub mi t te d by upload to course’sBlackboard site. The file you upload must be in PDF format. It is fine to write the homeworkin another format such as Word; from Word, you can save the file out as PDF for uploadin g .You can choose type ”pdf” when you save the file, or print it and choose ”Adobe pdf” as yourprinter. (Changing the file extension from doc, or docx to pdf does not change the format, onlymakes the file unreadable)Blackboard will stop accepting homework uploads afte r the posted due date. We cannot ac-cept late homework except for University -a p p r oved excuses (which include illness, a familyemergency, or travel as part of a University sports team or other University activity).Reading: The questions below are primarily based on the material in Chap t er s 11, 13 and14.1-2 of the book. (The rest of Chapter 14 is deferred to the next problem set.)(1) (10 p oi nts) Consider the trading network with intermediaries in Figure 1 in which thereare two sellers S1and S2(on the left), two buyers B1and B2(on the right) and two traders(intermediaries) T1and T2. Each seller can trad e with only one trader; trader T1for sellerS1and trader T2for seller S2. Buyer B1can only trade with trader T1. Buyer B2can onlytrade with trader T2. Both sellers value th e good at 0 and both buyers value th e good at 1, asindicated on the figure.S1 S2 B1 B2 T2 T1 1 1 0 0 Figure 1: The network buyers, sellers and traders for Question ( 1 ).1(a) Describe what all possible Nash equilibria are, including both prices and the flow ofgoods. How much profit can each trader make? Give a brief ex p l a n at i o n for your answer.(b) Now assume we add an extra buyer B3who can trade with either trader T1and T2, andwho has value 2 for the good. Describe what all possible Nash equilibria ar e now, includingboth pri ces and the flow of goods. How much profit can each trader m ake? Is it the same as inpart (a) ? Give a brief expl a n a t i o n for your answer to the question about profits.(c) Now suppose we no longer have either of the two buyers B1and B2around (only buyerB3). Describe what all possible Nash equilibria are now, including both prices and the flow ofgoods. How much profit c an each trader make? is it the same as in parts (a) or (b)? Give abrief expla n a ti o n for your answer to the question about profits.7481215136523101411911617Figure 2: The network of Web pages for Question (2).(2) (10 points) Consider the directed graph shown in Figure 2, with nodes representing Webpages and each directed ed g e representing a link from one Web page to another.(a) List the nodes in the largest strongly connected co m ponent of this graph.(b) As new links are created or old ones are removed among an existing set of Web pages,such as the one in Figu re 2, t h e set of n odes in the largest strongl y connected co m ponent canchange. Here’s an example of how such a change can occur, thr ou g h the addition of an edge.2Suppose you are allowed to add one link to the graph in Figure 2, going from on e no d e inthe figure to another; which link would you add if you wanted to increase the size of the largeststrongly co n n ect ed component by as much as possible? Give an explanation for your answer.(3) (10 points) One of the basic ideas b ehind the computation of hubs and authorities is todistinguish between pages that have multiple reinforcing endor sem ents a n d those that simplyhave high in-d e gr ee. (Recall that the in-degree of a node is the numbe r of links coming into it.)To explore this issue consider the network of Web pages in Fig u r e 3.(a) Show the values that you get if you run one round of computing hub and authorityvalues on the network of Web pages in Figure 3. (That is, the values com p u t ed by the hub-authority computation when we start with computing values for authorities, and then valuesfor hubs.)Show the values both before and after the final normalization step, in which we divide eachauthority score by the sum of all authority scores, and divide each hub score by the sum ofall hub scores. (We will call the scores obtained after this dividing-down step the normalizedscores. It’s fine to write the normalized scores as fractions rather than decimals. )A1 A5 A4 A6 A2 A3 B1 C B2 B3 Figure 3: The network of Web pages for Question (3).(b) Show the values that you get if you run a second rounds of computing hub and authorityvalues on the network of Web pages in Fi gu r e 3. (That i s, the va l u es computed by continuingthe hub-authority computation with computing one more round of values for authorities, andthen values for hubs.)(c) Both nodes B1and C have degree 3. How did the scores of these nodes change? Explainthe di ↵er en ce in a way understandable to people not taking this course: explain which one islikely to be a better page and why.3(d) How did the scores of nodes A1and A4change. Explain in the di↵eren ce in a wayunderstandable to people not taking this course: explain wh i ch one is likely to be a b et te r pageand