Truthfulness and stochastic dominance with monetary transfers

Martin Hoefer, Thomas Kesselheim, Berthold Vöcking

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. As our first main result, 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. As our second main result 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.
BibTeX
@article{hoefer2016truthfulness,
  author = {Martin Hoefer and Thomas Kesselheim and Berthold Vöcking},
  title = {{Truthfulness and stochastic dominance with monetary transfers}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2016},
  url = {https://openreview.net/forum?id=i81uV6mLzn},
}

Loading related content...

Figure