Combinatorial auctions

Vol. 589 M. Schwind, Dynamic Pricing and Automated Resource Allocation for Information Services Reinforcement Learning and Combinatorial Auctions. XII, 293 pages, 2007. 

ShefB, Y. Combinatorial Auctions in the Procurement of Transportation Services. Interfaces, 34(4) 245-252, 2004. 

Single-item auctioning is simple yet commonly used to offer one task at a time [10]. Combinatorial auctioning, on the other hand, is more complex in that multiple tasks are offered and participants can bid on any combination of these tasks. Since the number of combinations to be considered increases exponentially, auction administration, such as bid valuation, communication, and auction clearing, would soon become intractable [5]. Therefore, sequential single-item auctimi is a practicable approach when tasks are dynamically released, and is adopted in this chapter. 

We return to UCE prices in Section 5.1, in the context of an ascending-price combinatorial auction in which agents are interested in bundles of items. The primal-dual analysis is performed with respect to the hierarchy of extended LP formulations described in Section 2.3. 

Multi-Item Auctions. In this subsection we introduce multi-item auctions for multiple heterogenous items. This is the well known combinatorial auction problem, in which we allow bidders to have arbitrary valuations over bundles of items. 

Reverse auction. Combinatorial auctions are also proposed for procurement problems in markets with one buyer and multiple sellers. The reverse combinatorial auction is formulated as a set covering problem rather than a set packing problem. An interesting (and complicating) issue that arises in this setting is that there are various business rules that are used to constrain the choice of winners. These business rules appear as side constraints in the winner determination problem. The winner determination problem with no side constraints can be written as ... 

The communication complexity of a mechanism considers the size of messages that must be sent between agents and the mechanism to implement the outcome of a mechanism. To motivate this problem, recall that mechanism design often makes an appeal to the revelation-principle and considers direct mechanisms. However, direct mechanisms require agents to report complete and exact information about their type, which is often unreasonable in problems such as combinatorial auctions. In the worst-case the VCG mechanism for a combinatorial auction requires each agent to submit 2 numbers, given M items, to report its complete valuation function. 

One approach is to characterize restrictions on the type space in which the implementation problem is tractable. For example, the winner-determination problem in the VCG mechanism for a combinatorial auction can be solved in polynomial time with particular assumptions about the structure of agent valuations [89, 35]. A number of fast algorithms have also been developed to solve the winner-determination problem in combinatorial auctions, even though the problem remains theoretically intractable [93, 42, 2]. Recent experimental work illustrates the effectiveness of embedding the structure of agent valuations within mixed-integer programming formulations of the winner-determination problem [19]. 

A number of interesting tractable and strategyproof mechanisms have been suggested for problems in which the VCG mechanism is intractable. For example, Lehmann et al. [60] propose a truthful and feasible mechanism for a combinatorial auction problem with single-minded bidders, each with value... 

Given these objections to one-shot combinatorial auctions there has been considerable interest in the design of iterative combinatorial auctions, which can reduce the valuation work required by agents because optimal strategies must only be computed along the equilibrium path of the auction. 

For example, the DOS auction [36] solves the unit-demand (or assignment) problem, in which each agent wants at most one item. Another special case of a combinatorial auction for multiple identical items and decreasing marginal valuations is solved with Ausubel s auction [5] (see Section 5.2.2). 

Many iterative combinatorial auctions, including the DGS auction [36] and the /Bundle and /BEA auctions can be interpreted within the primal-dual design methodology described in Section 2.4. The following three steps are important in extending the primal-dual framework described in Section 2.4 to the combinatorial allocation problem ... 

In a multi-unit auction there is a set of K indivisible and homogeneous items, and agents have valuations, Vi m), for m > 0 units of the item. This is a special-case of the combinatorial auction problem, in which the items are identical. Useful auction designs for this problem do not simply introduce an identifier for each item and use combinatorial auctions. Rather, a useful auction allows agents to submit bids and receive price feedback expressed in terms of the quantity of units of the item. 

Davenport et al [32] have studied the use of reverse multi-unit auctions with volume discounts in a procurement setting. Winner determination formulations are provided in Section 3.2.2, where we also discuss the introduction of business rules as side constraints, which is an important consideration in practical electronic markets. A combinatorial auction is used for single units (lot) of multiple items, with all-or-nothing bids are allowed and nonlinear prices are used to feedback information. Volume discount auctions are also used, when multiple units of multiple items are being procured and for the restricted case of bids that are separable across items. Another consideration in procurement auctions is that the outcome should be such that the final prices should be profitable for both the buyer and the suppliers, i.e. a win-win outcome. The competitive equilibrium property can be used to operationalize this notion of achieving a win-win outcome [32]. 

Indeed, a limited combinatorial auction, in which operators can submit a restricted number of bids, has operated for the competitive tendering of London bus routes since 1997 [23]. 

Aaron Archer, Christos Papadimitriou, Kunal Talwar, and Eva Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agents. InProc. 14 th ACM Symposium on Discrete Algorithms, 2003. 

Y Bartal, R Gonen, and N Nisan. Incentive compatible multi unit combinatorial auctions. Technical report. The Hebrew University of Jerusalem, 2003. 

Craig Boutilier. Solving concisely expressed combinatorial auction problems. In Proc. 18th National Conference on Artificial Intelligence (AAAI-02), My 2002. 

Craig Boutilier and Holger Hoos. Bidding languages for combinatorial auctions. InProc. 17 th InternationalJoint Conference on Artificial Intelligence (IJCAI-01), 2001. 

Wolfram Conen and Tuomas Sandholm. Preference elicitation in combinatorial auctions. In Proc. 3rd ACM Conf on Electronic Commerce (EC-01), pages 256-259. ACM Press, New York, 2001. 

Sven de Vries and Rakesh V Vohra. Combinatorial auctions A survey. Informs Journal on Computing, 2002. Forthcoming. 

Wedad Elmaghraby and Pinar Keskinocak. Combinatorial auctions in procurement. Technical report. National University of Singapore, 2002. 

Yuzo Fujishima, Kevin Leyton-Brown, and Yoav Shoham. Taming the computational complexity of combinatorial auctions Optimal and approximate approaches. In Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI-99), pages 548-553, 1999. 

R Holzman, N Kfir-Dahav, D Monderer, and M Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior, 2001. 

B Hudson and T Sandholm. Effectiveness of preference elicitation in combinatorial auctions. In Proc. Agent-Mediated Electronic Commerce (AMEC TV) workshop at AAMAS 02, 2002. 

Daniel Lehmann, Liadan Ita O Callaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM, 49(5) 577-602, September 2002. 

NoamNisan. Bidding and allocation in combinatorial auctions. nProc. 2nd ACM Conf on Electronic Commerce (EC-00), pages 1-12, 2000. 

David C Parkes. Iterative Combinatorial Auctions Achieving Economic and Computational Efficiency. PhD thesis. Department of Computer and Information Science, University of Pennsylvania, May 2001. http //www.cis.upenn.edurdparkes/diss.html. 

David C. Parkes. Price-based information certificates for minimal-revelation combinatorial auctions. In Agent Mediated Electronic Commerce IV Designing Mechanisms and Systems, volume 2531 of Lecture Notes in Artificial Intelligence, pages 103-122. 2002. 

Michael H Rothkopf, Aleksandar Pekec, and Ronald M Harstad. Computationally manageable combinatorial auctions. Management Science, 44(8).T 131-1147, 1998. 

Tuomas W Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. CABOB A fast optimal algorithm for combinatorial auctions. In Proc. 17th Int. Joint Conf. on Artificial Intelligence, 2001. 

---