Algorithmic Game Theory Lecture 11 Highlights

Comp/Math 553: Algorithmic Game Theory Lecture 11 Yang Cai

Menu Reminder: Myerson s Lemma Examples Revenue Maximization (Intro) The Revelation Principle

Direct Auction and DSIC Defined by two rules: Allocation rule x :Rn X Payment rule p :Rn Rn Auction Execution: 1. Collect bids b=(b1 , ..., bn) 2. [allocation] Implement allocation x(b) 3. [payments] Charge prices p(b) Definition: (DSIC) A direct auction (x, p) is DSIC iff for all i, b-i it is optimal for bidder i to bid his true value:

Implementability and Monotonicity Definition 1: (Implementable Allocation Rule) An allocation rule x for a single-dimensional environment is implementable if there is a payment rulep s.t. the sealed-bid auction (x, p) is DSIC. Myerson s Lemma Definition 2: (Monotone Allocation Rule) An allocation rule xfor a single-dimensional environment is monotone if for every bidder i and bids b i by the other bidders, the allocation xi(z,b i) to i is non-decreasing in i s bid z.

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 non-positive transfers (i.e. bi = 0 implies pi(b) = 0, for all b-i).

Quick and Dirty 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.

Application of Myerson s Lemma

Single-item Auction Bidders Auctioneer v1 Item 1 vi i n vn Allocation Rule: give the item to the highest bidder. Payment Rule: Vickrey s Payment How about k-unit auction?

Sponsored Search Bidders (advertisers) Slots Auctionee r/Google v1 1 1 1 vi i j j n vn k k Allocation Rule: allocate the slots greedily based on the bidders bids. Payment Rule?

SINGLE-ITEM REVENUE- -MAXIMIZATION

One Bidder, One Item, Revenue Maximization Can we meaningfully maximize revenue? Suppose1 bidder whose value is v. Highest achievable revenue is v, if we were to offer a take-it-or-leave-it offer of the item at price v. Butv is private... How can we price the item optimally? Fundamental issue: fix any price; there is some v for which it fails to extract revenue v. Bidder s Private Value is too strong of a benchmark for the auction to compete against. Solution: Assume distribution F over bidder s value is known. Perform average case analysis

One Bidder, One Item, Revenue Maximization Posting price r gives expected revenue = r (1 F(r)) When F is the uniform dist. on [0,1], optimal choice of r is achieving expected revenue . The optimal posted price is also called the monopoly price. Is the optimal expected revenue of any auction?

Two Uniform Bidders, One Item Two bidders whose values are i.i.d. U[0,1]. Revenue of Vickrey s Auction is the expectation of the min of the two uniform random variables = 1/3. What else could we do? Include a reserve price? Vickrey with reserve has expected revenue 5/12 > 1/3. Is 5/12 the optimal expected revenue of any auction?

Revenue-Optimal Auctions [Myerson 81 ] Single-dimensional settings, distribution Fiof every bidder s private value known to all other bidders, the auctioneer. Exists Revenue-Optimal auction that is simple, direct, DSIC Optimality:The expected revenue of Myerson s auction when all bidders report truthfully (which is in their best interest to do since the auction is DSIC) is as large as the expected revenue of any other (potentially indirect) interim IR auction, when bidders use Bayesian Nash equilibrium strategies. Note: Reminder of Bayesian Nash equilibrium, general definition of direct/indirect mechanisms given later in this slide-deck.

The Power (?) of Indirect Mechanisms

Indirect Mechanisms? So far considered welfare maximization in single-item, k-unit, sponsored search auctions. Greedy allocation rule was monotone. Thus, combined with Myerson s payment formula can be complemented to a DSIC direct mechanism maximizing welfare in these settings. So restriction to direct mechanisms did not hurt us. As we foray into more complex objectives (e.g. revenue, next lecture) or more complex settings (e.g. spectrum auctions, later in this course) could it be that indirect mechanisms are more powerful than direct ones? Revelation principle: In very general settings, the answer is no!

-We will show this principle for general mechanism design settings (beyond single-dimensional) - Along the way we will define general mechanism design settings, indirect mechanisms, direct mechanisms,solution concepts, and implementability. The Revelation Principle

Preamble: Games of Incomplete Information Def: A game with (independent private values and strict) incomplete information and players 1, , n is specified by the following ingredients: (i) A set of actions Xi for each player i (ii) A set of types Ti, for each player i. An element ti Ti is the private information of player i Sometimes also have a distribution Fi over Ti (Bayesian Setting) (iii) For each player i, a utility function ui(ti, x1, , xn) is the utility of player i, if his type is ti and the players use actions x1, , xn

concepts naturally extend to mixed strategies Preamble: Strategies and Equilibria Def: A (pure) strategy of a player i is a function Def: Equilibrium (dominant , ex-post Nash and Bayesian Nash) A profile of strategies is an (pure) ex-post Nash equilibrium if for all i, all , and all we have that A profile of strategies is a (pure) dominant strategy equilibrium if for all i, all , and all we have that A profile of strategies is a (pure) Bayesian Nash equilibrium if for all i, ti and all we have that:

General Mechanisms (Quasi-Linear Setting) Def: A (general) mechanism for n bidders is defined by 1. players type spaces T1, , Tn 2. sometimes a distribution Fi over Ti is also known (Bayesian setting); in this case it is assumed that bidder i s type ti ~ Fi 3. a set of possible alternatives A setting 4. players valuation functions vi: Ti x A R 5. players action spaces X1, , Xn 6. an allocation function x : X1 x x Xn A 7. price functions pi: X1 x x Xn R Mechanism is called direct iff Xi=Ti, for all i mechanism A mechanism induces a game of incomplete information, which has the same type spaces and action spaces, and has utilities:

Incentive Compatibility of Direct Mechanisms - Indirect mechanisms are analyzed by studying the properties of the Dominant Strategy, ex-post Nash or Bayesian Nash equilibria of the incomplete information games they induce. - When analyzing direct mechanisms we will be interested in whether truthtelling is an equilibrium, i.e. whether strategies si(ti)=tifor all i comprise an equilibrium, distinguishing the following types of direct mechanisms: Def: A direct mechanism (x, p) is Dominant Strategy Incentive Compatible (DSIC) iff truth-telling is a dominant strategy equilibrium, i.e. Def: A direct mechanism (x, p) is Bayesian Incentive Compatible (BIC) iff truth-telling is a Bayesian Nash equilibrium, i.e.

Implementation (in general settings) Suppose is some allocation rule. Def: We say that a mechanism (x, p) implements f in dominant strategies if for some dominant strategy equilibrium of the induced game, we have that for all Ex: Vickrey s auction implements the maximum social welfare function in dominant strategies, because is a dominant strategy equilibrium, and maximum social welfare is achieved at this equilibrium. outcome of the mechanism at equilibrium Similarly we can define ex-post Nash/Bayesian Nash implementation. outcome of the allocation function on true types Remarks: 1. We only require that for some equilibrium and allow other equilibria to exist. 2. Concept generalizes implementability (from earlier in this slide-deck) to general mechanism design settings.

The Revelation Principle (DSE to DSIC) Theorem: If there is an arbitrary mechanism that implements some allocation rule f in dominant strategies, then there is also a direct, DSIC mechanism that implements f. Moreover, the payments of the players in the direct mechanism are identical to those of the original mechanism, at equilibrium, pointwise with respect to t1, ,tn. Proof idea: Simulation

Proof by Picture: new mechanism (direct) original mechanism (indirect)

Proof via Symbols Proof: Let be a dominant strategy equilibrium of the original mechanism such that , for all . Define a new direct mechanism as follows: Since each is a dominant strategy for player i in the original mechanism: for every , we have that Thus in particular this is true for t-i and and ti . So we get that and for any i.e. (x , p ) is DSIC and x =f.

Revelation Principle: Ex-Post Nash to DSIC, and Bayes-Nash to BIC Theorem: If there is an arbitrary mechanism that implements some allocation rule f in ex-post (respectively Bayesian) Nash equilibrium, then there is also a direct DSIC (respectively Bayesian IC) mechanism that implements f. Moreover, the payments of the players in the direct mechanism are identical to those of the original mechanism, at equilibrium, pointwise w.r.t. . Technical Lemma (gedanken experiment: from ex-post to dominant strategy equilibria): Let be an ex-post Nash equilibrium of a game . Define new action spaces . Then is a dominant strategy equilibrium of the game = {???? | ?? ??} ?? . Proof sketch for ex-post Nash to DSIC implementation: Restrict the action spaces in the original mechanism to the sets . Our technical lemma implies that now is a dominant strategy equilibrium. Now invoke the revelation principle for dominant strategy implementation. = {???? | ?? ??} ??