CADIA: Combinatorial Auction Winner Determination Using Item Association

Candidate: Chi Hong (Andy) Law
Type: Doctor of Philosophy (Ph.D), School of Interactive Arts and Technology
Date: August 4, 2005
Senior Supervisor: Marek Hatala, Associate Professor
Thesis: Download Thesis Document

Abstract

In combinatorial auctions (CAs), bidders are allowed to bid on any combination of items. Although CAs are economically efficient mechanisms for resources allocation, most auctioneers are hesitant to adopt them due to the fact that the CA winner determination process is a non-deterministic polynomial hard (NP-hard) problem. If an exhaustive search technique is used to solve the problem realistically, the number of auctioned items and bids must be small enough to be handled by the technique due to the constraints of today's computation power. Arising from the demand for CAs, this thesis presents a novel but also practical combinatorial auction winner determination approach. Such an approach has been designed and implemented into a system called CADIA.. CADIA is able to generate results with high accuracy and good performance in CAs of hundreds of items and thousands of bids. CADIA's knowledge for winner determination is discovered from a process of mining the auction data using item association. Such knowIedge is then used to identify particular bids as winners. Both potential winners and possible losers identified during the auctions are used as additional knowledge to further improve the results. Empirical evaluation shows that CADIA is more efficient than bruteforce technique based systems in terms of running time when searching for the optimal revenue. In situations where obtaining the optimal revenue becomes unrealistic to be handled by the brute-force technique, as in auctions of hundreds of items and thousands of bids, CADIA finds better approximate revenue than greedy search based systems.