Campus Event Calendar
Event Entry
What and Who
Truthfulness and Stochastic Dominance
Martin Hoefer
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 11 June 2013
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We consider truthfulness concepts for auctions with payments based on first- and second-order stochastic dominance. We assume bidders consider wealth in standard quasi-linear form as valuation minus payments. Additionally, they are sensitive to risk in the distribution of wealth stemming from randomized mechanisms. First- and second-order stochastic dominance are well-known to capture risk-sensitivity, and we apply these concepts to capture truth-telling incentives for bidders.
We provide a complete characterization of all social-choice functions over binary single-parameter domains that can be implemented by a mechanism that is truthful in first- and second-order stochastic dominance. We show that these are exactly the social-choice functions implementable by truthful-in-expectation mechanisms, and we provide a novel payment rule that guarantees stochastic dominance.
In addition, we extend the celebrated randomized meta-rounding approach for truthful-in-expectation mechanisms in packing domains. We design mechanisms that are truthful in first-order stochastic dominance by spending only a logarithmic factor in the approximation guarantee.
Contact
Martin Hoefer
--email hidden
passcode not visible
logged in users only
Martin Hoefer, 04/24/2013 16:54 -- Created document.