Multi-unit combinatorial auction

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

We have formulated CAPl under the assumption that there is at most one copy of each object. It is easy to extend the formulation to the case when there are multiple copies of the same object and bidders may want more than one copy of the same object. Such extensions, called multi-unit combinatorial auctions, are investigated by Leyton-Brown et al. [47] as well as by Gonen and Lehmann [34]. 

In fact, one must specify not only lanes but volume as well, so this problem constitutes an instance of a multi-unit combinatorial auction. 

Ricca Gonen and Daniel Lehmann. Optimal solutions for multi-unit combinatorial auctions Branch-and-bound heuristics. In Conference on Electronic Commerce (EC-00), Minneapolis, MN., pages 13-20, 2000. 

Kevin Leyton-Brown, Yoav Shoham, and Moshe Tennenholtz. An algorithm for multi-unit combinatorial auctions. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, Austin, TX, pages 56-61, 2000. 

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]. 

It is important to note that a growing area of multi-unit auction literature that has been left out of the discussion below is the design and use of combinatorial auctions. These auctions, where bidders can submit package or combinational bids, are often desirable when bidders realize synergies across objects in a multi-object auction. While extremely useful in helping to capture synergies, combinatorial auctions can be quite difficult to solve for the allocation that maximizes the seller s revenue (known as the winner determination problem). 

---