Truthful approximation mechanisms for restricted combinatorial auctions

When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be embedded in any truthful mechanism (e.g. VCG-like payment rules will not ensure truthfulness).We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where each bidder desires a specific known subset of items and only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann, O'Callaghan, and Shoham, who presented greedy heuristics. We show how to use If-Then-Else constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several canonical types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios.     

Industry concentration in common value auctions: theory and evidence

We examine theoretically and experimentally two countervailing effects of industry concentration in common value auctions. Greater concentration of information among fewer bidders reduces competition but increases the precision of private estimates. We demonstrate that this generally leads to more aggressive bidding. However, the reduction in competition dominates the informational effects, resulting in lower prices. We examine these hypothesized effects experimentally by conducting a series of auctions with constant informational content but distributed among a varying number of bidders. The experimental results are consistent with our theoretical predictions. The authors would like to thank Octavian Carare, Eric Friedman, Luke Froeb, Ron Harstad, Toshi Iizuka, Mike Rothkopf, Charles Thomas, and two anonymous referees, for many useful comments and suggestions.     

Ex-post full surplus extraction,straightforwardly

Consider an estimate of the common value of an auctioned asset that is symmetric in the bidders’ types. Such an estimate can be represented solely in terms of the order statistics of those types. This representation forms the basis for a pricing rule yielding truthful bidding as an equilibrium, whether bidders’ types are affiliated or independent. We highlight the link between the estimator and full surplus extraction, providing a necessary and sufficient condition for ex-post full surplus extraction, including the possibility of independent types. The results offer sharp insights into the strengths and limits of simple auctions by identifying the source of informational rents in such environments. Harstad acknowledges hospitable accommodation by the Fuqua School of Business, Duke University, and the Olin School of Business, Washington University in St. Louis, during parts of this research. We are grateful for comments and suggestions from Richard McLean and Jeroen Swinkels.     

The value of information for auctioneers

An auctioneer wants to sell an indivisible object to one of multiple bidders, who have private information about their valuations of the object. A bidder's information structure determines the accuracy with which the bidder knows her private valuation. The main result of the paper is that the auctioneer's revenue is a convex function of bidders' information structures. One implication is that assigning asymmetric information structures instead of symmetric information structures to bidders is always revenue-enhancing. This paper generalizes a result of Bergemann and Pesendorfer [D. Bergemann, M. Pesendorfer, Information structures in optimal auctions, J. Econ. Theory 137 (2007) 580–609], who show that revenue-maximizing information structures are asymmetric.     

Allocating multiple units

Summary. This paper studies the allocation and rent distribution in multi-unit, combinatorial-bid auctions under complete information. We focus on the natural multi-unit analogue of the first-price auction, where buyers bid total payments, pay their bids, and where the seller allocates goods to maximize his revenue. While there are many equilibria in this auction, only efficient equilibria remain when the truthful equilibrium restriction of the menu-auction literature is used. Focusing on these equilibria we first show that the first-price auction just described is revenue and outcome equivalent to a Vickrey auction, which is the multi unit analogue of a second-price auction. Furthermore, we characterize these equilibria when valuations take a number of different forms: diminishing marginal valuations, increasing average valuations, and marginal valuations with single turning points. Received: December 23, 1999; revised version: December 10, 2001     

Ascending auctions for multiple objects: the case for the Japanese design

Summary. We consider two ascending auctions for multiple objects, namely, an English and a Japanese auction, and derive a perfect Bayesian equilibrium of the Japanese auction by exploiting its strategic equivalence with the survival auction, which consists of a finite sequence of sealed-bid auctions. Thus an equilibrium of a continuous time game is derived by means of backward induction in finitely many steps. We then show that all equilibria of the Japanese auction induce equilibria of the English auction, but that many collusive or signaling equilibria of the English auction do not have a counterpart in the Japanese auction.Received: 2 September 2004, Revised: 20 April 2005, JEL Classification Numbers: C72, D44.Fabrizio Germano: Correspondence toWe are indebted to Philippe Jehiel for useful discussions and to Nicolas Vieille for suggestions in the proof of Proposition 2; we also thank seminar audiences in Athens, Basel, Beer-Sheva, Berlin, Brussels, Cambridge, Edinburgh, Exeter, Lausanne, Lisbon, London, Louvain-la-Neuve, Namur and Tel Aviv. Germano acknowledges financial support from Euopean Commission, TMR Network Grant ERBFMRXCT0055, “Cooperation and Information” as well from the Spanish Ministry of Science and Technology, Grants SEC2001-0792, SEJ2004-06319, and in form of a Ramon y Cajal Fellowship. Lovo is member of GREGHEC, unité CNRS, FRE-2810. The support of the Economic and Social Research Council (ESRC) is also gratefully acknowledged. The work was part of the programme of the ESRC Research for Economic Learning and Social Evolution.     

A Market-Based Mechanism for Allocating Space Shuttle Secondary Payload Priority

This is an investigation into the design of a market-based process to replace NASA's current committee process for allocating Shuttle secondary payload resources (lockers, Watts and crew). The market-based process allocates budgets of tokens to NASA internal organizations that in turn use the budget to bid for priority for their middeck payloads. The scheduling algorithm selects payloads by priority class and maximizes the number of tokens bid to determine a manifest. The results of a number of controlled experiments show that such a system tends to allocate resources more efficiently by guiding participants to make resource and payload tradeoffs. Most participants were able to improve their position over NASA's current ranking system. Furthermore, those that are better off make large improvements while the few that do worse have relatively small losses.     

Vickrey auctions with reserve pricing

Summary. We generalize the Vickrey auction to allow for reserve pricing in a multi-unit auction with interdependent values. In the Vickrey auction with reserve pricing, the seller determines the quantity to be made available as a function of the bidders' reports of private information, and then efficiently allocates this quantity among the bidders. Truthful bidding is a dominant strategy with private values and an ex post equilibrium with interdependent values. If the auction is followed by resale, then truthful bidding remains an equilibrium in the auction-plus-resale game. In settings with perfect resale, the Vickrey auction with reserve pricing maximizes seller revenues.Received: 31 December 2002, Revised: 5 May 2003, JEL Classification Numbers: D44, C78, D82.Correspondence to: Lawrence M. AusubelThe authors gratefully acknowledge the generous support of National Science Foundation Grants SES-97-31025, SES-01-12906 and IIS-02-05489. We appreciate valuable comments from Ilya Segal. Special thanks go to Mordecai Kurz, who served as Larry's dissertation advisor and who introduced both authors to the economics profession back at IMSSS at Stanford. Congratulations and best wishes are extended to Mordecai and his family on the happy occasion of the publication of Assets, Beliefs, and Equilibria in Economic Dynamics: Essays in Honor of Mordecai Kurz, in which this article also appears.     

Auctioning divisible goods

Summary. We derive equilibrium bidding strategies in divisible good auctions for asymmetrically informed risk neutral and risk averse bidders when there is random noncompetitive demand. The equilibrium bid schedules contain both strategic considerations and explicit allowances for the winner's curse. When the bidders' information is symmetric, the strategic aspects of bidding imply that there always exist equilibria of a uniform-price auction with lower expected revenue than provided by a discriminatory auction. When bidders are risk averse, there may exist equilibria of the uniform-price auction that provide higher expected revenue than a discriminatory auction. Received: November 4, 1999; revised version: March 9, 2001     

Overcoming free riding in multi-party computations—The anonymous case

This paper addresses the question of multi-party computation in a model with asymmetric information. Each agent has a private value (secret), but in contrast to standard models, the agent incurs a cost when retrieving the secret. There is a social choice function the agents would like to compute and implement. All agents would like to perform a joint computation, which input is their vector of secrets. However, agents would like to free-ride on others' contribution.A mechanism which elicits players' secrets and performs the desired computation defines a game. A mechanism is ‘appropriate’ if it (weakly) implements the social choice function for all secret vectors. namely, if there exists an equilibrium in which it is able to elicit (sufficiently many) agents' secrets and perform the computation, for all possible secret vectors. We show that ‘appropriate’ mechanisms approach agents sequentially and that they have low communication complexity.     

Asymptotic and small sample analysis of the stochastic properties and certainty equivalents of winning bids in independent private values auctions$\!$

Summary. This paper investigates the stochastic properties of the first price and second price winning bids in auctions with risk neutral bidders with independent and identically distributed valuations. In such an environment, the winning first price bids second order stochastically dominate the second price winning bids. A key result of this paper is that the ratio of the variance of the winning first price bid to that of the winning second price bid is strictly less than one even as the number of bidders goes to infinity. This suggests that the stochastic dominance of the winning first price bids does not vanish even in the limit. Both the asymptotic and small sample properties of winning bids are investigated. In particular, the small sample results suggest that the identification power of econometric procedures that rely on winning bids can decline rapidly as the number of bidders increases. This paper also includes a systematic evaluation of the difference in certainty equivalents between the two auction formats for several common distributions and number of bidders for the case of auctioneers with constant coefficient of absolute risk aversion. These results are presented in a form that makes it easy to apply them to a specific auction of interest.Received: 15 July 2002, Revised: 7 April 2003, JEL Classification Numbers: D44.I would like to thank David Pearce for helpful comments and discussion and a referee for suggestions that have greatly improved this paper.     

The Design of ``Smart' Water Market Institutions Using Laboratory Experiments

One of the problems with proposals for substantialinstitutional change in water systems is thatmodification and irreversibility make the processslow, cautious and costly to society. In this paper,we discuss the role that experimental economics canplay in evaluating proposed institutional changes tohelp facilitate a more rapid and smooth adoption ofchanges in the water system. Experimental economicsyields a formal and replicable system for analyzingalternative market structures before they are actuallyimplemented. For example, a water market can bedeveloped and tested in the laboratory under supplyand demand constraints that reflect drought conditionsthat might occur in California, or other arid regionsin the world. We present a prototype of a Californiawater transfer model and the results from a series ofwater market experiments. Results include realizedmarket efficiency and surplus distribution, as well asan analysis of market price volatility. Theimplications of this research extend well beyondCalifornia water markets, not only to water markets inother arid regions, but also to the design of marketsfor other environmental goods, including tradablepollution permits and fishery ITQs.