Robust Mechanism Design

The following sections are included:

• Foreword

• Acknowledgments

• Contents

The following sections are included:

• Introduction

• Leading Example: Allocating a Private Good with Interdependent Values

• Type Spaces

• Robust Foundations for Dominant and Ex Post Incentive Compatibility

• Full Implementation
  • Ex Post Implementation
  • Robust Implementation in the Direct Mechanism
  • The Robustness of Robust Implementation
  • Robust Implementation in the General Mechanism
  • Rationalizable Implementation
  • The Role of the Common Prior
  • Dynamic Mechanisms
  • Virtual Implementation

• Open Issues

• References

The mechanism design literature assumes too much common knowledge of the environment among the players and planner. We relax this assumption by studying mechanism design on richer type spaces.

We ask when ex post implementation is equivalent to interim (or Bayesian) implementation for all possible type spaces. The equivalence holds in the case of separable environments; examples of separable environments arise (1) when the planner is implementing a social choice function (not correspondence) and (2) in a quasilinear environment with no restrictions on transfers. The equivalence fails in general, including in some quasilinear environments with budget balance.

In private value environments, ex post implementation is equivalent to dominant strategies implementation. The private value versions of our results offer new insights into the relationship between dominant strategy implementation and Bayesian implementation.

We analyze the problem of fully implementing a social choice set in ex post equilibrium. We identify an ex post monotonicity condition that is necessary and — in economic environments — sufficient for full implementation in ex post equilibrium. We also identify an ex post monotonicity no veto condition that is sufficient. Ex post monotonicity is satisfied in all single crossing environments with strict ex post incentive constraints.

We show by means of two classic examples that ex post monotonicity does not imply nor is it implied by Maskin monotonicity. The single unit auction with interdependent valuations is shown to satisfy ex post monotonicity but not Maskin monotonicity. We further describe a Pareto correspondence that fails ex post monotonicity but satisfies Maskin monotonicity.

A social choice function is robustly implementable if there is a mechanism under which the process of iteratively eliminating strictly dominated messages leads to outcomes that agree with the social choice for all beliefs at every type profile. In an interdependent value environment with single crossing preferences, we identify a contraction property on the preferences which together with strict ex post incentive compatibility is sufficient to guarantee robust implementation in the direct mechanism. Strict ex post incentive compatibility and the contraction property are also necessary for robust implementation in any mechanism, including indirect ones.

The contraction property requires that the interdependence is not too large. In a linear signal model, the contraction property is equivalent to an interdependence matrix having an eigenvalue less than one.

A social choice function is robustly implemented if every equilibrium on every type space achieves outcomes consistent with it. We identify a robust monotonicity condition that is necessary and (with mild extra assumptions) sufficient for robust implementation.

Robust monotonicity is strictly stronger than both Maskin monotonicity (necessary and almost sufficient for complete information implementation) and ex post monotonicity (necessary and almost sufficient for ex post implementation). It is equivalent to Bayesian monotonicity on all type spaces.

We consider the role of the common prior for robust implementation in an environment with interdependent values. Specifically, we investigate a model of public good provision which allows for negative and positive informational externalities. In the corresponding direct mechanism, the agents’ reporting strategies are strategic complements with negative informational externalities and strategic substitutes with positive informational externalities. We derive the necessary and sufficient conditions for robust implementation in common prior type spaces and contrast this with our earlier results without the common prior. In the case of strategic complements the necessary and sufficient conditions for robust implementation do not depend on the existence of a common prior. In contrast, with strategic substitutes, the implementation conditions are much weaker under the common prior assumption.

The important role of dynamic auctions, in particular ascending price auctions, for the revelation of private information has been recognized for a long time. The advantage of sequential procedures is the ability to reveal and communicate private information in the course of the mechanism. The revelation of private information can decrease the uncertainty faced by the bidders and ultimately improve the final allocation offered by the mechanism. In auctions, the source of the uncertainty can be payoff uncertainty (about others’ payoff relevant information) or strategic uncertainty (about their bidding strategies)….

In a general interdependent preference environment, we characterize when two payoff types can be distinguished by their rationalizable strategic choices without any prior knowledge of their beliefs and higher order beliefs. We show that two payoff types are strategically distinguishable if and only if they satisfy a separability condition. The separability condition for each agent essentially requires that there is not too much interdependence in preferences across agents.

A social choice function—mapping payoff type profiles to outcomes— can be robustly virtually implemented if there exists a mechanism such that every equilibrium on every type space achieves an outcome arbitrarily close to the social choice function. This definition is equivalent to requiring virtual implementation in iterated deletion of strategies that are strictly dominated for all beliefs. The social choice function is robustly measurable if strategically indistinguishable payoff types receive the same allocation. We show that ex post incentive compatibility and robust measurability are necessary and sufficient for robust virtual implementation.

We consider parametric examples of symmetric two-bidder private value auctions in which each bidder observes her own private valuation as well as noisy signals about her opponent’s private valuation. We show that, in such environments, the revenue equivalence between the first and second price auctions (SPAs) breaks down and there is no definite revenue ranking; while the SPA is always efficient allocatively, the first price auction (FPA) may be inefficient; equilibria may fail to exist for the FPA. We also show that auction mechanisms provide different incentives for bidders to acquire costly information about opponents’ valuation. ©2004 Elsevier Inc. All rights reserved.

We show that a mechanism that robustly implements optimal outcomes in a one-dimensional supermodular environment continues to robustly implement ε-optimal outcomes in all close-by environments. Robust implementation of ε-optimal outcomes is thus robust to small perturbations of the environment. This is in contrast to ex-post implementation which is not robust in this sense as only trivial social choice functions are ex-post implementable in generic environments.

We consider the implementation of social choice functions under complete information in rationalizable strategies. A strict version of the monotonicity condition introduced by Maskin is necessary under the solution concept of rationalizability. Assuming the social choice function is responsive, i.e., in distinct states it selects distinct outcomes, we show that strict Maskin monotonicity is also sufficient under a mild “no worst alternative” condition. In particular, no economic condition is required. We discuss how our results extend when the social choice function is not responsive.

We consider the problem of pricing a single object when the seller has only minimal information about the true valuation of the buyer. Specifically, the seller only knows the support of the possible valuations and has no further distributional information. The seller is solving this choice problem under uncertainty by minimizing her regret. The pricing policy hedges against uncertainty by randomizing over a range of prices. The support of the pricing policy is bounded away from zero. Buyers with low valuations cannot generate substantial regret and are priced out of the market. We generalize the pricing policy without priors to encompass many buyers and many qualities.

We consider a robust version of the classic problem of optimal monopoly pricing with incomplete information. In the robust version, the seller faces model uncertainty and only knows that the true demand distribution is in the neighborhood of a given model distribution. We characterize the pricing policies under two distinct decision criteria with multiple priors: (i) maximin utility and (ii) minimax regret. The equilibrium price under either criterion is lower then in the absence of uncertainty. The concern for robustness leads the seller to concede a larger information rent to all buyers with values below the optimal price without uncertainty.

The following sections are included:

• Author Index

• Subject Index