INTRODUCTION

This chapter considers the problem of finding allocations that satisfy certain social goals when economic agents have private information regarding their preferences. This problem has been discussed since at least the early 20thcentury debate on alternative economic mechanisms, but it has received renewed attention recently in the literature on “market design,” which proposes mechanisms to solve various allocation problems of practical importance. For example, the “two-sided matching problem” arises in allocating workers across firms, students across schools, or medical interns across medical schools (Roth and Sotomayor (1990)). The “combinatorial auction problem” arises in allocating bundles of indivisible items among bidders (Cramton et al. (2006)). Both agents' preferences and social goals in these problems differ substantially from those in the classical economies studied earlier. In particular, agents' preferences often exhibit nonconvexities and indivisibilities, and the social goals may include exact or approximate efficiency, voluntary participation, stability to group deviations, and even some notions of fairness.

A major theme in the “market design” literature is that the choice of mechanism is not determined by incentives alone. Indeed, if incentive compatibility were the only concern, it could be verified with a direct revelation mechanism. However, full revelation of agents' preferences is often impractical or undesirable, for several reasons: First, sometimes full revelation requires a prohibitive amount of communication – e.g., a bidder in a combinatorial auction would have to announce his valuations for all possible bundles of objects, whose number is exponential in the number of objects.