Martin Hoefer
Abstract
We consider truthfulness concepts for auctions with payments based on first- and second-order stochastic dominance. We assume bidders consider wealth in standard quasilinear 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 metarounding 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.
- Atila Abdulkadiroglu and Tayfun Sönmez. 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 3 (1998), 689--701.Google Scholar
Cross Ref
- Aaron Archer and Éva Tardos. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS’01). 482--491. Google ScholarDigital Library
- Haris Aziz, Felix Brandt, and Markus Brill. 2013. On the tradeoff between economic efficiency and strategyproofness in randomized social choice. In Proceedings of the 12th Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’13). 287--294. Google ScholarDigital Library
- Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna. 2012. Mechanism design for a risk averse seller. In Proceedings of the 8th International Workshop on Internet & Network Economics (WINE’’12). 198--211. Google ScholarDigital Library
- Anna Bogomolnaia and Herve Moulin. 2001. A new solution to the random assignment problem. J. Econom. Theory 100 (2001), 295--328.Google ScholarCross Ref
- Anna Bogomolnaia and Herve Moulin. 2004. Random matching under dichotomous preferences. Econometrica 72 (2004), 257--279.Google ScholarCross Ref
- Chandra Chekuri, Sanjeev Khanna, and Bruce Shepherd. 2005. Multicommodity flow, well-linked terminals, and routing problems. In Proceedings of the 37th Symposium on Theory of Computing (STOC’05). 183--192. Google ScholarDigital Library
- George Christodoulou, Khaled Elbassioni, and Mahmoud Fouz. 2010. Truthful mechanisms for exhibitions. In Proceedings of the 6th Interntional Workshop on Internet & Network Economics (WINE’’10). 170--181. Google ScholarDigital Library
- Shahar Dobzinski and Shaddin Dughmi. 2013. On the power of randomization in algorithmic mechanism design. SIAM J. Comput. 42, 6 (2013), 2287--2304.Google ScholarDigital Library
- Shaddin Dughmi. 2012.Randomization and Computation in Strategic Settings. Ph.D. dissertation. Stanford University.Google Scholar
- Shaddin Dughmi and Yuval Peres. 2012. Mechanisms for Risk Averse Agents, Without Loss. (June 2012). CoRR 1206.2957.Google Scholar
- Shaddin Dughmi, Tim Roughgarden, and Qiqi Yan. 2011. From convex optimization to randomized mechanims: Toward optimal combinatorial auctions. In Proceedings of the 43rd Symposium on Theory of Computing (STOC’11). 149--158. Google ScholarDigital Library
- Lars Ehlers, Hans Peters, and Ton Storcken. 2002. Strategy-proof probabilistic decision schemes for one-dimensional single-peaked preferences. J. Econom. Theory 105 (2002), 408--434.Google ScholarCross Ref
- Peter Esö and Gabor Futo. 1999. Auction design with a risk averse seller. Econom. Lett. 65, 1 (1999), 71--74.Google ScholarCross Ref
- Hu Fu, Jason Hartline, and Darrell Hoy. 2013. Prior-independent auctions for risk-averse agents. In Proceedings of the 14th Conference on Electronic Commerce (EC’13). 471--488. Google ScholarDigital Library
- Allan Gibbard. 1977. Manipulation of schemes that mix voting with chance. Econometrica 45, 3 (1977), 665--681.Google ScholarCross Ref
- Ajay Gopinathan, Zongpeng Li, and Chuan Wu. 2011. Strategyproof auctions for balancing social welfare and fairness in secondary spectrum markets. In Proceedings of the 30th IEEE Conference on Computer Communications (INFOCOM’11). 3020--3028.Google ScholarCross Ref
- Martin Hoefer and Thomas Kesselheim. 2015. Secondary spectrum auctions for symmetric and submodular bidders. ACM Trans. Econom. Comput. 3, 2 (2015), 9. Google ScholarDigital Library
- M. Hoefer and T. Kesselheim. 2012. Secondary spectrum auctions for symmetric and submodular bidders. In Proceedings of the 13th Conference on Electronic Commerce (EC’12). 657--671. Google ScholarDigital Library
- Martin Hoefer, Thomas Kesselheim, and Berthold Vöcking. 2013. Truthfulness and stochastic dominance with monetary transfers. In Proceedings of the 14th Conference on Electronic Commerce (EC’13). 567--582. Google ScholarDigital Library
- Martin Hoefer, Thomas Kesselheim, and Berthold Vöcking. 2014. Approximation algorithms for secondary spectrum auctions. ACM Trans. Internet Techn. 14, 2--3 (2014), 16. Google ScholarDigital Library
- Audrey Hu, Steven Matthews, and Liang Zou. 2010. Risk aversion and optimal reserve prices in first- and second-price auctions. J. Econom. Theory 145, 3 (2010), 1188--1202.Google ScholarCross Ref
- Akshay-Kumar Katta and Jay Sethuraman. 2006. A solution to the random assignment problem on the full preference domain. J. Econom. Theory 131 (2006), 231--250.Google ScholarCross Ref
- Piotr Krysta and Berthold Vöcking. 2012. Online mechanism design (randomized rounding on the fly). In Proceedings of the 39th International Coll.oquium on Automata, Languages and Programming (ICALP’12). 636--647. Google ScholarDigital Library
- Ron Lavi and Chaitanya Swamy. 2011. Truthful and near-optimal mechanism design via linear programming. J. ACM 58, 6 (2011), 25. Google ScholarDigital Library
- Andreu Mas-Colell, Michael Whinston, and Jerry Green. 1995. Microeconomic Theory. Oxford University Press.Google Scholar
- Eric Maskin and John Riley. 1984. Optimal auctions with risk averse buyers. Econometrica 52, 6 (1984), 1473--1518.Google ScholarCross Ref
- Herve Moulin. 1980. On strategy-proofness and single peakedness. Public Choice 35, 4 (1980), 437--455.Google ScholarCross Ref
- Roger Myerson. 1981. Optimal auction design. Math. Oper. Res. 6 (1981), 58--73. Google ScholarDigital Library
- Noam Nisan. 2007. Introduction to mechanism design (for computer scientists). In Algorithmic Game Theory, Noam Nisan, Éva Tardos, Tim Roughgarden, and Vijay Vazirani (Eds.). Cambridge University Press, Chapter 9.Google Scholar
- Hans Peters, Tim Schulteis, and Dries Vermeulen. 2010. Generalized stochastic dominance and bad outcome aversion. Social Choice and Welfare 35, 2 (2010), 285--290.Google ScholarCross Ref
- Mukund Sundararajan and Qiqi Yan. 2010. Robust mechanisms for risk-averse sellers. In Proceedings of the 11th Conference on Electronic Commerce (EC’10). 139--148. Google ScholarDigital Library
- Berthold Vöcking. 2012. A universally-truthful approximation scheme for multi-unit auctions. In Proceedings of the 23rd Symposium on Discrete Algorithms (SODA’12). 846--855. Google ScholarDigital Library
- Lin Zhou. 1990. On a conjecture by gale about one-sided matching problems. J. Econom. Theory 52 (1990), 123--135.Google ScholarCross Ref
- Yuefei Zhu, Baochun Li, and Zongpeng Li. 2012. Truthful spectrum auction design for secondary networks. In Proceedings of the 31st IEEE Conference on Computer Communications (INFOCOM’12). 873--881.Google Scholar
Index Terms
- Truthfulness and Stochastic Dominance with Monetary Transfers
Recommendations
Truthfulness and stochastic dominance with monetary transfers
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceWe 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 ...
Truthfulness and stochastic dominance with monetary transfers
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceWe 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 ...
Single valued combinatorial auctions with budgets
EC '11: Proceedings of the 12th ACM conference on Electronic commerceWe consider budget constrained combinatorial auctions where each bidder has a private value for each of the items in some subset of the items and an overall budget constraint. Such auctions capture adword auctions, where advertisers offer a bid for ...
Reviews
Vladik Kreinovich
It is desirable to design auctions in such a way that participants have a financial incentive to provide true information about their interests. At first glance, an ideal description of this truthfulness requirement is that, in all possible situations, a person reporting the true valuation benefits gets the largest possible value of the difference v - p between the value v of the objects gained in the auction minus the corresponding payment p . However, such a universal truthfulness requirement is too strong: such auction schemes exist, but the resulting solutions are often of low quality. A much better quality is attained by truthful-in-expectation solutions, in which reporting the true valuation maximizes the expected monetary gain m = v - p . However, this does not necessarily mean that in the real-life implementations of the corresponding auction designs, participants will report their true valuations. The reason is that while it may sound reasonable to maximize the expected value of monetary gain, this is not, in general, how people make decisions. The decisions of a rational person correspond to maximizing the expected utility, where utility u ( m ) is an increasing (and usually nonlinear) function of the monetary gain. Different participants may make decisions based on different utility functions. From this viewpoint, it is desirable to look for auction schemes in which the truthful valuation is beneficial for all possible utility functions. This condition is difficult to check directly, since it requires considering all possible monotonic functions; however, it is known that such a condition can be equivalently reformulated as the requirement that F ( a ) is smaller than or equal to G ( a ) for all a , where F ( a ) is the truthful-valuation-case probability that the monetary m does not exceed a and G ( a ) is the similar probability for the case of a false valuation. This property is known as first-order stochastic dominance. The authors describe all social-choice functions that are truthful in first-order stochastic dominance. Interestingly, it turns out that these are the same functions that allow truthful-in-expectation solutions-but to gain first-order stochastic dominance, one needs to somewhat change the payment rules. Another interesting result is that the situation does not improve if we only consider, for example, risk-averse participants: if we can guarantee truthfulness for them, then we can also guarantee truthfulness for all participants. These interesting new results ensure that the corresponding auction designs encourage truthfulness and are, thus, ready for practical implementation. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments