Skip to main content

CADIA: Combinatorial auction winner determination using item association

Resource type
Thesis type
(Dissertation) Ph.D.
Date created
2005
Authors/Contributors
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.
Document
Copyright statement
Copyright is held by the author.
Permissions
The author has not granted permission for the file to be printed nor for the text to be copied and pasted. If you would like a printable copy of this thesis, please contact summit-permissions@sfu.ca.
Scholarly level
Language
English
Download file Size
etd2009.pdf 2.38 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0