Maximal revenue with multiple goods: nonmonotonicity and other observations

Reny, Philip J.; Hart, Sergiu Article Maximal revenue with multiple goods: nonmonotonicity and other observations Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Reny, Philip J.; Hart, Sergiu (2015) : Maximal revenue with multiple goods: nonmonotonicity and other observations, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 10, Iss. 3, pp. 893-922, https://doi.org/10.3982/TE1517 This Version is available at: https://hdl.handle.net/10419/150267 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Theoretical Economics 10 (2015), 893–922 1555-7561/20150893 Maximal revenue with multiple goods: Nonmonotonicity and other observations Sergiu Hart Department of Economics, Department of Mathematics, and The Federmann Center for the Study of Rationality, The Hebrew University of Jerusalem Philip J. Reny Department of Economics, University of Chicago Consider the problem of maximizing the revenue from selling a number of goods to a single buyer. We show that, unlike the case of one good, when the buyer’s values for the goods increase, the seller’s maximal revenue may well decrease.We then identify two circumstances where monotonicity does obtain: when optimal mechanisms are deterministic and symmetric, and when they have submodular prices. Next, through simple and transparent examples, we clarify the need for and the advantage of randomization when maximizing revenue in the multiplegood versus the one-good case. Finally, we consider “seller-favorable” mechanisms, the only ones that matter when maximizing revenue. They are essential for our positive monotonicity results, and they also circumvent well known nondifferentiability issues. Keywords. Revenue maximization, multidimensional types, nonmonotonicity, randomization, differentiability. JEL classification. C6, C7, D4, D8. 1. Introduction Consider the problem of a seller who wishes to maximize the revenue from selling multiple goods to a single buyer with private information about his value for the goods. In contrast to the one-good case where a complete solution has been known for years,1a general solution in the case of multiple goods remains elusive and, except under special circumstances,2very little is known about even the form of the solution or its properties. Sergiu Hart: [email protected] Philip J. Reny: [email protected] Previous versions: June 2011, November 2012 (Center for Rationality DP-630), April 2013, November 2013. Research partially supported by the European Research Council (FP7-249159) and the National Science Foundation (SES-0922535, SES-1227506). The authors thank Bob Aumann, Elchanan Ben-Porath, Eddie Dekel, Alex Gershkov, Ilan Kremer, Vijay Krishna, Noam Nisan, Motty Perry, Eyal Winter, and Asher Wolinsky for useful discussions and suggestions. We also thank the co-editor and the referees, whose perceptive comments, questions, and suggestions led us to sharpen and improve our results. 1See Myerson (1981), who deals also with multiple buyers. 2See, e.g., Armstrong (1996), Thanassoulis (2004), Pycia (2006), Manelli and Vincent (2006,2007,2012), Pavlov (2011), and Hart and Nisan (2014a,2014b). Copyright ©2015 Sergiu Hart and Philip J. Reny. Licensed under the Creative Commons AttributionNonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE1517 894 Hart and Reny Theoretical Economics 10 (2015) The present paper highlights some important differences between the one-good and the multiple-good cases. In Section 2, we exhibit the surprising phenomenon that the seller’s maximal revenue may well decrease when the buyer’s values for the goods increase.3This revenue nonmonotonicity can occur only when there is more than one good: revenue is easily shown to be nondecreasing in the buyer’s value when there is only a single good. Thus, the seemingly clear intuition that the seller is able to extract more revenue from buyers whose valuations for the goods are higher turns out to be false in general.4 Under what circumstances will the seller’s maximal revenue increase when the buyer’s distribution of valuations increases? In Section 2.3, we identify two such circumstances: one when the mechanism is deterministic and symmetric, and the other when payments to the seller can be described by a submodular pricing function. These positive revenue-monotonicity results are both interesting in their own right and help explain why counterexamples to monotonicity (ours included) cannot be entirely transparent—they must involve randomizations or asymmetries, and their revenue function cannot be submodular. In Section 3, we present a simple example where randomization is necessary for revenue maximization, and clarify why randomization is needed only when there are multiple goods. In Section 1.2, we formally introduce “seller-favorable” mechanisms, where, when the buyer is indifferent, the tie is always broken in favor of the seller. These mechanisms are the only ones that matter when maximizing the seller’s revenue, and also play an important role in the positive monotonicity results of Section 2.3.IntheAppendix,we characterize the revenue of seller-favorable mechanisms using directional derivatives, which exist everywhere; this has the additional benefit of circumventing nondifferentiability issues that arise from incentive compatibility, which, while ultimately harmless, are often a distracting nuisance within the analysis. The maximal-revenue problem has been shown to be significantly less well behaved when the values of the goods are not independent; see Hart and Nisan (2013,2014a, 2014b).5It is, therefore, important also to obtain (inevitably more subtle) examples with independent, and even independent and identically distributed (i.i.d.), values. We do so both for revenue nonmonotonicity and for randomization. 3What we compare is the maximal revenue from two given distributions, one having higher values than the other (formally, this means first-order stochastic dominance). 4When the mechanism is held fixed, there are well known examples in which the seller’s revenue unexpectedly falls; for instance, when the number of bidders increases (Matthews 1984,Menicucci 2009) and when the seller releases more information (Perry and Reny 1999). But in both of these cases, the seller’s maximal revenue cannot fall since the seller can always choose to ignore the additional bidders and can always choose not to release new information. Adams and Yellen (1977) show that a multiple-good monopolist, when facing a buyer who can consume at most one good, can sometimes increase profits by using negative advertising to reduce a consumer’s value for one of the goods. The constraint that buyers can consume at most one good is important for their example. See footnote 18 in Section 2.2 (we thank an anonymous referee for bringing the Adams and Yellen paper to our attention). 5It is shown there, for instance, that deterministic mechanisms always ensure at least one-half of the maximal revenue in the independent case, but only an arbitrarily small fraction in the general (correlated) case. Theoretical Economics 10 (2015) Maximal revenue with multiple goods 895 1.1 Preliminaries The seller possesses k≥1goods (or “items”), which are worth nothing to him (and there are no costs). The valuation of the goods to the buyer is given by a vector6 x=(x1x2xk)∈Rk +,wherexi≥0is his value for good i. The valuation is assumed to be additive over the goods: the buyer’s value of a subset L⊂{12k}of goods is i∈Lxi. The buyer knows the valuation vector x, whereas the seller knows only that xis drawn from a given probability distribution Fon Rk +. We make no further assumptions on F.Inparticular,Fmay possess atoms, and its support may be finite or infinite and need not be convex or even connected. The seller and the buyer are risk-neutral and have quasilinear utilities. A(direct) mechanism for selling the kgoods is given by a pair of functions (q s), where q=(q1q2qk):Rk +→[01]kand s:Rk +→R. If the buyer reports that his valuation is x, then qi(x) ∈[01]is the probability that the buyer receives good7i(for i=1k), and s(x) is the payment that the seller receives from the buyer. We call q the allocation function and call sthe payment function;therangeM:= {(q(x) s(x)) : x∈Rk +}⊂[01]k×Rof the mechanism is referred to as its menu.8When the buyer reports his valuation xtruthfully, his payoff is b(x) =k i=1qi(x)xi−s(x) =q(x) ·x−s(x) and the seller’s payoff is9s(x). A mechanism (q s) is individually rational (IR)ifb(x) ≥0 for all x∈Rk +, and it is incentive compatible (IC)ifb(x) ≥q(y) ·x−s(y) for all xy ∈Rk +. By the revelation principle, the maximal revenue from the distribution Fis Rev(F):= supEF[s(x)],wherexis distributed according to F, and the supremum is over all IC and IR mechanisms10 (q s). 1.2 Seller-favorable mechanisms We now introduce the concept of seller-favorable mechanisms: these are incentivecompatible mechanisms for which it is not possible to increase the seller’s payment function while leaving the buyer’s payoff function unchanged, without violating incentive compatibility. Formally, the IC mechanism (q s) is seller-favorable if there is no other IC mechanism (˜ q ˜ s) having the same buyer payoff function, i.e., ˜ q(x) ·x−˜ s(x) = b(x) =q(x) ·x−s(x) for all x∈Rk +, and a larger payment function, i.e., ˜ s(x) ≥s(x) for every x∈Rk +, with strict inequality for some x∈Rk +. This implies, in particular, that when the buyer is indifferent, ties must be broken in favor of the seller, i.e., q(y) ·x−s(y) =q(x) ·x−s(x) implies s(y) ≤s(x). 6The variable Ris the real line, Rkis the k-dimensional Euclidean space, and Rk +={x∈Rk:x≥0}is its nonnegative orthant. We follow the standard assumption that valuations are nonnegative; in Section A.1, we deal with arbitrary valuations. 7The assumption of risk neutrality implies that only the marginal probabilities of getting each good matter. 8An interpretation is that the seller “posts” the menu and the buyer “chooses” from it. 9In the literature, this is called transfer, cost, price, or revenue, and is denoted by t,c,p, and so on. We hope that using the mnemonic sfor the seller’s final payoff and bfor the buyer’s final payoff will avoid confusion. 10Such that sis measurable. In Section A.1 (footnote 48), we will see that measurability is not an issue. 896 Hart and Reny Theoretical Economics 10 (2015) When maximizing revenue, these are the only mechanisms that matter. Moreover, the restriction to seller-favorable mechanisms simplifies the analysis (in particular, it circumvents nondifferentiability issues; see the Appendix) and, as we will see in Section 2.3, it is needed to obtain monotonicity results. The characterization of IC mechanisms (qs) as those whose allocation function, q, is a subgradient of the buyer’s convex payoff function is well known (starting with Rochet 1985). It is an inconvenient and often technically annoying fact that the buyer’s convex payoff function, while differentiable almost everywhere, need not be differentiable everywhere. Proofs that are otherwise simple and elegant often require detours through subgradient measurable selection arguments.11 Such detours can be avoided when one restricts attention to seller-favorable mechanisms. The reason is that the buyer’s payoff function is not differentiable only when he is indifferent between a number of reports. But if the mechanism (q s) is seller-favorable, the buyer’s truthful report must maximize the seller’s payoff among all of the buyer’s optimal reports. As we will show in the Appendix, this implies that q(x) ·x=b(x;x), which denotes the directional derivative of bat xin the direction x(see the formal definitions after the proof of Lemma 13) for every buyer valuation x. Consequently, in a seller-favorable mechanism, the buyer’s payoff function bcompletely determines the seller’s payoff function sat every x, whether it is a point of differentiability of bor not, and s(x) =b(x;x) −b(x) for all x. Seller-favorable mechanisms are relatively easy to construct from any IC mechanism; moreover, doing so while preserving the menu (up to closure) and so preserving certain useful properties (such as submodularity; see Section 2.3)turnsouttobemore subtle. Proposition 1. Let (qs) be an IC mechanism, with buyer payoff function band menu M. Then there exists a seller-favorable mechanism (˜ q ˜ s) with buyer payoff function ˜ band menu  Msuch that ˜ b(x) =b(x) and ˜ s(x) ≥s(x) for all x∈Rk +,and 12  M⊂clM. Proposition 1 is proved in the Appendix (see Proposition 16), together with a number of additional useful results. 2. Nonmonotonicity:Increasing values may decrease revenue When the buyer’s values for the goods increase, what happens to the seller’s maximal revenue? It stands to reason that the revenue should also increase, as there is now more value for the seller to “extract.” While this is easily shown to be true when there is one good (Section 2.1), it is perhaps a surprise that it no longer holds when there are multiple goods (Sections 2.2 and 2.4). To see this, consider two situations: in the first, the valuation is given by the (Rk +- valued) random variable X1with distribution function F1; in the second, the valuation is given by the random variable X2with distribution function F2. Assume that X1≤X2 11For example, Lemma A.4 in Manelli and Vincent (2007); cf. footnote 56 in the Appendix. 12The notation clMdenotes the closure of the set M(in [01]k×R). Theoretical Economics 10 (2015) Maximal revenue with multiple goods 897 everywhere; i.e., in every state ω, the realization X1(ω) of X1is less than or equal to (in all kcoordinates) the realization X2(ω) of X2. What we will show is that the maximal revenue that is obtained from X2may well be smaller than the maximal revenue that is obtained from13 X1. In terms of distributions, the condition X1≤X2amounts to first-order stochastic domination of F1by14 F2. 2.1 Monotonicity for one good When there is only one good, i.e., k=1, incentive compatibility (IC) implies that a buyer with a higher valuation pays no less than a buyer with a lower valuation. Thus, increasing the valuation of the buyer can only increase the revenue. Proposition 2. Let F1and F2be two distributions on R+.IfF2first-order stochastically dominates F1,thenRev(F1)≤Rev(F2). Proof. First, we claim that every IC mechanism is monotonic in the sense that the seller’s payoff increases weakly with the buyer’s value: if x>y≥0, then s(x) ≥s(y).Indeed, for all x,y, the IC inequalities at xand at yimply (q(x) −q(y))x ≥s(x) −s(y) ≥ (q(x) −q(y))y,hence(q(x) −q(y))(x −y) ≥0;whenx>y, it follows that q(x) −q(y) ≥0 and, thus, s(x) −s(y) ≥0(because y≥0). Second, first-order stochastic dominance implies that EF1[s(x)]≤EF2[s(x)]for every IC mechanism, since sis a nondecreasing function.  Remark.Proposition 2 also follows easily from Myerson’s (1981) characterization of the optimal revenue when there is one good as Rev(F)=supp≥0p·(1−F(p)). However, the proof above shows that revenue monotonicity holds not only for optimal mechanisms, but for any incentive-compatible mechanism. 2.2 Nonmonotonicity for multiple goods Surprisingly, Proposition 2 does not hold when there is more than one good. That is, increasing the buyer’s valuations need not yield higher revenue to the seller. When there are multiple goods, one can easily construct examples of IR and IC mechanisms that are not monotonic.15 Take, for instance, the mechanism where the buyer is offered a choice from the following menu of four outcomes: get nothing and pay nothing (with payoff =0); or get good 1 for price 1(with payoff =x1−1); or get good 2 13Thus, in applications where the distribution of X2is not precisely known, and only a certain lower bound X1is given, the optimal revenue from X1does not necessarily provide a lower bound for the optimal revenue from X2. 14Formally, F2first-order stochastically dominates F1if and only if EF1[u(X)]≤EF2[u(X)]for every nondecreasing function u:Rk→R. As is well known, this is equivalent to having two random variables X1and X2with distributions F1and F2, respectively, that are defined on the same probability space and satisfy X1≤X2pointwise (this is called coupling). A comprehensive treatment of stochastic dominance can be found in Shaked and Shanthikumar (2007). 15Our first such example was constructed together with Noam Nisan. 898 Hart and Reny Theoretical Economics 10 (2015) Figure 1. The nonmonotonic mechanism (1). for price 2(with payoff =x2−2); or get both goods for price 4(with payoff =x1+x2−4); thus, the buyer’s payoff is b(x1x2)=max{0x1−1x2−2x1+x2−4}(1) See Figure 1 for the regions in the buyer’s valuation space where each outcome is chosen. If the valuation of the buyer is, say, x=(17 3), then his optimal choice is to pay 2for good 2 (so q(x) =(01)and s(x) =2), whereas if his valuation increases to x=(27 3) (where the first good is worth more) or even to x =(28 3)(where both goods are worth more), then his optimal choice is to pay 1for good 1 (so q(x)=q(x)=(10)and s(x)= s(x)=1). Thus the seller receives a lower payment (1instead of 2) when the buyer’s values increase.16 What is happening is that the initially unchosen good 1 is acting as an outside option for the buyer. When the buyer’s value for this outside option increases sufficiently, he switches away from good 2 toward good 1, which, because it happens to be cheaper than good 2, causes the seller’s revenue to fall. The above example, while insightful, ignores the fact that the seller optimally sets prices. In particular, the seller can optimally adjust prices in response to changes in 16When the value of one good goes up, the probability of getting it cannot go down (i.e., qi(x) is nondecreasing in xifor each good i; this follows from the convexity of the buyer payoff function b). However, at the same time, the probabilities of getting other goods may well go down, and in a such a way, moreover, that the allocation is worth less to the buyer—and so, by incentive compatibility, the seller’s payment goes down.Inourexample,forx=(17 3)and x=(27 3),wehaveq(x) =(01)and q(x)=(10), and so q(x) ·x>q(x )·xand s(x) > s(x). Theoretical Economics 10 (2015) Maximal revenue with multiple goods 899 the buyer’s value distribution. The difficult question then is whether this nonmonotonicity can also occur for the maximal revenue. We provide two examples: a simpler one (below), where the unique optimal mechanism is exactly the mechanism described above,17 and a more complicated one (Section 2.4), where the valuations of the two goods are independent and identically distributed. One reason that such examples are subtle is because the buyer can consume multiple goods (in fact, there is always a buyer type who gets the bundle of both goods in optimal mechanisms). Thus, when the buyer’s value of an inexpensive good that he is not purchasing increases (as in the above example), the seller may find it optimal to change the prices so that the buyer purchases a bundle of goods that includes the goods he originally purchased as well as the inexpensive good whose value increased. Consequently, the substitution away from an expensive good toward a cheaper one—which causes revenue to fall in the above example—might never occur (cf. our results in Section 2.3 below which give sufficient conditions for monotonicity). Thus, having the option to optimally price bundles of goods makes it more likely that the seller’s maximal revenue will not fall after an increase in the buyer’s values, and, hence, makes it more difficult to find an example in which they, in fact, do fall.18 Example 1. For every 0≤α≤1 4,letFαbe the distribution on R2: Fα= ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ (11)with probability 1 4 (12)with probability 1 4−α (22)with probability α (23)with probability 1 2. As αincreases, probability mass is moved from (12)to (22),andsoFαfirst-order stochastically dominates Fαwhen α>α . Nevertheless, the maximal revenue Rev(Fα) decreases with α(in the region 0≤α≤1 12 ). ♦ Proposition 3. In Example 1, for every 0≤α≤1 12 , Rev(Fα)=11 4−α 17This explains the reason for including the outcome x1+x2−4in the mechanism. 18In contrast, when the consumer can purchase at most one good—the “unit-demand” setup—the seller’s maximal revenue can easily fall. For example, suppose the buyer’s valuation is equally likely to be (11)or (13), and that he can consume at most one of the two goods. It is then optimal for the seller to set prices p1=1and p2=3, generating revenue 1+3=4. However, if the buyer’s valuation of (13)increases to (23), while the valuation (11)does not change, it is now optimal to set prices p1=1and p2=2, generating less revenue, namely 1+2=3(prices p1≥2and p2=3also generate revenue 3). This exampleisasimplificationofanexampleinAdams and Yellen (1977; Figure 9), who consider a buyer who can consume at most one of two brands (goods) of a single product. In the Adams and Yellen example, the maximal revenue decreases after the seller, through advertising, optimally modifies some values of some buyer types. While this is not a first-order stochastic dominance change in values, by considering first the decrease in some values and then the increase in other values, an example of the kind we have provided here emerges. A caveat with the Adams and Yellen analysis is that they restrict attention to pricing mechanisms and so they do not show that their mechanisms are fully optimal. However, it can be shown that the pricing mechanisms in the simplified example that we have given here are fully optimal among all mechanisms. 900 Hart and Reny Theoretical Economics 10 (2015) Valuation x=(x1x2) Outcome q(x) =(q1(x)q2(x)) s(x) (11)(10)1 (22)(10)1 (12)(01)2 (23)(11)4 Table 1. The optimal mechanism for Example 1. Proof. First, revenue of 11 4−αis achieved by the mechanism given in Table 1 (whose buyer payoff function is (1)). Indeed, revenue is 1 4·1+(1 4−α) ·2+α·1+1 2·4=11 4−α. Second, we show that a higher revenue cannot be obtained. Consider the inequalities q11 1+q11 2−s11 ≥0 1 q12 1+2q12 2−s12 ≥q11 1+2q11 2−s11 1 2 2q22 1+2q22 2−s22 ≥2q11 1+2q11 2−s11 3α 2q23 1+3q23 2−s23 ≥2q11 1+3q11 2−s11 1 4−3α 2q23 1+3q23 2−s23 ≥2q12 1+3q12 2−s12 1 4+α 2q23 1+3q23 2−s23 ≥2q22 1+3q22 2−s22 2α (2) (the first inequality is IR at (11)and the others are various IC constraints). Multiplying these inequalities by the multipliers on the right (which are all nonnegative when 0≤α≤1 12 ) and then adding them up yields −3 4−3αq11 2−2αq12 1+1 4−3αq12 2+2αq22 1+q23 1+3 2q23 2 ≥1 4s11 +1 4−αs12 +αs22 +1 2s23 The right-hand side is precisely the expected revenue at Fα, and the left-hand side is at most 0+0+(1 4−3α) +2α+1+3 2=11 4−α(since q11 2q12 1≥0and q12 2q22 1q23 1 q23 2≤1). Therefore, the revenue cannot exceed 11 4−α, and so the revenue of 11 4−α achieved by Table 1 is indeed maximal.  Once again, what is happening here is that the value of a good that is unchosen by one type of buyer—i.e., good 1 for the buyer with valuation (12)—increases with positive probability, to (22). This leads that buyer to switch away from the good he is currently purchasing, namely good 2, toward the previously unchosen good 1. Since good 1 is cheaper than good 2 and because the optimal prices do not change in this example, the seller’s maximal revenue falls.19 19In fact, for mechanisms (such as those in the examples above) that assign each of the goods with probabilities 0or 1only (called deterministic mechanisms below), a necessary condition for nonmonotonicity of the seller’s maximal revenue is that the value of a good to a buyer to whom the good is not assigned must rise (with positive probability). Theoretical Economics 10 (2015) Maximal revenue with multiple goods 907 Valuations x Outcome q(x) s(x) (1010)(1013)(1310)(1313), (1046)(4610)(1346)(4613) (4646), (1347)(4713)(1047)(4710) (00)0 (4647)( 32 1,187 384 13,057 )34,240 13,057 ≈26 (4746)( 384 13,057 32 1,187 )34,240 13,057 ≈26 (4747)( 35 1,187 35 1,187 )3,258 1,187 ≈27 (1380)( 32 1,187 5,647 5,935 )90,672 1,187 ≈764 (8013)( 5,647 5,935 32 1,187 )90,672 1,187 ≈764 (4680)( 35 1,187 5,647 5,935 )90,810 1,187 ≈765 (8046)( 5,647 5,935 35 1,187 )90,810 1,187 ≈765 (1080)(10100)(13100)(01)80 (8010)(10010)(10013)(10)80 (46100)(10046), (4780)(8047)(47100)(10047), (8080)(80100)(10080)(100100) (11)126 Table 2. The unique optimal mechanism for F2×F2. Proposition 10. In Example 2,F2first-order stochastically dominates F1and Rev(F2×F2)<Rev(F1×F1) Proof. Maximizing revenue for a distribution with finite support is a linear programming problem (the unknowns are the qi(x) and s(x) for all xin the support, the constraints are the IR and IC inequalities, and the objective function is the expected revenue). Using Maple yields the following situation.31 The (unique32) optimal mechanism for F2×F2consists of 11 outcomes; see Table 2 (the outcomes are ordered according to increasing payment to the seller s). For F1×F1, the same mechanism is optimal; however, the fifth and sixth outcomes are not used (the value 13 has probability 0) and may be dropped. This yields Rev(F1×F1)=408,189,937 5,875,650 and Rev(F2×F2)=30,614,162,731 440,673,750  and so indeed Rev(F1×F1)>Rev(F2×F2)(these revenues are 6947145 and 6947126). The nonmonotonicity of the payments can be seen at33 s(1080)> s(1380) s(4680)and s(8010)>s(8013) s(8046). 31The fractions appearing in the solutions below are exact. 32Uniqueness is proved using the dual linear progamming problem as in Section 2.2. 33Recall, however, that sbeing a nonmonotonic function, while necessary, is not sufficient; cf. the second paragraph of this section. 908 Hart and Reny Theoretical Economics 10 (2015) 3. Lotteries and revenue To maximize revenue in the one-good case (i.e., k=1), it suffices to consider deterministic mechanisms (specifically, “posted-price” mechanisms; see Myerson 1981). That is not so in the multiple-good case. Examples where the optimal mechanism requires randomization (i.e., in some of the outcomes the probability of getting a good is strictly between 0and 1)have been provided by Thanassoulis (2004) (in the slightly different context of “unit demand,” where the buyer is limited to one good), Pycia (2006), Manelli and Vincent (2006,2007), Briest et al. (2010) (for unit demand), and Pavlov (2011,Example 3(ii)). However, most of these examples are relatively complicated and require nontrivial computations, and it is not clear how and why randomization helps only when there are multiple goods. We will provide two examples that are simple and transparent enough that the need for randomization becomes clear. In the first, the values of the two goods are correlated; in the second, the values are independent and identically distributed.34 3.1 Lotteries for multiple goods Consider the following example with two goods and three possible valuations35 (the values of the two goods are correlated). Example 3. Let Fbe the two-dimensional probability distribution F=⎧ ⎪ ⎨ ⎪ ⎩ (10)with probability 1 3 (02)with probability 1 3 (33)with probability 1 3.♦ Proposition 11. The mechanism (q s) defined by Table 3 with buyer payoff function b(x1x2)=max01 2x1−1 2x2−2x1+x2−5(11) is the unique revenue-maximizing IC and IR mechanism for Fof Example 3. Thus, the buyer can get both goods for price 5, or get good 2 for price 2,orget good 1 with probability 1 2for price 1 2; the optimal revenue is 5 2=25. If the seller were restricted 34Manelli and Vincent (2007) provide an example (Example 1) of an “undominated mechanism” that uses lotteries. While they prove that an undominated mechanism is optimal for some distribution F,itis also claimed there (Theorem 9) that any undominated mechanism is optimal for some distribution with independent goods (i.e., a product distribution). However, there is an error in the proof of Theorem 9, as the set of product distributions (specifically, the set Gin their proof) is not convex. See the corrigendum in Manelli and Vincent (2012). 35Pycia (2006) solves the seller’s problem when there are exactly two valuations and shows that randomization may be needed. For instance, when the valuations are (23)and (61)with equal probabilities, the unique optimal mechanism gives the (23)buyer good 2 and a 1 2chance of getting good 1, for the total price of 4, and gives the (61)buyer both goods for the total price of 7. However, we have found that Example 3, with three possible valuations, provides more transparent insights (as there is a clearer separation between the IC and IR constraints). Theoretical Economics 10 (2015) Maximal revenue with multiple goods 909 Valuation x Outcome q(x) s(x) (10)( 1 20)1 2 (02)(01)2 (33)(11)5 Table 3. The unique optimal mechanism for Example 3. to deterministic mechanisms (where each qiis either 0or 1), then the optimal revenue would decrease to 7 3=233(attained, for instance, by selling separately, at the optimal single-good prices of 3for good 1 and 2for good 2; see below). A detailed explanation of the role of randomization and why it is needed only when there are multiple goods, follows the proof below. Proof of Proposition 11.Let(α1β1);σ1,(α2β2);σ2,and(α3β3);σ3be the outcome (q1(x)q2(x));s(x)at x=(10) (02),and(33), respectively (thus αiβi∈ [01]). The objective function is S:= σ1+σ2+σ3(this is three times the revenue). Consider the relaxed problem of maximizing Ssubject only to the individual-rationality constraints at (10)and (02), and to the two incentive-compatibility constraints at (33), i.e., α1−σ1≥0 2β2−σ2≥0 3α3+3β3−σ3≥3α1+3β1−σ1 3α3+3β3−σ3≥3α2+3β2−σ2 These inequalities can be rewritten as σ3+3α1+3β1−3α3−3β3≤σ1≤α1 σ3+3α2+3β2−3α3−3β3≤σ2≤2β2 Therefore, so as to maximize S=σ1+σ2+σ3,wemusttakeσ1=α1and σ2=2β2,which gives σ3≤3α3+3β3−2α1−3β1 σ3≤3α3+3β3−3α2−β2 Thus, we must take α3=β3=1,β1=α2=0,andthenσ3=min{6−2α16−β2},andso S=α1+2β2+min{6−2α16−β2}=min{2β2−α1β2+α1}+6. Since Sis increasing in β2,wemusttakeβ2=1,andthenS=min{2−α11+α1}+6is maximized at36 α1=1 2. 36For deterministic mechanisms (i.e., αiβi∈{01}), everything is the same up to this point, but now Sis maximized at both α1=0and α1=1; the optimal revenue for deterministic mechanisms is thus S/3=7 3. 910 Hart and Reny Theoretical Economics 10 (2015) x q(x) s(x) q(1)(x) s(1)(x) q(2)(x) s(2)(x) (10)( 1 20)1 2(10)1(00)0 (02)(01)2(01)2(01)2 (33)(11)5(11)4(11)5 Table 4. Replacing a lottery outcome when there are two goods. This is precisely the mechanism in Table 3, which is easily seen to satisfy also all the other IR and IC constraints.  To understand the use of randomization, consider the outcome (1 20);1 2at x= (10)in Table 3: it is a lottery ticket that costs 1 2and gives a 1 2probability of getting good 1; alternatively,37 it is a 1 2−1 2lottery between getting good 1 for the price 1(i.e., (10);1) and getting nothing, and paying nothing (i.e., (00);0). It is thus the average of these two deterministic outcomes, and we now consider what happens when we replace the lottery by either one of them (see Table 4). It turns out that in both cases, the revenue strictly decreases. In the first case, replacing (1 20);1 2by (10);1forces the price of the bundle to decrease to 4(otherwise, the (33)buyer would switch from paying 5for the bundle to paying 1for good 1); therefore, the net change in the revenue is 1 3·(1−1 2)+1 3·(4−5), which is negative.38 In the second case, replacing (1 20);1 2 by (00);0results in the loss of the revenue from the (10)buyer, without, however, increasing the revenue from the (33)buyer: indeed, if we were to increase the bundle price, then (33)would switch to (01);2, i.e., would get good 2 for price 2(and, if we were to drop this outcome (01);2altogether so as to increase the bundle price to 6, the total revenue would again decrease).39 It is instructive to compare this with a similar example, but with a single good. Assume the values are x=103, with equal probabilities of 1 3each (just like good 1 in Example 3). Take the mechanism with outcomes 1 2;1 2,0;0,1;2(see Table 5); it is easy to see that it is IC and IR, and its revenue is 5 6. The lottery outcome 1 2;1 2—getting the good with probability 1 2for price 1 2—is the average of 0;0and 1;1. Replacing the lottery 1 2;1 2with 1;1lowers the revenue to 2 3:the3buyer switches to 1;1. Replacing the lottery 1 2;1 2with 0;0increases the revenue to 1:the3buyer is now offered, and chooses, 1;3.Therevenueof5 6of the original mechanism, which used the lottery outcome, is precisely the average of the revenues from these two resulting mechanisms, 2 3 and 1(this averaging property holds at each valuation x). This is a general phenomenon when there is only one good: the revenue from a mechanism that includes an outcome that is a probabilistic mixture of two outcomes (a “lottery outcome”) is the average of the revenues obtained by replacing the lottery 37Because of risk neutrality. 38The buyer’s payoff function in this mechanism is b(1)(x) =max{x1−1x2−2x1+x2−4}. 39The buyer’s payoff function in this mechanism is b(2)(x) =max{0x2−2x1+x2−5}. Theoretical Economics 10 (2015) Maximal revenue with multiple goods 911 xqsq (1)s(1)q(2)s(2) 11 2 1 21100 0000000 3121113 Table 5. Replacing a lottery outcome when there is one good. with each one of these two outcomes and then adapting the remaining outcomes.40 Formally, this is the counterpart of expressing the corresponding buyer payoff function bas an average of two such functions; in the example above, b(x) =max{0x/2−1 2x−2} is the 1 2−1 2average of b(1)(x) =max{0x−1}and b(2)(x) =max{0x−3}(i.e., b(x) = (b(1)(x) +b(2)(x))/2for all x). Thus, lotteries are indeed not needed when there is only one good. Example 3 illustrates why this is not the case for multiple goods: replacing the lottery outcome with (00);0yields the mechanism (q(2)s(2)),whoserevenueislower than that of (q s) (whereas replacing 1 2;1 2with 0;0yields a higher revenue). In fact, the function bof (11) is an extreme point in the set of buyer payoff functions (in particular, it is not the average of the buyer functions in footnotes 38 and 39). This is exactly where having more than one good matters. In the case of one good, there is only one binding constraint per value x, namely, the outcome chosen by the next lower value. Consequently, removing an outcome (such as a lottery outcome) that is chosen by xenables the seller to increase the revenue obtained from all higher-valuation buyers (i.e., with values y>x), as they can no longer switch to the outcome that has been removed and they strictly prefer their own outcome to any of the outcomes chosen by values below x. In contrast, when there are multiple goods, such an increase in revenue may not be possible because there may be multiple binding constraints for each valuation x(in our example, buyer (33)is indifferent between reporting truthfully and reporting either (10)or (02)). These buyer types may switch to other outcomes that involve other goods, and so the total revenue may well decrease. Next, how does a lottery outcome increase revenue? The seller would like to earn positive revenue from selling good 1 to the (10)buyer, but without jeopardizing the higher revenue obtained from selling the bundle of both goods to the (33)buyer (and, as we have seen, he cannot increase the price of the bundle because of the “good 2 for price 2” alternative, i.e., (01);2). If the price of good 1 is above 1, then (10)will not buy it; if it is below 1, then (33)will switch from buying the bundle to buying good 1 (since his payoff will increase from 1to 2or more).41 Thus, selling good 1 does not help. What does help is selling only a fractional part of good 1, which has the effect of making this option less attractive to the high-valuation buyer (33)(since his possible gain 40This statement, which is easily proved in general—even when the two outcomes that are averaged are not necessarily deterministic—provides another proof of Myerson’s result that in the one-good case, it suffices to consider deterministic mechanisms (use this “local decomposition” repeatedly). 41As we saw above, lowering the price of the bundle to 4(while keeping the price of good 1 at 1)will not help either, because the total revenue decreases. 912 Hart and Reny Theoretical Economics 10 (2015) Valuations x Outcome q(x) s(x) (11)(00)0 (21)( 1 20)1 (12)(01 2)1 (14)(41)(22)(24) (42) (44)(11)4 Table 6. The unique optimal mechanism for Example 4. is smaller: it is only that fraction of the difference in values). Thus, the two conflicting desiderata—getting some revenue from a low-valuation buyer and not jeopardizing the higher revenue from a higher-valuation buyer—are reconciled by offering to sell fractions of the goods, i.e., lotteries. In the present example, that optimal fraction turns out to be 1 2; it comes from balancing the incentives between the two goods (specifically, 1 2is the ratio of two value differences, 3−2for good 2 and 3−1for good 1; see the Proof of Proposition 11 above).42 Finally, we note that mechanism design is a sequential game, with the seller moving first. In such games, the use of randomization may, in general, be strictly advantageous to the first mover (take, for instance, the sequential matching pennies game). Thus, the surprising fact here is not that randomization can increase revenue (when there are multiple goods), but that it cannot do so when there is only one good.4344 3.2 Lotteries for independent and identically distributed goods We now provide a simple example where lotteries are necessary to achieve the maximal revenue for two goods that are independent and identically distributed. Example 4. Let Fbe the one-dimensional probability distribution F=⎧ ⎪ ⎨ ⎪ ⎩ 1with probability 1 6 2with probability 1 2 4with probability 1 3, and take two independent F-distributed goods, i.e., F=F×F.♦ Proposition 12. The mechanism (q s) defined by Table 6 with buyer payoff function b(x1x2)=max01 2x1−11 2x2−1x1+x2−4 is the unique optimal mechanism for F=F×Fof Example 4. 42Thus, one can easily get other probabilities by changing the values. Moreover, the example is highly robust: it has a large neighborhood of distributions for which any optimal mechanism requires lotteries. 43We thank Bob Aumann for this comment. 44Pycia (2006) shows how, in the multiple-goods case, nondeterministic mechanisms are generically needed to maximize revenue. Theoretical Economics 10 (2015) Maximal revenue with multiple goods 913 Proof. First, the revenue from the mechanism in Table 6 is easily computed: it is 61 18 . Second, consider the following inequalities, which are various individual rationality and incentive-compatibility constraints:45 q11 1+q11 2−s11 ≥0 3 q12 1+2q12 2−s12 ≥0 8 2q21 1+q21 2−s21 ≥0 8 2q22 1+2q22 2−s22 ≥0 17 q12 1+2q12 2−s12 ≥q11 1+2q11 2−s11 1 2q21 1+q21 2−s21 ≥2q11 1+q11 2−s11 1 2q22 1+2q22 2−s22 ≥2q12 1+2q12 2−s12 3 2q22 1+2q22 2−s22 ≥2q21 1+2q21 2−s21 3 q14 1+4q14 2−s14 ≥q12 1+4q12 2−s12 3 4q41 1+q41 2−s41 ≥4q21 1+q21 2−s21 3 2q22 1+2q22 2−s22 ≥2q14 1+2q14 2−s14 1 2q22 1+2q22 2−s22 ≥2q41 1+2q41 2−s41 1 2q24 1+4q24 2−s24 ≥2q22 1+4q22 2−s22 8 4q42 1+2q42 2−s42 ≥4q22 1+2q22 2−s22 8 4q44 1+4q44 2−s44 ≥4q24 1+4q24 2−s24 2 4q44 1+4q44 2−s44 ≥4q42 1+4q42 2−s42 2 (12) Multiplying each inequality by the weight on the right and adding up yields s11 +3s12 +3s21 +9s22 +2s14 +2s41 +6s24 +6s42 +4s44 ≤2q22 1+q14 1+10q41 1+8q24 1+24q42 1+16q44 1(13) +2q22 2+10q14 2+q41 2+24q24 2+8q42 2+16q44 2 The left-hand side turns out to be precisely 36 times the expected revenue of the seller for the distribution F=F×F, i.e., 36EF[s(x)], and the right-hand side is bounded from above by 122 (replace all q1and q2there by their upper bound of 1). Therefore, EF[s(x)]≤122 36 =61 18 . Recalling that 61 18 is precisely the revenue of the mechanism in Table 6 shows that Table 6 is optimal. Finally, to see that Table 6 is the only optimal mechanism, by the proof above, for the maximal revenue of 61 18 to be achieved, all the inequalities must become equalities. First, all the q1and q2appearing on the right-hand side of (13) must equal 1: 1=q22 1=q14 1=q41 1=q24 1=q42 1=q44 1(14) =q22 2=q14 2=q41 2=q24 2=q42 2=q44 2 45These specific inequalities and their corresponding multipliers below were obtained by solving the dual of the linear programming problem of maximizing revenue. 914 Hart and Reny Theoretical Economics 10 (2015) Second, the inequalities in (12), which are now equalities, yield, after substituting (14), s44 =s24 =s42 =s22 =s14 =s41 =4s 12 =s21 =1s 11 =0 q11 1=q11 2=q12 1=q21 2=0q 21 1=q12 2=1 2 Together with (14) this yields precisely the mechanism in Table 6. It can be checked that the maximal revenue achievable by a deterministic mechanism is 10 3(obtained by the mechanism with price 2for each good). Appendix A.1 Seller-favorable mechanisms This appendix deals with incentive-compatible and seller-favorable mechanisms, introduced in Section 1.2. The main results are collected in Theorem 17; see also Remarks (a) and (b) after Corollary 18 for a discussion of implementation issues. To be as general as possible, we will work here with an arbitrary domain D⊂Rk of valuations; Dcould be Rk +, or it may be finite or infinite, and, in general, need not be convex or even connected. A mechanism is thus (q s):D→[01]k×Rand the buyer’s payoff function is b(x) =q(x) ·x−s(x).TherangeM:= (qs)(D) = {(q(x) s(x)) :x∈D}of the mechanism, also called the menu of the mechanism, consists of all those combinations of allocations g∈[01]kand payments t∈Rthat are used (Mis a subset of [01]k×R). The mechanism is incentive-compatible (IC) if b(x) = maxy∈D(q(y) ·x−s(y)) =max(gt)∈M(g ·x−t) for every x∈D.Itisseller-favorable if there is no other incentive-compatible mechanism (˜ q ˜ s) on Dhavingthesamebuyerpayoff function, i.e., ˜ q(x) ·x−˜ s(x) =b(x) =q(x) ·x−s(x) for all x∈D, and a larger payment function, i.e., ˜ s(x) ≥s(x) for every x∈D, with strict inequality for some x∈D.Thisimplies, in particular, that when the buyer is indifferent, ties must be broken in favor of the seller, i.e., q(y) ·x−s(y) =q(x) ·x−s(x) implies s(y) ≤s(x). The first lemma shows that one may extend any IC mechanism to a larger domain, even all Rk, and without increasing the menu Mbeyond its closure, which we denote by clM. Lemma 13. Let (q s) be an IC mechanism on a domain D⊂Rk, with menu M= (q s)(D).Then(q s) can be extended to an IC mechanism (¯ q ¯ s) on the whole space Rk, with menu M=(¯ q ¯ s)(Rk)that satisfies M⊂M⊂cl M. Proof. Defining b(x) := sup(gt)∈M(g ·x−t) for every x∈Rkextends the buyer’s payoff function from Dto Rk. The function sis bounded from below (since b(x) =q(x)·x−s(x) is finite for x∈D), and so there is τsuch that t≥τfor all (g t) ∈M. Fix some element (g0t0)∈M;then,foreveryx∈Rk,onlythose(g t) in Mwith t≤x1+t0matter for b(x) (since g·x−t≥g0·x−t0implies t≤(g −g0)·x+t0≤x1+t0). Therefore, for every x∈Rk, the supremum in the definition of b(x) is attained, say at (¯ q(x) ¯ s(x)) ∈ clM;forx∈D,wetake(¯ q(x) ¯ s(x)) =(q(x)s(x)).Thusb(x) =¯ q(x) ·x−¯ s(x) = Theoretical Economics 10 (2015) Maximal revenue with multiple goods 915 max(gt)∈clM(g ·x−t) =maxy∈Rk(¯ q(y) ·x−¯ s(y)) for every x∈Rk,whichsaysthat(¯ q ¯ s) is IC on Rk. We shall thus consider without loss of generality mechanisms on Rk. The buyer’s payoff function b, as the pointwise supremum of affine functions, is a convex function on Rk, finite everywhere (since, as we have seen, for every x∈Rk,thesupremumis attained). We recall a few useful concepts for convex functions.46 Let f:Rk→Rbe a real convex function defined on Rk(and so dom f=Rk). The directional derivative of f at x∈Rkin the direction y∈Rkis f(x;y) := limδ→0+(f (x +δy) −f(x))/δ. Since f is convex, f(x;y) always exists. A vector g∈Rkis a subgradient of fat x∈Rkif f(y) −f(x) ≥g·(y −x) for all y∈Rk.Theset∂f ( x) of subgradients of fat xis a nonempty compact set, and f(x;y) =max{g·y:g∈∂f ( x )}for every x y ∈Rk. Finally, if 0≤f(x+z)−f(x)≤k i=1ziholds for every xz ∈Rkwith z≥0, then the function fis nondecreasing and nonexpansive.47 Let Bkbe the collection of all real functions on Rkthat are nondecreasing, nonexpansive, and convex. Lemma 14. Let (q s) be an IC mechanism on Rk. Then the buyer’s payoff function b belongs to Bk,andforeveryx∈Rk,thevectorq(x) is a subgradient of bat xand s(x) ≤ b(x;x) −b(x). Proof.LetM=(q s)(Rk)be the menu of (qs);thenb(x) =q(x) ·x−s(x) = max(gt)∈M(g ·x−t), as a supremum of affine functions, is a convex function. For every xy ∈Rk,weget b(y) −b(x) ≥(q(x) ·y−s(x)) −(q(x) ·x−s(x)) =q(x) ·(y −x) (15) which says that q(x) is a subgradient of bat x.Thus,q(x) ·x≤sup{g·x:g∈∂b(x)}= b(x;x) and so s(x) =q(x) ·x−b(x) ≤b(x;x) −b(x) for every x∈Rk. Finally, taking y= x+zwith z≥0in (15)impliesthat0≤q(x) ·z≤b(x +z) −b(x) ≤q(x +z) ·z≤k i=1zi, and so bis nondecreasing and nonexpansive.  Lemma 15. Let bbe a function in Bk. Then there exists an IC mechanism (q s) on Rk such that the buyer’s payoff function is b. Proof. Being nondecreasing, nonexpansive, and convex on Rk, the function bsatisfies 0≤b(x) −b(x −z) ≤g·z≤b(x +z) −b(x) ≤k i=1zifor every x∈Rk,everyg∈∂b(x), and every z∈Rk +.Inparticular,∂b(x) ⊂[01]k, and so we choose for each xsome q(x) ∈ ∂b(x) and put s(x) := q(x) ·x−b(x).Thenq(y) ·y−s(y) =b(y) ≥b(x) +q(x) ·(y −x) = q(x) ·y−s(x) (the inequality since q(x) ∈∂b(x))andso(q s) is IC.  46See Rockafellar (1970) for convex functions, their derivatives, and (sub)gradients. 47For convex f,thisisequivalentto0≤∂f(x)/∂xi≤1for all iand all x, where the derivative exists (i.e., for a.e. x). 916 Hart and Reny Theoretical Economics 10 (2015) Proposition 16. Let (qs) be an IC mechanism on a domain D⊂Rk, with buyer payoff function band menu M=(qs)(D). Then there exists a seller-favorable IC mechanism (˜ q ˜ s) on Rksuch that48 (i) ˜ q(x) ·x−˜ s(x) =b(x) =q(x) ·x−s(x) for every x∈D (ii) ˜ s(x) =b(x;x) −b(x) ≥s(x) for every x∈D (iii)  M:= (˜ q ˜ s)(Rk)⊂cl((q s)(D)) =cl M. Remark. Since b(x;x) =maxg∈∂b(x) g·x, choosing in the proof of Lemma 15 a˜ q(x) in ∂b(x) where this maximum is attained yields (˜ q ˜ s) that satisfies (i) and (ii), and so it is seller-favorable (by Lemma 14). However, the additional conclusion (iii) that the menu does not change (up to closure) is needed so as to guarantee that certain properties of the mechanism, such as submodularity, are preserved by seller-favorability (as in Corollary 20 in Section A.2 below); (iii) requires a somewhat more elaborate proof. Proof of Proposition 16. Applying Lemma 13 allows us to assume without loss of generality that the domain of (q s) is the whole space, i.e., D=Rk(the result for the extended mechanism clearly implies the result for the original one; note that if Mis the menu of the extended mechanism, then  M⊂clMimplies  M⊂clMbecause M⊂clM). For every x∈Rk,define(˜ q(x) ˜ s(x)) to be any limit point of the bounded sequence of points (q(xn) s(xn)) ∈[01]k×R,wherexn:= (1+1/n)x for each positive integer n (the sequence s(xn)is bounded because s(xn)=q(xn)·xn−b(xn)and bis continuous). Thus (˜ q ˜ s) satisfies (i) (again, because bis continuous) and (iii), and it is IC because (q s) is IC. Now for any xand n,Lemma 14 implies that ˜ q(x) ∈∂b(x) and q(xn)∈∂b(xn). In particular,49 for every g∈∂b(x),wehave0≤(q(xn)−g) ·(xn−x) =(q(xn)−g) ·x/n. Multiplying by nand taking the limit gives ˜ q(x) ·x≥g·x,andso˜ q(x) ·x= maxg∈∂b(x) g·x=b(x;x). The equality in (ii) follows because ˜ s(x) =˜ q(x) ·x−b(x) = b(x;x)−b(x) by (i), and the inequality in (ii) follows from Lemma 14, which also implies that (˜ q ˜ s) is seller-favorable.  It is useful to gather the above results into one theorem. Theorem 17. Let (q s) :D→[01]k×Rbe a mechanism defined on a domain D⊂Rk, with menu M:= (qs)(D) ={(q(x)s(x)):x∈D}and buyer payoff function50 b:Rk→R given by b(x) := supy∈D(q(y) ·x−s(y)) =sup(gt)∈M(g ·x−t) for every x∈Rk. Then the following statements hold: (i) The mechanism (q s) is an IC mechanism if and only if it is the restriction to Dof an IC mechanism (¯ q ¯ s) on Rkwith the same buyer payoff function band menu M:= (¯ q ¯ s)(Rk)that satisfies M⊂M⊂cl M. 48As the proof below shows, (i) and (ii) hold, in fact, for all x∈Rk,withbthe buyer payoff function of the extension of (qs) from Dto Rkobtained by Lemma 13. The equality in (ii) implies, in particular, that the payment function ˜ sof a seller-favorable mechanism is a Borel-measurable function on Rk. 49If fis a convex function, then (g −g)·(x −y) ≥0for all x,y,allg∈∂f ( x) , and g∈∂f ( y ) (add the inequalities f(y)−f(x)≥g·(y −x) and f(x)−f(y)≥g·(x −y)). 50The buyer’s payoff function bis always taken to be defined on the whole space Rk.