We introduce a framework for decentralized combinatorial auctions. We identify and formalize an underlying solution concept that we call strongness, and derive bounds on the revenue of strong auctions. We show how our framework encompasses some existing results and use it to develop a new decentralized auction for bidders with sub-additive valuations. We prove that, for bidders with downward sloping demands, the new auction outperforms the VCG mechanism in terms of revenue.
Joint work with Mahyar Salek, Microsoft Research Cambridge