Efficient Mechanisms with Risky Participation

AAAI Conferences

There is a fundamental incompatibility between efficiency, interim individual rationality, and budget-balance in mechanism design, even for extremely simple settings. Yet it is possible to specify efficient mechanisms that satisfy participation and budget-balance constraints in expectation, prior to types being realized. We do so here, in fact deriving mechanisms that are individually rational for each agent even ex post of other agents' type realizations. However, participation must still bear some risk of loss. For agents that are risk neutral, we show how the center can extract the entire surplus in expectation, or alternatively provide an equal expected share of the surplus for each participant, without violating dominant strategy incentive compatibility, efficiency, or ex ante budget-balance. We compare these solutions to a third efficient mechanism we design explicitly to address risk aversion in trade settings: payments are defined to minimize the odds of loss, satisfying ex ante participation constraints for agents with attitudes toward risk ranging from neutrality to high loss-aversion.


A Bargaining Mechanism for One-Way Games

AAAI Conferences

We introduce one-way games, a framework motivated by applications in large-scale power restoration, humanitarian logistics, and integrated supply-chains. The distinguishable feature of the games is that the payoff of some player is determined only by her own strategy and does not depend on actions taken by other players. We show that the equilibrium outcome in one-way games without payments and the social cost of any ex-post efficient mechanism, can be far from the optimum. We also show that it is impossible to design a Bayes-Nash incentive-compatible mechanism for one-way games that is budget-balanced, individually rational, and efficient. Finally, we propose a privacy-preserving mechanism that is incentive-compatible and budget-balanced, satisfies ex-post individual rationality conditions, and produces an outcome which is more efficient than the equilibrium without payments.


Balanced Trade Reduction for Dual-Role Exchange Markets

AAAI Conferences

We consider dual-role exchange markets, where traders can offer to both buy and sell the same commodity in the exchange but, if they transact, they can only be either a buyer or a seller, which is determined by the market mechanism. To design desirable mechanisms for such exchanges, we show that existing solutions may not be incentive compatible, and more importantly, cause the market maker to suffer a significant deficit. Hence, to combat this problem, following McAfee's trade reduction approach, we propose a new trade reduction mechanism, called balanced trade reduction, that is incentive compatible and also provides flexible trade-offs between efficiency and deficit.


MUDA: A Truthful Multi-Unit Double-Auction Mechanism

AAAI Conferences

In a seminal paper, McAfee (1992) presented a truthful mechanism for double auctions, attaining asymptotically-optimal gain-from-trade without any prior information on the valuations of the traders. McAfee's mechanism handles single-parametric agents, allowing each seller to sell a single unit and each buyer to buy a single unit. This paper presents a double-auction mechanism that handles multi-parametric agents and allows multiple units per trader, as long as the valuation functions of all traders have decreasing marginal returns. The mechanism is prior-free, ex-post individually-rational, dominant-strategy truthful and strongly-budget-balanced. Its gain-from-trade approaches the optimum when the market size is sufficiently large.


Assessing the Robustness of Cremer-McLean with Automated Mechanism Design

AAAI Conferences

In a classic result in the mechanism design literature, Cremerand McLean (1985) show that if buyers’ valuations are sufficiently correlated, a mechanism exists that allows the seller to extract the full surplus from efficient allocation as revenue. This result is commonly seen as “too good to be true” (in practice), casting doubt on its modeling assumptions. In this paper, we use an automated mechanism design approach to assess how sensitive the Cremer-McLean result is to relaxing its main technical assumption. That assumption implies that each valuation that a bidder can have results in a unique conditional distribution over the external signal(s). We relax this, allowing multiple valuations to be consistent with the same distribution over the external signal(s). Using similar insights to Cremer-McLean, we provide a highly efficient algorithm for computing the optimal revenue in this more general case. Using this algorithm, we observe that indeed, as the number of valuations consistent with a distribution grows, the optimal revenue quickly drops to that of a reserve-price mechanism. Thus, automated mechanism design allows us to gain insight into the precise sense in which Cremer-McLean is “too good to be true.”