Truthfulness and stochastic dominance with monetary transfers

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.

References

1. Abdulkadiroglu, A. and Sönmez, T. 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 3, 689--701.
2. Archer, A. and Tardos, É. 2001. Truthful mechanisms for one-parameter agents. In Proc. 42nd Symp. Foundations of Computer Science (FOCS). 482--491.
3. Aziz, H., Brandt, F., and Brill, M. 2013. On the tradeoff between economic efficiency and strategyproofness in randomized social choice. In Proc. 12th Conf. Autonomous Agents and Multi-Agent Systems (AAMAS). To appear.
4. Bhalgat, A., Chakraborty, T., and Khanna, S. 2012. Mechanism design with risk aversion. In Proc. 8th Intl. Workshop Internet & Network Economics (WINE). 198--211.
5. Bogomolnaia, A. and Moulin, H. 2001. A new solution to the random assignment problem. J. Econom. Theory 100, 295--328.
6. Bogomolnaia, A. and Moulin, H. 2004. Random matching unter dichotomous preferences. Econometrica 72, 257--279.
7. Chekuri, C., Khanna, S., and Shepherd, F. B. 2005. Multicommodity flow, well-linked terminals, and routing problems. In Proc. 37th Symp. Theory of Computing (STOC). 183--192.
8. Christodoulou, G., Elbassioni, K., and Fouz, M. 2010. Truthful mechanisms for exhibitions. In Proc. 6th Intl. Workshop Internet & Network Economics (WINE). 170--.
9. Dobzinski, S. and Dughmi, S. 2009. On the power of randomization in algorithmic mechanism design. In Proc. 50th Symp. Foundations of Computer Science (FOCS). 505--514.
10. Dughmi, S. 2012. Randomization and computation in strategic settings. Ph.D. thesis, Stanford University.
11. Dughmi, S. and Peres, Y. 2012. Mechanisms for risk averse agents, without loss. CoRR 1206.2957.
12. Dughmi, S., Roughgarden, T., and Yan, Q. 2011. From convex optimization to randomized mechanims: Toward optimal combinatorial auctions. In Proc. 43rd Symp. Theory of Computing (STOC). 149--158.
13. Ehlers, L., Peters, H., and Storcken, T. 2002. Strategy-proof probabilistic decision schemes for one-dimensional single-peaked preferences. J. Econom. Theory 105, 408--434.
14. Esö, P. and Futo, G. 1999. Auction design with a risk averse seller. Econom. Lett. 65, 1, 71--74.
15. Fu, H., Hartline, J., and Hoy, D. 2013. Prior-independent auctions for risk-averse agents. In Proc. 14th Conf. Electronic Commerce (EC). CoRR 1301.0401.
16. Gibbard, A. 1977. Manipulation of schemes that mix voting with chance. Econometrica 45, 3, 665--681.
17. Gopinathan, A., Li, Z., and Wu, C. 2011. Strategyproof auctions for balancing social welfare and fairness in secondary spectrum markets. In Proc. 30th IEEE Conf. Computer Communications (INFOCOM). 3020--3028.
18. Hoefer, M., Kesselheim, T., and Vöcking, B. 2011. Approximation algorithms for secondary spectrum auctions. In Proc. 23rd Symp. Parallelism in Algorithms and Architectures (SPAA). 177--186.
19. Hu, A., Matthews, S., and Zou, L. 2010. Risk aversion and optimal reserve prices in first- and second-price auctions. J. Econom. Theory 145, 3, 1188--1202.
20. Katta, A.-K. and Sethuraman, J. 2006. A solution to the random assignment problem on the full preference domain. J. Econom. Theory 131, 231--250.
21. Krysta, P. and Vöcking, B. 2012. Online mechanism design (randomized rounding on the fly). In Proc. 39th Intl. Coll. Automata, Languages and Programming (ICALP). 636--647.
22. LaviS11 Lavi, R. and Swamy, C. 2011. Truthful and near-optimal mechanism design via linear programming. J. ACM 58, 6, 25.
23. Mas-Colell, A., Whinston, M., and Green, J. 1995. Microeconomic Theory. Oxford University Press.
24. Maskin, E. and Riley, J. 1984. Optimal auctions with risk averse buyers. Econometrica 52, 6, 1473--1518.
25. Moulin, H. 1980. On strategy-proofness and single peakedness. Public Choice 35, 4, 437--455.
26. Myerson, R. 1981. Optimal auction design. Math. Oper. Res. 6, 58--73.
27. Nisan, N. 2007. Introduction to mechanism design (for computer scientists). In Algorithmic Game Theory, N. Nisan, É. Tardos, T. Roughgarden, and V. Vazirani, Eds. Cambridge University Press, Chapter 9.
28. Peters, H., Schulteis, T., and Vermeulen, D. 2010. Generalized stochastic dominance and bad outcome aversion. Social Choice and Welfare 35, 2, 285--290.
29. Sundararajan, M. and Yan, Q. 2010. Robust mechanisms for risk-averse sellers. In Proc. 11th Conf. Electronic Commerce (EC). 139--148.
30. Vöcking, B. 2012. A universally-truthful approximation scheme for multi-unit auctions. In Proc. 23rd Symp. Discrete Algorithms (SODA). 846--855.
31. Zhou, L. 1990. On a conjecture by Gale about one-sided matching problems. J. Econom. Theory 52, 123--135.
32. Zhu, Y., Li, B., and Li, Z. 2012. Truthful spectrum auction design for secondary networks. In Proc. 31st IEEE Conf. Computer Communications (INFOCOM). 873--881.

Index Terms

• Theory of computation

  • Design and analysis of algorithms