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.     

Survival auctions

Dynamic clock auctions with drop-out information typically yield outcomes closer to equilibrium predictions than do comparable sealed-bid auctions. However, clock auctions require congregating bidders for a fixed time interval, which has limited field applicability and introduces inefficiencies of its own given the time cost of congregating bidders. In this experiment we explore the effects of removing these inefficiencies through survival auctions—a multi-round sealed-bid auction which is theoretically isomorphic to the dynamic clock auction with drop-out information. Kagel’s research was partially supported by National Science Foundation Grants No. 0136925 and 0136928. Any opinions, findings, and conclusions or recommendations in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. We thank the associate editor, an anonymous referee, seminar participants at Purdue University, especially Tim Cason, participants at International Industrial Organization April 2004 Conference, the ESA June 2003 meetings, and our discussant, Tim Salmon, for valuable comments. Kirill Chernomaz provided valuable research assistance. The usual caveat applies.     

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.     

Ascending price Vickrey auctions

We show that an ascending price auction for multiple units of a homogeneous object proposed by Ausubel (i) raises prices for packages until they reach those nonlinear and non-anonymous market clearing prices at which bidders get their marginal products and (ii) the auction is a primal–dual algorithm applied to an appropriate linear programming formulation in which the dual solution yields those same market clearing prices. We emphasize the similarities with efficient incentive compatible ascending price auctions to implement Vickrey payments when there is a single object or when objects are heterogeneous but each buyer does not desire more than one unit. A potential benefit of these common threads is that it helps to establish the principles upon which Vickrey payments may be implemented through decentralized, incentive compatible procedures.     

Sequential vs. single-round uniform-price auctions

We study sequential and single-round uniform-price auctions with affiliated values. We derive symmetric equilibrium for the auction in which k₁ objects are sold in the first round and k₂ in the second round, with and without revelation of the first-round winning bids. We demonstrate that auctioning objects in sequence generates a lowballing effect that reduces the first-round price. Total revenue is greater in a single-round, uniform auction for k=k₁+k₂ objects than in a sequential uniform auction with no bid announcement. When the first-round winning bids are announced, we also identify a positive informational effect on the second-round price. Total expected revenue in a sequential uniform auction with winning-bids announcement may be greater or smaller than in a single-round uniform auction, depending on the model's parameters.     

Auctions with Financial Externalities

We study auctions with financial externalities, i.e., auctions in which losers care about how much the winner pays. In the first-price auction, larger financial externalities result in a lower expected price; in the second-price auction, the effect is ambiguous. Although the expected price in the second-price auction may increase if financial externalities increase, the seller is not able to gain more revenue by guaranteeing the losers a fraction of the auction revenue. With a reserve price, we find that both auctions may have pooling at the reserve price. This finding suggests that identical bids need not be a signal of collusion, in contrast to what is sometimes argued in anti-trust cases. We gratefully acknowledge financial support from the Dutch National Science Foundation (NWO 510.010.501 and NWO-VICI 453.03.606). For valuable discussions and comments, we would like to thank Eric van Damme, Jacob Goeree, Thomas Kittsteiner, Marta Kolodziejczyk, seminar participants at Tilburg University, Humboldt University Berlin, and National University of Singapore, and audiences at ESEM 2001 in Lausanne, and the FEEM 2002 conference in Milan on auctions and market design. The suggestions of an anonymous referee of this Journal greatly improved the article. The usual disclaimer applies.     

Vickrey allocation rule with income effect

We consider situations in which a society tries to efficiently allocate several homogeneous and indivisible goods among agents. Each agent receives at most one unit of the good. In this paper, we establish that on domains that include nonquasi-linear preferences—preferences exhibiting income effects—an allocation rule that satisfies Pareto-efficiency, strategy-proofness, individual rationality, and nonnegative payment uniquely exists, which is the Vickrey allocation rule. H. Saitoh is a JSPS Research Fellow.     

Equilibria in second price auctions with participation costs

We investigate equilibria of sealed-bid second price auctions with bidder participation costs in the independent private values environment. We focus on equilibria in cutoff strategies (participate and bid the valuation iff it is greater than the cutoff), since if a bidder finds it optimal to participate, she cannot do better than bidding her valuation. When bidders are symmetric, concavity (strict convexity) of the cumulative distribution function from which the valuations are drawn is a sufficient condition for uniqueness (multiplicity) within this class. We also study a special case with asymmetric bidders and show that concavity/convexity plays a similar role.     

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.     

Second price auctions on general preference domains: two characterizations

Auction theory usually assumes the quasi-linearity of individual preferences. We drop this assumption and define an extension of second price mechanisms that applies to general preferences. It turns out that the extended second price mechanisms are the only rules satisfying efficiency, strategy-proofness, and a mild non-imposition property. Their definition is simple just as much as the definition of usual second price mechanisms: everyone reports his maximum willingness to pay and the bidder whose reported value is highest buys the auctioned object for the price equal to the second highest reported value. The characterization is valid if efficiency is replaced by envy-freeness. I gratefully acknowledge an associate editor and two anonymous referees for their very helpful comments. Hiroki Saitoh and Shigehiro Serizawa independently obtain a result that is closely related to my main result (see, Remark in Sect. 1). I thank them for sending me the paper and communication, and Yuji Fujinaka for informing me about their work. I also thank the financial support by KAKENHI (19310031).     

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.     

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.     

Strategic price discounting and rationing in uniform price auctions

I modify the uniform-price auction rules in allowing the seller to ration bidders. This allows me to provide a strategic foundation for underpricing when the seller has an interest in ownership dispersion. Moreover, many of the so-called “collusive-seeming” equilibria disappear.     

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.     

Combinatorial auctions with decreasing marginal utilities

In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure. While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities. No such approximation algorithm exists in a setting allowing for arbitrary complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.     

Optimal sale across venues and auctions with a buy-now option

We characterize the optimal selling mechanism for a seller who faces demand demarcated by a high and a low end and who can access an (online) auction site (by paying an access cost) in addition to using his own store that can be used as a posted price selling venue. We first solve for the optimal mechanism of a direct revelation game in which there is no venue-restriction constraint. We find that the direct optimal mechanism must necessarily incorporate a certain kind of pooling. We then show that even with the venue constraint, the seller can use a two stage indirect mechanism that implements the allocation rule from the optimal direct mechanism, and uses the venues in an optimal fashion. The first stage of the indirect mechanism is a posted price at the store. If the object is not sold, we move to stage two, which involves an auction at the auction site. A feature of this auction is a buy-now option which is essential for implementing the pooling feature of the optimal direct mechanism. We also show that the buy-now option in the optimal mechanism is of a “temporary” variety, and that a “permanent” buy-now option, in contrast, cannot implement the optimal mechanism. Auctions with a temporary buy-now option are in widespread use on eBay. We thank the Associate Editor, George Deltas, for his insightful comments. We also thank seminar participants at the University of Basel and the SAET conference 2007.     

Information aggregation in auctions with an unknown number of bidders

Information aggregation, a key concern for uniform-price, common-value auctions with many bidders, has been characterized in models where bidders know exactly how many rivals they face. A model allowing for uncertainty over the number of bidders is essential for capturing a critical condition for information to aggregate: as the numbers of winning and losing bidders grow large, information aggregates if and only if uncertainty about the fraction of winning bidders vanishes. It may be possible for the seller to impart this information by precommitting to a specified fraction of winning bidders, via a proportional selling policy. Intuitively, this could make the proportion of winners known, and thus provide all the information that bidders need to make winner's curse corrections.