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.     

Simultaneous use of auctions and posted prices

I consider a model in which several identical objects are sold simultaneously via an auction and a posted price mechanism. The model explains several empirical regularities regarding bidding behavior in eBay auctions such as the finding that some bidders bid multiple times over the course of the auction, and that bidders tend to bid with greater frequency near the end of the auction than the beginning. I also show that sellers prefer to simultaneously use auctions and posted prices than to use either mechanism individually.     

Information revelation in auctions

Auction theory has emphasized the importance of private information to the profits of bidders. However, the theory has failed to consider to what extent initially private information will remain private. We show that in a variety of contexts bidders will reveal their information, even if this information revelation is (ex ante) detrimental to them. Similarly, a seller may reveal her information although this revelation lowers revenues. We also show that bidders may be harmed by private information, even in contexts where more information has traditionally been presumed to be beneficial.     

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.     

Auctions for social lending: A theoretical analysis

Prosper, today the second largest social lending marketplace with nearly 1.5 million members and $380 million in funded loans, employed an auction mechanism amongst lenders to finance each borrower's loan until 2010. Given that a basic premise of social lending is cheap loans for borrowers, how does the Prosper auction do in terms of the borrower's payment, when lenders are strategic agents with private true interest rates? We first analyze the Prosper auction as a game of complete information and fully characterize its Nash equilibria, and show that the uniform-price Prosper mechanism, while simple, can lead to much larger payments for the borrower than the VCG mechanism. We next compare the Prosper mechanism against the borrower-optimal auction in an incomplete information setting, and conclude by examining the Prosper mechanism when modeled as a dynamic auction, and provide tight bounds on the price for a general class of bidding strategies.     

Nonstandard bidder behavior in real-world auctions

Empirical work on auctions has found that bidders deviate from standard behavior in important ways. We investigate a range of these behaviors, including nonrational herding, auction fever, quasi-endowment effect, and escalation of commitment. Our innovations are to more completely control for unobservables by using new data from a field experiment on eBay, and by accounting for censoring of bids below the starting price. Consistent with standard auction theory and in contrast to the predictions of the nonstandard behaviors, we find that auction starting price has no effect on bidder willingness to pay in a private-values setting. We conclude that there is little evidence that these nonstandard behaviors are important in the field.     

Bidding in private-value auctions with uncertain values

Auctions are often used to sell idiosyncratic goods difficult for potential bidders to value ex ante. Laboratory auctions with uncertainty over final values in this experiment resulted in 18% and 27% of bids above the expected value of the item in private-value first-price and English auctions, respectively. Risk-seeking preferences as measured on an individual decision task cannot explain overbidding and the first-price auction results suggest that risk aversion may not be a good explanation for bidding behavior observed with certain values. Several candidate explanations fail to explain overbidding, rather it appears to stem from some bidders who are prone to overbidding. Relative to first-price auctions, the size and frequency of overbids are significantly larger in English auctions, while more English auctions are won by overbidders. Differences between the formats appear to be driven by the dynamic nature of English auctions which is consistent with popular notions of “auction fever.”     

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.     

Equilibrium selection in common-value second-price auctions

This note considers equilibrium selection in common-value second-price auctions with two bidders. We show that for each ex post equilibrium in continuous and undominated strategies, a sequence of “almost common-value” auctions can be constructed such that each of them possesses a unique undominated and continuous equilibrium and the corresponding sequence of equilibria converges to that ex post equilibrium. As an implication, no equilibrium selection of this model based on perturbations seems to be more convincing than others.     

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.     

Private monitoring in auctions

We study infinitely repeated first-price auctions in which a bidder only learns whether or not he won the object. While repetition of the stage-game equilibrium is the unique Nash equilibrium in public strategies, with patient bidders there are simple Nash equilibria in private strategies that improve on bid rotation. Sequential rationality is appropriately captured by essentially perfect Bayesian equilibrium (EPBE), which ignores behavior after irrelevant histories. Our main result is the construction of EPBEa that improve upon bid rotation. Assuming symmetry, the exclusionary schemes of Skrzypacz and Hopenhayn [Tacit collusion in repeated auctions, J. Econ. Theory 114 (2004), 153–169], including asymptotically efficient ones, are supported as EPBEa.     

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.     

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.     

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.     

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.     

Optimal auctions with asymmetrically informed bidders

Summary. The paper analyzes a problem of optimal auction design when the seller faces asymmetrically informed bidders. Specifically, we consider a continuum of risk-neutral uninformed bidders taking part into the auction along with n risk-averse informed bidders. The contribution of the paper is threefold. First, we fully characterize the optimal auction in this non standard environment and in a very general set-up. We find that when informed bidders reveal “bad news” about the value of the good, the seller optimally awards the object to the uninformed bidders. Secondly, we show that the seller is better off in presence of uninformed bidders because this allows to lower the informational rents paid to the informed bidders. Last, we find that, with bi-lateral risk neutrality, the seller always awards the good to the uninformed bidders thereby keeping all the surplus.Received: 22 October 2004, Revised: 21 April 2005, JEL Classification Numbers: D44, D82.We are very grateful to two anonymous referees, Jacques Crémer, Patrick François, Angel Hernando-Veciana and seminar participants at the 2004 SCSE conference (Quebec, Canada) for their valuable comments. Moez Bennouri acknowledges the financial support by the Initiative of the New Economy (INE) program of SSHRC (Canada).