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 nd these topics of su cient 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 de nitely 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 o ered for sale, and bidders are required to submit their o ers 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 2 N submits a bid ai 2Ai = R+ (so we rule out negative bids); given any bid pro le a = (ai)i2N, the auctioneer determines the set of high bidders H(a) according to H(a) =fi2N :8j6= i; ai ajg: 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 su cient to determine payo s. 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 payo 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 rst-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 di erences may appear to be subtle, but they are substantial. Suppose that each bidder i2N observes a signal si2[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 speci cation of payo uncertainty. In this simpli ed (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 si2[0;1] and s i2[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. 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 \auction". 2 Otherwise, valuations are interdependent; for instance, a pedagogically useful and con- venient speci cation is vi(s) = Pi2N si. This is known as the \wallet game3" (note again the implicit symmetry assumption). The latter is a speci cation with pure common values. The expression \interdependent values" allows for intermediate cases such as vi(s) = aisi +Pj6=isj, for some ai > 1. In either case, the signals si, i2N, may be independent (so that F(s) = Qi2N Fi(si) for some collection of one-dimensional cdf’s Fi, i2N) or correlated; for instance, suppose that there exist N + 1 i.i.d. random variables x0;x1;:::;xN, uniform on [0; 12], such that si = x0 +xi for every i2N. 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 rst-price auction, the winning bidder pays her bid. Thus, the payment rule m : A!RN+ is de ned by mi(a) = a i i2H(a) 0 i62H(a) In a second-price auction, she pays the highest non-winning bid: that is, mi(a) = max j6=iaj i2H(a) 0 i62H(a) Auctions are modelled as (in nite) Bayesian games. In the simpli ed setting we are looking at, signals contain all payo -relevant information (although other formulations could be considered). It is typical to let = S and ti(s) = si [0;1]N 1 re ecting 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 de ne a common prior on . As I have already noted, this has several implications for equilibrium analysis; one could entertain di erent hypotheses, but this is not the point of today’s lecture. Also note that the resulting game G = (N; ;(Ai;ui;ti)i2N) is in nite 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 speci cation of payo s: xing a payment rule m, for any pro le a2A, ui(a;s) = 1 jH(a)j[vi(s) mi(a)] i2H(a) 0 i62H(a) Analysis We now consider a few even more special illustrative cases. Before we begin, consider the following de nition: De nition 1 Fix a bidding game G de ned as above, and a player i2N. 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 a0i for type si of bidder i i , 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(a0i;(aj(sj))j6=i;si;s i) and moreover there exists a pro le of opponents’ bid functions and a pro le of signal real- izations for which the above inequality is strict. With private values, however, this reduces to the requirement that, for all pro les of opponents’ actions a i (not bid functions!), ui(ai;a i;si;s i) ui(a0i;a i;si;s i) 8s i2[0;1]N 1 and that the inequality be strict for at least one pro le of opponents’ actions; this is a consequence of the assumption that s i does not a ect vi(s). But this leads to the conclusion that, for any signal realization s2[0;1]N, bidder i2N and pair of actions ai;a0i, ai weakly dominates a0i for type si of bidder i i ai weakly dominates a0i in the game without payo uncertainty de ned by G(s) = fN;(Ai;ui( ;s))i2Ng. 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 pro le of \truthful" bid functions de ned by ai(si) = si for every i 2 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 e cient 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 e cient outcomes. Thus, for example, the k-good extension of the second-price auction (known as the Vickrey auction) also achieves e ciency. First-Price Auctions with Independent Private Values The analysis of rst-price auctions requires more work, and more restrictive assumptions. In particular, we need to assume a lot of symmetry: in particular, assume thatvi(si;s i) = v(si) for all s = (si;s i)2[0;1]N (so the same function v : [0;1]!R+ de nes valuations for all players) and Fi = F for all i2I (so signals are i.i.d.). Also assume that v(1) = v <1 and v(0) = 0. Finally, we assume that v and F are continuously di erentiable, and that the density f = F0 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 x2[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, di erentiable bid functions. The strategy we shall follow is to assume that such an equilibrium pro le (ai)i2N = (a;:::;a) exists, and derive some conditions which the pro le must satisfy in order to be an equilibrium in di erentiable bid functions. Then, we show that any pro le of di erentiable bid functions satisfying the above conditions is indeed an equilibrium. 4Note well: in this literature, an auction mechanism is deemed e cient if there is at least one equilibrium of the associated game which induces an e cient allocation. Other equilibria may well be ine cient. 5 Note that this approach does not establish existence directly: rst, no pro le of bid functions satisfying the derived conditions may exist (so the second part of the argument may be empty); second, even if they do exist, they may fail to be increasing and/or di erentiable (so the rst part of the argument may be unwarranted). To establish existence, one must invoke results from the theory of di erential equations. With this in mind, note that Bidder i’s payo function when her opponents follow the equilibrium bid functions can be written as follows: Ui(ai;si) = X J Nnfig 1 jJj+ 1 Prfs i : H(ai;(a(sj))j6=i) = J[figg[si ai]: That is: if she wins the object by bidding ai, Bidder i’s utility is si ai; for any realization of the signals, she may be the only high bidder, or there may be another high bidder, or there may be two, etc., in which case she wins with correspondingly smaller probability. The assumptions we have made simplify the analysis considerably. First, since the model is perfectly symmetric, we can drop all indices from actions and signals. Second, since we are assuming that the common equilibrium bid function is increasing, and that G has a density, ties occur with probability zero (i.e. there is G-almost always only one winner). Thus, only one term (corresponding to J = Nnfig) is nonzero in the above summation. Third, since the equilibrium bid function is increasing and signals are independent, it can be inverted, and the probability that the bid a is the winning bid is given by G(a 1(a))N 1; this is the probability that all opponents observe signals which induce them (in the equilibrium under consideration) to bid at most a. Thus, we get U(a;s) = [G(a 1(a))]N 1[s a] Now, if a is a best reply to the equilibrium belief, then it must satisfy the rst-order condition (N 1)G(a 1(a))N 2g(a 1(a)) 1a0(a 1(a))[s a] [G(a 1(a))]N 1 = 0: If the pro le under consideration is an equilibrium then the above restriction must hold for a = a(s); this allows one to simplify the expression somewhat. Moreover, since G is strictly positive by assumption, we can divide throughout by G(s)N 2 to get (N 1)g(s)[s a(s)] = G(s)a0(s); (1) the interpretation in terms of cost-bene t tradeo should be clear. Another necessary con- dition for a to be a best-reply is a(0) = 0. Thus, we have a rst-order linear di erential equation and a boundary condition; given our regularity conditions, a solution exists and is determined by the above necessary conditions. 6 Incidentally, this is where symmetry plays a role. Without it, Equation (1) would be replaced by a system of di erential equations, and a more sophisticated machinery (or some clever trick) is required to establish the existence of a solution. We shall compute it explicitly under the additional assumption that G(s) = s, i.e. signals are uniformly distributed. Then the above di erential equation reduces to (N 1)[s a(s)] = sa0(s) whence we can verify immediately that a(s) = N 1N s is the only solution satisfying a(0) = 0. Given this parametrization, it is easy to verify that the pro le (N 1N s;:::;N 1N s) is indeed Bayesian Nash equilibrium of the rst-price auction. Indeed, it is the only symmetric equi- librium in di erentiable and increasing strategies. Note that this veri cation is necessary, because the di erential equation derived above was only a necessary condition for the func- tion a( ) to be a best reply. More generally, it can be shown that Equation (1), along with the boundary condition a(0) = 0, indeed de nes a Bayesian Nash equilibrium of the game. In case you are wondering whether invoking, say, concavity of the objective function to conclude that Equation (1) is also a su cient condition for a to de ne an equilibrium, think about the following: the concavity of the objective function U(a;s) depends on exogenously given entities such as v and G, but also on the function a itself. Two observations are in order. First, note that bidders shade their bids|the latter is always below their valuation, although the di erence shrinks to zero in the limit. However, under the same assumptions about signal distributions and valuations, rst- and second-price auctions yield the same expected revenues to the seller. To see this in our simple example, note that at any state s, the price paid to the seller equals the second-highest signal; hence, expected revenues are equal to the expectation of the second order statistic drawn from an i.i.d. uniform sample of size N. This is Z s N(N 2)!1!G(s)N 2[1 G(s)]g(s)ds = N(N 1) Z sN 1(1 s)ds = N 1N + 1: On the other hand, expected revenues in a rst-price auction equal N 1N times the expectation of the rst order statistic, Z sNG(s)N 1g(s)ds = N Z sNds = NN + 1: Again, this is actually an instance of a more general fact (see Myerson’s paper for details): assuming we are willing to compare equilibria in di erent games, rst- and second-price auctions are revenue-equivalent with private values. 7 Notes on interdependent values I will limit my remarks to the simplest possible example of bidding in an interdependent values-regime: the wallet game. In particular, assume there are only two bidders. Let us consider the second-price auction rst. A crucial di erence between private- and interdependent-values settings is that players no longer have weakly dominant strategies. With private values, a player who bids less than her valuation risks losing the object, and gains nothing conditional upon winning because her payment is not determined by her bid, but by her opponent’s. With interdependent values, her valuation conditional upon winning the object depends on her opponent’s bid function, because the latter determines the set of types against which she wins; thus, indirectly, her own bid determines her valuation conditional upon winning, and the entire logic of the Vickrey-Groves-Clark mechanism breaks down. Indeed, \truthful bidding" is not even de ned, if not perhaps with reference to a xed equilibrium belief! Thus, we can at best hope to obtain e ciency in equilibrium, not as a consequence of the sole assumption that players do not choose weakly dominated actions. Indeed, we shall see that e ciency may fail to obtain in equilibrium. Let us solve the wallet game under the second-price payment rule: recall that vi(s) = s1 + s2. I claim that the pro le (2s1;2s2) is a Bayesian Nash equilibrium of the associated game. We need only check that 2s is a best reply for type s against the putative equilibrium belief. Her expected payo when she bids a is given by U(a;s) = Z 1 2a 0 (s+s2 2s2)ds2 = 12as 12a2 which has a maximum at a = 2s, as one can easily check; the second-order conditions are also easily veri ed. Also note that, since values are purely common, any allocation mechanism is trivially e cient. However, there are examples of three-bidder games with interdependent values in which e ciency fails. Note that revenues equal twice the expected value of the minimum of two i.i.d. uniform random variables, or (from our previous analysis) 23. Let us now consider a rst-price auction in this setting. I claim than now (s1;s2) is an equilibrium pro le. To see this, note that U(a;s) = Z a 0 (s+s2 a)ds2 = a(s a) + 12a2 and again the claim is proved. From our previous analysis, expected revenues equal the expected value of the maximum of two i.i.d. uniform variates, or (again) 23. This, however, is not generally the case for interdependent-values settings. 8 Micro-Notes on Correlation The foregoing discussion leaves open the issue of correlation vs. independence of signals. I will merely point out the di erences between these two cases in a limiting case: you should consult Myerson’s 1981 paper, or Cremer and McLean’s paper, for more on the topic. Let us consider a two-bidder rst-price auction with private values and perfectly correlated signals: that is, Prfs1 = s2g= 1. Thus, as soon as a bidder learns her signal, she also learns her opponent’s signal; for all practical purposes, at the interim stage the players are actually engaged in a game with complete information. It should be clear that the only equilibrium in the game where both signals equal some s2[0;1] is for both players to bid exactly s, i.e. their valuation (if the winning bidder bids more than her opponent, she gains by reducing her bid; if both are bidding a < s, then either one can gain by raising her bid slightly above a). Thus, there is no shading, and the seller is able to extract the whole surplus from the players. This turns out to be a general result. In any case, this simple example emphasizes that the stochastic structure of the signals matters. 9