Abstract

We study welfare losses in combinatorial auctions that result from restricting the bidding space to a subspace of the valuation space. We present a general technique to establish lower and upper bounds on the Price of Anarchy for valuation compressions of this kind. Bounds obtained through this technique automatically extend to a large class of game-theoretic solution concepts. We use this technique to prove lower and upper bounds on the Price of Anarchy for valuations and bids ranging from subbaditive to additive. We conclude by showing that finding a pure Nash equilibrium for subadditive valuations and additive bids is NP-hard. This is in stark contrast to our bounds for coarse correlated equilibria, which can be obtained through repeated play and regret minimization in polynomial time.

About the speaker: Paul is a PhD student at EPFL . He received his Master’s degree (German Diplom) “with distinction” in Computer Science from Karlsruhe Institute of Technology (KIT) in 2008. He did part of his studies at University of Media and Arts Karlsruhe. He is a fellow of the Swiss National Academic Foundation and an alumnus of the German National Academic Foundation. He has been awarded a Best Paper Award at EC’12 and a Best Poster Award at WWW ’10.