Networked Life-Homework 3 Solved

Exercise 1. A simple ad space auction (exercise 2.1 in book)   
Three advertisers (1, 2, 3) bid for two ad spaces (A, B). The average revenues per click   are $6, $4, $3 for the bidders, respectively, and the clickthrough rate of the ad spaces are 500, 300 clicks per hour respectively (assumed not to depend on which advertiser uses the ad space).

 

a    Draw the bipartite graph with nodes indicating advertisers/ad spaces and edges indicating values per hour. Indicate the maximum matching with bold lines.

b    Assume a GSP auction with truthful bidding, what is the result of the auction in terms of the allocation, the prices charged, and the payoffs received?

 

Exercise 2. eBay auction (exercise 2.2 in book)  

Alice lists a lamp for sale on eBay via auction with both the start price and reserve price set to $7.00 and a duration of 5 days. The minimal increment is $0.25 and the following events happen during the auction:

•   Day 1 Bidder 1 uses a proxy agent, setting the maximum bid up to $11.00.

•   Day 2 Bidder 2 bids $9.25.

•   Day 3 Bidder 3 uses a proxy agent, setting the maximum bid up to $17.25.

•   Day 4 Bidder 2 bids $13.65.

•   Day 5 Bidder 1 uses a proxy agent, setting the maximum bid up to $27.45.

List the bidding history of all three bidders over each day of the auction. Who is the winner and what price does she pay?

Exercise 3. More items than bidders (exercise 2.3 in book)    
Alice and Bob are bidding for three ad slots on a webpage, and one bidder can win at most one slot. Assume that both bidders have the same quality score and they bid at the beginning of the day. Also assume that they bid once at the beginning of the day and their bids remain the same during the rest day (i.e., the slot allocation will be determined once). Under this assumption, whoever wins slot 1, 2 or 3 will get a total rate (to her website) of 500, 300 or 200 clicks per hour, respectively. Assume that Alice profits $r per click it receives.

 

a    Denote by b1 and b2 the bids by Alice and Bob respectively. In a GSP auction, discuss Alice’s payoff in terms of b1 and b2.

b    Does Alice have a dominant strategy? If so, what is it? Hint: compute the net payoff and the best response 𝑏1 (perhaps a set of values) of Alice as a function of 𝑏2 that is assumed fixed. Check if there is a value for 𝑏1 that maximizes her payoff (i.e., is a best response) for any value of 𝑏2.

 

Exercise 4. Spectrum auction and package bidding (exercise 2.5 in book)   
Wireless cellular technologies rely on spectrum assets. Around the world, auctions have emerged as the primary means of assigning spectrum licenses to companies wishing to provide wireless communication services. For example, from July 1994 to July 2011, the US Federal Communications Commission (FCC) conducted 92 spectrum auctions, raising over $60 billion for the US Treasury, and assigned thousands of licenses to hundreds of firms to different parts of the spectrum and different geographic regions of the country.

The US FCC uses simultaneous ascending auction, in which groups of related licenses are auctioned simultaneously[1] and the winner pays the highest bid. The British OfCom, in contrast, runs package bidding, where each potential spectrum bidder can bid on a joint set of frequency bands.

Among the many issues involved in spectrum auctioning is the debate between simultaneous ascending auction and package bidding auction. We will illustrate the inefficiency resulting from disallowing package bidding in a toy example. The root cause for this inefficiency is “bidder- specific complementarity” and the lack of competition.

Suppose that there are two bidders for two adjacent seats in a movie theater. Bidder 1 is planning to watch the movie together with her spouse as part of a date. She values the two spots jointly at $15, and a single spot is worth nothing. Bidder 2 plans to watch the movie by himself, and values each seat at $10, and the two seats together at $12 (since it is a little nicer to have no one sitting next to him on one side of his seat).

 

a    Assume a simultaneous ascending auction is used for the seats, and Bidder 1 correctly guesses that Bidder 2 values $10 for one seat and $12 for two seats together. What strategy will Bidder 1 take? What is the result of the auction, in terms of the allocation, the price charged, and the payoffs received? Hint: Try to guess a dominant strategy for Bidder 1. Is it sensible that she bids even 1c in this auction?  

b    Repeat part (a) but now assume package bidding[2] is used. In particular, Bidder 1 can bid on a package consisting of both seats. Explain the differences with (a).

 

Exercise 5. VCG auction     

Find the prices obtained by a VCG mechanism for the bidders (1,  2,  3, 4 )  and items (A, B) below  (the numbers above the edges are the bidders’ valuations).

 

Exercise 6. Cyclic ranking (exercise 3.2 in book)    

 

 

 

   

Write out the matrix H of the graph above. Iterate 𝜋[𝑘]𝑇 = 𝜋[𝑘 − 1]𝑇 𝐻, where 𝑘 = 0,1, 2, …, and let the initialization be        

𝜋[0] = [1/2, 1/2, 0, 0]𝑇 

 

What happens to the vectors {𝜋[𝑘]} as k becomes large? Solve for 𝜋∗  such that 𝜋∗𝑇 = 𝜋∗𝑇𝐻 and    .

 

 

Exercise 7. PageRank with a different θ (exercise 3.3 in book)  
  

Compute the PageRank vector 𝜋∗ of the graph in the Figure above, for 𝜃 = 0.1, 0.3, 0.5, and 0.85. What do you observe?

 

Exercise 8. Block aggregation in PageRank (exercise 3.4 in book)        Set θ = 0.85 and start with any normalized initial vector π[0].

 

 

a.       Compute the PageRank vector  𝑇 of the graph in figure (a) above with

 

                                                                                                        1          0

                                                                                          𝐻 = (                     ) 

                                                                                                      1/3     2/3

 

Note the uneven splitting of link weights from node B. This will be useful later in the problem.

b.       Compute the PageRank vectors [𝜋1∗ 𝜋2∗]𝑇 and   𝜋 𝑇 of the two graphs in figure (b)  above

c.       If we divide the graph in exercise 7 into two blocks as shown in the figure below, we can  

             approximate  𝜋∗ in the previous question by  

 

𝜋̃∗  𝑇 

 

 

 

Compute this vector. Explain the advantage, in terms of computational load, of using this approximation instead of directly computing  𝜋∗.

 

 

 

 

Exercise 9. Order of PageRank  

 

Which of the following arrangements of the nodes in the graph represents them in descending order of PageRank? Provide an analytical explanation.

 

  

 

 

a)      𝟑 𝟒 𝟓 𝟔 

b)      𝟒 𝟑 𝟓 𝟔 

c)       𝟑 𝟒 𝟔 𝟓 

d)      𝟒 𝟓 𝟑 𝟔