Document Open Access Logo

Price of Anarchy for Mechanisms with Risk-Averse Agents

Authors Thomas Kesselheim, Bojana Kodric

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.155.pdf
  • Filesize: 476 kB
  • 14 pages

Document Identifiers

Author Details

Thomas Kesselheim
  • University of Bonn, Institute of Computer Science, Bonn, Germany
Bojana Kodric
  • MPI for Informatics and Saarland University, Saarbrücken, Germany

Funding

This work is supported by DFG through Cluster of Excellence MMCI.

Cite AsGet BibTex

Thomas Kesselheim and Bojana Kodric. Price of Anarchy for Mechanisms with Risk-Averse Agents. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 155:1-155:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.155

Abstract

We study the price of anarchy of mechanisms in the presence of risk-averse agents. Previous work has focused on agents with quasilinear utilities, possibly with a budget. Our model subsumes this as a special case but also captures that agents might be less sensitive to payments than in the risk-neutral model. We show that many positive price-of-anarchy results proved in the smoothness framework continue to hold in the more general risk-averse setting. A sufficient condition is that agents can never end up with negative quasilinear utility after playing an undominated strategy. This is true, e.g., for first-price and second-price auctions. For all-pay auctions, similar results do not hold: We show that there are Bayes-Nash equilibria with arbitrarily bad social welfare compared to the optimum.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic mechanism design
  • Theory of computation → Quality of equilibria
Keywords
  • Mechanism Design
  • Price of Anarchy
  • Risk Aversion
  • Smoothness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Daniel Bernoulli. Exposition of a new theory on the measurement of risk. Commentaries of the Imperial Academy of Science of Saint Petersburg, 1738. Republished Econometrica 22(1), 23-36 (1954). Google Scholar
  2. Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna. Mechanism design for a risk averse seller. In Proc. 8th Intl. Workshop Internet &Network Economics (WINE), pages 198-211, 2012. Google Scholar
  3. Shaddin Dughmi and Yuval Peres. Mechanisms for risk averse agents, without loss. CoRR, abs/1206.2957, 2012. Google Scholar
  4. Paul Dütting, Thomas Kesselheim, and Éva Tardos. Mechanism with unique learnable equilibria. In Proc. 15th Conf. Econom. Comput. (EC), pages 877-894, 2014. Google Scholar
  5. Amos Fiat and Christos H. Papadimitriou. When the players are not expectation maximizers. In Proc. 3rd Intl. Symp. Algorithmic Game Theory (SAGT), pages 1-14, 2010. Google Scholar
  6. Gadi Fibich, Arieh Gavious, and Aner Sela. All-pay auctions with risk-averse players. Int. J. Game Theory, 34(4):583-599, 2006. Google Scholar
  7. Hu Fu, Jason Hartline, and Darrell Hoy. Prior-independent auctions for risk-averse agents. In Proc. 14th Conf. Electr. Commerce (EC), pages 471-488. ACM, 2013. Google Scholar
  8. Martin Hoefer, Thomas Kesselheim, and Berthold Vöcking. Truthfulness and stochastic dominance with monetary transfers. ACM Trans. Econom. Comput., 4(2):11:1-11:18, 2016. Google Scholar
  9. Darrell Hoy. The concavity of atomic splittable congestion games with non-linear utility functions. In EC 2012, Workshop on Risk Aversion in Algorithmic Game Theory and Mechanism Design, 2012. Google Scholar
  10. Darrell Hoy, Nicole Immorlica, and Brendan Lucier. On-demand or spot? selling the cloud to risk-averse customers. In Proc. 12th Intl. Conf. Web and Internet Economics (WINE), pages 73-86, 2016. Google Scholar
  11. Audrey Hu, Steven A Matthews, and Liang Zou. Risk aversion and optimal reserve prices in first-and second-price auctions. J. Econom. Theory, 145(3):1188-1202, 2010. Google Scholar
  12. Thomas Kesselheim and Bojana Kodric. Price of anarchy for mechanisms with risk-averse agents. CoRR, abs/1804.09468, 2018. URL: http://arxiv.org/abs/1804.09468.
  13. Bettina S Klose and Paul Schweinzer. Auctioning risk: The all-pay auction under mean-variance preferences. Technical report, University of Zurich, 2014. URL: http://dx.doi.org/10.5167/uzh-67043.
  14. Harry M Markowitz. Portfolio selection: efficient diversification of investments, volume 16. Yale university press, 1968. Google Scholar
  15. Harry M. Markowitz. Mean-variance approximations to expected utility. Europ. J. Oper. Res., 234(2):346-355, 2014. Google Scholar
  16. Andreu Mas-Colell, Michael Dennis Whinston, Jerry R Green, et al. Microeconomic theory, volume 1. Oxford university press New York, 1995. Google Scholar
  17. Eric Maskin and John Riley. Optimal auctions with risk averse buyers. Econometrica, pages 1473-1518, 1984. Google Scholar
  18. Timothy Mathews and Brett Katzman. The role of varying risk attitudes in an auction with a buyout option. J. Econom. Theory, 27(3):597-613, 2006. Google Scholar
  19. Steven A Matthews. Selling to risk averse buyers with unobservable tastes. J. Econom. Theory, 30(2):370-400, 1983. Google Scholar
  20. Reshef Meir and David C. Parkes. Playing the wrong game: Smoothness bounds for congestion games with behavioral biases. SIGMETRICS Performance Evaluation Review, 43(3):67-70, 2015. Google Scholar
  21. Evdokia Nikolova and Nicolás E. Stier Moses. A mean-risk model for the traffic assignment problem with stochastic travel times. Oper. Res., 62(2):366-382, 2014. Google Scholar
  22. Evdokia Nikolova and Nicolás E. Stier Moses. The burden of risk aversion in mean-risk selfish routing. In Proc. 16th Conf. Econom. Comput. (EC), pages 489-506, 2015. Google Scholar
  23. Georgios Piliouras, Evdokia Nikolova, and Jeff S. Shamma. Risk sensitivity of price of anarchy under uncertainty. ACM Trans. Econom. Comput., 5(1):5:1-5:27, 2016. Google Scholar
  24. Tim Roughgarden. Intrinsic robustness of the price of anarchy. In Proc. 41st Symp. Theory of Computing (STOC), pages 513-522, 2009. Google Scholar
  25. Mukund Sundararajan and Qiqi Yan. Robust mechanisms for risk-averse sellers. In Proc. 11th Conf. Econom. Comput. (EC), pages 139-148, 2010. Google Scholar
  26. Vasilis Syrgkanis and Éva Tardos. Composable and efficient mechanisms. In Proc. 45th Symp. Theory of Computing (STOC), pages 211-220, 2013. Google Scholar
  27. John von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton, New Jersey: Princeton University Press. XVIII, 625 p., 1944. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact