!1!Solutions for Problem Set 5 1. It is not at equilibrium. After one step updating, the PageRank value is A B C D E F G H Original 1/4 1/12 1/12 1/12 1/24 1/8 1/6 1/6 One-Step Update 1/4 1/12 1/8 1/12 1/24 1/8 1/6 1/8 The computation is the following, A: 1/6+1/12 = 1/4, B: 1/12, C: 1/12+1/24 = 1/8, D: 1/12, E: 1/24, F: 1/24+1/12 = 1/8, G: 1/24 + 1/8 = 1/6, H: 1/12. Since node C and node D get different numbers after one-step updating, it violates the definition of the equilibrium 2. (a). Assigning an unknown value ! to node A, and then compute the value for the subsequent nodes. A B C D E a a/2 3a/8 3a/4 13a/16 The computation is the following, A: a, B: a/2, D: 3a/4, C: 3a/8 E: a/4 + 3a/8 + 3a/16 = 13a/16. To normalize, we set A+B+C+D+E = 1, which is !(1+1/2+3/4+3/8+13/16) = 1. Hence, ! =!"!!. Plugging ! = 16/55 back to the above table, we have A B C D E 16/55 8/55 6/55 12/55 13/55 (b). Similar to (a), we assign ! to node A, and then get the following table A B C D E X a 2a/3 a/3 2a/3 5a/6 a/3 Doing the normalization, we get ! =!!". Hence, the above the table equals A B C D E X 6/23 4/23 2/23 4/23 5/23 2/23!2!The page rank of B went from 0.15 to 0.17, got higher (despite having an extra node), while E’s rank went from 0.24 to 0.22, down some. (c). Adding extra nodes such as X helps B’s page rank. If nodes A and B are in the same domain, under the same web manager, than adding such extra nodes to ”boost” B’s rank becomes possible. 3. (a). The matching is x—a , y—b, z—c. Letting the prices of slots be !!, !!, !!, any prices that satisfy the following inequalities clear the market, 0 ≤ !!≤ 10, 5 + !!≤ !!≤ 6 + !!, 12 + !!≤ !!≤ 16 + !!. (b). No, it is not a Nash equilibrium. The bidders who are not best responding to the other bidders are advertisers x and y. Currently x has a payoff of 10 = 8 − 6 ×5. If x bids less than 5 then x will get slot c at a price of 0 which results in a payoff of 16. Similarly, y can increase his profit by bidding less than z’s bid of 5. 4. (a). In the second price auction each bidder bids truthfully. So x bids 5, y bids 4 and z bids 2. Bidder x has the highest bid so he wins. The price that x pays is the second highest bid which is 4. (b). In the VCG procedure x will be assigned item a and the two fictional items, b and c, will be assigned to bidders y and z. (It does not matter which of fictional items is assigned to y and to z.) The price that x pays is the value that y and z could obtain without x but with the item that x receives, which is 4, minus the value that y and z could obtain without x and without the item that x receives, which is 0. So x pays 4 just as in the second price auction. This price is the harm that x creates for the other bidders as it is the reduction in the maximum value that they could obtain that is created by x taking item a. Bidders y and z pay nothing. Formally, !"#$% !"# = !!!!!− !!!!!!!, so !"#$!!!"# = !!!!!− !!!!!!!= 4 − 0 = 4 !"#$!!!"# = !!!!!− !!!!!!!= 5 − 5 = 0 !"#$!!!"# = !!!!!− !!!!!!!= 5 − 5 =