Winner determination

In an auction, a set of tasks are offered by an auctioneer in the announcement phase. Broadcast with the auction announcement, each of the robots estimates the cost of a task separately and submits a bid to the auctioneer. Once all bids are received or a pre-specified deadline has passed, the auction is cleared. In the winner determination phase, the auctioneer decides with some selection criteria which robot wins which task [9]. This chapter adopts cost minimisation, in that an auctioned task is awarded to a robot offering the lowest bid price. 

The structure of the bidding language in an auction is important because it can restrict the ability of agents to express their preferences. In addition, the expressiveness allowed also has a big impact of the the properties of the auction. This has prompted research that examines bidding languages and their expressiveness and the impact on winner determination [20, 19, 13]. In this section we will outline two aspects of bidding languages that are central to auctions (i) the structure of bids allowed, and (ii) the rules specified by the bid that restrict the choice of bids by the seller. 

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

Minimum/Maximum number of winning supplier requirements introduce integral counts (for those suppliers who have winning bids versus those who do not) and lead to a set-cover type of constraint that make winner determination NP-hard. 

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

The computational aspects of market clearing depends on the market structure [54]. The aspects of market structure that have an impact on winner determination are as follows ... 

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

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

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

Tuomas W Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. Winner determination in combinatorial auction generalizations. In Proc. International Conference on Autonomous Agents, Workshop on Agent-based Approaches to B2B, pages 35-41, 2001. 

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 formulation for winner determination just given is not flexible enough to encompass some of the variations that have been considered in the literature. For example technical constraints may prevent certain combinations of assets being awarded. Also, the auctioneer may impose side constraints that limit amounts that any one bidder can obtain. For a more comprehensive formulation we refer the reader to de Vries and Vohra [26]. 

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. 

Tuomas W. Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1-2) 1-54, 2002. 

---