1 
Author  Brammert Ottens  Title  Comparing Winner Determination Algorithms for Mixed MultiUnit Combinatorial Auctions 
Year  2007 
Faculty  Faculty of Science 
Institute/dept.  FNWI/FGw: Institute for Logic, Language and Computation (ILLC) 
Series  ILLC Master of Logic Theses / ILLC ; MoL200717 
Abstract  Comparing Winner Determination Algorithms for Mixed MultiUnit Combinatorial Auctions Brammert Ottens
Abstract: In this thesis three different approaches to the Winner Determination Problem (WDP) for Mixed MultiUnit Combinatorial Auctions (MMUCA) are explored. The first, due to [Cerquides et al., 2007] is based on a traditional integer programming approach. The second, due to [Uckelman and Endriss, 2007] is based on constraint programing and the third is based on a division of the original problem in two subproblems. These two subproblems are the problem of finding an allocation that produces enough goods, and the problem of finding a sequence of the transformations in this allocation. It is shown that both problems are NPcomplete. However, in the case of an acyclic goods graph the problem of finding a sequence becomes trivial. This is also the case when any cycles present limit themselves to just one good, i.e. the good occurs both in the input and in the output of a transformations. All three algorithms are tested using two different datasets. The first is created using the generator described in [Vinyals et al., 2007] and discerns three different types of transformations, input, output and inputoutput transformations. The second is created using a generator that discerns four different types of transformations, namely input, output, structured and unstructured transformations. In terms of performance the results are not conclusive. Although the constraint programming approach does not perform very well, the performance of both the integer programming approach and the division approach vary. In several situations the latter is better and in other situations the former is better. Furthermore, the influence of the number of transformations on the complexity of the auction varies for the different datasets. However, the results do show that structured auctions are easier to solve than unstructured and hybrid auctions and that the division approach performs much better on structured auctions. 
Document type  Preprint 
Download  
Document finder 

Use this url to link to this page: http://dare.uva.nl/en/record/419938
Contact us about this recordNotify a colleague
Add to bookbag
