Algorithmic Game Theory Lecture on General Mechanisms and Implementation

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

Menu Revelation Principle Myerson s Optimal Auction

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. = {???? | ?? ??} ??

Revelation Principle - Given indirect mechanism (x, p) and dominant strategy/ex-post Nash equilibrium s1, ,sn can construct direct, DSIC mechanism (x , p ) such that: t1, ,tn: x (t1, ,tn) = x(s1(t1), ,sn(tn)) p (t1, ,tn) = p(s1(t1), ,sn(tn)) - Given indirect mechanism (x, p) and a Bayesian Nash equilibrium s1, ,sn can construct direct, BIC mechanism (x , p ) such that: t1, ,tn: x (t1, ,tn) = x(s1(t1), ,sn(tn)) p (t1, ,tn) = p(s1(t1), ,sn(tn))

SINGLE-ITEM REVENUE MAXIMIZATION

Bayesian Single-dimensional Environment Definition: o n bidders o Each bidder i : o has a private value vi (scalar!), her value per unit of stuff that she gets. o satisfies vi ~ Fi , where Fi is known to everyone (auctioneer and other bidders) o A feasible set X. Each element of X is an n- dimensional vector (x1, x2, . . . , xn), where xi denotes the amount of stuff given to bidder i. Examples: k-unit auctions, sponsored search

Revenue-Optimal Auctions [Myerson 81 ] Bayesian Single-dimensional settings. 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.

Expected Revenue = Expected Virtual Welfare

Revenue = Virtual Welfare [Myerson 81] Fix a Bayesian single-dimensional environment, where bidder distributions are F1, ,Fn, and F=F1x xFn. Let also (x,p) be a BIC mechanism satisfying interim IR and NPT. The expected revenue of this mechanism under truth-telling is Ev~F[ i pi(v)]=Ev~F[ i xi(v) i (vi)], where i (vi) := vi- (1-Fi(vi))/fi(vi) is bidder i s virtual value function (fi is the density function for Fi). Proof given shortly, after some notation, and a version of Myerson s lemma from lecture 10 for BIC implementability.

Interim Allocation, Price Rule In a Bayesian, single-dimensional setting, given a direct auction (x, p), we define its interim allocation rule and interim price rule for bidder i as follows: The interim allocation rule expresses the allocation that bidder i expects to receive when reporting vi in expectation over the other bidders values, assuming that they report truthfully. Similarly, for the interim price rule. For notational, simplicity we often omit the hats, representing both the interim and the ex-post allocation rule for bidder i by xi () with the meaning of the function being determined by the number of arguments. Similarly, we denote both the interim and ex-post price rule by pi( ).

Recall Myersons Lemma for DSIC Implementation [Myerson 81] Fix a single-dimensional environment. BIC (a) An allocation rule x is DSIC implementable if and only if it is monotone. interim BIC interim (b) If x is DSIC implementable, there is an essentially unique payment rule such that the direct mechanism (x, p) is DSIC, given by the formula: BIC interim (c) In particular, there is a unique payment rule such that the mechanism is DSIC and additionally interim IR and NPT. BIC

Myersons Lemma for BIC Implementation [Myerson 81] Fix a single-dimensional environment. (a) An allocation rule x is BIC implementable if and only if it is interim monotone (i.e. for all i, xi (vi) is in vi). (b) If x is BIC implementable, there is an essentially unique interim payment rule such that the direct mechanism (x, p) is BIC, given by the formula: (c) In particular, there is a unique interim payment rule such that the mechanism is BIC and additionally interim IR and NPT.

Revenue = Virtual Welfare [Myerson 81] Fix a Bayesian single-dimensional environment, where bidder distributions are F1, ,Fn, and F=F1x xFn. Let also (x,p) be a BIC mechanism satisfying interim IR and NPT. The expected revenue of this mechanism under truth-telling is Ev~F[ i pi(v)]=Ev~F[ i xi(v) i (vi)], where i (vi) := vi- (1-Fi(vi))/fi(vi) is bidder i s virtual value function (fi is the density function for Fi). Proof: on the board

Example Applications

One U[0,1] Bidder, One Item Recall that posting a price of achieves expected revenue . Is the optimal expected revenue of any IR auction? Answer: yes, it is! Proof: The virtual transform for U[0,1] distribution is: By Myerson s theorem, any BIC, IR, NPT mechanism (x,p) has revenue . Notice that for all possible x(): Hence, posting a price of is optimal as it achieves the best possible expected virtual welfare, and hence expected revenue.

Two U[0,1] Bidders, One Item Recall that Vickrey without reserve has expected revenue , while Vickrey with reserve has expected revenue 5/12. Is 5/12 the optimal expected revenue of any interim IR auction? Answer: yes it is!

Two U[0,1] Bidders, One Item (cont.) Recall that the virtual transform for v~U[0,1] is: (v)= 2v-1 By Myerson s theorem, Optimizing expected revenue = Optimizing expected virtual welfare subject to interim monotonicity (needed for BIC) Let s try to optimize virtual welfare point-wise on every bid profile (forgetting about interim monotonicity temporarily) On bid profile (v1,v2), the pair of virtual values are ( (v1), (v2))=(2v1-1, 2v2-1). How should we allocate? If max{v1,v2} , let s give the item to the bidder with highest value/virtual value. Otherwise, (v1), (v2) < 0. So let s not allocate the item. Note that the above allocation rule is monotone, so by Myerson s lemma there is a price rule that makes it DSIC. DSIC + pointwise optimal virtual welfare => DSIC, Revenue-optimal Now, notice that the above auction is identical to Vickrey auction with reserve (which has revenue 5/12 and is actually DSIC).