Eco514-Game Theory Lecture 8: Applications(1)-Simultaneous Auctions Marciano siniscalchi October 12. 1999 Introduction This lecture, as well as the next, exemplify applications of the framework and techniques developed so far to problems of economic interest. Neither lecture attempts to cover the example applications in any generality, of course; you may however find these topics of sufficient interest to warrant further study Auction theory is generally indicated as one of the "success stories"of game theory There is no doubt that the game-theoretic analysis of auctions has informed design decisions of great practical relevance. If you are interested in recent applications of auction theory, youshoulddefinitelycheckoutthefollowingUrl:http://www.market-design.comin particular, the Library section contains downloadable working papers in PDF format) This lecture focuses on the simplest possible setting, in which a single good is offered for sale, and bidders are required to submit their offers in a sealed envelope (so we are ruling out ascending or descending auctions: but see below ) Also, I shall focus on the analysis of"popular"auction forms: Myerson's 1981 paper deals with optimal auctions from a mechanism design standpoint. Finally, I will employ equilibrium analysis throughout Framework and auction forms The basic bidding game form may be represented as follows: each bidder i E N submit a bid ai E Ai=R+(so we rule out negative bids ); given any bid profile a =(aiieN, the auctioneer determines the set of high bidders H(a) according to H(a)={i∈N:≠,a1≥a Finally, the object is randomly assigned to one of the high bidders(each of whom equally likely to receive it), referred to as the winning bidder. Thus, the winning bidder is a high bidder, but only one high bidder will be the winning bidder
Eco514—Game Theory Lecture 8: Applications (1)—Simultaneous Auctions Marciano Siniscalchi October 12, 1999 Introduction This lecture, as well as the next, exemplify applications of the framework and techniques developed so far to problems of economic interest. Neither lecture attempts to cover the example applications in any generality, of course; you may however find these topics of sufficient interest to warrant further study. Auction theory is generally indicated as one of the “success stories” of game theory. There is no doubt that the game-theoretic analysis of auctions has informed design decisions of great practical relevance. If you are interested in recent applications of auction theory, you should definitely check out the following URL: http://www.market-design.com (in particular, the Library section contains downloadable working papers in PDF format). This lecture focuses on the simplest possible setting, in which a single good is offered for sale, and bidders are required to submit their offers in a sealed envelope (so we are ruling out ascending or descending auctions: but see below). Also, I shall focus on the analysis of “popular” auction forms: Myerson’s 1981 paper deals with optimal auctions from a mechanism design standpoint. Finally, I will employ equilibrium analysis throughout. Framework and Auction Forms The basic bidding game form may be represented as follows: each bidder i ∈ N submits a bid ai ∈ Ai = R+ (so we rule out negative bids); given any bid profile a = (ai)i∈N , the auctioneer determines the set of high bidders H(a) according to H(a) = {i ∈ N : ∀j 6= i, ai ≥ aj}. Finally, the object is randomly assigned to one of the high bidders (each of whom is equally likely to receive it), referred to as the winning bidder. Thus, the winning bidder is a high bidder, but only one high bidder will be the winning bidder.1 1
The bulk of the literature assumes quasi-linear preferences(although risk-aversion does play a role, and is analyzed in several papers). However, this is clearly not sufficient to determine payoffs. We still need to specify: (i) how much the object is worth to each bidder we shall assume quasi-linear utility); and (ii)the bidders'transfers to the seller. Moreover unless we assume that players'valuations are known, we need to specify (iii) the form of payoff uncertainty we are interested in Specifying (i),(ii) and (ii) leads to a taxonomy of bidding games With respect to (i), we distinguish between private and interdependent values: in the former setting, each player knows her valuation for the object(but may be uncertain about her opponents' valuation); in the latter, one or more players may be uncertain about her valuation, which will typically be related to other players'valuations and or realizations of underlying state variables. In particular, if the object is worth the same to all bidders, but no bidder is certain of the value, we are in a pure common values setting Payment rules(ii)pin down the auction mechanism, the most popular being first-price, second-price and (to a lesser degree) all-pay auctions Finally, with respect to(iii), whatever information bidders receive or hold(be it their valuation or a signal thereof) may be either independent or correlated A few examples will clarify (i) and (ii: the differences may appear to be subtle, but they are substantial Suppose that each bidder i E N observes a signal si E 0, 1, that F denotes the joint cdf of the signals, and that bidder i s valuation is a function vi: [0, 1 -R+. This is a very common specification of payoff uncertainty n this simplified(but very popular) framework, (i) and (ii) entail restrictions on th functions v; and F respectively. If u (si, S-i)=v(si, s'i) for all s; E 0, 1] and s-i E [0, 1]N-1 then we are in a setting with private values: bidder i's valuation is uniquely determined by her own signal si, which she observes. In the simplest case, ui(si, s-i)= si(which, note well, also entails a symmetry assumption) I Sellers may also set a reserve price: all bids below the reserve price are simply rejected. In this case the object may remain unsold if all bids are below the reserve price. Although Myerson shows that, in certain situations, setting a positive reserve price maximizes expected revenues, we shall simply ignore this 2In the most common auction formats, only the winning bidder is required to pay. However, in all-pay auctions, as the name suggests, all bidders pay their bid. Indeed, one can conjure up just about any kind of payment rule: as long as the winning bidder is a high bidder, you can still call the resulting mechanism an
The bulk of the literature assumes quasi-linear preferences (although risk-aversion does play a role, and is analyzed in several papers). However, this is clearly not sufficient to determine payoffs. We still need to specify: (i) how much the object is worth to each bidder (we shall assume quasi-linear utility); and (ii) the bidders’ transfers to the seller.2 Moreover, unless we assume that players’ valuations are known, we need to specify (iii) the form of payoff uncertainty we are interested in. Specifying (i), (ii) and (iii) leads to a taxonomy of bidding games: • With respect to (i), we distinguish between private and interdependent values: in the former setting, each player knows her valuation for the object (but may be uncertain about her opponents’ valuation); in the latter, one or more players may be uncertain about her valuation, which will typically be related to other players’ valuations and/or realizations of underlying state variables. In particular, if the object is worth the same to all bidders, but no bidder is certain of the value, we are in a pure common values setting. • Payment rules (ii) pin down the auction mechanism, the most popular being first-price, second-price and (to a lesser degree) all-pay auctions. • Finally, with respect to (iii), whatever information bidders receive or hold (be it their valuation or a signal thereof) may be either independent or correlated. A few examples will clarify (i) and (iii): the differences may appear to be subtle, but they are substantial. Suppose that each bidder i ∈ N observes a signal si ∈ [0, 1], that F denotes the joint cdf of the signals, and that bidder i’s valuation is a function vi : [0, 1]N → R+. This is a very common specification of payoff uncertainty. In this simplified (but very popular) framework, (i) and (iii) entail restrictions on the functions vi and F respectively. If vi(si , s−i) = vi(si , s0 −i ) for all si ∈ [0, 1] and s−i ∈ [0, 1]N−1 , then we are in a setting with private values: bidder i’s valuation is uniquely determined by her own signal si , which she observes. In the simplest case, vi(si , s−i) = si (which, note well, also entails a symmetry assumption). 1Sellers may also set a reserve price: all bids below the reserve price are simply rejected. In this case, the object may remain unsold if all bids are below the reserve price. Although Myerson shows that, in certain situations, setting a positive reserve price maximizes expected revenues, we shall simply ignore this possibility. 2 In the most common auction formats, only the winning bidder is required to pay. However, in all-pay auctions, as the name suggests, all bidders pay their bid. Indeed, one can conjure up just about any kind of payment rule: as long as the winning bidder is a high bidder, you can still call the resulting mechanism an “auction”. 2
Otherwise, valuations are interdependent; for instance, a pedagogically useful and con- venient specification is vi (s)= ieN S;. This is known as the "wallet game (note again the implicit symmetry assumption The latter is a specification with pure common values. The expression"interdependent values"allows for intermediate cases such as vi (s)=a;:+2itiS, for some ai>1 either case, the signals si, i E N, may be independent(s F(s)=leN Fi(si) for some collection of one-dimensional cdf's Fi, i E N or correlated; for instance, suppose that there exist N+l i.i.d. random variables o, 11,. N, uniform on 0,1, such that Si=ro+ai for every iE N The key intuition is that, since bids will be functions of the signals, when signals are correlated, bidder i can make inferences about her opponents equilibrium bids based on her own signal. This is of course true regardless of whether values are private or interdependent biste inally, payment rules are relatively simple to specify. In a first-price auction, the winning m2(a) ani∈H(a) 0 i H(a) In a second-price auction, she pays the highest non-winning bid: that m2(a) 0xa,i∈H(a) i g H(a Auctions are modelled as (infinite)Bayesian games. In the simplified setting we are looking at, signals contain all payoff-relevant information(although other formulations could considere ed ). It is typical to let g2= s and t(s)=s1×[0,1]-1 reflecting the assumption that players know their signal, and nothing else. Indeed, in this setting, the distinction between the signal si and the corresponding type si x 0, 1]N-Iis blurred, and I will follow conventional usage by adopting whatever term is most convenient The cdf F is then used to define a common prior on Q. As I have already noted, this has several implications for equilibrium analysis; one could entertain different hypotheses, but this is not the point of today's lecture Also note that the resulting game G=(N, Q, (Ai, ui, tien)is infinite both because action spaces are(Ai=R+) and because the state space is. It should be noted that bidding An 3The idea is as follows: players place their wallets on the table, then bid for the money contained in all allets. Each participant knows how much money she is carrying in her own wallet, but ignores the content of the other wallets
Otherwise, valuations are interdependent; for instance, a pedagogically useful and convenient specification is vi(s) = P i∈N si . This is known as the “wallet game3” (note again the implicit symmetry assumption). The latter is a specification with pure common values. The expression “interdependent values” allows for intermediate cases such as vi(s) = aisi + P j6=i sj , for some ai > 1. In either case, the signals si , i ∈ N, may be independent (so that F(s) = Q i∈N Fi(si) for some collection of one-dimensional cdf’s Fi , i ∈ N) or correlated; for instance, suppose that there exist N + 1 i.i.d. random variables x0, x1, . . . , xN , uniform on [0, 1 2 ], such that si = x0 + xi for every i ∈ N. The key intuition is that, since bids will be functions of the signals, when signals are correlated, bidder i can make inferences about her opponents’ equilibrium bids based on her own signal. This is of course true regardless of whether values are private or interdependent. Finally, payment rules are relatively simple to specify. In a first-price auction, the winning bidder pays her bid. Thus, the payment rule m : A → RN + is defined by mi(a) = ai i ∈ H(a) 0 i 6∈ H(a) In a second-price auction, she pays the highest non-winning bid: that is, mi(a) = maxj6=i aj i ∈ H(a) 0 i 6∈ H(a) Auctions are modelled as (infinite) Bayesian games. In the simplified setting we are looking at, signals contain all payoff-relevant information (although other formulations could be considered). It is typical to let Ω = S and ti(s) = si × [0, 1]N−1 reflecting the assumption that players know their signal, and nothing else. Indeed, in this setting, the distinction between the signal si and the corresponding type si × [0, 1]N−1 is blurred, and I will follow conventional usage by adopting whatever term is most convenient. The cdf F is then used to define a common prior on Ω. As I have already noted, this has several implications for equilibrium analysis; one could entertain different hypotheses, but this is not the point of today’s lecture. Also note that the resulting game G = (N, Ω,(Ai , ui , ti)i∈N ) is infinite both because action spaces are (Ai = R+) and because the state space is. It should be noted that bidding 3The idea is as follows: players place their wallets on the table, then bid for the money contained in all wallets. Each participant knows how much money she is carrying in her own wallet, but ignores the content of the other wallets. 3
games exhibit serious discontinuities, so that the existence of Nash equilibria, and even best replies(see below) is not guaranteed by the standard machinery Quasi-linearity completes the specification of payoffs: fixing a payment rule m, for any profile a∈A, mot()-m(o)i∈H(a) i g H(a) nalysIs We now consider a few even more special illustrative cases. Before we begin, consider the following definition Definition 1 Fix a bidding game g defined as above, and a player iE N. a bid function for bidder i is a function ai: Si-A That is a bid function is a degenerate signal-contingent randomized action Second-Price Auctions with Private values Let us assume for notational simplicity that vi(s)=si. These bidding games are traditionally analyzed using the notion of weak dominance. An action ai weakly dominates an alternative action a; for type s; of bidder i iff, for all opponent bid functions(a,)i#i and for all realization of the opponents' signals t(a,(a3(s;)≠,sS-)≥t(a1,(a(s)≠i,S,-) and moreover there exists a profile of opponents' bid functions and a profile of signal real- izations for which the above inequality is strict p Lith private values, however, this reduces to the requirement that, for all profiles of onents'actions a_i(not bid tions!) ui( vs-∈0,1 and that the inequality be strict for at least one profile of opponents'actions; this is a consequence of the assumption that s-i does not affect vi(s But this leads to the conclusion that, for any signal realization s E 0, 1, bidder iE N and pair of actions ai, ah, ai weakly dominates a for type si of bidder i iff ai weakly dominates a; in the game without payoff uncertainty defined by G(s)=N, (Ai, ui( s))ieN. This is the game you analyzed in Problem Set 1, so you have already proved the following result
games exhibit serious discontinuities, so that the existence of Nash equilibria, and even best replies (see below) is not guaranteed by the standard machinery. Quasi-linearity completes the specification of payoffs: fixing a payment rule m, for any profile a ∈ A, ui(a, s) = 1 |H(a)| [vi(s) − mi(a)] i ∈ H(a) 0 i 6∈ H(a) Analysis We now consider a few even more special illustrative cases. Before we begin, consider the following definition: Definition 1 Fix a bidding game G defined as above, and a player i ∈ N. A bid function for bidder i is a function ai : Si → Ai . That is, a bid function is a degenerate signal-contingent randomized action. Second-Price Auctions with Private Values Let us assume for notational simplicity that vi(s) = si . These bidding games are traditionally analyzed using the notion of weak dominance. An action ai weakly dominates an alternative action a 0 i for type si of bidder i iff, for all opponent bid functions (aj )j6=i and for all realization of the opponents’ signals, ui(ai ,(aj (sj ))j6=i , si , s−i) ≥ ui(a 0 i ,(aj (sj ))j6=i , si , s−i) and moreover there exists a profile of opponents’ bid functions and a profile of signal realizations for which the above inequality is strict. With private values, however, this reduces to the requirement that, for all profiles of opponents’ actions a−i (not bid functions!), ui(ai , a−i , si , s−i) ≥ ui(a 0 i , a−i , si , s−i) ∀s−i ∈ [0, 1]N−1 and that the inequality be strict for at least one profile of opponents’ actions; this is a consequence of the assumption that s−i does not affect vi(s). But this leads to the conclusion that, for any signal realization s ∈ [0, 1]N , bidder i ∈ N and pair of actions ai , a0 i , ai weakly dominates a 0 i for type si of bidder i iff ai weakly dominates a 0 i in the game without payoff uncertainty defined by G(s) = {N,(Ai , ui(·, s))i∈N }. This is the game you analyzed in Problem Set 1, so you have already proved the following result: 4
Proposition 0.1 In any second-price auctions with private values, bidding one's valuation is the unique weakly dominant action. Therefore, the profile of "truthful" bid functions defined by ai(si)= si for every i E N, is a Bayesian Nash equilibrium of the associated bidding game Thus, truthful bidding is a Bayesian Nash equilibrium of the second-price auction regardless of the assumptions one makes about the underlying signal structure. This is viewed as a particularly comforting result: truthful bidding is certainly"focal"in this setting Proposition 0. 1 shows that it follows from the assumption that players do not choose weakly dominated actions. You already know that the(complete-information version of the) game has other Bayesian Nash equilibria If participants bid truthfully, then no bidder has a higher valuation for the object than the winner. Thus, under truthful bidding, the second-price auction places the object in the right "hands; that is, it is an efficient mechanism. 4 Incidentally, you may already know that second-price auctions are special cases of Vickrey- Groves-Clark direct mechanisms. With private values, truthful reporting is weakly dominant in such mechanisms, and always leads to efficient outcomes. Thus, for example, the k-good extension of the second-price auction(known as the Vickrey auction) also achieves efficiency First-Price Auctions with Independent Private values The analysis of first-price auctions requires more work, and more restrictive assumptions. In particular, we need to assume a lot of symmetry: in particular, assume that ui (si, s-i)=v(si) for all s=(Si, S_i)E 0, 1(so the same function v: 0, 1-R+ defines valuations for all players) and Fi= F for all i E I(so signals are i.i. d ) Also assume that v(1)=i<oo and v(0)=0. Finally, we assume that v and F are continuously differentiable, and that the density f= F is bounded away from zero Now observe that since the valuation function is bounded, we can renormalize it without loss of generality so that v (1)=1. Having done this, since both v and F are continuous and v is increasing, we can further simplify both the notation and the algebra, again without loss of generality, by considering an equivalent setting in which v(s)=s and F is replaced with a new cdf G such that the density of any valuation E [0, 1]under the original model f(o(a)), equals the density of x under G, i.e. g(a) We look for a symmetric equilibrium in increasing, differentiable bid function strategy we shall follow is to assume that such an equilibrium profile(alien exists, and derive some conditions which the profile must satisfy in order to be an equilibrium in differentiable bid functions. Then, we show that any profile of differentiable bid functions satisfying the above conditions is indeed an equilibrium aNote well: in this literature, an auction mechanism is deemed efficient if there is at least one equilibrium of the associated game which induces an efficient allocation. Other equilibria may well be inefficient
Proposition 0.1 In any second-price auctions with private values, bidding one’s valuation is the unique weakly dominant action. Therefore, the profile of “truthful” bid functions defined by ai(si) = si for every i ∈ N, is a Bayesian Nash equilibrium of the associated bidding game. Thus, truthful bidding is a Bayesian Nash equilibrium of the second-price auction— regardless of the assumptions one makes about the underlying signal structure. This is viewed as a particularly comforting result: truthful bidding is certainly “focal” in this setting; Proposition 0.1 shows that it follows from the assumption that players do not choose weakly dominated actions. You already know that the (complete-information version of the) game has other Bayesian Nash equilibria. If participants bid truthfully, then no bidder has a higher valuation for the object than the winner. Thus, under truthful bidding, the second-price auction places the object in the “right” hands; that is, it is an efficient mechanism.4 Incidentally, you may already know that second-price auctions are special cases of VickreyGroves-Clark direct mechanisms. With private values, truthful reporting is weakly dominant in such mechanisms, and always leads to efficient outcomes. Thus, for example, the k-good extension of the second-price auction (known as the Vickrey auction) also achieves efficiency. First-Price Auctions with Independent Private Values The analysis of first-price auctions requires more work, and more restrictive assumptions. In particular, we need to assume a lot of symmetry: in particular, assume that vi(si , s−i) = v(si) for all s = (si , s−i) ∈ [0, 1]N (so the same function v : [0, 1] → R+ defines valuations for all players) and Fi = F¯ for all i ∈ I (so signals are i.i.d.). Also assume that v(1) = ¯v < ∞ and v(0) = 0. Finally, we assume that v and F¯ are continuously differentiable, and that the density ¯f = F¯0 is bounded away from zero. Now observe that, since the valuation function is bounded, we can renormalize it without loss of generality so that v(1) = 1. Having done this, since both v and F¯ are continuous and v is increasing, we can further simplify both the notation and the algebra, again without loss of generality, by considering an equivalent setting in which v(s) = s and F¯ is replaced with a new cdf G such that the density of any valuation x ∈ [0, 1] under the original model, ¯f(v −1 (x)), equals the density of x under G, i.e. g(x). We look for a symmetric equilibrium in increasing, differentiable bid functions. The strategy we shall follow is to assume that such an equilibrium profile (ai)i∈N = (a, . . . , a) exists, and derive some conditions which the profile must satisfy in order to be an equilibrium in differentiable bid functions. Then, we show that any profile of differentiable bid functions satisfying the above conditions is indeed an equilibrium. 4Note well: in this literature, an auction mechanism is deemed efficient if there is at least one equilibrium of the associated game which induces an efficient allocation. Other equilibria may well be inefficient. 5