Hypertree decompositions for optimal winner determination in combinatorial auctions

Abstract

A combinatorial auction is an auction in which various items are sold and a bid can be placed for more than one item at once. The winner determination problem for a combinatorial auction is the task of determining a set of mutually disjoint bids that brings the maximal revenue from the auction. This problem is known to be NP-complete.<br />To cope with the NP-completeness of the winner determination problem for general combinatorial auctions, there were attempts to identify the most general classes of combinatorial auction instances on which the problem is feasible in polynomial time. One of these attempts resulted in a polynomial time algorithm for combinatorial auction instances with associated dual hypergraphs having the hypertree width bounded by some natural number.<br />In this thesis we describe the essential concepts involved in solving the winner determination problem by means of the ComputeSetPackingK algorithm, which is a polynomial time algorithm that utilizes the notion of hypertree decomposition. We implemented the algorithm, and the description of our implementation is given in the thesis. The experimental evaluation of our implementation showed how the essential parameters of the combinatorial auctions (distributions used for generating problem instances, numbers of items and bids) and of the decomposition method (the width and the size of the constructed hypertree) influence the performance of the algorithm. The results and analysis of our experimental tests, as well as a comparison of ComputeSetPackingK with the other approaches for different distributions with respect to their hardness to be solved, are also presented within the thesis.<br />