Truthful Risk-Managed Combinatorial Auctions

Alan Holland, Barry O’Sullivan

Given a winning-bid withdrawal in a combinatorial auction, finding an alternative repair solution of adequate revenue without causing undue disturbance to the remaining winning bids in the original solution may be difficult or even impossible. This "bid-takers exposure problem" may be preemptively addressed by finding a solution that is robust to winning-bid withdrawal. We introduce the concept of monotonicity-in-expectation. We provide impossibility results concerning truthful mechanisms for robust solutions with bounded social-welfare losses in which the bid-taker cannot rescind items fromwinning bidders to repair a solution. We also show that this result extends to combinatorial auctions that include a form of leveledcommitment contract. However, we present a positive result regarding truthfulness for combinatorial auctions in a restricted setting that comprises a computationally efficient allocation algorithm that seeks to maximize expected social welfare.