Math-Comp 553: Algorithmic Game Theory. Assignment 5 Solutions 1. Sponsored Search Auctions. Assume we have n = 2 bidders with values v1 > v2 and m = 2 ad slots with click through rates c1 > c2. (a) Assuming the bids are truthful, what is the revenue if we use a generalized second price auction. (b) Explain how the VCG mechanism would work here. What revenue would it give? Solution (a) With a GSP, the top bidder gets the slot with the higher clickthrough rate and pays a price equal to the per-click bid of the second bidder.
- top bidder
- optimum value for the original problem
- problem with the weights
- slot winners
- approximation algorithm for the corresponding allocation problem
- toll
- allocation
- algorithm
- value
- problem