TU1 S.I S Sc H GA0L B U SI,N.ESS SC H OO L From the Department of OPERATIONS AND MANAGEMENT SCIENCE Meyersonis seminal paper on mechanism design invokes differential reasoning in deriving his classical results. The argumsents used do not readily lend themselves to parallel derivations for finite type spaces. Because of this difference, and the transparency and intellectual dominance of Myerson's work, relatively few papers have looked at the case with finite agent types beyond the two-type case. This paper provides that parallel argument in the regular case, for which Myerson'S results are most often invoked. The results here for finite type spaces can be read alongside Myerson's results with no intuitive leaps. A minor error in Myerson's presentation, irrelevant with symmetrical agents, is corrected, allowing the results to handle the symmetrical and asymmetrical cases in one unified way. LEADING IN THOUGHT AND ACTION

Optimal Mechanisms with Finite Agent Types William S. Lovejoy University of Michigan Business School 701 Tappan, Ann Arbor, MI 48109-1234 Working paper WP03-024 October 15, 2003 Abstract Myerson's seminal paper on mechanism design invokes differential reasoning in deriving his classical results. The arguments used do not readily lend themselves to parallel derivations for finite type spaces. Because of this difference, and the transparency and intellectual dominance of Myerson's work, relatively few papers have looked at the case with finite agent types beyond the two-type case. This paper provides that parallel argument in the regular case, for which Myerson's results are most often invoked. The results here for finite type spaces can be read alongside Myerson's results with no intuitive leaps. A minor error in Myerson's presentation, irrelevant with symmetrical agents, is corrected, allowing the results to handle the symmetrical and asymmetrical cases in one unified way.

The number of papers and presentations on optimal mechanism design with finite agent types is far fewer than those for continuous type spaces. This probably follows from a difficulty in replicating the line of argument in Myerson's (1981) seminal paper, which invokes differential reasoning in deriving his classical results for optimal mechanisms. Because of this difference, and the transparency and intellectual dominance of Myerson's work, relatively few papers have looked at the case with finite agent types beyond the two-type case. However, the difference between continuous and finite type spaces can be more than cosmetic. For example, in procurement auctions types represent the cost structures of agent firms, and an analysis of optimal pre-auction investments by agents may lead to single points, or several discrete points, as possible investment (hence, type) solutions. As research moves forward to deconstruct the decision processes that lead up to type the difference between finite and continuous type spaces may become more than a mathematical detail. The articles that do exist on finite agent types do not follow Myersons line of argument, for the reasons noted. Rather, they either analyze the two-type case and exploit the natural simplifications that attend that assumption (c.f. Fudenberg and Tirole 2002), or they use mathematical programming or optimal control theory logic (references provided below). The alternative derivations end up, as they must, with accurate expressions for the optimization problem to be solved, sometimes in the form of necessary rather than sufficient conditions. However, these expressions do not as readily suggest the form of the optimal mechanism (at least, in the case of "regular auctions," which we will define below) as Myerson's results. We restrict attention to regular auctions in this paper, because these are where the cleanliness and transparency of Myerson's framework gives it an advantage over the alternative approaches mentioned. Finally, all existing derivations for finite agent types known to the author assume symmetrical agents, while Myerson's paper and this one handle the symmetrical and asymmetrical cases in one unified way. The mathematical tricks needed to overcome the obstacles to a derivation that parallels Myerson's arguments are well-known and documented, but have yet to be used in that fashion. This note provides this parallel derivation and the finite-type counterpart to Myerson's famous lemma 3. Hence, the component parts of this derivation are not new, although their use in concert to generate our eventual expressions is. The advantage of presenting the results in this way is the intuitive transparency that accrues to those who have already internalized Myerson's classical work. Theorem 1 below can be read alongside Myerson's lemma 3 with no intuitive leaps, and the results here converge to Myerson's as the feasible types become dense in a type space. 1

The critical result that allows us to circumvent the need for differential arguments is the replacement of global incentive compatibility constraints with local counterparts (lemma 1 below) and showing that even greater simplifications must hold at optimality (lemma 2 below). These arguments are well-known. For the intellectual heritage of this replacement in the context of finite agent types see Harris, Kriebel and Raviv (1982); Hart (1983) and Moore (1988). For text-book articulations of the argument see Stole (2001); Li, Malakhov and Vohra (2002) and Fudenberg and Tirole (2002). Stole and Li et al provide general results for finite agent types through a control theory and mathematical programming lens. Assume that there are n agents, and agent i has a type vi E HQ where Qi is a finite set with mi > 1 elements. We will number these elements as follows. Let ai = vt < 2 <... < vmi = b, so ai and bi (equivalently v1 and v"i) are the least and greatest elements of ~i and vk is increasing in k for 1 < k < mi. The principal's uncertainty about the value each agent places on the contract is captured in a probability distribution iri(vi), which is the probability that agent i has value vi. All other agents share this assessment of agent i's possible values. The values of various agents are assumed to be independent, so that the principal will assess the probability of any value vector v E JR with the product 7r(u) = HIl1T (vi). Agent i knows her own value, but she share's the generic understanding of other agent's values, so that she assesses the probability that the other (n-1) agents have values v-i E Rn-1 as 7r-_i(v_i) = Inj7zj(yj(). The principal's value for keeping the contract and not giving it to any of the n agents is vo, and is known to all. The principal wishes to select a mechanism to maximize his utility. By invoking the revelation principle, the principal can without loss of generality restrict himself to direct revelation mechanisms. In these, each agent reports her true type vi so that the principal receives the n-dimensional vector v in total. The principal declares, prior to the agents issuing these reports, the probability law that will map v into the allocation of the contract and the expected payment by each agent. That is, the principal declares a mechanism, which is a pair of functions p(v) and x(v) both with ranges in Rn. pi(v) is the probability that agent i will receive the contract, as a function of the vector of messages (v) received, and xi(v) is the expected payment by agent i, also as a function of the messages received. The principal wishes to select a mechanism (p, x) to maximize his utility, given that the agents will decide what message to deliver after they learn what p and x will be. We assume that all parties are risk-neutral with additive and separable utilities for money, so that the expected utility for agent i who reports her type truthfully is Ui(p, x, ti) = 7r-i( —i)[vipi(i,, Vi) - Xi( —i, i)] v-i 2

We ignore the linear revision functions ei in Myerson's model. The expected utility for the principal is n n Uo(p, x) = r(V)[Vo(1 - Pi ()) + x i('-)] iV - i-1 i As noted above, and consistent with Myerson's development, we restrict ourselves to direct revelation mechanisms without loss of generality. In these, the principal must choose a mechanism that is consistent with several feasibility constraints. Specifically, a mechanism (p, x) is feasible if it satisfies the following three conditions: 1. p must reflect a legitimate probability distribution, so that pi(y) > 0 for all i and v, and En pi(^) < 1 for all v. 1 - En= Pi(v) is the probability that the principal does not award the contract to any agent (in this case the principal gets vo). 2. No agent can be coerced into joining the bidding. That is, each agent must perceive at least as high an expected utility from joining the game as staying out. Mathematically this is the constraint that for all agents i and values vi E Qi, Ui(p, x, vi) > 0. 3. No agent should be able to do better (in expected utility) by lying, relative to telling the truth about her type. Mathematically this is Ui (p, X, vi) > 7Tr-i(V-i) [vip(*-i, s) - X(vi, s)] VI-i for all agents i, vi E i, and s C fi. Much of the analysis here (and in Myerson) involves finding a more convenient, but equivalent, form for feasibility. In the literature, (2) are called the "individual rationality" or I.R. constraints, and (3) are called the "incentive compatibility" or I.C. constraints. A key result in the continuous type case is Myerson's lemma 2, which provides an equivalent form for the I.C. constraints. As we have noted, his argument relies on differential reasoning, which does not translate directly for finite type spaces. However, the following two lemmas (which catalog results found in the references cited above) lead to essentially the same result. First, we define the following variables. Let Qi(p, vi) = Y_,i -i(v-i)p(_-i, vi). Thus, Qi (p, vi) is the probability that agent i will be awarded the contract if she reports Zv. Also, define Ui(slvi) =,_,I [vipi(vi, s) - xi( _i, s)], which is the expected utility for agent i if she reports value s when her true value is vi. If mi = 1 (there is only one possible type) for any agent i, then the I.C. constraints for that agent are automatically satisfied. Otherwise we can invoke the following. 3

Lemma 1: For any agent i with mi > 2, the I.C. constraints are equivalent to the following: a) Qi(p, vi) is nondecreasing in vi on 2i. b) Ui (vkl k) > Uii(k-1 k) for all 2 < k < m,. c) Uiz(v|lv) > Ul(vk+'llk) for all 1 < k < mi- 1. Proof: The I.C. constraints are equivalent to U(vzlvi) > Uit(sIvi) for all i, vi E Qi and s e Qi. Hence, the I.C. constraints imply (b) and (c). But, the I.C. constraints also imply (a). To see this, note that Ui (svi) = ',vi 7-ri(v_i)[spi(-_i, s) - xi(vi, s) + pi(v,-i, S)(Vi - s)] Ui (p, x, s) + Zi 71-i (vi)pi(v -i, s)(vi - s) = Ui(p,, s) + Qi(p, s)(vi - s) for all i, vi E Qi and s E Qi. Now, the I.C. constraints imply (b) and (c), as noted, which in turn imply that U, (V k) -i (V1 i) >0 > i(k ( -1) - Ui (k1 -1) for all i, and all 2 < k < mi. We can rewrite this as Ui (p,, Y)-Ui (p,, V-1) -_)- Qi (, ik-) (ik- ik) > i (p, X, vik) + Qi (, Vik) (v -i)Ui (p, xk-1), which is equivalent to Qi(, V i- )(k 1- v_ ) > Qi(p, vk)(v1 - Vk) which is equivalent to QiZ(p, v/- 1)(V- ) < Qi(p, vk)(vk - vk-1). Now, since vk > v-1 we have that Qi(p,v~1-) < Qi(p, vk) for all i and 2 < k < mi. So, the I.C. constraints imply that Qi(p,vi) is nondecreasing in vi. So, the I.C. constraints imply (a) - (c). The proof is complete if we can show that (a) - (c) imply the I.C. constraints. To show this, suppose (a) and (b) hold, then Ui (iklvik) =i (p ) > (Vk- ) U ( lvi = Ui (p, xk l)+Q.(p, k-)(vk-vk- 1 ). Likewise by the same argument Ui(p, -1) > U (p, k-2) + Qi(p, k-2) (k1 k-2). Hence, Ui (v> l - v-) U(P. c vh2) + Qi(P, ik 2)(vik-1 Vk-2) + Qp h k-1)( -1) 4

which since Qi is monotone is greater than or equal to U (p 2 x, -2) + Q(p, k k-1( + ~k-1 _ j2) =U(p, x, Xv-2) + Qi(p, vi-2)(k - 2) = t(v - 2 ). So, by induction if Qi is monotone we will have Ui(zklvuk) > lt(slv ) for all i, all 2 < k < mi and all s E Qi with s < k. A symmetrical argument starting with the upward local constraints (c) and monotonicity (a) reveals that Ui (/k I V/k) =U (p, xI /k) > Uj(p, x, +1) + Qp, I1)(v - ki+l) ~ U(p, x, +2) + Q,(p, u+2)(Q+l - v+2) + Q (p vk+f,k k+1) > U (p, x: +2) + Q(pz j+2)( - vk+2) and by induction Ui(VklVk) > Ui(p, x, s) + Qi(p, s)(vi - s) = Ui(slvi) for all i, all 1 < k < mi - 1, and all s e Qi with s > k. Putting these together, we see that (a) - (c) imply that Ui(vklik) > Ui(sIik) for all i, all vik E Qi, and all s e Qi. But, these are just the I.C. constraints. QED Armed with this equivalence result, we can recast the principal's mechanism design problem as maximizing Uo(p, x) subject to the following constraints 4) pi(y) > 0 for all i and v, and >=Pi(v) <: 1 for all v. 5) Ui(p,x, vi) > 0 for all agents i and values vi C Q. 6) Qi(p, vi) is nondecreasing in vi on Qi for all agents i. 7) Uit(iVl\Vk) > t (v-lhk ) for all agents i such that mi > 2 and all 2 < k < mi. 8) ti(vifl|A) > Ui(it+lIvP) for all agents i such that mi > 2 and all 1 < k < mi - 1. A key result allowing further analysis of this problem in closed form is the following. 5

Lemma 2:111 the principal's optimal mechanism design problem of maximizing Uo(p, x) subject to constraints (4) - (8), for all agents i with mi > 2, constraints (7) must be binding at optimality, and when these are binding then constraints (8) are automatically satisfied. Proof: Suppose (p, x) is an optimal mechanism, and constraints (7) are not binding. Then, we must have bfUi jr{ Ui(p, x,i4 > ttk -Upxu>) + Qi(p, Vj)i4 v>k1). This is equivalent to U~pxv)- U (pI xI1,u'>') > Qi (pIu1(z -uh) 0. So the left hand side must be strictly greater than zero, or Z r_, irjIui)[ p(Vti,v) _ Xi (V_,vtJi) 1kik-w>I wuuh1 -i(-x(ti, v>1)] >0o. Then, the principal can raise xi (tel, vik) slightly, increasing his objective but violating no constraints. This contradicts the assumption of optimality. So, at optimality constraints (7) must be binding. But, now that we know (7) are binding let's look at b4(v{~Iv) - Ui(w/ikvik) for any 1 <I k< mi -1 = U(pkcc v1) + Qi~, (PIt~+)4 -1i k4~1) -k~p c,1). Because we know (7) are binding, we know that U cc, 14~k1) Ui U(p, cc, vi) + (i jp, 14) (k1~1- 14) so that =U(, c, 1)+ Q,(p, wk)(uk+l1 14i) + Q, (p, Vk~')(1 k vk1) -k~p c 4 7= (14k+1 -Z 14)(Qi (p, 14) - Qijp ( v~+1)) K 0 where the last inequality follows because Qi is nondecreasing in vj. So, when (6) 'is satisfied and constraints (7) are binding, (8) is satisfied. QED Hence, for any agent with rni ~ 2 we can without loss of optimality replace (7) and (8) with the single constraint that (7) is binding, which is equivalent to Ui (p,cc,14+') = U, (pI XI,14) ~ Q, (p,14) (14~ -14i) for all i and all 1 </k <rni -1 This is an expression that is recursive in kc and can be rewritten as (9) U (p, cc, 14) = liJ (p, cc, ai) +Z Q(pv)v~ 11- v) for all i and all 1 K kc < rri where we define a sum from 1 toO0 (that is, Z>0= which is the required sum for k -=1) to be zero. 6

Note that (9) is the discrete version of Myerson's equation (4.3). Also, by defining E~= = O (9) holds for all mi > 1 and we can from this point forward analyze any mixture of agents with singleton types (mi = 1) and more (mi > 2) in one unified way. So facing agents with finite type spaces and mi > 1 for all i, the principal's mechanism design problem can be expressed as choosing (p, x) to maximize Uo(p, x) subject to the constraints (4), (5), (6), and (9). It is apparent that (9) and Ui(p,x,ai) > 0 for all i will imply (5). So, we can write the principal's mechanism design problem as follows. Maximize(p,x) E 7r(M) [u0(1 - Ei=1 pi()) + Zi i xi()] Subject to 10) pi(y) > 0 for all i and v, and E=lpi(v) < 1 for all v. 11) Ui(p, x,ai) > 0 for all agents i. 12) Qi(p, vi) is nondecreasing in vi on Qi, for all agents i. 13) Ui(p, x, vk) = Ui(p,x, ai) + Ek-l Qi(p, vi)(vi+ - vi) for all i and all 1 < k < mi. Now we can pick up Myerson's reasoning and carry it forward, yielding at each step a finite type counterpart to Myerson's results. The next lemma shows that for any p the principal can define an x to satisfy (11) and (13). Lemma 3: If for any p satisfying (10) and any i and Iv = (-ti, z4) the principal defines xi(v) = vikpi() - l(j + l- v)pi(v_,v i) then Ui(p,,ai) = 0 and Ui(p,c,vik) Ui(p, x, ai) + EX (Qi(p, v)Q1 - vi3) for all i and all 1 < k < mi Proof: We have by definition Ui(p, x, V) = - _i t(-i(V-i) [LVikpi (-i, v/ik)-Xi (v-i,' //)] and want to choose x so that (13) holds. That is, we want to choose x so that Ui (p, X,,,i) - T, (z)[ ( p(,i) p (-i (-i,)] -U x7 a7i) + E, 1 Qi(Pi Vi v ^ = Ui (p, x, ai) ~jl Qi (, )( +vi1 -i )v) = i (p, x, ai) + ZX= E,_, w(-i(V-j)pPi(V-i, v)(,vi - ij) But these equalities are equivalent to Ui(p,x, ai) = _7rii(i) [,p(i ) -Xi(i,)] - EZ -i(-i)tE —1 (>i!/ )p ('- i) 7

= -,_i T-i(y-i) [uipi(-i, i) - xi(Vi, ik) Z-I( -P i, Vi-)]. So if for any v = (~ti, yk) we set Xi(Vl) = ikpi(v) 7 k- 1 (v+ 1 - j)p ( ) then we simultaneously get Ui(p, x, ai) = 0 and Ui(p, x, vik) = Ui(p, x,ai)+_L1 Qi(p, i)(v+l V ). QED We are now ready to prove the main result, which is the discrete analog to Myerson's Lemma 3. For any vi = Vk and k < mi -1 define Avi = v/k+l vk. Define this to be zero for k = mi. That is, for any v. E Qi, Avi is the upward difference to the next highest type for agent i, and for the highest type Avi = 0. Theorem 1: Suppose p maximizes S ir(v) Zpi(V) [i - o - (-F ) A(i] subject to (10) and (12). Suppose also that for any i and v- (v-i, ik) Xi(>) =,ikpi(V) _ Ek-1(Mi+1 _ V)i( i) =- - 4)p("-) -). Then (p, x) is an optimal auction. Proof: The key is to rewrite the principal's objective function as choosing (p, x) to maximize n _ n 1 - F7 (vi) -U ~ i(p,x, ai) + 7r(V) Pi(v) [vi- o- r -- Ai] i=1 1 i= 1(Vi) subject to the constraints (10) - (13). But, x only appears in the second term in the objective function and in the constraints (11) and (13). So, if we choose x to minimize 2n1 Ui(p, x, ai) subject to (11) and (13) we are doing the best we can. If for any p we define x as in Lemma 3, we have i= Ui(P, x, a) = 0 which is the best possible outcome for the principal, and (11) and (13) are automatically satisfied. The result then follows. So, the key is to show that the objective function can be written as claimed. The remainder of the proof justifies this. The principal's objective is Zm T(v) [vo (1 - in Pi ()) + Zil i (/)] = vo + i__ Z, r(i) [i(VQ) - Vopi(&)] = /0 + EL1 Ei 7 (l) [CXi(/) - ViPi(I) + ViPi(V) - V0Pi()] = vo + En 7r(u) [-(ViPi((V) - - i(v)) + Pi(I)(/vi - /o)] 8

= o + = E, 7(r) [P (v) (v - vo)] - Z I= E_, T- (-i.) E 7ri i(i ) [(-i Pi ) )- Xi( -i, i)]l Note that this last term is just - 1 i ~kl I 7ri(4T)Ui (p, X, V) We will now expand this using (13) to get E- 1 Ek=1 7i (v )Ui (p, X, lik) - k=1 + 47ri (p X ai) + 1 Qi- )] 1 - ZV= Eri ^(^ h a p -2_ En E Zwi E @QdpIi4(v$ 1 - ) =E t =i / k=l 71i ( Vii ) i k= ) 1 > i 1 i) ( Vi+ I It can be verified that we can resequence the sums Ek=I 32=1 Eml 2 mJ+i SO that the term is Eni= l Ekl 7ri (v( p, X En 1 Em- m~l 1rmi 7(i ) Q, )- Q( ) ( j+ l k= z i=kj+ Yi =1 2i -') Because Em7 7ri(vk) = 1 and EjY+l 7i(vik) = (1- Fi(vi)) this term is - Ei=1 Ui(p, x, ai) - E2 1 Qi(p, )(/i1 - v)(1 - F(v)). By the definition of Qi this is - Li Ui(p,, ai)- Ei=i E 1 E.._ 7r-()p(_i, )( 1- )( - Fi(vi)) Noting that for any v = (_i, i), 7ri(v-i) = (-'i) by the independent values assumpni(vi) tion, we have that this term is = Ui (p, x, ai) - En= E2i7 1 E_1( i P i - )( ) - ()) '- i> jp, _ ') a - z>i z-, 27J1 ( 4)('1 - / f)(1 -- i()) - Ei= Ui(p, x, ai) - = E _ i (-=I vi) (vii+- ) ((- )) Recalling that vi = -O when vi = vimi (and, anyway, 1-Fi(Vi3) = O under those conditions), we can equivalently take the sum from j 1 to mi, and the term is n Tn. 1 E, Fi r(v')) =- — Ein=I Ui (p, x, ai - ni= ~V. n'i(vi) Pi (V-i'/ 'i)/\ 'i (1 V —i)(,i)) Now, adding this term back we get the principal's objective function as vO + E-=i E 7-(l/)Pi(I)(/i - V0) - Lit U(p, a Pi(v-i) v v-i)Ai( - Fi(vi)) v= i- Ui(P, ai) - E, 7(v) E=1pi i() [ - o - Fi( i)i] which is the desired expression, completing the proof. QED 9

Note that for any agent with a singleton type, mi = 1, principal will ask for the transfer xi () = jiPi () and Ui(p,x,vi) = Ui(px,ai) = 0. That is, with complete information about an agent's type, the principal extracts all potential rents from that agent, as expected. Optimal mechanisms in the regular case The beauty of this result is the simplicity with which optimal mechanisms can be identified, almost by inspection. Myerson, again, provides the conceptual groundwork. However, direct translation of Myerson's results is complicated by the fact that Myerson's paper contains a minor error in his section on regular auctions, and in his continuous type case ties need not be considered because they are probability zero events. This is not the case with finite type spaces. Refining Myerson's results We begin by refining Myerson's results for continuous type spaces. Recall that we are ignoring Myerson's linear revision functions ei. In this case, Myerson's "virtual value" for agent i is defined as 1 - Fi(vi) Vi -) - fi2f(vi) An auction with continuous type spaces is called "regular" if this virtual value is strictly increasing in type vi. It is apparent from the objective function in Myerson's lemma 3 that if all agents have virtual values less than o,? the principal should not award the contract (pi = 0 for all agents i). This defines the reservation price for the auction. Otherwise, the principal will want to award the contract to the agent with the highest virtual value (pi = 1 for that agent). Equivalently, one can consider the principal as another bidder, who submits a bid with virtual value o0, and the contract goes to the bidder with the highest virtual value. As noted, in the continuous type case ties are probability zero events and can be ignored in expectation. The problem with this easy prescription is that in the general case we might violate the constraint that the probability of winning be nondecreasing in type (Myerson's equation 4.2). However, this is not a problem for regular auctions. If the agent with the highest virtual value gets the contract in a regular auction, then an agent's probability of winning is automatically nondecreasing in type (because the virtual value is). Hence, the optimal allocation p is easy in the regular case, and then the optimal transfers x can be computed directly from p as in Myerson's lemma 3. To make this explicit, Myerson defines the function zi(vi) to be the infimal type for agent i such that agent i's virtual value meets or exceeds both the principal's value vo 10

and the virtual value of all other agents. This infimum is attained if the virtual value is a continuous function, which is commonly assumed. In that case, zi (vi) is the minimal winning type for agent i given the values of all other agents. Myerson's equation (5.4) is appropriate in his setting, in which ties can be ignored. However, with either continues or finite type spaces, the influence of ai (the lower support of the beliefs regarding agent i's type) on the optimal transfers cannot be ignored, as Myerson apparently does in his equations (5.5) and (5.6). Myerson derives equations (5.5) and (5.6) as if zi(vi) > ai always. It can be shown that this is guaranteed in the symmetric case, but not in general. With continuous types, the correct expression for Myerson's (5.5) should be ralz a, pi(V-i, s)ds [yi - max{a/, zQi(-i}]t where [x]+ denotes the greater of x and zero. It follows that the zi (vi) term should be replaced by max{ai, zi(v-i)} in Myerson's optimal transfer equation (5.6). It is apparent that if agent i cannot value the contract below ai dollars, and the principal knows this, then if the principal awards the contract to agent i he will ask for ai dollars even if all competing bids are strictly below ai. This revision is not required for symmetric auctions, which dominate current applications. In the asymmetrical case, however, the difference can be significant. Optimal mechanisms in the regular case with finite agent types To construct optimal auctions in the finite type case we follow Myerson's logic refined as suggested above, using our theorem 1 rather than Myerson's lemma 3 as a point of departure. Define agent i's virtual value by <v- (vi) vi(l't) Viw- L(vvj) We call the auction "regular" if Vi(v) is nondecreasing in v for all agents i. It is easily shown that if all agents have only two possible types the auction is always regular, whether or not the agent types are symmetrical. Again, we can consider the principal to submit a "bid" with virtual value vo and we will want to award the contract to the bidder with the highest virtual value if that bidder is unique. We discuss ties below. As before, by awarding the contract to agents with the highest virtual value, constraint (12) is automatically satisfied in the regular case. The simplest case is where a single agent, i say, has the unique maximal virtual value. Then pi () = 1 and pj(v) = 0 for all j $ i. If the lowest possible value in agent i's feasible set, ai = u, is higher than any competing bid, it can be verified that the optimal transfer 11

in Theorem 1 reduces to xi(y) = ai and xj(v) = 0 for all j 4 i. If, on the other hand, there is an integer r such that v? > ai is the smallest feasible winning bid for agent i, yet still a unique maximum among the competing bids, then the optimal transfer from the winning agent is i is v[ instead of ai. This is consistent with Myerson's results, refined as above. With finite agent types ties may occur with positive probability. This will always be the case with symmetric auctions. The principal can break ties arbitrarily, but the choice can affect transfers and hence the potential information rents to agents. We illustrate this with an example motivated by Harris and Raviv (1981). Those authors prove the form of an optimal mechanism by constructing an upper bound and then proving their mechanism attains it. Here we will derive the result directly from Theorem 1. There are two symmetrical agents each drawing her type uniformly from a finite set [l, u2,..., r]. Hence, the probability that any one type from this set is drawn is 1/r. Further, the type levels are equally spaced, so that vk - vk-l = d a constant, for k > 2. The principal's value vo is fixed and known to all. In this case, 1 - Fi(v k)= (- /r - and the virtual value for agent i with vi = vk is vk - (r - k)6 for 1 < k < (r - 1). For the highest type the virtual value is just vi. Hence, the virtual value is strictly increasing in type, and this is a regular auction. The principal should award the contract to the highest bidder, if that bidder is unique and has a virtual value exceeding vo (Harris and Raviv assume that v0 > 21 - Vr which is sufficient to imply that the contract is awarded with probability one). It is implicit in Harris and Raviv that each agent has an equal probability of winning in the case of a tie, but here we allow potentially weighted schemes. Assume that in the case of a tie, the principal will give the contract to agent 1 with probability q, and to agent 2 with probability (1 - q). We now look at the potential resolutions for this auction. Suppose that agent 1 wins the auction outright because vl = vk > v2 = Ik where k < k. Hence, k denotes the winning bid and k the second price. In this case agent 1 is asked to pay xl(v) = qvk + (1 - q)k+l. So, when q < 1 she is asked to pay more than the second price, the extra payment decreasing in her probability of winning ties. This is not the case with a continuous type space. If agent 2 wins (v2 = k > vl = A, so k still denotes the second price) she is asked to pay x2(v) = (1- q)vk + qvik+l, with the same interpretation except the payment increases in q. If they tie (1l = v2) then the contract is awarded according to q and the agents are asked to pay (in expectation) x (v) = qvl and x2(M) = (1 - q)t2. One obvious implementation in the case of a tie is to award the contract according to q and ask for full value from the winning agent. So, agents earn no rent in the case of a tie. Harris and Raviv show that an optimal mechanism will ask for payment equal (in expectation) to the second price plus half of S from a unique winner, 12

and half the value from each agent in a tie. This is consistent with the above optimal mechanism with q = 1/2. The discrete nature of the type space decreases the information rents to agents relative to a second price auction. With the more general tie-breaking rule q $.5 and a discrete type space, more information rents accrue to the favored agent unless the agents tie. References Fudenberg, D. and J. Tirole. Game Theory. The MIT Press, Cambridge, MA, 2002. Harris, M. and A. Raviv. Allocation Mechanisms and the Design of Auctions. Econometrica 49 (6), Nov 1981, 1477-1499. Harris, M. C. Kriebel and A. Raviv. Asymmetric Information, Incentives and Intrafirm Resource Allocation, Management Science 28(6), 1982, 604-620.. Hart, O. Optimal Labour Contracts under Asymmetric Information: An Introduction. Review of Economics Studies 50 (1), Jan 1983, 3-35. Li, X., A. Malakhov and R. Vohra. A Primer on Optimal Auctions. Unpublished working paper. Northwestern University, 2003. Moore, J. Contracting between two parties with private information. Review of Economic Studies LV, 1988, 49-69. Stole, L. Lectures on the Theory of Contracts and Organizations. Unpublished working paper, University of Chicago, 2001. 13