Effects of suboptimal bidding in combinatorial auctions

Stefan Schneider, Pasha Shabalin, Martin Bichler

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Though the VCG auction assumes a central place in the mechanism design literature, there are a number of reasons for favoring iterative combinatorial auction designs. Several promising ascending auction formats have been developed throughout the past few years based on primal-dual and subgradient algorithms and linear programming theory. Prices are interpreted as a feasible dual solution and the provisional allocation is interpreted as a feasible primal solution. iBundle( 3) (Parkes and Ungar 2000), dVSV (de Vries et al. 2007) and the Ascending Proxy auction (Ausubel and Milgrom 2002) result in VCG payoffs when the coalitional value function satisfies the buyer submodularity condition and bidders bid straightforward, which is an expost Nash equilibrium in that case. iBEA and CreditDebit auctions (Mishra and Parkes 2007) do not even require the buyer submodularity condition and achieve the same properties for general valuations. In many situations, however, one cannot assume bidders to bid straightforward and it is not clear from the theory how these non-linear personalized price auctions (NLPPAs) perform in this case. Robustness of auctions with respect to different bidding behavior is therefore a critical issue for any application. We have conducted a large number of computational experiments to analyze the performance of NLPPA designs with respect to different bidding strategies and different valuation models. We compare the results of NLPPAs to those of the VCG auction and those of iterative combinatorial auctions with approximate linear prices, such as ALPS (Bichler et al. 2009) and the Combinatorial Clock auction (Porter et al. 2003). While NLPPAs performed very well in case of straightforward bidding, we could observe problems with respect to auctioneer revenue, efficiency, and speed of convergence in case of non-best-response bidding behavior. Under suboptimal bidding strategies, dVSV and CreditDebit auctions have a significantly lower efficiency than iBundle(3). In contrast, linear price combinatorial auctions were robust against all strategies, except collusive behavior which makes it very difficult for any auctioneer to select an efficient solution in general. While our results achieve high efficiency values on average, one can easily construct examples, where linear price CAs cannot be efficient (Bichler et al. 2009). Linear-price designs suffer from the fact that they cannot be 100% efficient, but they have shown to be robust against many strategies and bear a few advantages: - Only a linear number of prices needs to be communicated. - Linear prices, if perceived as a guideline, help bidders to easily find interesting items and bundles and allow for endogenous bidding (Kwon05). - The perceived fairness of anonymous prices might be an issue in some applications. - The number of auction rounds is much lower. Overall, robustness of combinatorial auction formats against different bidding strategies is, aside from efficiency, fairness, and speed of convergence, an important topic auctioneers need to care about.

Original languageEnglish
Title of host publicationAuctions, Market Mechanisms and Their Applications - First International ICST Conference, AMMA 2009, Revised Selected Papers
Number of pages2
StatePublished - 2009
Event1st Conference on Auctions, Market Mechanisms, and Their Applications, AMMA 2009 - Boston, MA, United States
Duration: 8 May 20099 May 2009

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering
Volume14 LNICST
ISSN (Print)1867-8211


Conference1st Conference on Auctions, Market Mechanisms, and Their Applications, AMMA 2009
Country/TerritoryUnited States
CityBoston, MA


Dive into the research topics of 'Effects of suboptimal bidding in combinatorial auctions'. Together they form a unique fingerprint.

Cite this