Risk management for combinatorial auctions
Loading...
Files
Full Text E-thesis
Date
2005-07-31
Authors
Holland, Alan
Journal Title
Journal ISSN
Volume Title
Publisher
University College Cork
Published Version
Abstract
Auction theory has traditionally regarded bids in auctions as enforceable commitments. We relax this important, yet often incorrect, assumption that is common to almost all prior literature on the subject. This work addresses the possibility of winning bids being withdrawn, or reneged upon, before a transaction is completed successfully. In particular, we examine the significance of winning-bid withdrawal in a combinatorial auction setting. We find that it may be difficult or even impossible for the bid-taker to find a repair solution of adequate revenue without causing undue disturbance to the remaining winning bids in the allocation. We have called this the bid-taker's exposure problem and we also show that it is exacerbated for a risk averse bid-taker. It is preferable for the bid-taker to pre-empt uncertainty by choosing a solution that is robust to bid-withdrawal and provides a guarantee that possible with-drawls may be repaired easily with a bounded loss in revenue. We discuss the computational difficulties posed by risk management and investigate a constraint programming approach to tackling the problem. We also analyze the drawbacks of this approach and motivate useful extensions to the framework. We then propose a new framework that facilitates solution robustness for constraint programs in a wide range of settings. We briefly demonstrate its versatility with an application to job-shop scheduling. We then apply this new framework to combinatorial auctions in order to investigate the trade-off between robustness and revenue. We also introduce a new auction model that improves solution reparability by facilitating backtracking on winning bids by the bid-taker. We demonstrate experimentally that fewer winning bids partake in robust solutions, thereby reducing any associated overhead in dealing with extra bidders. Finally, we consider the case in which the bid-taker wishes to optimize some social objective, thereby necessitating truthful bidding. We have provided some impossibility results pertaining to truthful mechanism design that incorporate robust solutions. However, we also propose a means of circumventing this problem for restricted class of combinatorial auctions. We develop an approximate allocation algorithm that incentivizes truthful bidding whilst attaining an allocation that minimizes the risk of revenue loss in the event of a winning bid being withdrawn.
Description
Keywords
Combinatorial auctions , Risk management , Auction theory
Citation
Holland, A. 2005. Risk management for combinatorial auctions. PhD Thesis, University College Cork.