Comp/Math 553: Algorithmic Game Theory Lecture 09 Yang Cai Menu Vickrey Auction Case Study: Sponsored Search Auction Myersons Lemma Back to Sponsored Search Auction VICKREY AUCTION

Second Price/Vickrey Auction Another idea: Charge the winner the second highest bid! maybe a bit strange But essentially used by Sothebys (modulo reserve price). Second-Price/Vickrey Auction Lemma 1: In a second-price auction, every bidder has a dominant strategy: set her bid bi equal to her private value vi. That is, this

strategy maximizes the utility of bidder i, no matter what the other bidders bid. Hence trivial to participate in. (unlike first price auction) Proof: See the board. Second-Price/Vickrey Auction Lemma 2: In a second-price auction, every truthful bidder is guaranteed non-negative utility. Sometimes called Individual Rationality Proof: See the board.

Second Price/Vickrey Auction [Vickrey 61 ] The Vickrey auction satisfies the following: (1)[strong incentive guarantees] It is dominant-strategy incentive-compatible (DSIC) and IR

(2) [strong performance guarantees] If bidders report truthfully, then the auction maximizes the social welfare i vixi, where xi is 1 if i wins and 0 if i loses. (3) [computational efficiency] The auction can be implemented in polynomial (linear) time. Second Price/Vickrey Auction Questions: Whats so special about 2nd price? How about charging the highest bidder the

3rd price? Whats next? These three properties: (i) strong incentive guarantees, (ii) strong performance guarantees, (iii) computational efficiency are criteria for a good auction. Our goal in future lectures will be to: Tackle more complex allocation problems Tackle more complex objectives, such as revenue

Case Study: Sponsored Search Auction Sponsored Search Auction In 2012, sponsored search generated 43.6 billion dollars for Google, which was 95% of its revenue. In the meantime, the market grows by ~20% per

year. Sponsored Search Auction: Setup Bidders (advertisers) v1 1 jj vn

kk Bidder is value for slot j is jvi. o Items are non identical 1 j

k slots for sale. Slot j has click-through-rate (CTR) j. Two complications: o Multiple items 11 vi n

Auctioneer/ Google i Slots k

Sponsored Search Auction: Goals (1) Ideally, DSIC and IR; i.e. truthful bidding should be a dominant strategy, never leading to negative utility. (2) Social welfare maximization; i.e. the assignment of bidders to slots should maximize vvixi, where xi denotes the CTR of the slot to which i is assigned (or 0 if i is not assigned to any slot). Each slot can only be assigned to one bidder, and each bidder gets only one slot. (3) Polynomial running time. Remember millions of these auctions are run every day!

Sponsored Search Auction Two things to consider: who wins what (allocation) and how much to charge (prices)? Tackle these questions one at a time: 1) Assume that bidders will bid truthfully. Then, how do we assign bidders to slots so that properties (2) and (3) hold? 2) Subject to (1), how do we set the prices so that truthful bidding is a dominant strategy? Sponsored Search Auction

1) Assume that bidders will bid truthfully. Then, how do we assign bidders to slots so that properties (2) and (3) are satisfied? Greedy Alg. 2) Subject to 1), how do we set the prices so that truthful bidding is a dominant strategy? use Vickrey payments for each slot?

(i.e. charge whoever got slot j, the value of whoever got slot j-1, etc.) Generalized Second Price Auction GSP auction: Suppose there are 2 slots for sale, the first slot has CTR 1=50% and the second slot has CTR 2=30%. Your value vi happens to be 1000 - the last 3 digits of your McGill ID #. You need to submit a bid bi. Allocation rule: allocate the slots greedily according to the bids.

If you win slot j, that is, your bid is the j-th highest bid, then your utility is j(vi pj+1), where pk is the k-th largest bid. Otherwise, your utility is 0. Your goal is to maximize your utility. Lets Play it! - Whats your bid if you are playing against the whole class? Sponsored Search Auction GSP is not truthful! Example: 3 bidders 2 slots. v1=7, v2=6 and v3=1; 1=1 and 2=0.4.

Instead of being truthful, its better for bidder 1 to bid 5 and win the second slot. Sponsored Search Auction 1) Assume that bidders will bid truthfully. Then, how do we assign bidders to slots so that properties (2) and (3) are satisfied? Greedy Alg.

2) Subject to 1), how do we set the prices so that truthful bidding is a dominant strategy? Myersons Lemma! Myersons Lemma Single-dimensional Environment Definition: o n bidders

o Each bidder i has a private value vi, its value per unit of stuff that she gets. o A feasible set X. Each element of X is an ndimensional vector (x1, x2, . . . , xn), where xi denotes the amount of stuff given to bidder i. Single-dimensional Environment Examples: o Single-item auction: X is the set of 0-1 vectors that have at most one 1 o Selling k units of the same item to unit-demand bidders: X are the 0-1 vectors satisfying vi xi k. o Sponsored search auction: X is the set of ndimensional vectors corresponding to assignments of

bidders to slots. If bidder i is assigned to slot j, then the component xi equals the CTR j of its slot. Sealed-Bid Auction in Single-dim Environments Make Two choices: Allocation rule x : Rn X X X Payment rule p : Rn X Rn X Sealed-Bid Auction Execution: 1. Collect bids b=(b1 , ..., bn) 2. [allocation] Implement allocation x(b) 3. [payment rule] Charge prices p(b)

Two important definitions Definition 1: (Implementable Allocation Rule) An allocation rule x for a single-dimensional environment is implementable if there is a payment rule p s.t. the sealedbid auction (x, p) is DSIC. - Example: When selling a single indivisible item, the allocation rule that gives the item to the highest bidder is implementable. -

Pending Question: Is the Greedy allocation rule implementable in Sponsored Search? - How about giving the item to the second highest bidder in single-item settings? How about the lowest bidder? Two important definitions Definition 2: (Monotone Allocation Rule) An allocation rule x for a single-dimensional environment is monotone if for

every bidder i and bids bi by the other bidders, the allocation xi(z, bi) to i is non-decreasing in is bid z. - In single-item settings, the allocation rule that gives the item to the highest bidder is monotone, while the allocation rules that give the item to the second highest or the lowest bidder are not monotone. - The Greedy allocation rule for Sponsored Search is monotone.

Myersons Lemma [Myerson 81 ] Fix a single-dimensional environment. (a) An allocation rule x is implementable if and only if it is monotone. (b) If x is implementable/monotone, there is an essentially unique payment rule such that the sealed-bid mechanism (x, p) is DSIC, given by the formula:

(c) In particular, there is a unique payment function such that the mechanism is DSIC and additionally IR with nonpositive transfers (i.e. bi = 0 implies pi(b) = 0, for all b-i). Myersons Lemma Corollaries Corollary: The greedy allocation rule for sponsored search is implementable. Thus, there is a DSIC auction that maximizes social welfare. On the other hand, in single-item settings, allocating to the second-highest bidder or the lowest bidder are both not implementable.