Abstract: Combinatorial auctions, the task of allocating items to strategic buyers with combinatorial valuations over bundles, has been a paradigmatic problem for mechanism design. The celebrated VCG mechanism solves the problem, but it is expensive in computation and communication, motivating the search for alternative mechanisms. We overview the advances of algorithmic mechanism design on this subject, and propose an online-learning approach to mechanism design, sidestepping impossibility barriers that have been identified for buyers with submodular valuations.
(Based on joint work with Vassilis Syrgkanis)