Mechanism design with maxmin agents: theory and an application to bilateral trade

Wolitzky, Alexander Article Mechanism design with maxmin agents: theory and an application to bilateral trade Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Wolitzky, Alexander (2016) : Mechanism design with maxmin agents: theory and an application to bilateral trade, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 11, Iss. 3, pp. 971-1004, https://doi.org/10.3982/TE2089 This Version is available at: https://hdl.handle.net/10419/150299 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 11 (2016), 971–1004 1555-7561/20160971 Mechanism design with maxmin agents: Theory and an application to bilateral trade Alexander Wolitzky Department of Economics, MIT This paper studies mechanism design when agents are maxmin expected utility maximizers. A first result gives a general necessary condition for a social choice rule to be implementable. The condition combines an inequality version of the standard envelope characterization of payoffs in quasilinear environments with an approach for relating agents’ maxmin expected utilities to their objective expected utilities under any common prior. The condition is then applied to give an exact characterization of when efficient trade is possible in the bilateral trading problem of Myerson and Satterthwaite (1983), under the assumption that agents know little beyond each other’s expected valuation of the good (which is the information structure that emerges when agents are uncertain about each other’s ability to acquire information). Whenever efficient trade is possible, it may be implemented by a relatively simple double auction format. Sometimes, an extremely simple reference price rule can also implement efficient trade. Keywords. Mechanism design, maxmin, ambiguity aversion, bilateral trade, Myerson–Satterthwaite. JEL classification. D81, D82. 1. Introduction “Robustness” has been a central concern in game theory and mechanism design since at least the celebrated argument of Wilson (1989). The Wilson doctrine is usually interpreted as calling for mechanisms that perform well in a wide range of environments. However, there is also growing and complementary interest in robustness concerns on the part of economic agents instead of (or in addition to) on the part of the mechanism designer; that is, in asking what mechanisms are desirable when agents use “robustly optimal” strategies. This paper pursues this question in the case where agents are maxmin expected utility (MMEU) maximizers (Gilboa and Schmeidler 1989), which Alexander Wolitzky: [email protected] For helpful comments, I thank Pierpaolo Battigalli, Aaron Bodoh-Creed, Subir Bose, Gabe Carroll, Glenn Ellison, Aytek Erdil, Ben Golub, Faruk Gul, Fuhito Kojima, Massimo Marinacci, Paul Milgrom, Stephen Morris, Suresh Mutuswami, Phil Reny, Ilya Segal, Andy Skrzypacz, Joel Sobel, Juuso Toikka, several anonymous referees, and seminar participants at Brown, Collegio Carlo Alberto, Columbia, Indiana, Leicester, Northwestern, NYU, Princeton, Simon Fraser, Stanford, Toronto, UBC, USC, UT Austin, Washington University, and the 2014 Cowles Foundation Conference on Economic Theory. I thank Jason Huang for excellent research assistance. Copyright ©2016 Alexander Wolitzky. Licensed under the Creative Commons Attribution-NonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE2089 972 Alexander Wolitzky Theoretical Economics 11 (2016) is perhaps the best-established model of robust decision-making under uncertainty, as well as the model most commonly adopted in prior studies of mechanism design with robustness concerns on the part of agents. In particular, the paper develops a general necessary condition for a social choice rule to be implementable, and applies this condition to give an exact characterization of when efficient trade is possible in the classical bilateral trade setting of Myerson and Satterthwaite (1983). The necessary condition for implementation generalizes a well known necessary condition in the Bayesian independent private values setting, namely that the expected social surplus must exceed the expected sum of information rents left to the agents, as given by an envelope theorem. That this condition has any analogue with maxmin agents is rather surprising, for two reasons. First, the usual envelope characterization of payoffs need not hold with maxmin agents. Second, and more importantly, a maxmin agent’s subjective belief about the distribution of opposing types depends on her own type. This is also the situation with Bayesian agents and correlated types, where results are quite different from those in the classical independent types case (Crémer and McLean 1985,1988,McAfee and Reny 1992). The derivation of the necessary condition (Theorem 1) addresses both of these issues. For the first, I rely on an inequality version of the standard envelope condition that does hold with maxmin agents. For the second, I note that, by definition, an agent’s maxmin expected utility is lower than her expected utility under any belief she finds possible. This implies that the sum of agents’ maxmin expected utilities is lower than the sum of their “objective” expected utilities under any possible common prior, which in turn equals the expected social surplus under that prior (for a budget-balanced mechanism). Hence, a necessary condition for a social choice rule to be implementable is that the resulting expected social surplus exceeds the expected sum of information rents for any possible common prior; that is, for any prior with marginals that the agents find possible. The second part of the paper applies this necessary condition to give an exact characterization of when efficient bilateral trade is implementable, under the assumption that the agents know each other’s expected valuation of the good (as well as bounds on the valuations), but little else. As explained below, this is the information structure that emerges when agents have a (unique) common prior on values at an ex ante stage and are maxmin about how the other agent might acquire information before participating in the mechanism. In this setting, the assumption of maxmin behavior may be an appealing alternative to the Bayesian approach of specifying a prior over the set of experiments that the other agent may have access to, especially when this set is large (e.g., consists of all possible experiments) or the agents’ interaction is one shot. Furthermore, the great elegance of Myerson and Satterthwaite’s theorem and proof suggests that their setting may be one where relaxing the assumption of a unique common prior is particularly appealing.1 1This is in line with Gilboa’s exhortation in his monograph on decision-making under uncertainty to “[consider] the MMEU model when a Bayesian result seems to crucially depend on the existence of a unique, additive prior, which is common to all agents. When you see that, in the course of some proof, things cancel out too neatly, this is the time to wonder whether introducing a little bit of uncertainty may provide more realistic results” (Gilboa 2009, p. 169). Theoretical Economics 11 (2016) Mechanism design with maxmin agents 973 Figure 1. In the bilateral trade setting, efficient trade is possible in the region below the curve and impossible in the region above it. The second main result (Theorem 2) shows that the Myerson–Satterthwaite theorem sometimes continues to hold when agents are maxmin about each other’s information acquisition technology—but sometimes not. In the simplest bilateral trade setting, where the range of possible seller costs and buyer values is [01], the average seller cost is c∗, and the average buyer value is v∗,Figure 1 indicates the combination of parameters (c∗v∗)for which an efficient, maxmin incentive compatible, interim individually rational, and weakly budget balanced mechanism exists. Above the curve, the formula for which is c∗ 1−c∗log1+1−c∗ c∗+1−v∗ v∗log1+v∗ 1−v∗=1 the Myerson–Satterthwaite theorem persists, despite the lack of a unique common prior or independent types. Below the curve, the Myerson–Satterthwaite theorem fails. I call the mechanism that implements efficient trade for all parameters below the curve in Figure 1 the αi(θi)double auction. It is so-called because when a type θiagent and a type θjagent trade, the type θiagent receives a share αi(θi)of the gains from trade that depends only on her own type and not on her opponent’s. The αi(θi)double auction has the property that an agent’s worst-case belief is the belief that minimizes the probability that strict gains from trade exist; this may be seen to be the belief that her opponent’s type always takes on either the most favorable value for which there are no gains from trade or the most favorable value possible. If an agent misreports her type to try to get a better price, the requirement that her opponent’s average value is fixed forces the deviator’s worst-case belief to put more weight on the less favorable of these values, which reduces her expected probability of trade. The share αi(θi)is set so that this first-order cost in terms of the probability of trade exactly offsets the first-order benefit in terms of price, which makes the αi(θi)double auction incentive compatible for maxmin agents.2Finally, the αi(θi)double auction is weakly budget balanced if and 2In contrast, the cost of shading one’s report in terms of foregone gains from trade would be second order for a Bayesian, as both the probability that shading results in a missed opportunity to trade and the foregone gains from trade conditional on missing a trading opportunity would be small. 974 Alexander Wolitzky Theoretical Economics 11 (2016) only if α1(θ1)+α2(θ2)≤1for all θ1,θ2; that is, if and only if the shares that must be left to the two agents sum to less than 1. This inequality holds in precisely the region below the curve in Figure 1. I also derive some additional results in the bilateral trade setting. Most notably, I show that if the average types of the two agents do not have gains from trade with each other (e.g., if the pair (c∗v∗)lies below the 45° line in Figure 1), then efficient trade can be implemented with an extremely simple mechanism, which I call a reference rule. A reference rule works by setting a “reference price” p∗and specifying that trade occurs at price p∗if this is acceptable to both agents, and otherwise that trade occurs (when efficient) at the reservation price of the agent who refuses to trade at p∗.Thisresult thus illustrates a case where introducing robustness concerns on the part of agents leads simple mechanisms to satisfy desirable mechanism design criteria. This paper joins a growing literature on games and mechanisms with maxmin agents or with agents who follow “robust” decision rules more generally. In contrast to much of this literature, the current paper shares the following important features of classical Bayesian mechanism design: (i) the implementation concept is (partial) Nash implementation; (ii) the only source of uncertainty in the model concerns exogenous random variables, namely other agents’ types; (iii) for Theorem 1, the model admits the possibility of a unique common prior as a special case. Several recent papers derive permissive implementability results with maxmin agents by relaxing these assumptions, in contrast to the relatively restrictive necessary condition of Theorem 1. Bose and Daripa (2009), Bose and Mutuswami (2012), and Bose and Renou (2014)relax (i) by considering dynamic mechanisms that exploit the fact that maxmin agents may be time-inconsistent. A central feature of their approach is that agents cannot commit to strategies, so they do not obtain implementation in Nash equilibrium. Their approach also relies on taking a particular position on how maxmin agents update their beliefs, an issue that does not arise here. Di Tillio et al. (2014)andBose and Renou (2014)relax (ii) by assuming that agents are maxmin over uncertain aspects of the mechanism itself. This lets the designer extract the agents’ information by introducing “bait” provisions into the mechanism. The mechanisms considered in these four papers are undoubtedly interesting and may be appealing in particular applications. However, they arguably rely on a more thoroughgoing commitment to maxmin behavior than does the current paper (agents must be time-inconsistent or must be maxmin over endogenous random variables). Even if one accepts this commitment, it still seems natural to ask what is possible in the more “standard” case where (i) and (ii) are satisfied. De Castro and Yannelis (2010) relax (iii) by assuming that agents’ beliefs are completely unrestricted, and they find that efficient social choice rules are then always implementable. This is consistent with Theorem 1, as with completely unrestricted beliefs agents can always expect the worst possible allocation, which implies that the necessary condition of Theorem 1 is vacuously satisfied. For example, in the bilateral trade setting, efficient trade is always implementable, as agents are always certain that they will not trade and are therefore willing to reveal their types. Thus, De Castro and Yannelis show that ambiguity aversion can soften the Myerson–Satterthwaite impossible result— consistent with Theorem 2—but they do so only under the rather extreme assumption of completely unrestricted beliefs. Theoretical Economics 11 (2016) Mechanism design with maxmin agents 975 Finally, Bose et al. (2006) and Bodoh-Creed (2012) satisfy (i), (ii), and (iii).3Their results are discussed below, but the main differences are that neither of these papers derives a general necessary condition for implementability like Theorem 1,andtheir treatment of applications focuses not on efficiency, but on revenue maximization. Importantly, this revenue maximization is conducted with respect to the mechanism designer’s “true” prior, whereas in my model there is no notion of a true prior and the designer is simply a stand-in for all the various games the agents could play among themselves. For example, Bodoh-Creed does consider an application to bilateral trade, but he investigates the minimum expected budget deficit required to implement efficient trade (from the designer’s perspective), rather than whether efficient trade is possible with ex post budget balance.4 The paper proceeds as follows. Section 2 presents the model. Section 3 gives the general necessary condition for implementation. Section 4 applies this condition to characterize when efficient bilateral trade is implementable. Section 5 contains additional results in the bilateral trade setting, including the results on implementation with reference rules. Section 6 concludes. The Appendix contains omitted proofs and auxiliary results. 2. Model Agents and Preferences:AgroupNof nagents must make a social choice from a bounded set of alternatives Y⊆Rn.Eachagentihas a one-dimensional type θi∈[ ¯ θi¯ θi]=i⊆R. Agents have quasilinear utility. In particular, if alternative y=(y1yn)is selected and atypeθiagent receives transfer ti,herpayoffisθiyi+ti.5 Agent i’s type is her private information. In addition, each agent ihas a set of possible beliefs −iabout her opponents’ types, where −iis an arbitrary nonempty subset of (−i), the set of Borel measures φ−ion −i. (Throughout, probability measures are denoted by φ, and the corresponding cumulative distribution functions are denoted by F.) Each agent ievaluates her expected utility with respect to the worst possible distribution of her opponents’ types among those distributions in −i;thatis,theagents are maxmin optimizers. 3Lopomo et al. (2014) also satisfy (i), (ii), and (iii), but consider agents with incomplete preferences as in Bewley (2002) rather than maxmin preferences. There are two natural versions of incentive compatibility in their model, which bracket maxmin incentive compatibility (and Bayesian incentive compatibility) in terms of strength. They show that the stronger of their notions of incentive compatibility is often equivalent to ex post incentive compatibility (whereas maxmin incentive compatibility is not), and that full extraction of information rents is generically possible under the weaker of their notions and is sometimes possible under the stronger one. 4The literature on mechanism design with risk-averse agents is more tangentially related to the current paper. Chatterjee and Samuelson (1983) and Garratt and Pycia (2015) propose mechanisms for efficient bilateral trade with risk-averse agents. In contrast, I maintain the assumption that utility is quasilinear. The mechanisms I propose bear little resemblance to those proposed for risk-averse agents. 5The assumption that utility is multiplicative in θiand yiis for simplicity. One could instead assume that utility equals vi(y θi)+tifor some absolutely continuous and equidifferentiable family of functions {vi(y·)},asinMilgrom and Segal (2002)orBodoh-Creed (2012). 976 Alexander Wolitzky Theoretical Economics 11 (2016) Mechanisms:Adirect mechanism (yt) consists of a measurable allocation rule y: →Yand a measurable and bounded transfer rule t:→Rn. Given a mechanism (yt),let Ui(ˆ θiθ−i;θi)=θiyi(ˆ θiθ−i)+ti(ˆ θiθ−i) Ui(ˆ θiφ−i;θi)=Eφ−i[Ui(ˆ θiθ−i;θi)] Ui(θi)=inf φ−i∈−i Ui(θiφ−i;θi) Thus, Ui(ˆ θiθ−i;θi)is agent i’s utility from reporting type ˆ θiagainst opposing type profile θ−igiven true type θi,Ui(ˆ θiφ−i;θi)is agent i’s expected utility from reporting type ˆ θiagainst belief φ−igiven true type θi,andUi(θi)is agent i’s worst-case expected utility from reporting her true type θi.6 A distinguishing feature of this paper is the notion of incentive compatibility employed,whichIcallmaxmin incentive compatibility. A mechanism is maxmin incentive compatible (MMIC) if θi∈argmax ˆ θi∈i inf φ−i∈−i Ui(ˆ θiφ−i;θi)for all θi∈ii∈N (1) I restrict attention to MMIC direct mechanisms throughout the paper. This is without loss of generality under the assumption that agents cannot hedge against ambiguity by randomizing, in that an agent’s utility from playing a mixed strategy μi∈(i) is Eμiinfφ−i∈−iUi(ˆ θiφ−i;θi)rather than infφ−i∈iEμiUi(ˆ θiφ−i;θi). Under this “nohedging” assumption, the proof of the revelation principle is completely standard.7 A brief aside on the no-hedging assumption: While the alternative is also reasonable, the no-hedging assumption is the standard one in decision theory. In particular, the uncertainty aversion axiom of Schmeidler (1989)andGilboa and Schmeidler (1989) says that the agent likes mixing ex post (i.e., state by state); mixing over acts ex ante does not affect her utility. In addition, as noted by Raiffa (1961), if agents could hedge with randomization, then one would not observe the Ellsberg paradox or other well documented, ambiguity-averse behavior. The no-hedging assumption is also standard in the literature on mechanism design with maxmin agents (e.g., Bose et al. 2006,De Castro and Yannelis 2010,Bodoh-Creed 2012,Di Tillio et al. 2014).8 In addition to MMIC, I consider the following standard mechanism design criteria. 6The term “worst case” is only used heuristically in this paper, but the meaning is generally that if minφ−i∈−iUi(ˆ θiφ−i;θi)exists, then a minimizer is a worst-case belief; while if the minimum does not exist (which is possible, as Ui(ˆ θiφ−i;θi)may not be continuous in φ−iand −imay not be compact), then a limit point of a sequence {φ−i}that attains the infimum is a worst-case belief. 7Under the solution concept of Nash equilibrium. In particular, there is no strategic uncertainty or “higher order ambiguity” (as in Ahn 2007). See the working paper version of this paper (Wolitzky 2016) for further details. 8However, Agranov and Ortoleva (forthcoming) present experimental evidence that sometimes agents do display a strict preference for randomization. Models of such preferences include Machina (1985), Cerreia-Vioglio et al. (2015), and Fudenberg et al. (2015).Saito (2015) axiomatizes a utility function that identifies an agent’s belief that randomization hedges ambiguity. Theoretical Economics 11 (2016) Mechanism design with maxmin agents 977 •Ex Post Efficiency (EF):Forallθ∈y(θ)∈arg maxy∈Yiθiyi. •Interim Individual Rationality (IR):Forallθi∈iUi(θi)≥0. •Ex Post Weak Budget Balance (WBB):Forallθ∈iti(θ) ≤0. •Ex Post Strong Budget Balance (SBB):Forallθ∈iti(θ) =0. Efficiency is self-explanatory. Interim individual rationality is imposed with respect to agents’ own worst-case beliefs; it also happens that all results in the paper continue to hold with ex post individual rationality (i.e., Ui(θiθ−i;θi)≥0for all θi∈i,θ−i∈−i). The ex post version of budget balance seems appropriate in the absence of a “true” prior distribution; as indicated above, this focus on ex post budget balance is an important point of contrast to the otherwise closely related papers of Bose et al. (2006) and BodohCreed (2012). The difference between weak and strong budget balance is that with weak budget balance, the mechanism is allowed to run a surplus. For purposes of comparison with the results of Section 4, recall that the standard Myerson–Satterthwaite theorem requires only (ex ante) weak budget balance. Also note that since MMIC is a weaker condition than dominant strategy incentive compatibility, an efficient allocation rule can always be implemented with a Vickrey–Clarke–Groves (VCG) mechanism if budget balance is not required. An allocation rule yis maxmin implementable if there exists a transfer rule tsuch that the mechanism (yt) satisfies MMIC, IR, and WBB. 3. Necessary conditions for implementation I begin with a general necessary condition for maxmin implementation, which generalizes a standard necessary condition for Bayesian implementation with independent private values. In an independent private values environment with common prior distribution F, it is well known that an allocation rule yis Bayesian implementable only if the expected social surplus under yexceeds the expected information rents that must be left for the agents so as to satisfy incentive compatibility. It follows from standard arguments (e.g., Myerson 1981) that this condition may be written as  iθ∈ θiyi(θ)dφ≥ iθi∈i (1−Fi(θi))yi(θiφ−i)dθi(2) where yi(θiφ−i)=Eφ−i[yi(θiθ−i)] (recall that φis the measure corresponding to cumulative distribution function F). I will show that a similar condition is necessary for maxmin implementation, despite the lack of independent types (in that an agent’s worst-case belief over her opponent’s types depends on her own type) or a unique common prior. Intuitively, the required condition will be that (2) holds for all distributions Fwith marginals that the agents find possi- 978 Alexander Wolitzky Theoretical Economics 11 (2016) ble, with the modification that, on the right-hand side of (2), the expected information rents under Fare replaced by the expectation under Fof type θi’s “minimum possible” information rent. To formalize this, given a measure φ∈(),letφSdenote its marginal with respect to Sfor S⊆N.Let∗be the set of product measures φ∈i∈N(i)such that φ−i∈ −ifor all i∈N. Some examples may clarify this definition. •If n=2, then ∗=1×2(where i≡−j). •Suppose the set of each agent i’s possible beliefs takes the form of a product −i= j=ii jfor some sets of measures i j⊆(j).Then∗=j∈N(i=ji j). •If n>2, it is possible that ∗is empty. For instance, take the previous example with i=ji j=∅for some j. Finally, let ˜ yi(θi)=inf φ−i∈−i yi(θiφ−i) Thus, ˜ yi(θi)is the smallest allocation that type θimay expect to receive. The following result gives the desired necessary condition. Theorem 1. If allocation rule yis maxmin implementable, then, for every measure φ∈∗,  iθ∈ θiyi(θ)dφ≥ iθi∈i (1−Fi(θi))˜ yi(θi)dθi(3) Comparing (2)and(3), (2) says that the expected social surplus under Fmust exceed the expected information rents, whereas (3) says that the expected social surplus must exceed the expectation of the agents’ minimum possible information rents, reflecting the fact that agents’ subjective expected allocations are not derived from F.In addition, (2) must hold only for the “true” distribution F(i.e., the common prior distribution), while (3) must hold for any “candidate” distribution F(i.e., any distribution in ∗). Furthermore, (3) is a generalization of (2), since in the case of a unique independent common prior φit follows that −i={φ−i}for all i,∗={φ},and˜ yi(θi)=yi(θiφ−i),so (3) reduces to (2). Finally, if yis continuous, then (3) also shows that (2) changes continuously as a slight degree of ambiguity aversion is introduced into a Bayesian model. The differences between (2)and(3) suggest that maxmin implementation is neither easier nor harder than Bayesian implementation in general and, more generally, that expanding the sets of possible beliefs −ican make implementation either easier or harder. In particular, expanding the sets −iexpands ∗, which implies that (3) must hold for a larger set of measures φ. However, expanding −ialso reduces ˜ yi(θi)and, thus, reduces the right-hand side of (3), making (3) easier to satisfy. Indeed, Section 4 shows that efficient bilateral trade is sometimes maxmin implementable Theoretical Economics 11 (2016) Mechanism design with maxmin agents 985 Now, letting tb(v c) =αb(v)(v −c) −v ts(c v) =αs(c)(v −c) +c for all c<v, so that the resulting mechanism is an αi(θi)double auction as described in the Introduction, it may be verified that weak budget balance holds for all (c v) if and only if it holds for (c =0v =1)(and it also may be verified that δs 0ˆ vis indeed a worst-case belief). Therefore, efficient trade is implementable if and only if tb(10)+ ts(01)≤0or, equivalently, αb(1)+αs(0)≤1. This is precisely condition (∗). In other words, condition (∗) says that the shares of the social surplus that must be left to the highest types in the αi(θi)double auction sum to less than 1. Finally, why does the sufficient condition for implementability that αb(1)+αs(0)≤1 match the necessary condition from Theorem 1? Recall that the necessary condition is that expected social surplus exceeds (a lower bound on) expected information rents (i.e., (3) holds) for any distribution φs×φb∈s×b. A first observation is that it suffices to compare the social surplus and information rents under the critical distribution δs 01× δb 01, as this distribution may be shown to minimize the difference between the leftand right-hand sides of (3). Note that the expected social surplus under δs 01×δb 01equals (1−c∗)v∗(1),asunderδs 01×δb 01there are strict gains from trade only if c=0and v=1, which occurs with probability (1−c∗)v∗. On the other hand, the expectation of (the lower bound on) the buyer’s information rent under δb 01equals v∗1 0 ˜ yb(v) dv +(1−v∗)0 0 ˜ yb(v) dv   =0  which may be shown to equal (1−c∗)v∗αb(1). The explanation for the appearance of the αb(1)term here is that this is the fraction of the social surplus that must be left to a type v=1buyer in an MMIC mechanism when a type vbuyer’s subjective expected allocation is ˜ yb(v) (in particular, the bound on an agent’s subjective information rent given by integrating ˜ yi(θi)is tight in the current setting). Symmetrically, the expectation of the seller’s information rent under δs 01equals (1−c∗)v∗αs(0), and therefore the necessary condition from Theorem 1 reduces to (1−c∗)v∗≥(1−c∗)v∗(αb(1)+αs(0)) or αb(1)+αs(0)≤1. The approach taken to constructing the αi(θi)double auction is quite different from standard approaches in Bayesian mechanism design. In particular, the approach here is to posit a type vbuyer’s worst-case belief to be δs 0v (the belief that minimizes the probability that strict gains from trade exist), to solve a differential equation coming from incentive compatibility for tb(v0), which gives the formula for αb(v),andthen to verify that δs 0v is indeed a type vbuyer’s worst-case belief in the resulting double 986 Alexander Wolitzky Theoretical Economics 11 (2016) auction. In contrast, a standard approach might be to use an “off-the-shelf” mechanism, like an AGV mechanism (Arrow 1979,d’Aspremont and Gérard-Varet 1979). However, as argued above, standard arguments for why using such mechanisms is without loss of generality do not apply with maxmin agents; moreover it is not even clear how to define AGV mechanisms in such environments. A related point is that efficient trade may be implementable even though every individually rational VCG mechanism runs an expected deficit for some measure φ∈∗, in contrast to the results of Makowski and Mezzetti (1994), Williams (1999), and Krishna and Perry (2000) for Bayesian mechanism design with smoothly path-connected type spaces. For example, this is the case whenever c∗<v ∗and condition (∗)andtheassumptions of Theorem 2 hold. To see this, recall that a VCG mechanism is a mechanism where, for all cv ∈[01], tb(v c) =−cy(cv) +hb(c) for some expected transfer function hbthat depends only on c(and symmetrically for the seller). Note that efficiency and individual rationality of type v=0imply that hb(c∗)≥0(and symmetrically hs(v∗)≥0), as otherwise one would have Ub(0)≤Ub(0δc∗;0)=0+hb(c∗)<0 Hence, the expected deficit of such a mechanism under the measure δc∗×δv∗∈∗ equals tb(v∗c∗)+ts(c∗v∗)=(v∗−c∗)(1)+hb(c∗)+hs(v∗)>0 5. Further results on bilateral trade This sections presents additional results on bilateral trading with maxmin agents. Section 5.1 characterizes when efficient trade is possible with reference rules,aparticularly simple class of mechanisms. Section 5.2 describes how the assumption that agents know each other’s expected valuation may be interpreted in terms of information acquisition. Section 5.3 discusses the role of Dirac measures in these results, and proposes slight modifications to the definition of the αi(θi)double auction and reference rule that ensure that these mechanisms are robust to eliminating weakly dominated strategies. 5.1 Efficient trade with reference rules A common justification for introducing concerns about robustness into mechanism design is that these considerations may argue for the use of simpler or otherwise more intuitively appealing mechanisms. The αi(θi)double auction introduced in the previous section is simple in some ways, but it does involve a carefully chosen transfer rule. In this section, I point out that efficient trade can also be implemented in an extremely simple class of mechanisms—which I call reference rules—in the case where the average types of the two agents do not have gains from trade with each other (i.e., when c∗≥v∗). Theoretical Economics 11 (2016) Mechanism design with maxmin agents 987 Reference rules also have the advantage of satisfying strong rather than weak budget balance.22 I define a reference rule as follows. Definition 1. In the bilateral trade setting, a mechanism (yt) is a reference rule if y(cv)=1if c≤v 0if c>v and there exists a price p∗∈[01]such that ts(c v) =−tb(v c) =⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ p∗if c≤p∗≤v cif p∗<c≤v vif c≤v<p ∗ 0if c>v With a reference rule, the agents trade at a reference price p∗if they are both willing to do so; otherwise they trade at the reservation price of the agent who is unwilling to trade at the reference price.23 Reference rules clearly satisfy EF, (ex post) IR, and SBB, so an MMIC reference rule implements efficient trade. The following result characterizes when MMIC reference rules exist; that is, when efficient trade is implementable with reference rules. Proposition 1. Assume that δθ∗ i∈ifor i=12. Then efficient trade is implementable with reference rules if and only if c∗≥v∗. The intuition for why reference rules are incentive compatible when c∗≥v∗and p∗∈ [v∗c∗]is captured in Figure 2. Observe that every buyer with value v≤c∗may be certain that no gains from trade exist, as he may believe that the distribution of seller values is the Dirac distribution on c∗. Hence, certainty of no-trade is a worst-case belief for these buyers, and they are therefore willing to reveal their information. In contrast, buyers with value v>c ∗do believe that gains from trade exist with positive probability. But it is optimal for these buyers to reveal their values truthfully as well: misreporting some ˆ v>c ∗does not affect the price regardless of the seller’s cost (as the price equals cif c>p ∗and equals p∗if c≤p∗), and misreporting some ˆ v≤c∗again gives payoff 0in 22Another advantage of reference rules is that when c∗≥v∗, they are maxmin incentive compatible in a stronger sense than that of Section 2. First, they remain incentive compatible if agents can hedge ambiguity by randomizing. In addition, they also remain incentive compatible if the order of the maximizing and minimizing operators in (1) is reversed, so that agents are pessimistic Bayesians rather than worst-case optimizers. 23The term “reference rule” is taken from Erdil and Klemperer (2010), who recommend the use of such mechanisms in multi-unit auctions. They highlight that reference rules perform well in terms of agents’ “local incentives to deviate,” a different criterion from what I consider here. Reference rules also bear some resemblance to the “downward flexible price mechanism” of Börgers and Smith (2012). Their mechanism starts with a fixed price p∗which the seller may then lower to any p<p ∗, whereupon the parties decide whether to trade at price p. 988 Alexander Wolitzky Theoretical Economics 11 (2016) Figure 2. Reference rules with p∗∈[v∗c∗]are incentive compatible. Figure 3. When c∗<v ∗, no reference rule is incentive compatible. the worst case (as certainty that the seller’s value equals c∗would again be a worst-case belief). Therefore, truthtelling is optimal for every buyer type. The argument for sellers is symmetric. Conversely, Figure 3 indicates why reference rules are not incentive compatible when c∗<v ∗. Suppose the reference price p∗is greater than c∗. Consider a buyer with value v∈(c∗p∗). If he reports his value truthfully, then whenever he trades under the reference rule he does so at price v,whichgiveshimpayoff0. Suppose he instead shades hisreportdowntosomeˆ v∈(c∗v). Then whenever he trades the price is ˆ v—which gives him a positive payoff—and, in addition, he expects to trade with positive probability (since ˆ v>c ∗). Hence, he will shade down. The same argument shows that in any reference rule a seller with c∈(p∗v∗)shades up. Figure 3 shows that a consequence of this argument is that a reference rule cannot be MMIC for both agents at once when c∗<v ∗, regardless of where the reference price p∗is set. Theoretical Economics 11 (2016) Mechanism design with maxmin agents 989 5.2 Information acquisition interpretation The assumption that agents know the mean and bounds on the support of the distribution of each other’s value emerges naturally when agents share a unique common prior at an ex ante stage but are uncertain about the information acquisition technology that the other can access prior to entering the mechanism. This section provides the details of this argument. Consider the following extension of the model. Each agent i’s ex post utility is ˜ θiy+ti, where ˜ θi∈Ris her realized ex post value. (In the bilateral trade application, the buyer’s ex post value is ˜ v=˜ θband the seller’s ex post cost is ˜ c=−˜ θs.)Thereisanexantestageat which the agents’ beliefs about the ex post values (˜ θ1˜ θ2)are given by a (unique) common product measure ˜ φon [¯ θ1¯ θ1]×[ ¯ θ2¯ θ2]with mean (θ∗ 1θ∗ 2)(the common prior). For each agent i, there is a set of possible signaling functions (“experiments”) Si,where a signaling function i∈Siis a map from ito an arbitrary message set Mi, and is thus informative of agent i’s own ex post value only. Each agent iknows her own signaling function i, but is completely uncertain about her opponent’s, knowing only that it lies in the set Sj.Agenti’s interim value, θi—which corresponds to her type in the main model—is her posterior expectation of ˜ θiafter observing the outcome of her experiment. That is, after observing outcome mi,agenti’s valuation for the good is given by θi≡E˜ φi[˜ θi|i(˜ θi)=mi](7) Note that the issue of updating “ambiguous beliefs” does not arise in this model. In particular, the updating in (7) is completely standard. However, the following observation shows that the main model can be interpreted as resulting from each agent’s being maxmin about the identity of her opponent’s signaling function j∈Sjat the interim stage (i.e., after she observes her own signal). Remark 1. If a measure φiis the distribution of θi=E˜ φi[˜ θi|i(˜ θi)=mi]under ˜ φifor some experiment i, then Eφi[θi]=θ∗ iand suppφi⊆i(where suppφidenotes the support of φi). The fact that Eφi[θi]=θ∗ iis the law of iterated expectation. The fact that supp φi⊆i follows because ˜ θi∈[ ¯ θi¯ θi]with probability 1under ˜ φi. Thus, assuming that agent j finds possible a particular set of measures φisatisfying Eφi[θi]=θ∗ iand suppφi⊆i amounts to assuming that Siis a particular subset of the set of all functions i→Mi.24 With this interpretation, the assumption that δθ∗ i∈imeans that agent jfinds it possible that agent iacquires no information about her value before entering the mechanism (beyond the common prior), while the assumption that δi θl iθh i ∈imeans that agent j finds it possible that agent iobserves a binary signal of her value, where the bad realization lowers her expectation of ˜ θito θl iand the good realization raises her expectation of ˜ θito θh i. 24More precisely, the set of possible interim measures φiis jointly determined by Siand the prior ˜ φ. For example, every measure φisuch that Eφi[θi]=θ∗ iand suppφi⊆iis the distribution of θifor some experiment if and only if the prior puts probability 1on agent i’s ex post value being either ¯ θior ¯ θi(see, for example, Theorem 1 of Shmaya and Yariv 2009 or Proposition 1 of Kamenica and Gentzkow 2011). 990 Alexander Wolitzky Theoretical Economics 11 (2016) 5.3 TheroleofDiracmeasures In both the αi(θi)double auction and the reference rule, an agent’s worst-case belief is a Dirac (or “two-point”) measure. Thus, in these mechanisms, a maxmin agent effectively ignores the outcome that results when her opponent’s type takes on all but one or two values. This section argues that this feature is not essential for the results. A first observation is that excluding Dirac measures per se has no effect on the results if the agents’ sets of possible beliefs are sufficiently rich. In particular, if the Dirac measures referenced in the statements of Theorem 2 and Proposition 1 are not contained in iitself but are contained in its closure, then these results go through as written. For instance, this would be the case if iconsists of all measures on iwith mean θ∗ ithat are absolutely continuous with respect to Lebesgue measure. The proof is simply that, with the max inf formulation of (1), excluding accumulation points of idoes not affect agents’ utility from any report under any mechanism where Uj(ˆ θjθi;θj)is everywhere left or right continuous in θi, and both the αi(θi)double auction and the reference rule satisfy this property. Nonetheless, one might object that if Dirac measures are viewed as a limiting case in this way, an agent should still not completely discount the possibility that her opponent’s type could take on other values. A natural way to formalize this concern is to strengthen the definition of (1) to require that truthtelling is not only maxmin optimal, but also not weakly dominated. I now show that Theorem 2 and Proposition 1 are both robust to this modification, although the mechanisms involved need to be changed slightly. In the construction in the proof of Theorem 2,αb(v) =0if v<c ∗,soabuyerwith value v<c ∗gets payoff 0against every seller type from truthtelling, but gets a positive payoff against some types (and payoff 0against the others) from shading her report down (and similarly for sellers with c>v ∗). However, the specification of αb(v) for types v<c ∗can be altered without affecting the desirable properties of the αi(θi)double auction, as the following result shows. The intuition is that the αi(θi)double auction runs a strict ex post surplus whenever v<c ∗(recall that the surplus is smallest when v=1and c=0), so some of this surplus can be returned to the buyer without violating budget balance. Proposition 2. Theorem 2 continues to hold when the definition of MMIC is strengthened to require that truthtelling is not weakly dominated for any type. A similar modification of the reference rule ensures the truthtelling is not weakly dominated: when v<c ∗,changetb(v c) from −vto −((1−ε)v +εc). However, since reference rules are strongly budget balanced, this modification violates budget balance unless ts(c v) is also changed from vto (1−ε)v +εc. This change can in turn lead to a violation of MMIC for the seller. Nonetheless, it turns out that MMIC is preserved if εis not too large and satisfies the assumptions of Theorem 2. Theoretical Economics 11 (2016) Mechanism design with maxmin agents 991 Proposition 3. Assume that c∗>v ∗and that δ0c ∈sfor all c∈[c∗1]and δv1∈b for all v∈[0v∗].Then,foreveryp∗∈(v∗c∗),theε-modified reference rule given by ts(c v) =−tb(v c) =⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ p∗if c≤p∗≤v (1−ε)c +εv if p∗<c≤v (1−ε)v +εc if c≤v<p ∗ 0if c>v satisfies EF, IR, and SBB, and satisfies MMIC for all ε∈(0p∗). In addition, under such a mechanism truthtelling is not weakly dominated for any type. 6. Conclusion This paper contributes to the study of mechanism design where agents follow robust decision rules, in particular where agents are maxmin expected utility maximizers. I establish two main results. First, I give a general necessary condition for a social choice rule to be implementable, which generalizes the well known condition from Bayesian mechanism design that expected social surplus must exceed expected information rents. This condition involves both a modification of the usual envelope characterization of payoffs and a connection between agents’ maxmin expected utilities and the objective expected social surplus under a common prior. Second, I apply this result to give a complete characterization of when efficient bilateral trade is possible, when agents know little beyond each other’s expected valuation of the good (which is the information structure that results when agents are maxmin about how one’s opponent may acquire information before participating in the mechanism). Somewhat surprisingly, the Myerson– Satterthwaite impossible result sometimes continues to hold with maxmin agents, despite the lack of a unique common prior or independent types. When instead efficient trade is possible, it is implementable with a relatively simple double auction format, the αi(θi)double auction. Sometimes, it is also implementable with extremely simple reference rules. A clear direction for future work is investigating positive implementation results beyond the bilateral trade context of two agents and two social alternatives. I have argued that standard mechanisms may fail to have desirable properties with maxmin agents, and in general it is not immediately clear how to generalize the mechanisms I construct in this paper (the αi(θi)double auction and the reference rule) beyond the bilateral trade case. However, one important setting where a relatively straightforward generalization does exist is the multilateral public good provision problem, where nagents must decide whether to provide a public good at cost C(Mailath and Postlewaite 1990). In this case, the (correlated) belief of a type θiagent that minimizes the probability that the good is provided is a two-point distribution, under which either all of her opponents’ valuations take on their highest possible values or these valuations sum to C−θi(so strict gains from trade barely fail to exist). This characterization of worst-case beliefs can then be exploited to develop a maxmin incentive compatible trading mechanism, generalizing the αi(θi)double auction. However, note that these worst-case beliefs involve correlation, while my necessary condition for implementation involves independent beliefs. 992 Alexander Wolitzky Theoretical Economics 11 (2016) This suggests that developing an exact characterization of when efficient public good provision is possible with more than two agents would require a significant extension of the analysis of the bilateral case. More broadly, it also seems important to consider models of robust agent behavior beyond the maxmin expected utility model. Mechanism design with ambiguityaverse but non-MMEU agents is left for future research, as is mechanism design under other models of robust agent behavior such as minmax regret (Linhart and Radner 1989,Bergemann and Schlag 2008,2011). The integration of models of robust agent behavior in mechanisms and models of robustness concerns on the part of the mechanism designer (Bergemann and Morris 2005,Chung and Ely 2007)mustalsoawaitfuture research. Appendix:Omitted proofs Proof of Theorem 2 For the proof of Theorem 2, it is convenient to return to the notation of Section 2,which treats the buyer and seller symmetrically. We also allow for arbitrary type spaces 1and 2, assuming only that the most favorable type of each agent has gains from trade with the average type of the other agent, while the least favorable type of each agent does not: that is, ¯ θi+θ∗ j>0≥¯ θi+θ∗ jfor i=12.25 This assumption is clearly satisfied in the case in the text, where ¯ θb+¯ θs=¯ θb+¯ θs=0. Noting that condition (∗∗)belowgeneralizes condition (∗), the following result generalizes Theorem 2. Theorem 3. Assume that ¯ θi+θ∗ j>0≥¯ θi+θ∗ jand that δθi¯ θi∈ifor all θi∈[ ¯ θiθ∗ i],for i=12. Then efficient trade is implementable if and only if ¯ θ1+min{¯ θ2−¯ θ1} ¯ θ1+¯ θ2 ¯ θ1−θ∗ 1 θ∗ 1+min{¯ θ2−¯ θ1}log1+θ∗ 1+min{¯ θ2−¯ θ1} ¯ θ1−θ∗ 1(∗∗) +¯ θ2+min{¯ θ1−¯ θ2} ¯ θ1+¯ θ2 ¯ θ2−θ∗ 2 θ∗ 2+min{¯ θ1−¯ θ2}log1+θ∗ 2+min{¯ θ1−¯ θ2} ¯ θ2−θ∗ 2≥1 Proof.Necessity. By Theorem 1, efficient trade is implementable only if, for all φ∈ 1×2,  iθ∈ θiyi(θ)dφ− iθi∈i (1−Fi(θi))˜ yi(θi)dθi≥0(8) for some allocation rule yisatisfying yi(θ) =1if θi+θj>0 0if θi+θj<0 25An earlier version of the paper shows that if ¯ θi+θ∗ j≤0and δθ∗ j∈jfor some i∈{12}, then efficient trade is always implementable (with strong budget balance). Theoretical Economics 11 (2016) Mechanism design with maxmin agents 993 Note that, for any such allocation rule yi, ˜ yi(θi)=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0if θi≤−θ∗ j θ∗ j+θi ¯ θj+θiif θi∈(−θ∗ j−¯ θj) 1if θi>−¯ θj This is immediate for the θi≤−θ∗ jand θi>−¯ θjcases, and follows by Chebyshev’s inequality in the θi∈(−θ∗ j−¯ θj)case.26,27 Let φi=δmax{¯ θi−¯ θj}¯ θi(which is assumed to be an element of i,as−¯ θj<θ ∗ i)for i=12,andletφ=φ1×φ2.Letβi=(θ∗ i+min{¯ θj−¯ θi})/( ¯ θi+min{¯ θj−¯ θi}),whichisthe probability that θi=¯ θiunder δmax{¯ θi−¯ θj}¯ θi.Observethat  iθ∈ θiyi(θ)dφ=(¯ θi+¯ θj)βiβj+max{¯ θi+¯ θj0}βi(1−βj) +max{¯ θj+¯ θi0}βj(1−βi) and, using the assumption that ¯ θi+θ∗ j≤0, θi∈i (1−Fi(θ))˜ yi(θi)dθi=min{¯ θi−¯ θj} max{¯ θi−θ∗ j} βiθ∗ j+θi ¯ θj+θidθi+¯ θi min{¯ θi−¯ θj} βidθi =(¯ θi+θ∗ j)βi−(¯ θj−θ∗ j)βilog1+θ∗ j+min{¯ θi−¯ θj} ¯ θj−θ∗ j Combining these observations and collecting terms, the left-hand side of (8) equals ζ−1+¯ θ1+min{¯ θ2−¯ θ1} ¯ θ1+¯ θ2 ¯ θ1−θ∗ 1 θ∗ 1+min{¯ θ2−¯ θ1}log1+θ∗ 1+min{¯ θ2−¯ θ1} ¯ θ1−θ∗ 1(9) +¯ θ2+min{¯ θ1−¯ θ2} ¯ θ1+¯ θ2 ¯ θ2−θ∗ 2 θ∗ 2+min{¯ θ1−¯ θ2}log1+θ∗ 2+min{¯ θ1−¯ θ2} ¯ θ2−θ∗ 2 where ζ=β1β2(¯ θ1+¯ θ2)>0. The bracketed term in (9) nonnegative if and only if condition (∗∗) holds. Hence, condition (∗∗) is necessary. Sufficiency. The αi(θi)double auction is defined by y(θiθj)=1if θi+θj>0 0if θi+θj≤0 ti(θiθj)=αi(θi)θj−(1−αi(θi))min{θi−¯ θj}if θi+θj>0 0if θi+θj≤0 26The form of Chebyshev’s inequality I use throughout the paper is, for random variable Xwith mean x∗ and upper bound ¯ x,Pr(X ≥x) ≥(x∗−x)/( ¯ x−x). This follows because x∗≤Pr(X ≥x) ¯ x+Pr(X < x)x.See, for example, p. 319 of Grimmett and Stirzaker (2001). 27As will become clear, the value of ˜ yi(−¯ θj)does not matter for the proof. 994 Alexander Wolitzky Theoretical Economics 11 (2016) for i=12,where αi(θi)=⎧ ⎨ ⎩ 1− ¯ θj−θ∗ j θ∗ j+min{θi−¯ θj}log(1+θ∗ j+min{θi−¯ θj} ¯ θj−θ∗ j )if θi>−θ∗ j 0if θi≤−θ∗ j This mechanism is clearly efficient. I show that it satisfies IR and MMIC, and that it satisfies WBB if and only if condition (∗∗) holds. Claim 1. The αi(θi)double auction satisfies (ex post) IR. Proof.Ifθi+θj≤0, then Ui(θiθj;θi)=0.Ifθi+θj>0, then Ui(θiθj;θi)=θi+αi(θi)θj−(1−αi(θi))min{θi−¯ θj} ≥αi(θi)(θi+θj) Now αi(θi)is of the form 1−(1/x)log(1+x) for x>0and (1/x)log(1+x) ∈(01)for x>0,soαi(θi)∈(01)for all θi. This yields (ex post) IR.  Claim 2. The αi(θi)double auction satisfies WBB if and only if condition (∗∗)holds. Proof. WBB is trivially satisfied when θ1+θ2≤0, so suppose that θ1+θ2>0. If θ1<−¯ θ2and θ2<−¯ θ1, t1(θ1θ2)+t2(θ1θ2)=(θ1+θ2)(α1(θ1)+α2(θ2)−1) Since αi(θi)is nondecreasing in θi(as (1/x)log(1+x) is decreasing in x), this expression is nonpositive for all θ1,θ2with θ1+θ2>0if and only if α1(¯ θ1)+α2(¯ θ2)≤1. Condition (∗∗)impliesα1(¯ θ1)+α2(¯ θ2)≤1and is equivalent to this inequality when ¯ θi≤− ¯ θjfor i=12. If θ1≥− ¯ θ2and θ2≥− ¯ θ1, then t1(θ1θ2)+t2(θ1θ2)=α1(θ1)θ2+α2(θ2)θ1+(1−α1(θ1))¯ θ2+(1−α2(θ2))¯ θ1 =θ1+θ2−(1−α1(θ1))(θ2−¯ θ2)−(1−α2(θ2))(θ1−¯ θ1) This expression is nondecreasing in θ1and θ2(as αi(θi)∈(01)is nondecreasing and θi≥¯ θi), so it is nonpositive for all θ1,θ2with θ1+θ2>0if and only if ¯ θ1+¯ θ2−(1−α1(¯ θ1))( ¯ θ2−¯ θ2)−(1−α2(¯ θ2))( ¯ θ1−¯ θ1)≤0 Moving the product terms to the right-hand side and dividing by ¯ θ1+¯ θ2(which is positive) shows that this inequality is equivalent to condition (∗∗)when ¯ θi≥− ¯ θjfor i=12 (which is the case under consideration). Finally, if θ1<−¯ θ2and θ2≥− ¯ θ1(which is the hardest case), t1(θ1θ2)+t2(θ1θ2)=(α1(θ1)+α2(θ2)−1)θ1+α1(θ1)θ2+(1−α2(θ2))¯ θ1 =(θ1+θ2)α1(θ1)−θ1−¯ θ1 θ1+θ2 (1−α2(θ2)) Theoretical Economics 11 (2016) Mechanism design with maxmin agents 1001 or (v 1]can be improved upon, so it follows that the infimum of Ub(ˆ vφs;v) over measures φswith expectation c∗is attained at the measure that puts mass only on {0v}, namely δ0v. The above claim gives Ub(v) =((v −c∗)/v)(v −p∗). Since a standard reference rule corresponds to ε=0, the same argument gives ˜ Ub(v) =((v −c∗)/v)(v −p∗).Hence, Ub(v) =˜ Ub(v), completing the proof of MMIC. Finally, to see that truthtelling is not weakly dominated for any type when ε>0, note that reporting ˆ v<vcannot dominate truthtelling because Ub(v(v +ˆ v)/2;v) > 0= Ub(ˆ v(v +ˆ v)/2;v). Moreover, reporting ˆ v>vcannot dominate truthtelling because in this case Ub(ˆ vc;v) ≤Ub(vc;v) for all c, as noted above. References Agranov, Marina and Pietro Ortoleva (forthcoming), “Stochastic choice and preferences for randomization.” Journal of Political Economy.[976] Ahn, David S. (2007), “Hierarchies of ambiguous beliefs.” Journal of Economic Theory, 136, 286–301. [976] Arrow, Kenneth (1979), “The property rights doctrine and demand revelation under incomplete information.” In Economics and Human Welfare (Michael J. Boskin, ed.), 23– 38, New York, Academic Press. [981,986] Bergemann, Dirk and Stephen Morris (2005), “Robust mechanism design.” Econometrica, 73, 1771–1813. [992] Bergemann, Dirk and Karl Schlag (2011), “Robust monopoly pricing.” Journal of Economic Theory, 146, 2527–2543. [992] Bergemann, Dirk and Karl H. Schlag (2008), “Pricing without priors.” Journal of the European Economic Association, 6, 560–569. [992] Bewley, Truman F. (2002), “Knightian decision theory: Part I.” Unpublished paper. [975] Bodoh-Creed, Aaron (2014), “Correction to ambiguous beliefs and mechanism design.” Working paper. [979] Bodoh-Creed, Aaron L. (2012), “Ambiguous beliefs and mechanism design.” Games and Economic Behavior, 75, 518–537. [975,976,977,979,980,981] Börgers, Tilman and Doug Smith (2012), “Robustly ranking mechanisms.” American Economic Review, 102, 325–329. [987] Bose, Subir and Arup Daripa (2009), “A dynamic mechanism and surplus extraction under ambiguity.” Journal of Economic Theory, 144, 2084–2114. [974] Bose, Subir and Suresh Mutuswami (2012), “Bilateral bargaining in an ambiguous environment.” University of Leicester Department of Economics Working Paper 12/10. [974] Bose, Subir, Emre Ozdenoren, and Andreas Pape (2006), “Optimal auctions with ambiguity.” Theoretical Economics, 1, 411–438. [975,976,977,979] 1002 Alexander Wolitzky Theoretical Economics 11 (2016) Bose, Subir and Ludovic Renou (2014), “Mechanism design with ambiguous communication devices.” Econometrica, 82, 1853–1872. [974] Carbajal, Juan Carlos and Jeffrey C. Ely (2013), “Mechanism design without revenue equivalence.” Journal of Economic Theory, 148, 104–133. [979] Cerreia-Vioglio, Simone, David Dillenberger, Pietro Ortoleva, and Gil Riella (2015), “Deliberately stochastic.” Unpublished paper. [976] Chatterjee, Kalyan and William Samuelson (1983), “Bargaining under incomplete information.” Operations Research, 31, 835–851. [975] Chung, Kim-Sau and Jeff Ely (2007), “Foundations of dominant strategy mechanisms.” Review of Economic Studies, 74, 447–476. [992] Crémer, Jacques and Richard P. McLean (1985), “Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent.” Econometrica, 53, 345–361. [972] Crémer, Jacques and Richard P. McLean (1988), “Full extraction of the surplus in Bayesian and dominant strategy auctions.” Econometrica, 56, 1247–1257. [972] d’Aspremont, Claude and Louis-André Gérard-Varet (1979), “Incentives and incomplete information.” Journal of Public Economics, 11, 25–45. [981,986] De Castro, Luciano and Nicholas Yannelis (2010), “Ambiguity aversion solves the conflict between efficiency and incentive compatibility.” Discussion Paper 1532, Center for Mathematical Studies in Economics and Management Science. [974,976,982,983] Di Tillio, Alfredo, Nenad Kos, and Matthias Messner (2014), “The design of ambiguous mechanisms.” Working paper, Bocconi University. [974,976] Erdil, Aytek and Paul Klemperer (2010), “A new payment rule for core-selecting package auctions.” Journal of the European Economic Association, 8, 537–547. [987] Fudenberg, Drew, Ryota Iijima, and Tomasz Strzalecki (2015), “Stochastic choice and revealed perturbed utility.” [976] Garratt, Rod and Mark Pycia (2015), “Efficient bilateral trade.” Working paper, available at SSRN 2444279. [975] Gilboa, Itzhak (2009), Theory of Decision Under Uncertainty. Econometric Society Monographs. Cambridge University Press, New York. [972] Gilboa, Itzhak and David Schmeidler (1989), “Maxmin expected utility with a nonunique prior.” Journal of Mathematical Economics, 18, 141–153. [971,976] Grimmett, Geoffrey and David Stirzaker (2001), Probability and Random Processes,third edition. Oxford University Press, New York. [993] Kamenica, Emir and Matthew Gentzkow (2011), “Bayesian persuasion.” American Economic Review, 101, 2590–2615. [989] Theoretical Economics 11 (2016) Mechanism design with maxmin agents 1003 Kos, Nenand and Matthias Messner (2013), “Extremal incentive compatible transfers.” Journal of Economic Theory, 148, 134–164. [979] Krishna, Vijay and Motty Perry (2000), “Efficient mechanism design.” Working paper, available at SSRN 64934. [981,986] Linhart, P. B. and Roy Radner (1989), “Minimax-regret strategies for bargaining over several variables.” Journal of Economic Theory, 48, 152–178. [992] Lopomo, Giuseppe, Luca Rigotti, and Chris Shannon (2014), “Uncertainty in mechanism design.” Unpublished paper, University of Pittsburgh. [975] Machina, Mark J. (1985), “Stochastic choice functions generated from deterministic preferences over lotteries.” Economic Journal, 95, 575–594. [976] Mailath, George and Andrew Postlewaite (1990), “Asymmetric information bargaining problems with many agents.” Review of Economic Studies, 57, 351–367. [991] Makowski, Louis and Claudio Mezzetti (1994), “Bayesian and weakly robust first best mechanisms: Characterizations.” Journal of Economic Theory, 64, 500–519. [981,986] McAfee, R. Preston and Philip J. Reny (1992), “Correlated information and mechanism design.” Econometrica, 60, 395–421. [972] Milgrom, Paul R. and Ilya Segal (2002), “Envelope theorems for arbitrary choice sets.” Econometrica, 70, 583–601. [975,979,980] Myerson, Roger B. (1981), “Optimal auction design.” Mathematics of Operations Research, 6, 58–73. [977] Myerson, Roger B. and Mark A. Satterthwaite (1983), “Efficient mechanisms for bilateral trading.” Journal of Economic Theory, 29, 265–281. [971,972] Raiffa, Howard (1961), “Risk, ambiguity, and the Savage axioms: Comment.” Quarterly Journal of Economics, 75, 690–694. [976] Saito, Kota (2015), “Preferences for flexibility and randomization under uncertainty.” American Economic Review, 105, 1246–1271. [976] Schmeidler, David (1989), “Subjective probability and expected utility without additivity.” Econometrica, 57, 571–587. [976] Segal, Ilya and Michael D. Whinston (2002), “The mirrlees approach to mechanism design with renegotiation (with applications to hold-up and risk-sharing).” Econometrica, 70, 1–45. [979] Shmaya, Eran and Leeat Yariv (2009), “Foundations for Bayesian updating.” Unpublished paper, CalTech. [989] Williams, Steven R. (1999), “A characterization of efficient, Bayesian incentive compatible mechanisms.” Economic Theory, 14, 155–180. [981,986] 1004 Alexander Wolitzky Theoretical Economics 11 (2016) Wilson, Robert (1989), “Game theoretic analysis of trading processes.” In Advances in Economic Theory (Truman Bewley, ed.), 33–70, Cambridge University Press, New York. [971] Wolitzky, Alexander (2016), “Mechanism design with maxmin agents: Theory and an application to bilateral trade.” Unpublished paper. [976] Co-editor Faruk Gul handled this manuscript. Submitted 2015-1-29. Final version accepted 2015-10-15. Available online 2015-10-15.