BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Valuation Compressions in Combinatorial Auctions - Paul Dütting (
 EPFL)
DTSTART:20120618T140000Z
DTEND:20120618T150000Z
UID:TALK38226@talks.cam.ac.uk
CONTACT:Felix Fischer
DESCRIPTION:We study welfare losses in combinatorial auctions that result 
 from restricting the bidding space to a subspace of the valuation space. W
 e present a general technique to establish lower and upper bounds on the P
 rice of Anarchy for valuation compressions of this kind. Bounds obtained t
 hrough this technique automatically extend to a large class of game-theore
 tic solution concepts. We use this technique to prove lower and upper boun
 ds on the Price of Anarchy for valuations and bids ranging from subbaditiv
 e 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 ob
 tained through repeated play and regret minimization in polynomial time.\n
 \nAbout the speaker: \nPaul is a PhD student at EPFL. He received his Mast
 er's degree (German Diplom) "with distinction" in Computer Science from Ka
 rlsruhe 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 Nat
 ional Academic Foundation and an alumnus of the German National Academic F
 oundation. He has been awarded a Best Paper Award at EC'12 and a Best Post
 er Award at WWW'10. 
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR