Combinatorial auction problem

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. 

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

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. 

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

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

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

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

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

---