Winner determination problem

Indivisible Bids. Now, suppose that bidders specify all-or-nothing constraints on the bids and state that the bids are indivisible. In addition, suppose that the bidders also submit multiple bids with an XOR bidding language. Let Mi denote the number of bids from supplier i, and N denote the number of suppliers. The winner determination problem can be formulated as a knapsack problem, introducing xij 0,1 to indicate that bid j from bidder i is... 

Forward auction. For the forward auction case of a single seller with multiple buyers, the winner-determination problem can be written as ... 

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 interesting aspect of these side constraints is how they impact the computational complexity of the winner determination problem. For example, introducing either of the following constraint classes will transform even a tractable problem (e.g. with a totally unimodular structure) into a hard problem ... 

Homogeneous Bids. First, we consider the case of bids and asks for multiple units of the same item, but without allowing bundle bids. Moreover, we assume that multiple bids and asks submitted by the same bidder are connected with additive-or logic. For the moment we also assume that bids and asks are divisible, so that a fraction of a bid can be matched with an ask (or multiple fractions with multiple asks). We provide a general formulation of the winner determination problem in this setting. The formulation captures different market structures, in terms of aggregation and differentiation. 

However, if the bids are indivisible we just define the decision variable, Xij e 0,1, as a binary variable that takes a value 1 if bid bi is assigned to ask aj and zero otherwise and replace equation (5.14) with Xij G 0,1. Still, if we now restrict the exchange so as not to allow any aggregation then the winner-determination problem is an assignment problem which can be solved very efficiently in polynomial time [1]. Consider a bipartite graph with asks on one side (the asks are differentiated by price and seller) and the bids on the other. The constraint (5.12) can be replaced with ... 

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

Martin Bichler and Jayant Kalagnanam. Winner determination problems in multi-attribute auctions. Technical report, IBM Research report, 2002. 

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

The designer thus faces a tradeoff. Restricting the bids could make the underlying winner determination problem easy. However, by restricting the bids one limits the preferences that can be expressed by bidders. This will produce allocations that are economically inefficient. 

The resulting winner determination problem was a set-partitioning problem. Cost was not the only criterion. Carrier-reliability, load balancing and incumbency concerns mattered to THD. These nonmonetary preferences were not revealed to the bidders. 

The winner determination for supply curve auctions can also be written as a set covering problem as shown Eq. (5.11) using a Dantzig-Wolfe type decomposition [39]. To use a set covering model we introduce the concept of supply... 

If we had a parallel computer which could determine all the winners (3,8,6,7) of the first line simultaneously i.e. in one time step and in two more steps the winners of the second (8,7) and third (8) line, we would need in total only log2 8=3 parallel computational steps i.e. the computer time T for parallel search scales as T log2 N. This demonstrates how problems which are exponentially hard... 

---