Smooth multibidding mechanisms

Smooth multibidding mechanisms∗ David Pérez-Castrillo†and Nicolas Quérou‡ November 5, 2010 Abstract We propose a smooth multibidding mechanism for environments where a group of agents have to choose one out of several projects (possibly with the help of a social planner). Our proposal is related to the multibidding mechanism (Pérez-Castrillo and Wettstein, 2002) but it is “smoother” in the sense that small variations in an agent’s bids do not lead to dramatic changes in the probability of selecting a project. This mechanism is shown to possess several interesting properties. Unlike in the study by Pérez Castrillo and Wettstein (2002), the equilibrium outcome is unique. Second, it ensures an equal sharing of the surplus that it induces. Finally, it enables reaching an outcome as close to efficiency as is desired. JEL Classification numbers: D78, D72 Keywords: mechanism design, NIMBY ∗We thank Inés Macho-Stadler, Pedro Rey-Biel and David Wettstein for helpful remarks. Part of this research was conducted while the second author visited the Institute of Economic Analysis (IAE) and the INRA-LAMETA. The hospitality of these institutions is greatly appreciated. David Pérez-Castrillo acknowledges the financial support from ECO2009-7616, Consolider-Ingenio CSD2006-16, 2009SGR-169, Barcelona Economics-Xarxa CREA and ICREA Academia. David Pérez-Castrillo is MOVE fellow. †Dept. of Economics & CODE, Universitat Autònoma de Barcelona, 08193 Bellaterra (Barcelona), Spain. Email: david.p[email protected]. Tel: +34 935811405. Fax: +34 935813767. ‡Queen’s University Management School, Queen’s University Belfast, University Sq. 25, BT7 1NN Belfast, UK. E-mail: n.[email protected]. Tel: +44 2890975024. Fax: +44 2890975156 1 1 Introduction 1.1 Contribution The design of mechanisms that help agents reach decisions on contentious issues is a very relevant and active line of research. A mechanism that leads to an efficient project requires information about agents’ preferences for each possible decision. The multibidding mechanism, proposed by Pérez-Castrillo and Wettstein (2002) allows the agents to express their relative preference for projects. It proceeds as follows. Each agent submits a vector of bids, one for each project, with the sole restriction that the sum of each agent’s bids is zero. Therefore, bids measure relative rather than absolute valuation. Each agent also nominates one of the projects specifically. The project with the highest aggregate bid(sumofbidsmadeforthisproject)ischosen. Incasethereismorethanonesuch project, there is a rule that gives priority to projects that have been nominated by some agent. The winning project is carried out, agents pay the promised bid corresponding to this project, and any surplus is shared among the agents, so that the mechanism is budget-balanced. The main property of the multibidding mechanism is that all its Nash (and strong Nash) equilibrium outcomes are efficient. However, in general environments, the mechanism has two weak aspects that we address in the current paper. First, it requires the tiebreaking rule that, at equilibrium, is always used because all projects’ equilibrium aggregate bids are zero. Therefore, the tiebreaking rule plays a crucial role. As Ehlers (2009) highlights, removing the agents’ abilities to nominate one specific project and using tiebreaking rules may prevent an equilibrium from existing. Because agents do not nominate a specific project in many real-world processes such as auctions, this lack of robustness constitutes a weakness of the initial mechanism. Second, the set of equilibrium outcomes is quite large, as it consists of all the outcomes where each agent’s payoffis at least the expected payoffhe would obtain in a situation where all the projects have the same probability of being developed. Therefore, almost any (“reasonable”) sharing of the surplus is an equilibrium outcome. In the present paper, we tackle the issues highlighted above by proposing a smooth multibidding mechanism. It is close to the original proposal but ours is “smoother” in 2 the sense that small variations of an agent’s bids do not lead to dramatic changes in the probability of selecting a project. In the smooth mechanism, each agent only submits a vector of bids, without nominating any project. All projects can be selected, with each project’s probability being a function of its aggregate bid as well as the aggregate bids of the rest of the projects. Projects with a negative aggregate bid have a very low, but positive, fixed probability of being selected (a function of some parameter ). Each project with a positive aggregate bid is selected with a probability that is a function of the level of its (and others’) positive aggregate bid. We first show that, for a given value of , the equilibrium outcome is unique.This property is important because it highlights that there is no coordination issue with respect to agents’ expectation about the final outcome. We then characterize the equilibrium outcome. Although there may be several equilibrium strategies, the differences among them only concern bids for those projects that, at equilibrium, end up with negative aggregate bids. We identify the set of projects with positive equilibrium bids as well as each agent’s bids to any project in this set. Only projects that are efficient, or whose total valuation is very close to the efficient one, ultimately receive a positive aggregate bid. In case some non-efficient project receives a positive aggregate bid, its level reflects thedegreeofinefficiency. Second, the smooth multibidding mechanism ensures a fair share of the surplus that it induces. Indeed, an agent’s equilibrium payoffin the mechanism is the sum of the value of the average project plus his fair share of the remaining surplus. That is, agents obtain the same level of utility as in the original multibidding mechanism, and the surplus is divided in equal parts among the agents. This fairness property ensures that the mechanism is politically feasible, which is an important characteristic for practical implementation. Third, the mechanism does not rely on the use of tiebreaking rules and is immune to the criticism raised by Ehlers (2009). It can be thus thought of as a more natural mechanism than the initial one. Finally, it is apparent from the previous description that the smooth multibidding mechanism does not achieve efficiency. It does, however, get as close to efficiency as one wishes. We show that each agent’s expected payoffincreases as the value of the parameter decreases; therefore, total efficiency increases as well. Moreover, the probability of 3 choosing an inefficient project converges to zero as the value of the parameter becomes small. We can bound the level of expected inefficiency as a function of the parameter : the maximum level of inefficiency of a project that receives a positive aggregate bid is a linear function of the square root of . To summarize, the present mechanism exhibits the interesting properties of uniqueness and fairness of its equilibrium outcome. The weakness compared to the initial mechanism (which guarantees full efficiency) is only minor as a social planner relying on the new protocol would be able to get as close to full efficiency as she wishes. Therefore, this mechanism constitutes an interesting option for practical implementations. 1.2 Applicability of the mechanism and related literature There are many economic situations where this mechanism can be successfully used. A first case concerns the complex problem of the location of noxious facilities, such as prisons, dump sites, nuclear waste repositories, or airports. Many authors address this type of problem; we can refer among other papers to Kunreuther and Kleindorfer, 1986; Rob, 1989; O’Sullivan, 1993; Ingberman, 1995; Pérez-Castrillo and Wettstein, 2002; Minehart and Neeman, 2002; and Laurent-Lucchetti and Leroux, 2009. Whereas the construction of such facilities may provide large global benefits, their cost is usually borne by the hosting agent. The sitting problems are so severe and so common that an acronym is used to refertothem:NIMBY(NotInMyBackYard). Another sensitive decision problem concerns the location of large international research infrastructures. The decision about the city that should host such a facility is always the subject of hot debate among the candidates and other interested countries and institutions. In 2002, the European Commission started the European Strategy Forum on Research Infrastructures (ESFRI) to support and facilitate multilateral initiatives leading to a better use and development of research infrastructures, including biological archives, communication networks, research vessels, satellite and aircraft observation facilities, telescopes, synchrotrons, and particle accelerators. Although its 2006 Report presented a first roadmap identifying 35 projects with the scientificneedsforthenext10-20years,ESFRI is silent about how the interested countries should determine the location of the facility. 4 However, this is a very difficult decision that involves many scientific, economic, and social issues. For each project, supporting countries should work out a procedure to choose the host of the facility. Therefore, they must first decide on a mechanism and then use the procedure to elect the hosting city. The previous examples belong to a general class of problems in which a group of agents has to choose one out of several projects. In some situations, the set of projects coincides with the set of agents, as is the case if a group of municipalities meet to choose one of them to host a dump site or a hospital. In another context, the set of agents is larger than the set of projects, as is typically the case when countries or institutions build a large international research infrastructure: in such a situation, all countries may not have an own proposal regarding the specifics of the project to be carried out. The main objective of a mechanism in such situations would be to maximize the aggregate welfare of all the agents (efficiency). Moreover, such decisions typically require to compensate (some) agents with monetary transfers. The protocol defined in the present contribution can be considered a valuable option to be considered. We have highlighted our contribution to the literature that offers mechanisms to decide the location of noxious facilities or any other joint decision by a group of agents. Our proposal is also related to papers that look for mechanisms that agents can use to choose whether to develop a project and which one to develop (see, for instance, Moulin, 1984, and Jackson and Moulin, 1992); to reach good allocations in economic environments with public goods and externalities (Varian, 1994a and 1994b); to dissolve a partnership (McAfee, 1992); to sell (or not) a project to one agent when it affects many (Jehiel et al., 1996); or to award an indivisible good to one agent (in the spirit of King Solomon’s dilemma; see, for instance, Glazer and Ma, 1989, and Perry and Reny, 1999). Our contribution can also expand the set of applications of the multibidding mechanism as part of more complex mechanisms implementing solution concepts. Indeed, variants of the multibidding mechanism (without the need to resort to the tiebreaking rule) have been used in several environments; see Pérez-Castrillo and Wettstein (2001), Bergantiños and Vidal-Puga (2003, 2010), Macho-Stadler et al. (2006), Porteiro (2007), Slikker (2007), Ju et al. (2007), Kamijo (2008), Ehlers (2009), Ju and Wettstein, (2009), 5 and Veszteg (2010).1 Finally, our paper can also be related to the literature on virtual (or −)implementation (Matsushima, 1988, and Abreu and Sen, 1991) in the sense that our objective is not to achieve an exact implementation of an efficient and fair outcome but to get as “close” as wished to that allocation. The paper is organized as follows. In Section 2, we present the environment and the smooth multibidding mechanism. The equilibrium strategies and outcome are stated in Section 3. Section 4 studies the main properties of the equilibrium outcome, including the convergence properties when the parameter goes to zero. We provide a simple example in Section 5. Finally, Section 6 concludes the paper. All proofs are included in the Appendix. 2 The environment and the mechanism We consider a set of agents ={1}whichhavetochoosewhichprojectwillbe carried out of a set of possible projects ={1}. The utility (payoff)ofagentif project is selected is given by  . We denote by ≡P∈ the sum of agents’ utilities if project is implemented. Project is efficient if ≥for all ∈.Wedenotebythe set of efficient projects, that is, ={∈≥for all ∈} Information about all the values  is complete among the agents; that is, each agent knows not only the value he assigns to the projects but also the values assigned by the other agents. However, the planner does not have information about these values. Alternatively, even if she did have some information, she would not want to use it. The planner is interested in designing an impartial mechanism that will treat all the agents in a symmetric manner. We propose a smooth multibidding mechanism through which agents influence the probability that projects are selected. We now describe the mechanism, which has a unique stage. 1For further discussions and applications, see Pérez-Castrillo and Veszteg (2007) and Veszteg (2010). 6 Each agent ∈makes a vector of bids ≡¡ ¢∈in R,oneforeachin with P∈ =0. All agents make their decision simultaneously. Once the agents have chosen their bids, the outcome of the smooth multibidding mechanism is the following. For each ∈,≡P∈ denotes the aggregate bid for project and ≡()∈ denotes the vector of aggregate bids. The probability that project be carried out if the vector of aggregate bids is is ()= () P∈() where we consider the following function (): ()= for all 0 +for all ≥0 with 0. Finally, if project is chosen, each agent ∈pays his bid for that project,  , and he receives a fair share of the aggregate bid, .Therefore,agent’s utility if project is implemented is  − +1  The smooth multibidding mechanism borrows from the multibbiding mechanism of Pérez-Castrillo and Wettstein (2002) the idea of allowing the agents to express their relative preference for projects through a vector of bids. However, under the original mechanism, the probability of selecting any project abruptly jumps from 0 to 1 as the aggregate bid for this project just passes the maximum aggregate bid for the other projects. Under our proposal, a higher (positive) aggregate bid for a project increases the probability that it is selected, but the increase is “smooth”. This feature allows us to offer a mechanism that does not require ad hoc tiebreaking rules. 3 The equilibria of the smooth multibidding mechanism In this section, we characterize the Nash equilibria (NE) of the smooth multibidding mechanism. We proceed as follows. First, we derive several properties that are necessarily 7 satisfied by NE of the game. Second, we use these properties to provide a characterization of the set of NE. Let us proceed now with the analysis. Consider a vector of agents’ bids ()∈and let denote the set of projects for which the aggregate bid is positive under this vector of strategies, that is, ≡{∈0}. Similarly, denote by ≡{∈0}and ≡{∈=0}so we have ∪=\. Additionally, we denote the number of projects in .2The probability that project ∈is chosen is given by ()= + +∈for all ∈  +∈for all ∈\ Agent chooses his vector of bids to maximize his expected profits given the bids chosen by the rest of the agents. Agent ’s profits are Π( −)=X ∈ ()∙ − +1 ¸ Therefore, agent chooses to solve the following program, which we denote by []: X ∈ ()∙ − +1 ¸ s.t. X ∈  =0 To proceed with our analysis we note first, that agent ’s program []is well behaved except that the derivative on the right of function ()with respect to (hence, with respect to  as well) is different from its derivative on the left, at the point =0. We introduce the First-Order Conditions (FOCs) of the program. Denoting by the Lagrange multiplier of the constraint, the FOC of []for any ∈are:    =Π   ( −)+=−(−1) ()+=0,(1) wherewehavetakenintoaccountthat() =0for all ∈and ∈. Itisworthwhile to notice that ()is the same for all ∈, which supports the following property: 2Although the sets ,,anddepend on the the vector of aggregate bids , we avoid using the notations (),()(),and()for simplicity. 8 increasing agent ’s bid to a project in and decreasing another of this agent’s bids to adifferent project in does not matter, as long as both projects still receive a negative aggregate bid after the changes. The FOC for any ∈is    =() ∙ − +1 ¸−(−1) ()+ X ∈\{} () ∙ − +1 ¸+X ∈\ () ∙ − +1 ¸+=0 (2) where ()  =(−1)+P∈\{} ¡ +P∈¢2(3) ()  =−+ ¡ +P∈¢2for all ∈\{}(4) ()  =− ¡ +P∈¢2for all ∈\.(5) Finally, for any ∈, it needs to be the case that   ≥0ontheleftand   ≤0on the right. In fact, the derivative on the left is the same as the left-hand side of equation (1), which is independent of . Therefore, the derivative   ≥0on the left always holds (it holds with equality). Therefore, we only have to add the following condition:    =() ∙ − +1 ¸−(−1) ()+ X ∈ () ∙ − +1 ¸+X ∈\(∪{}) () ∙ − +1 ¸+≤0,(6) for any ∈ where ()  =(−1)+P∈ ¡ +P∈¢2(7) and () is given by (4) for any ∈, and it is given by (5) for any ∈\(∪). The previous FOCs are necessary (although not sufficient) to characterize the NE of the proposed mechanism given that any equilibirum must be interior. Next, we use the FOCs of each agent’s program to characterize the set and the NE aggregate and individual bids to these projects. Lemma 1 conveys useful information about the equilibrium aggregate bids for the projects in . 9 When only efficient projects are selected by the mechanism, the form of the aggregate bids is simple. According to this expression, the aggregate bid will be higher as the difference between the value of an efficient project and those of the other projects increases. Moreover, all efficient projects will be selected with equal probability approximately equal to 1 as the parameter becomes arbitrarily small. In particular, the probability that an efficient project is selected converges to 1as tends toward 0. Propositions 6 and 7 enable us to provide a final result on the relative efficiency of the mechanism as the value of the parameter becomes small. Specifically, we show that, for any equilibrium, the probability of implementing an inefficient project converges to zero. Therefore, the outcome of the mechanism gets as close to efficiency as one wishes as the parameter tends towards zero. Proposition 8 The outcome of the smooth multibidding mechanism converges to full efficiency as the parameter converges to zero. In other words, if project ∈denotes an inefficient project, its probability to be implemented at the equilibrium converges to zero as becomes small. The above result confirms that the effectofavariationoftheparameteris intuitive. Regarding the actual implementation of the mechanism, small values of this parameter will ensure that the chance of choosing an inefficient project comes close to zero. 5Example Before concluding the paper, it might be useful to highlight the main properties of the mechanism with a simple example. Let us consider the following situation. Two agents (1and 2)havetomakeacollectivedecisionontheimplementationofa project. There are four potential choices corresponding to the set ={1234}where the agents’ benefits are: 1 1=6,2 1=3;1 2=4,2 2=6;1 3=2,2 3=1;and1 4=8, 2 4=2, respectively. The weighting parameter is positive; we will highlight how its value influences the outcome of the mechanism. At equilibrium of the smooth multibidding mechanism, Project 3 will receive a negative aggregate bid for any possible (this follows from Theorem 1 (a)). Project 1 will also 16 receive negative aggregate bid as soon as 12. In this case, Proposition 7 provides the expression for the aggregate bids of projects 2 and 4 (the efficient projects): 2=4=−+√2+40 and Theorem 1 (c) enables one to find the equilibrium individual bids for projects 1 and 2. For example, the bids that agents submit for project 2 are 1 2=−2+1 2h−+√2+4i 2 2=2+1 2h−+√2+4i. The probability that projects 2 and 4 are selected at equilibrium is 2()=4()= √4+ 2£√+√4+¤ therefore, each 2()and 4()converges to 12as converges to zero. Finally, regarding the agents’ equilibrium payoffs, we know from Proposition 4 that, for instance, agent 1’s payoffis given by the following expressions: Π1=5+1 2"1 £√+√4+¤³10√4++6 √´−8# which corresponds to this agent’s value of the average project (5) plus his fair share of the collective benefits. The collective benefits converge towards the total value 10 of an efficient project minus the total value of the average project 8.Therefore,Π1converges to 6as converges to 0. 6Conclusion Relying on the main characteristics of the multibidding mechanism (Pérez-Castrillo and Wettstein, 2002), we developed a new procedure for choosing efficient projects in situations where the social planner does not have information on the agents’ preferences. Even though the present protocol does not achieve efficiency, it has a number of interesting properties compared to the mechanism developed in Pérez-Castrillo and Wettstein (2002). That is, it implements a unique equilibrium outcome, satisfies a fairness property 17 and is immune to the problems highlighted by Ehlers (2009) as the use of tiebreaking rules is avoided (by making the probability to select a given project continuous). Moreover, it may come as close to full efficiency as the social planner wishes. As uniqueness and fairness of the resulting outcome are important properties for practical implementation (among other things, fairness ensures that the mechanism will be politically feasible), this mechanism may be considered a valuable tool for such problems of collective decision making. 7 Appendix Proof of Lemma 1. Assume contains at least two projects, otherwise the lemma holds trivially. The derivative of the payoffto any agent ,whenaddinganinfinitesimal to  and substracting from  0is 1 ¡ +P∈¢∙ − +1 ¸−(−1)  (+) ¡ +P∈¢− 1 ¡ +P∈¢∙ 0− 0+1 0¸+(−1)  (+0) ¡ +P∈¢ Thepreviousderivativemustbezeroattheoptimum,thatis,  − −(−2) = 0− 0−(−2) 0.(11) Summing over we get −(−1) =0−(−1) 0, which is equivalent to (8). ProofofProposition1. The FOC for any ∈implies =(−1)   (+∈). Therefore, we write the FOC with respect to ∈(equation (2)) as (after easy simplifications) 1 ¡ +P∈¢2"Ã +X ∈ !∙ − +1 ¸−X ∈ ∙ − +1 ¸#−  ¡ +P∈¢2X ∈  −(−1)   ¡ +P∈¢=0(12) or Ã +X ∈ !∙ − −(−2) ¸−X ∈ ∙ − +1 ¸−X ∈  =0(13) 18 Summing (13) over ∈we obtain Ã +X ∈ ![−(−1) ]−X ∈ −X ∈ =0 i.e., −X ∈ − (−1) +X ∈ (−)−(−1) X ∈ =0(14) Note that we can write the last two terms in (14) as X ∈ [(−)−(−1) ]=−1 −1X ∈ [(−)−(−1) ]2= −1 −1X ∈ (−)2−(−1) 2 +2−2X ∈ , wherewehaveusedequation(8).Therefore,(14)canbewrittenas()=0. Proof of Lemma 2. First, suppose \contains at least two projects. Take projects ∈\and ∈satisfying ≥. We know that for any agent ∈, changes in ¡ ¢∈\do not influence his profits as long as ≤0for all ∈\is maintained. Therefore, if 0then agent can increase  to  = −and decrease  to  = +for some other ∈\. The derivative of the payoffto any agent ,when adding a positive infinitesimal to  and substracting from  is 1 ¡ +P∈¢£ −¡ −¢¤−(−1)   ¡ +P∈¢− 1 ¡ +P∈¢∙ − +1 ¸+(−1)  (+) ¡ +P∈¢ Thepreviousderivativecannotbepositiveattheoptimum,thatis, £ − +¤−∙ − −(−2) ¸≤0for all ∈. Summing the previous equation over ,weget −+(−1)≤0.(15) However, the last inequality cannot hold if ≥and 0 19 Second, suppose \={}and pick such that is the lowest among the elements in . Taking into account that ≤,then≤for all ∈.Forthisproject, 0()|=0=−" (−1) + 2 X ∈ −2#≤− (−1) 0 and ()|=0=−X ∈ −1 (−1) X ∈ (−)2≤0. Therefore, 0is not possible. ProofofProposition2. We first prove by contradiction that project does not belong to if (10) does not hold. We know that, according to Lemma 2, ⊂if ∈. Denote by the project in with the lowest total valuation: ≤for all ∈.Then ()|=0=−X ∈ −1 (−1) X ∈ (−)2≤ −X ∈ −1 (−1) 2 X ∈ (−)≤0 Also, 0()|=0=−£ (−1) + 2 P∈−2¤0which, together with 00() 0implies that ()0for all positive . However, this is not possible at equilibrium. Second, we prove that (10) does not hold if ∈\.Notethat(10)cannothappen for if {}=\. Therefore, we take ∈\and and suppose that there are at least two projects outside .Considersome∈. By the same calculations as in the proof ofLemma2,weobtain(see(15))−+(−1)≤0,thatis,≤1 (−1) (−) or, ()|=1 (−1) (−)≤0This is equivalent to −1 (−1) (−)2−1 (−1) " (−1) + 2 X ∈ −2#(−)+ −X ∈ −1 (−1) X ∈ (−)2≤0,(16) i.e., −X ∈ −1 (−1) X ∈ (−)2−2 (−1) X ∈ (−)+ 2 (−1)(−)−1 (−1)(−)2≤0 20 Using that −(−)2−2(−)=−2 −2 +2and 2(−)−(−)2= 2 −2 , the previous inequality is equivalent to −X ∈ −1 (−1) 2 −1 (−1) X ∈ 2 +2 (−1)X ∈ + 1 (−1) 2 −1 (−1) 2 ≤0 i.e., −X ∈ −1 (−1) X ∈ (−)2≤0(17) Given that ⊃for any ∈, it is necessarily the case that equation (10) cannot hold, as we wanted to prove. ProofofTheorem1.The necessity of parts ()and ()comes from propositions 1 and 2. For part (), note that from (11), we know that  − +1 = − +1 +(−1) (−) for any  ∈. Therefore, we can write (12) as Ã +X ∈ !∙ − +1 ¸−X ∈ ∙ − +1 +(−1) (−)¸− X ∈  −−1 Ã +X ∈ !=0, i.e., ∙ − +1 ¸−X ∈  −1 "(−1) X ∈ 2 +(−1) #=0(18) We use (8) to show that X ∈ 2 =X ∈∙+1 (−1) (−)¸2 = 2 +2 (−1)X ∈ −2 (−1)+1 (−1)2X ∈ (−)2 21 Therefore, (18) is equivalent to ∙ − +1 ¸−X ∈  − 1 "(−1) 2 +2X ∈ −2+1 (−1) X ∈ (−)2+(−1) #=0 and, using that ()=0,weobtain ∙ − +1 ¸−X ∈  −1 "−X ∈ #=0, and part ()follows. For part (), from the same calculations as in the proof of Lemma 3, it follows that, for any agent , any project ∈and any ∈we have    =1 ¡ +P∈¢£ − ¤−1 ¡ +P∈¢∙ − −(−2) ¸≤0 as agents do not have incentives to deviate. This implies the following inequality:  − −∙ − −(−2) ¸≤0(19) Using ()and rewriting, we check that part ()follows for any ∈.Part()is also implied by ()for any ∈when \is a singleton, \={},using =−P∈ . Finally, when \contains at least two projects, any agent can unilaterally amend his bids regarding the projects in  to make any project with an initially negative aggregate bid get one equal to zero. Moreover, the resulting situation is payoffequivalent to the initial one. This implies that condition (19) must hold for all projects ∈once we increase  to  so that the =0,thatis, = −. Therefore, condition (d) must hold. We now show that ()to ()are also sufficient conditions for NE. Consider any vector of bids ()∈satisfying ()to ().Wewillprovethat()∈is indeed a NE by showing that is a best response to −. Any best response to −must satisfy the FOCs. We denote by = +P∈\  for any ∈ and by ,the set and number corresponding to the vector of bids ( −). Following the same calculations as in the proof of Lemma 1, FOCs imply  − −(−2) = 0− 0−(−2) 0for any 0∈.(20) 22 Also, when \has at least two elements, calculations similar to those in Lemma 2 imply  − +≤ 0− 0−(−2) 0for any ∈\0∈.(21) When \only contains one element, that is, \={}for some ∈,then(21) also holds as it is implied by (20). Indeed, summing (20) over ∈\and taking into account that  =−P∈ and =−P∈,weobtain X ∈  + +(−2) =(−1) 0−(−1) 0−(−1)(−2) 0for any 0∈, that is,  − += 0− 0−(−2) 0+ X ∈  +2(−1) − 0+ 0+(−2) 0for any 0∈. Therefore, (21) holds if  0− 0+1 0≥1 X ∈  +(−1) ∙2 +0¸for some 0∈ Since =−P∈\, it is necessarily the case that 2 +0≤0for some 0∈\. Moreover,  0− 0+1 0≥1 P∈ for any 0∈\.3Therefore, (21) also holds for when \={}. Now, we take any 0∈and rewrite (20) and (21) as  +X ∈\  −(2−2) = 0+X ∈\  0−(2−2) 0for any 0∈,(22)  +X ∈\  ≤ 0+X ∈\  −(2−2) 0for any ∈\0∈.(23) 3Any best response must ensure expected profits higher or equal than 1 P∈ ,whichis the level that agent can secure with the “safe” strategy  =−P∈\ :profits under are 1 P∈£ − ¤=1 P∈ because =0for all ∈. Therefore, all the projects ∈ must provide this level of profits in case they are chosen; otherwise, agent woulddecreaseallthebids on those projects which provide less profits (he would also increase  , still ensuring that is negative); this would increase the probability of success of those projects whose profits in case there are chosen is higher or equal than 1 P∈ . 23 Equation (23) is a necessary condition for to be in \. Similarly, because is positive if ∈, a necessary condition for to be in is (following (22))  +X ∈\    0+X ∈\  0−(2−2) 0(24) Therefore, if 0∈,then∈if and only if (24) holds. Equation (24) implies that if 0∈,then∈if  +P∈\ is larger than  0+P∈\ 0. An implication is that ∈if and only if  +P∈\ is larger than some threshold. Also notice that this is also necessarily true for the set (possibly with a different threshold). Therefore, either ⊂or ⊂. We go back to (20), which we rewrite as (25) (2−2) ¡ 0− ¢= 0− −(−2) X ∈\¡ 0− ¢for any 0∈.(25) Taking into account that (25) also holds for (instead of )if0∈,then  0− = 0− for any 0∈∩,(26) that is,  = +(and also =+), for some ∈R,forall∈∩. Take some ∈. The FOC with respect to  is (see (13)) ⎛ ⎝ +X ∈ ⎞ ⎠∙ − −(−2) ¸−X ∈ ∙ − +1 ¸−X ∈  =0(27) First, suppose that ≤0Then, (24) is more limiting for than for ; therefore, ⊂. Equation (27) becomes ⎛ ⎝ +X ∈ +⎞ ⎠∙ − −(−2) −2(−1) ¸− X ∈ (+)∙ − +1 −(−1) ¸−X ∈  =0 24 which we write as Ã +X ∈ !∙ − −(−2) ¸−X ∈ ∙ − +1 ¸−X ∈  − ⎛ ⎝X ∈\ ⎞ ⎠∙ − −(−2) ¸+X ∈\ ∙ − +1 ¸+ ⎛ ⎝∙ − −(−2) ¸−2(−1) ⎛ ⎝ +X ∈ ⎞ ⎠−X ∈∙ − +1 ¸+(−1) X ∈ ⎞ ⎠+ 2µ−2(−1) +(−1) ¶=0(28) The sum of the first three terms in (28) is equal to zero, as it corresponds to the FOC of . Then after some calculations, (28) becomes −⎛ ⎝(−1) [(+)+2 +X ∈ ]+X ∈µ∙ − +1 ¸−∙ − +1 ¸¶⎞ ⎠+ X ∈\ µ∙ − +1 ¸−∙ − +1 ¸¶+⎛ ⎝X ∈\ ⎞ ⎠(−1) =0(29) We notice that because of condition (),£ − +1 ¤−£ −+1 ¤=1 [−] for any  ∈(in particular, this is also true if  ∈). Moreover, Lemma 1 implies that −+(−1)=(−1)or any  ∈. Therefore, (29) can be written as (−1) X ∈\ 2 −(−1) ⎡ ⎣+2 +2X ∈ ⎤ ⎦=0(30) The first term in (30) is non-negative; in fact, it is zero if and only if \is empty. Moreover, +2 +2P∈is positive. Taking into account that ≤0,(29)only holds if \is empty, that is, =and =0. Second, suppose that ≥0, which implies (following (24)) that ⊃.Wetake ∈and we rewrite (27): ⎛ ⎝ +X ∈ + +X ∈\ ⎞ ⎠∙ − −(−2) −2(−1) ¸− X ∈ (+)∙ − +1 −(−1) ¸−X ∈\ ∙ − +1 ¸−X ∈  =0 25 Bound can be rewritten as follows: =(−1)(−1) 2⎡ ⎢ ⎣v u u u t4 (−1)2(−1) ⎡ ⎣(−1)∗−X ∈{} ⎤ ⎦+1−1⎤ ⎥ ⎦≤ (−1)(−1) 2v u u u t4 (−1)2(−1) ⎡ ⎣(−1)∗−X ∈{} ⎤ ⎦≤ ≡(−1)(−1) 2s4 (−1)2(−1)(−1)∗ Therefore, ∗−≤, which gives the expression stated in the Proposition. ProofofProposition7.The expression for follows immediately from ()=0 once we take into account that =for any  ∈when =. It is also immediate that converges to 0as tends towards 0.Finally, ()= +  +P∈ =1  (2−)+r22+4 (−1) ³−P∈´  +r22+4 (−1) ³−P∈´ which converges to 1 as tends towards 0. ProofofProposition8. Let ∈denote a second-best project and ≡∗−0 denote the difference between the value of an efficient project and that of .Wehave ∗− ∗= ∗0Let us consider that the parameter takes values such that ³ ∗´21 (−1)(−1) Then, by Proposition 6 we deduce that project does not belong to for the above values of the parameter , which implies that any inefficient project is in \as well. Therefore, for small enough values of ,=and, according to Proposition 7, the probability of selecting an efficient project converges to 1as the parameter tends to zero, which ensures convergence to an efficient outcome as tends to zero. References [1] Abreu, D. and A. Sen (1991). “Virtual implementation in Nash equilibrium”, Econometrica 59(4), 997-1021. 32 [2] Bergantiños, G. and J.J. Vidal-Puga (2003). “An implementation of the Owen value”, Games and Economic Behavior 44(2), 412-427. [3] Bergantiños, G. and J.J. Vidal-Puga (2010). “Realizing fair outcomes in minimum cost spanning tree problems through non-cooperative mechanisms”, European Journal of Operational Research 201(3), 811-820. [4] Ehlers, L. (2009). “Choosing wisely: The natural multi-bidding mechanism”, Economic Theory 39(3), 505-512. [5] Ingberman, D.E. (1995). “Siting noxious facilities: Are markets efficient?”, Journal of Environmental Economics and Management 29(3), 20-33. [6] Glazer, J. and C.A. Ma (1989). “Efficient allocation of a ‘prize’ - King Solomon’s dilemma”, Games and Economic Behavior 1(3), 222-233. [7] Jackson, M. and H. Moulin (1992). “Implementing a public project and distributing its cost”, Journal of Economic Theory 57(1), 125-140. [8] Jehiel, P., B. Moldovanu and E. Stacchetti (1996). “How (not) to sell nuclear weapons”, American Economic Review 86 (4), 814-829. [9] Ju, Y., P. Borm and P Ruys (2007). “The consensus value: a new solution concept for cooperative games”, Social Choice and Welfare 28(4), 685-703. [10] Ju, Y. and D. Wettstein (2009). “Implementing cooperative solution concepts: A generalized bidding approach”, Economic Theory 39, 307-330. [11] Kamijo, Y. (2008). “Implementation of weighted values in hierarchical and horizontal cooperation structures”, Mathematical Social Sciences 56(3), 336-349. [12] Kunreuther, H. and P.R. Kleindorfer (1986). “A sealed-bid auction mechanism for siting noxious facilities”, American Economic Review (Papers and Proceedings) 76(2), 295-299. [13] Laurent-Lucchetti, J. and J. Leroux (2009). “Choosing and Sharing”, w.p. HEC Montréal. 33 [14] Macho-Stadler, I., D. Pérez-Castrillo and D. Wettstein (2006). “Efficient bidding with externalities”, Games and Economic Behavior 57, 304-320. [15] Matsushima, H. (1988). “A new approach to the implementation problem”, Journal of Economic Theory 45, 128-144. [16] McAfee, R.P. (1992). “Amicable divorce: Dissolving a partnership with simple mechanisms”, Journal of Economic Theory 56(2), 266-293. [17] Minehart, D. and Z. Neeman (2002). “Effective siting of waste treatment facilities”, Journal of Environmental Economics and Management 43, 303-324. [18] Moulin, H. (1984). “The conditional auction mechanism for sharing a surplus”, Review of Economic Studies 51(1), 157-170. [19] O’Sullivan, A. (1993). “Voluntary auctions for noxious facilities: Incentives to participate and the efficiency of siting decisions”, Journal of Environmental Economics and Management 25(1), 12-26. [20] Pérez-Castrillo, D. and R. Veszteg (2007). “Choosing a common project: Experimental evidence on the multibidding mechanism”, Journal of Economic Behavior & Organization 63(3), 394-411. [21] Pérez-Castrillo, D. and D. Wettstein (2001). “Bidding for the surplus: A noncooperative approach to the Shapley value”, Journal of Economic Theory 100(2), 274-294. [22] Pérez-Castrillo, D. and D. Wettstein (2002). “Choosing wisely: A multibidding approach”, American Economic Review 92, 1577-1587. [23] Perry, M. and P.J. Reny (1999). “A general solution to King Solomon’s dilemma”, Games and Economic Behavior 26(2), 279-285. [24] Porteiro, N., (2007). “An efficient and egalitarian negotiation procedure for economies with externalities”, Social Choice and Welfare 28, 19-40. 34 [25] Rob, R., (1989). “Pollution claim settlements under private information”, Journal of Economic Theory 47(2), 307-333. [26] Slikker, M., (2007). “Bidding for surplus in network allocation problems”, Journal of Economic Theory 137, 493-511. [27] Varian, R.H. (1994a). “Sequential contributions to public goods”, Journal of Public Economics 53(2), 165-186. [28] Varian, R.H. (1994b). “A solution to the problem of externalities when agents are well informed”, American Economic Review 84(5), 1278-1293. [29] Veszteg, R. (2010). “Multibidding game under uncertainty”, Review of Economic Design 14 (3-4), 311-329. 35