IJCAI11ContentsIndexHelpTermsIJCAI WebsiteEfficient Mechanisms with Risky ParticipationRuggiero CavalloYahoo! Research111 West 40th StreetNew York, NY [email protected] is a fundamental incompatibility between ef-ficiency, interim individual rationality, and budget-balance in mechanism design, even for extremelysimple settings. Yet it is possible to specify efficientmechanisms that satisfy participation and budget-balance constraints in expectation, prior to typesbeing realized. We do so h ere, in fact derivingmechanisms that are individually rational for eachagent even ex post of other agents’ type realiza-tions. However, participatio n must still bear somerisk of loss. For agents that are risk neutral, weshow how the center can extract the entire surplusin expectation, or alternatively provide an equal ex-pected share of the surplus for each participant,without violating dominant strategy incentive com-patibility, efficiency, or ex ante budget-balance. Wecompare these solutions to a third efficient mecha-nism we design explicitly to address risk aversionin trade settings: payments are defined to mini-mize the odds of loss, satisfying ex ante participa-tion constraints for agents with attitudes toward riskranging from neutrality to high loss-aversion.1 IntroductionWe address a general problem of efficient decision-makingamongst self-interested agents when commitment can be es-tablished prior to values bein g learned. Let us start with anexample: Two software companies decide to collaborate onbuilding a new web technology in advance of the upcomingsummer Olympic games two years in the future. It cannotbe determined in advance of the games what the most advan-tageous way of using the technology will be: whether bothcompanies should provide it, whether just one should get fullcontrol, whether it should be sold off, etc. Eventually eachcompany (agent) will privately learn its own value for each ofthe possible choices and a decision will be made.Can a budget-balanced payment mechanism be designed—enforced by a third-party (“the center”)1that shares the1One can imagine the center as an agent that has engineered theprocess, e.g., the parent company of subsidiaries that are run inde-pendently but could yield net efficiency gains through collaboration.agents’ expectations about how their own values will berealized—that achieves a social-welfare maximizing outcomein dominant strategies while, at the time the business union isformed, establishing that each agent and the center expectsto gain from joining the venture? Furthermore, can we iden-tify a mechanism that strikes an effective balance betweenthe likely benefit to each agent and to the center, so that eventhose who are significantly loss-averse choose to participate?Mechanism design uses monetary payments as a tool toachieve desirable outcomes in decision settings with self-interested agents, such as the above. Often the goal is tomaximize social welfare (efficiency). In addition to (and insupport of) efficiency, the properties of individual rational-ity (IR) (no agent is made worse off from participating) andno-deficit (net transfers from the mechanism to the agents arenon-positive) are typically essential. Consider, for instance,bilateral trade, where a good is initially held by one agent andthere is another who potentially values the good higher thanthe first. Ideally, the good would change hands if and onlyif the second agent’s value is higher, and additionally bothagents would end up at least as well off from having partici-pated as not, but without requiring a subsidy from the mech-anism. Unfortunately this ideal is unreachable, as demon-strated by the Myerson-Satterthwaite impossibility theorem[Myerson and Satterthwaite, 1983].In the face of this theorem there has been significant workin designing mechanisms that do not achieve efficiency butmaintain interim2IR and no-deficit (see, e.g.,[Gresik andSatterthwaite, 1989; Yoon, 2008; Rustichini et al., 1994;Tatur, 2005]). Although making sacrifices in social welfare isone natural response, another approach—novel, to our knowl-edge, which we initiate here—is to maintain domin ant strat-egy efficiency and instead go outside the scope of the impos-sibility result by moving the individual rationality demandfrom interim to the requirement that each agent expect togain from p articipating ex ante of his own type realization(given the probability distribution over his type) even ex postof the other agents’ type realizations. This notion is signifi-cantly weaker than fully ex post IR but significantly strongerthan fully ex ante IR, as it removes any need for agents toform expectations or reason about the types of others. Hark-ing back to the software company collaboration example, be-2Ex post of your own type realization, ex ante of others’.133Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligencefore learning its value function, company A should expectto gain from joining the venture regardless of how companyB’s value function eventually turns out. We demonstrate theexistence o f dominant strategy efficient solutions that alwayssatisfy this IR no tion and are ex ante no-deficit, for arbitrarydistributions over types.But, granting tha t a participation decision can be forcedprior to learning values, if the proposition agents face isparticipation in a “risky” mechanism that is expected tobring gains but may bring losses, agent attitudes toward r iskbecome critical. There is abundant evidence that in eco-nomic settings people are not completely neutral towards risk,but rather often manifest significant loss-aversion (see, e.g.,[DellaVigna, 2009]). Yet the prevailing assu mption in mech-anism design research is risk neutrality,3an unsettling mis-match with reality. In this paper, in addition to designingmechanisms that have desirable revenue or fairness proper-ties for risk neutral agents, we will provide a mechanism thatis robust to a wide range of attitudes towards loss, includingsignificant loss-aversion.In the mechanisms we propose, the payment for eachagent is defined in a way that exploits valuation informa-tion reported by the others. This makes the mechanismsespecially compelling (less risky) when types are corre-lated, i.e., when considering any agent i, knowing the typesof agents other than i provides good information about i’stype. And, interestingly, the literatu re