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.     

License auctions with royalty contracts for (winners and) losers

This paper revisits the licensing of a non-drastic process innovation by an outside innovator to a Cournot oligopoly. We propose a new mechanism that combines a restrictive license auction with royalty licensing. This mechanism is more profitable than standard license auctions, auctioning royalty contracts, fixed-fee licensing, pure royalty licensing, and two-part tariffs. The key features are that royalty contracts are auctioned and that losers of the auction are granted the option to sign a royalty contract. Remarkably, combining royalties for winners and losers of the auction makes the integer constraint concerning the number of licenses irrelevant.     

Internet auctions with many traders

We study a multi-unit auction environment similar to eBay. Sellers, each with a single unit of a homogeneous good, set reserve prices at their own second-price auctions. Each buyer has private value for the good and wishes to acquire a single unit. Buyers can bid as often as they like and move between auctions. We characterize a perfect Bayesian equilibrium for this decentralized dynamic mechanism in which, conditional on reserve prices, an efficient set of trades occurs at a uniform price. In a large but finite market, the sellers set reserve prices equal to their true costs under a very mild distributional assumption, so ex post efficiency is achieved. Buyers’ strategies in this equilibrium are simple and do not depend on their beliefs about other buyers’ valuations, or the number of buyers and sellers.     

Revealing information in auctions: the allocation effect

When there are two bidders, releasing independent information in an English auction with private values makes the seller worse off. However, this is no longer true with more bidders: when there is enough competition, revelation benefits the auctioneer. In three examples the dividing case is shown to be three bidders. This allocation effect applies to other standard auctions and parallels the bundling decision in a multi-unit auction. I would like to thank Jeremy Bulow, Willie Fuchs, Paul Klemperer, Rob McMillan, Phil Reny, Jeff Zwiebel and especially Andy Skrzypacz. I also grateful to two referees and an Associate Editor for a number of helpful comments.     

Collusion in one-shot second-price auctions

Summary. Most of the literature on collusive behavior in auctions ignores two important issues that make collusion difficult to sustain at least in one-shot interactions: the detection of cheating and the verification of bids. Colluding bidders may deceive each other by using shill bidders. Also, if the identities of the bidders and their bids are not published then it would be difficult to verify the bid of a colluding bidder. This paper addresses these problems in one shot second price auctions where one bidder offers another bidder a side payment in exchange for not participating in the auction, while the number of other bidders is stochastic. In spite of the barriers to collusion mentioned above, a simple side payment mechanism which depends only on the auction price is introduced. It induces a successful collusion, eliminates the verification problem, provides no incentive for the use of shill bidders and guarantees that the proponent obtains ex-post non-negative payoff. The colluding bidders are ex-ante strictly better off compared with the competitive case, irrespective of their types.Received: 27 November 2002, Revised: 28 January 2005, JEL Classification Numbers: C72, D44, D82.Yair Tauman: Correspondence toWe would like to thank an anonymous referee for very valuable comments and suggestions that significantly improved the paper. We thank Shmuel Zamir for a helpful discussion.     

The law of small numbers: investigating the benefits of restricted auctions for public procurement

A commonly accepted view in the academic literature is that dispensing with competition may only be beneficial when tendering complex contracts. However, restricted auctions are frequently used among EU member states to procure small contracts. In this article, we investigate this paradox. Using an original data set of 180 contracts used by a local public buyer of social housing between 2006 and 2009, we show that limiting competition may enable economies to be made on transaction costs while the most efficient bidders still come forward, and that abuses such as corruption or favouritism do not result. To our knowledge, this article is the first to shed light on the advantages of using restricted auctions when tendering small simple contracts.     

A short proof of the Bulow-Klemperer auctions vs. negotiations result

Summary. Bulow and Klemperer [1] have provided an upper bound on the value of bargaining power for a seller of an indivisible object. Specifically, negotiating optimally with N buyers yields lower revenue than an English auction with N + 1 buyers. In this paper, a short and intuitive proof of this result is presented.Received: 2 August 2004, Revised: 6 December 2004, JEL Classification Numbers: C78, D44, D82.I would like to thank Per B. Overgaard and an anonymous referee for many valuable comments.     

Ratifiability of efficient collusive mechanisms in second-price auctions with participation costs

We investigate whether efficient collusive bidding mechanisms are affected by potential information leakage from bidders' decisions to participate in them within the independent private values setting. We apply the concept of ratifiability introduced by Cramton and Palfrey [Cramton, P.C., Palfrey, T.R., 1995, Ratifiable mechanisms: Learning from disagreement, Games Econ. Behav. 10 (2), 255–283] and show that when the seller uses a second-price auction with participation costs, the standard efficient cartel mechanisms such as pre-auction knockouts analyzed in the literature will not be ratified by cartel members. A high-value bidder benefits from vetoing the cartel mechanism since doing so sends a credible signal that she has high value, which in turn discourages other bidders from participating in the seller's auction.     

Mental processes and strategic equilibration: An fMRI study of selling strategies in second price auctions

This study is the first to attempt to isolate a relationship between cognitive activity and equilibration to a Nash Equilibrium. Subjects, while undergoing fMRI scans of brain activity, participated in second price auctions against a single competitor following predetermined strategy that was unknown to the subject. For this auction there is a unique strategy that will maximize the subjects’ earnings, which is also a Nash equilibrium of the associated game theoretic model of the auction. As is the case with all games, the bidding strategies of subjects participating in second price auctions most often do not reflect the equilibrium bidding strategy at first but with experience, typically exhibit a process of equilibration, or convergence toward the equilibrium. This research is focused on the process of convergence.In the data reported here subjects participated in sixteen auctions, after which all subjects were told the strategy that will maximize their revenues, the theoretical equilibrium. Following that announcement, sixteen more auctions were performed. The question posed by the research concerns the mental activity that might accompany equilibration as it is observed in the bidding behavior. Does brain activation differ between being equilibrated and non-equilibrated in the sense of a bidding strategy? If so, are their differences in the location of activation during and after equilibration? We found significant activation in the frontal pole especially in Brodmann’s area 10, the anterior cingulate cortex, the amygdala and the basal forebrain. There was significantly more activation in the basal forebrain and the anterior cingulate cortex during the first sixteen auctions than in the second sixteen. The activity in the amygdala shifted from the right side to the left after the solution was given.     

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.     

Green auctions: A biodiversity study of mechanism design with externalities

This paper uses a mechanism design approach to study the biodiversity improvement in a territory, where the government is the principal and the landholders are the agents. In particular, I analyze an optimal mechanism that considers multidimensional bid which includes both the biodiversity improvement of the project and its cost. Additionally, this mechanism incorporates the externality (either positive or negative) that a biodiversity project causes in the surrounding agents who decided not to participate. Specifically, I assume that externalities enter in the cost function of the nonparticipating landholders. I show that, in the case of negative externalities, the government will implement a transfer function which is decreasing in the landholder's efficiency level. On the other hand, in the case of a positive externality, paradoxically the government may be interested in the nonparticipation of the most efficient landholders.     

Mechanism Design with Interdependent Valuations: Surplus Extraction

If valuations are interdependent and agents observe their own allocation payoffs, then two-stage revelation mechanisms expand the set of implementable decision functions. In a two-stage revelation mechanism agents report twice. In the first stage - before the allocation is decided - they report their private signals. In the second stage - after the allocation has been made, but before final transfers are decided - they report their payoffs from the allocation. Conditions are provided under which an uninformed seller can extract (or virtually extract) the full surplus from a sale to privately informed buyers, in spite of the buyers’ signals being independent random variables. This research was started when I was visiting the Department of Applied Mathematics of the University of Venice, and continued while visiting the European University Institute in Florence. Their financial support is gratefully acknowledged.     

Information acquisition in auctions: Sealed bids vs. open bids

This paper studies the incentives of a bidder to acquire information in an auction when her information acquisition decision is observed by the other bidders before bidding. Our results show that the sealed bid (second price) auction may induce more information acquisition about a common component of the value than the open (English) auction but less about the private component of the value. Moreover, we show that more information about the private value and less information about the common value may improve efficiency and revenue. Consequently, our results suggest new arguments in favor of the open auction.     

Regret in auctions: theory and evidence

The sealed-bid first-price auction of a single object in the case of independent privately-known values is the simplest auction setting and understanding it is important for understanding more complex mechanisms. But bidders bid above the risk-neutral Nash equilibrium theory prediction. The reasons for this “over bidding” remain an unsolved puzzle. Several explanations have been offered, including risk aversion, social comparisons, and learning. We present a new explanation based on regret and a model that explains not only the observed over bidding in sealed-bid first-price auctions, but also behavior in several other settings that is inconsistent with risk aversion. The authors gratefully acknowledge support from the National Science Foundation.     

Finding and retaining the dominant strategy: The second-price, English and ‘sealed offer’ English auctions

Using experiments in a procurement setting, this study examined the performance abilities of three auctions: the second-price, English, and a new ‘sealed offer’ English. Additionally, to see if dominant strategy learning would be transferred, after fifteen periods with one of the three auctions, all subjects completed a second 15 periods with the second-price auction. The English auction performed best overall. However, only limited learning was found to occur, with some subjects that had adopted the dominant strategy in the English switching in the second-price. Lessons from the new mechanism transferred better, but initial learning of the dominant strategy was slower.     

Sequencing strategies in large, competitive, ascending price automobile auctions: An experimental examination

This paper reports on a large-scale field experiment testing strategies available to a seller participating in simultaneous competitive sequential ascending price automobile auctions. Every other week, the seller offered approximately 100 vehicles for sale in an auction environment in which several competing sellers offered on the order of 3000 vehicles. The experiment tested various sequences in which the seller could offer the vehicles, such as high values first or low values first. Surprisingly, and contrary to intuition drawn from the theory of single item and single seller auctions, the worst performing sequence from those tested is for the seller to order vehicles from highest to lowest values. The best sequence is to group the vehicles by type and offer the low valued vehicles first and then move to offer the higher valued vehicles.     

Auctions with costly information acquisition

We characterize optimal selling mechanisms in auction environments where bidders must incur a cost to learn their valuations. These mechanisms specify for each period, as a function of the bids in previous periods, which new potential buyers should be asked to bid. In addition, these mechanisms must induce the bidders to acquire information about their valuations and to reveal this information truthfully. Using a generalized Groves principle, we prove a very general “full extraction of the surplus” result: the seller can obtain the same profit as if he had full control over the bidders’ acquisition of information and could have observed directly their valuations once they are informed. We also present appealing implementations of the optimal mechanism in special cases. For helpful comments we thank George Deltas, David Martimort, an anonymous referee, and seminar participants in Mannheim, Rutgers, Tel Aviv, Toulouse, the Society for Economic Design 2002 conference in New York, and the 2003 North American Summer Meetings of the Econometric Society in Evanston, IL. Yossi Spiegel thanks the IIBR for financial assistance and Charles Zheng thanks the NSF for grant SES-0214471.     

Dissolving a partnership (un)fairly

Summary. In an incomplete information, common values setting with risk-neutral agents, we consider mechanisms for allocating the assets of a dissolving partnership where the mechanism designer has no information about the distribution of signals of the agents. We find that the divide and choose mechanism systematically favors the chooser and hence fails on the grounds of fairness. We also examine the fairness properties of the winning and losing bid auctions and show that they systematically favor winning (resp. losing) bidder in ex post allocation of surplus. Finally, we show that a binding arbitration mechanism implements fair allocations.Received: 17 May 2002, Revised: 5 June 2003, JEL Classification Numbers: D39, D44I thank an anonymous referee for extremely helpful suggestions. I also gratefully acknowledge the support of the National Science Foundation and the Hoover Institution.