University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Valuation Compressions in Combinatorial Auctions

Valuation Compressions in Combinatorial Auctions

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity