A Kernel-Based Iterative Combinatorial AuctionS´ebastien LahaieYahoo! ResearchNew York, NY [email protected] paper describes an iterative combinatorial auction forsingle-minded bidders that offers modularity in the choice ofprice structure, drawing on ideas from kernel methods and theprimal-dual paradigm of auction design. In our implementa-tion, the auction is able to automatically detect, as the roundsprogress, whether price expressiveness must be increased toclear the market. The auction also features a configurable stepsize which can be tuned to trade-off between monotonicity inprices and the number of bidding rounds, with no impact onefficiency. An empirical evaluation against a state of the artascending-price auction demonstrates the performance gainsthat can be obtained in efficiency, revenue, and rounds to con-vergence through various configurations of our design.IntroductionCombinatorial auctions have become a canonical mecha-nism for resource allocation in the presence of non-additivevalues. In these kinds of auctions, agents place bids on pack-ages to express complementarities between resources; appli-cation areas include task assignment, distributed scheduling,spectrum allocation and supply chain management, amongmany others (Cramton et al. 2006). Iterative auctions, whichproceed over rounds, are particularly attractive in many do-mains because they incorporate preference elicitation intothe auction procedure—at each round, agents only need toevaluate the parts of their preferences relevant to biddingagainst the current prices (Parkes and Ungar 2000). In lightof this motivation, the choice of price structure (e.g., linear)is a central element of an iterative auction design because itimpacts the complexity of bidding.In this work we describe an iterative combinatorial auc-tion that achieves modularity in price structure. Our auctionapplies to the class of single-minded bidders, which is thesimplest valuation class exhibiting complementarity. We de-velop our auction by relying on the primal-dual paradigm ofauction design introduced by de Vries et al. (2007). Underthis paradigm, one formulates the efficient allocation prob-lem as an appropriate linear program, and then examines themechanics of the primal-dual algorithm on this formulation.It turns out that the steps of the algorithm have natural inter-pretations as auction mechanics: bidding, allocation, priceCopyrightc 2011, Association for the Advancement of ArtificialIntelligence (www.aaai.org). All rights reserved.update, and termination. However, each application of theparadigm requires a domain-specific formulation of the al-location problem and therefore a separate implementation.To develop a modular implementation of the paradigm wederive a formulation of the allocation problem that is in asense parametrized by the price structure. We achieve thisby drawing on techniques from kernel methods, building onthe work of Lahaie (2009), who introduced the idea of us-ing kernel representations for prices in market settings. Bysubstituting in the appropriate kernel, a practitioner can tai-lor our auction implementation to the application at hand:there is a kernel for uniform prices, as in the auction ofAusubel (2004); a kernel for linear prices, as in the auctionof Demange et al. (1986); and a kernel for bundle prices, asin the auction of de Vries et al. (2007) among others.Besides the standard price structures just mentioned, ourframework can accommodate much more exotic structuresthan have been considered so far—for instance, we can drawon the huge variety of kernels that already exist in the ma-chine learning literature. We identify the property that musthold for a kernel to work within our auction, and explainhow a generic kernel can be adapted so that it is satisfied.In our implementation we use the polynomial kernel, whichleads to prices that are fixed-degree polynomials, interpolat-ing between linear and bundle prices. We show how to detectwhen the degree is too low to clear the auction and thereforeupdate it when needed. This strategy can in fact be appliedwith any family of kernels of increasing complexity.Our auction is neither purely ascending nor descending;the price trajectory on any bundle can oscillate. While as-cending prices are sometimes considered easier for biddersto cope with, flexibility in the price trajectory allows oneto decrease the number of rounds to convergence withoutimpacting efficiency. We evaluate our auction implementa-tion against iBundle (Parkes and Ungar 2000), a state ofthe art ascending-price combinatorial auction, and find thatit compares favorably along several metrics including ef-ficiency, revenue, and number of rounds. In the process,we also discover that the problem instances generated byCATS (Leyton-Brown et al. 2000), a standard test suite forevaluating combinatorial auctions, can be cleared to veryhigh levels of efficiency using no more than quadratic prices.We note that we do not address incentives in this work—ourfocus is on the computational aspects of auction design.Proceedings of the Twenty-Fifth AAAI Conference on Artificial IntelligenceProceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence695ModelThere is a set of buyers N = {1,...,n} and m distinctindivisible items held by a single seller. A bundle is a sub-set of the items. We associate each bundle with its indicatorvector, and denote the set of bundles by X = {0, 1}m. Thebundle containing all items is denoted by 1, while the emptybundle is denoted by 0, though for clarity we will often alsouse ∅ for the latter. We write x ≤ xto denote that bun-dle x is contained in bundle x(the inequality is understoodcomponent-wise).Buyer i has a valuation function vi: X → R+denotinghow much it is willing to pay for each bundle. In this work,we assume that each buyer is single-minded, meaning thatits valuation is characterized by a bundle-value pair (xi,vi)as follows:vi(x)=viif x ≥ xi0 otherwise(We are using viin two different roles here with a slightabuse of notation.) We require that xi= ∅; therefore eachvaluation is normalized, with vi(∅)=0. In words, buyer iwould like to acquire all the items in bundle xi, but is notinterested in any others. We assume that the seller does notderive any value from retaining any bundle of items.An allocation is a vector of n bundles indicating whateach buyer receives. Since buyer i is only interested in