1 Simplified Mechanisms with an Application to Sponsored-Search Auctions Paul Milgrom1 First draft: August 16, 2007 This draft: December 17, 2008 A mechanism can be simplified by restricting its message space. If the restricted message spaces satisfy a certain “outcome closure property,” then the simplification is “tight”: for every , any Nash equilibrium of the simplified mechanism is also an Nash equilibrium of the unrestricted mechanism. Prominent auction and matching mechanisms are tight simplifications of mechanisms studied in economic theory and often incorporate price-adjustment features that facilitate simplification. The generalized second price auction used for sponsored-search advertising is a tight simplification of a series of second-price auctions that eliminates the lowest revenue equilibrium outcomes and leaves intact only higher revenue equilibria. Keywords: sponsored search, generalized second-price auctions, mechanism design. JEL Categories: D44, C78 I. Introduction Real-world resource allocation mechanisms are often much simpler than the direct mechanisms featured in economic theory.2 The reason is not hard to see: when there are 1 Support for this research was provided by National Science Foundation Grant SES-0648293 and by Yahoo! Thanks to Marissa Beck and Richard Steinberg for comments and to Joshua Thurston-Milgrom for editorial help. Any opinions expressed here are those of the author alone. 2 A direct mechanism is a mechanism in which each participant’s strategy is a message describing that participant’s private information, or “type.”2 more than a few distinct items to be allocated, the sheer number of combinations of items makes it too costly for participants to determine and express all of their relevant values, as direct mechanisms ordinarily require. The resource allocation mechanisms used in practice often employ messages that are too simple to describe preferences completely. For example, in simultaneous first-price auctions of the sort utilized for wholesale trading of used cars to dealers, the auctioneer typically accepts individual bids on cars, and allows the bidder no opportunity to describe the extent to which it might be willing to substitute one car for another. Similarly, the National Resident Matching Program (NRMP) uses a variant of the celebrated Gale-Shapley algorithm3 to assign doctors to hospitals, but accepts reports from hospitals that consist only of a number of positions and a rank order list of doctors, allowing a hospital only a meager opportunity to describe its preferences about the composition of its incoming class. For our theoretical analysis, we view the short messages in these examples as reports of preferences from a restricted set. The bids on cars in our example describe the values of a hypothetical bidder with additive preferences, and the NRMP messages describe the relevant choices by a hospital which, given a choice between two doctors, would make that choice independently of the other doctors that it has hired. In our theory, a simplified mechanism is derived from an original mechanism by restricting the set of messages. How does such a simplification affect the performance of the mechanisms observed in practice? This question is problematic, because a simplified mechanism may 3 Gale and Shapley (1962).3 correspond to more than one extension. Different extensions assign different outcomes to the excluded message profiles, and any of these might be compared to the outcome of the simplification. Still, there are specific extensions that are of obvious interest. One is the menu auction of Bernheim and Whinston (1986), which is an extension of the first-price auction that allows bidders to express separate values or bids for every package. The auctioneer accepts the collection of bids that maximizes the total value of the allocation and charges each bidder the price it has bid for its assigned package. For a full preference report, this mechanism entails a number of bids that grows exponentially with the number of lots or items sold. How much is a well-informed bidder harmed by a simplification that restricts messages to ones that describe additively separable preferences when other bidders are similarly restricted? The answer? None at all. If the bidder would win a collection of lots S at a price of p in the menu auction, then it could win the same collection with additive bids for the individual items that sum to no more than p an arbitrarily small amount. Of course, for a bidder who was less confident about its opportunities, the restriction to additive bids could be quite costly. A similar analysis applies to the National Resident Matching Program. The NRMP algorithm selects the doctor-best stable matching4 for the preferences reported by doctors and hospitals. This selection is no accident; it was an explicit goal of the mechanism’s design.5 Although the current NRMP algorithm allows hospitals to report 4 A matching of doctors to hospitals is stable if three conditions are satisfied: (1) no hospital prefers to dismiss any of its doctors, (2) no doctor prefers to quit his hospital, and (3) no doctor-hospital pair can make a deal that both prefer (taking into account that, after the deal, the hospital may choose to dismiss some of its assigned doctors). A doctor-best stable matching is a stable matching M with the property that there is no doctor D and stable matching M′ such that D strictly prefers his hospital in M′ to his hospital in M. 5 Roth and Peranson (1999).4 only a limited set of preferences, it would be easy to extend it to allow hospitals to report preferences from any class for which doctor-best stable matchings always exist. The largest such class that also includes all the preferences that are currently reportable is the class of substitutable preferences.6 One may ask: how much harm does a particular hospital suffer when its messages are restricted to those allowed by the NRMP, rather than to the wider class of substitutable preferences? To investigate that question, fix a hospital H, reports by the doctors, and simple reports by the other hospitals. Is hospital H hurt by its inability to use some substitutable preference report? If hospital H is sufficiently well informed, then for any set of doctors S that hospital H could hire by making the alternative report, it can hire the same set by reporting that it has |S| openings and that the doctors in S