An algorithm for computing the outcome of combinatorial auctions with proxy bidding

Proxy bidding has proved useful in a variety of real auction formats, such as eBay, and has been proposed for some combinatorial auctions. Previous work on proxy bidding in combinatorial auctions requires the auctioneer essentially run the auction with myopic bidders to determine the outcome. In addition to being computationally costly, this process is only as accurate as the bid increment, and decreasing the bid increment to improve accuracy greatly increases the running time. In this paper, we present an algorithm that computes the outcome of the proxy auction by examining only the events that cause the proxy bidders to change their behaviors. This algorithm is much faster than the alternative, and computes exact solutions.