Valuation Compressions in Combinatorial Auctions

Add to your list(s) Download to your calendar using vCal

• Paul Dütting (EPFL)
• Monday 18 June 2012, 15:00-16:00
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Felix Fischer.

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.

This talk is part of the Optimization and Incentives Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Economics and Computer Science Talks
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• Optimization and Incentives Seminar
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.