Networks: Fall 2013 Homework 5David Easley and´Eva Tardos Due at 11:15am, Friday, November 1, 2013As noted on the course home page, homework solutions must be submitted 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 uploading.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 after the posted due date. We cannot ac-cept late homework except for University-approved 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 Chapters 14.3-5 andChpater 15 of the book.(1) (8 points) Let’s consider the limiting PageRank values that result from the Basic PageR-ank Update Rule (i.e. the version where we don’t introduce a scaling factor s). In Chapter 14,these limiting values are described as “exhibiting the following kind of equilibrium: if we takethe limiting PageRank values and apply one step of the Basic PageRank Update Rule, then thevalues at every node remain the same. In other words, the limiting PageRank values regeneratethemselves exactly when they are updated.”B CFAED1/41/121/121/241/121/6G H1/81/6Figure 1: The network of Web pages for Question (1).1This description gives a way to check whether an assignment of numbers to a set of Webpages forms an equilibrium set of PageRank values: the numbers should add up to 1, and theyshould remain unchanged when we apply the Basic PageRank Update Rule. (See for exampleFigure 14.7 in Chapter 14 of the book.)Try this on the network of Web pages shown in Figure 1. In particular, say whether theindicated set of numbers forms an equilibrium set of PageRank values under the Basic PageRankUpdate Rule. Also, provide an explanation for your answer: specify either why they form anequilibrium, or how they fail to form an equilibrium.(2) )(12 points) Designers of Web content often reason explicitly about how to create pagesthat will score highly on search engine rankings. As a result, search engines need to have specialrules about links between pages from the same domain. In a scaled-down setting, this questionexplores the issues with such links.A B E D C Figure 2: The network of Web pages for Question (2).(a) Consider the network in Figure 2, and find the equilibrium PageRank values for thisnetwork. Give an explanation for your answer. (Hint: You can use the approach described inclass; let a denote the (unknown) PageRank value of node A, then work out the other PageRankvalues in terms of a, and then determine a value for a.)(b) Suppose the designers of Web page B are thinking of creating an additional Web pageX, and have convinced the owner of Web page A to help. They can now add links between A,B and X . They are thinking of adding a link from A to X and then from X to B. Find theequilibrium PageRank values for this new network with new node X and new links from A toX and from X to B. How did the pagerank of B change? How did it change relative to thepagerank of E?2(c) One issue that search engines have to worry about is “web spam”, efforts by somedomains to artificially increase the ranking of their pages. Explain how parts (a) and (b) ofthis question illustrate such an issue.(3) (10 points) Suppose a search engine has three ad slots (a, b and c) that it can sell. Slota has a clickthrough rate of 5, slot b has a clickthrough rate of 3 and slot c has a clickthroughrate of 2. There are three advertisers (x, y and z) who are interested in these slots. Advertiserx values clicks at 8 per click, advertiser y values clicks at 6 per click, and advertiser z valuesclicks at 5 per click.(a) Set up this problem of allocating slots to advertisers as a matching market in whichthe values per click, as well as the clickthrough rates, are known. Run the procedure that weused in Chapter 10 to construct market clearing prices. What are the market clearing pricesand what perfect matching between advertisers and slots occurs when you use these marketclearing prices? [You do not need to show the steps of the procedure. It’s enough to displaythe final prices and the perfect matching.](b) Suppose the search engine uses a form of the generalized second price auction in whicheach advertiser is asked to announce a bid per click. We will assume that all the advertisersknow their own value per click as well as the values per click for the other two advertisers.The advertiser with the highest bid per click gets the top slot (a) and pays per click the bidannounced by the second highest bidder, the advertiser with the second highest bid per clickgets the second slot (b) and pays per click the bid announced by the third highest bidder, theadvertiser with the third highest bid per click (in our case the bidder with the lowest bid perclick) gets the third slot (c) and pays 0 per click for slot (as there is no lower bid). In thisbidding game is it a Nash equilibrium for each advertiser to bid his true value per click? Thatis, is it a Nash equilibrium for advertiser x to bid 8 per click, advertiser y to bid 6 per click,and advertiser z to bid 5 per click? Explain.(4) (10 points) In lecture we discussed the relationship between the VCG Principle andsecond price auctions. In particular, we saw that the VCG Principle is a generalization of theidea behind second price auctions to a setting in which the seller has more than one object tosell. In this problem we will explore this relationship in an example. Suppose that a seller hasone item, lets call it item a. There are three buyers, lets call them x, y, and z. The values thatthese buyers (x, y, and z) have for the item are 5, 4, and 2, respectively.(a) Suppose that the seller runs a second price auction for the item. Which buyer will winthe auction and how much will this buyer pay?(b) Now lets suppose that the seller uses the VCG procedure to allocate the item. Rememberthat the first step in the running the VCG procedure when there are more bidders than itemsis to create fictional items, which each buyer values at 0, so that the number of items to beallocated is the same as the number of bidders. Lets call these additional items