IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v44y2019i1p354-375.html
   My bibliography  Save this article

Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

Author

Listed:
  • Jian Li

    (Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, P.R. China)

  • Amol Deshpande

    (Department of Computer Science, University of Maryland, College Park, Maryland 20742)

Abstract

We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input data set are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, minimum weight matchings, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk-averse or risk-prone behaviors, and, instead, we consider a more general objective, which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). Under the assumption that there is a pseudopolynomial-time algorithm for the exact version of the problem (this is true for the problems mentioned above), 1 we can obtain the following approximation results for several important classes of utility functions: If the utility function μ is continuous, upper bounded by a constant and μ ( x ) approaches 0 as x approaches infinity, we show that we can obtain a polynomial-time approximation algorithm with an additive error ε for any constant ε > 0. If the utility function μ is a concave increasing function, we can obtain a polynomial-time approximation scheme (PTAS). If the utility function μ is increasing and has a bounded derivative, we can obtain a PTAS. Our results recover or generalize several prior results on stochastic shortest-path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.

Suggested Citation

  • Jian Li & Amol Deshpande, 2019. "Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 354-375, February.
  • Handle: RePEc:inm:ormoor:v:44:y:2019:i:1:p:354-375
    DOI: 10.1287/moor.2017.0927
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2017.0927
    Download Restriction: no

    File URL: https://libkey.io/10.1287/moor.2017.0927?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Samuelson, Paul A, 1977. "St. Petersburg Paradoxes: Defanged, Dissected, and Historically Described," Journal of Economic Literature, American Economic Association, vol. 15(1), pages 24-55, March.
    2. Daniel Kahneman & Amos Tversky, 2013. "Prospect Theory: An Analysis of Decision Under Risk," World Scientific Book Chapters, in: Leonard C MacLean & William T Ziemba (ed.), HANDBOOK OF THE FUNDAMENTALS OF FINANCIAL DECISION MAKING Part I, chapter 6, pages 99-127, World Scientific Publishing Co. Pte. Ltd..
    3. Ishwar Murthy & Sumit Sarkar, 1998. "Stochastic Shortest Path Problems with Piecewise-Linear Concave Utility Functions," Management Science, INFORMS, vol. 44(11-Part-2), pages 125-136, November.
    4. Jonathan F. Bard & James E. Bennett, 1991. "Arc Reduction and Path Preference in Stochastic Acyclic Networks," Management Science, INFORMS, vol. 37(2), pages 198-215, February.
    5. Murthy, Ishwar & Sarkar, Sumit, 1997. "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, Elsevier, vol. 103(1), pages 209-229, November.
    6. C. Elliott Sigal & A. Alan B. Pritsker & James J. Solberg, 1980. "The Stochastic Shortest Route Problem," Operations Research, INFORMS, vol. 28(5), pages 1122-1129, October.
    7. Brian C. Dean & Michel X. Goemans & Jan Vondrák, 2008. "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 945-964, November.
    8. Mordechai I. Henig, 1990. "Risk Criteria in a Stochastic Knapsack Problem," Operations Research, INFORMS, vol. 38(5), pages 820-825, October.
    9. Robert L. Carraway & Robert L. Schmidt & Lawrence R. Weatherford, 1993. "An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(2), pages 161-173, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yasemin Merzifonluoglu & Joseph Geunes, 2021. "The Risk-Averse Static Stochastic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 931-948, July.
    2. Aloysius, John A., 2003. "Rational escalation of costs by playing a sequence of unfavorable gambles: the martingale," Journal of Economic Behavior & Organization, Elsevier, vol. 51(1), pages 111-129, May.
    3. Basieva, Irina & Khrennikova, Polina & Pothos, Emmanuel M. & Asano, Masanari & Khrennikov, Andrei, 2018. "Quantum-like model of subjective expected utility," Journal of Mathematical Economics, Elsevier, vol. 78(C), pages 150-162.
    4. Benjamin Y. Hayden & Michael L. Platt, 2009. "The mean, the median, and the St. Petersburg paradox," Judgment and Decision Making, Society for Judgment and Decision Making, vol. 4(4), pages 256-272, June.
    5. Lee, Jisun & Joung, Seulgi & Lee, Kyungsik, 2022. "A fully polynomial time approximation scheme for the probability maximizing shortest path problem," European Journal of Operational Research, Elsevier, vol. 300(1), pages 35-45.
    6. Christian Seidl, 2013. "The St. Petersburg Paradox at 300," Journal of Risk and Uncertainty, Springer, vol. 46(3), pages 247-264, June.
    7. Brian C. Dean & Michel X. Goemans & Jan Vondrák, 2008. "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 945-964, November.
    8. Taylan İlhan & Seyed M. R. Iravani & Mark S. Daskin, 2011. "TECHNICAL NOTE---The Adaptive Knapsack Problem with Stochastic Rewards," Operations Research, INFORMS, vol. 59(1), pages 242-248, February.
    9. Nie, Yu (Marco) & Wu, Xing & Dillenburg, John F. & Nelson, Peter C., 2012. "Reliable route guidance: A case study from Chicago," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(2), pages 403-419.
    10. Murthy, Ishwar & Sarkar, Sumit, 1997. "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, Elsevier, vol. 103(1), pages 209-229, November.
    11. Will Ma, 2018. "Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 789-812, August.
    12. James C. Cox & Eike B. Kroll & Marcel Lichters & Vjollca Sadiraj & Bodo Vogt, 2019. "The St. Petersburg paradox despite risk-seeking preferences: an experimental study," Business Research, Springer;German Academic Association for Business Research, vol. 12(1), pages 27-44, April.
    13. Knowles, Glenn J., 1980. "Estimating Utility Functions," Risk Analysis in Agriculture: Research and Educational Developments, January 16-18, 1980, Tucson, Arizona 271570, Regional Research Projects > W-149: An Economic Evaluation of Managing Market Risks in Agriculture.
    14. Valerii Salov, 2015. "The Role of Time in Making Risky Decisions and the Function of Choice," Papers 1512.08792, arXiv.org.
    15. Stefanie Kosuch & Abdel Lisser, 2010. "Upper bounds for the 0-1 stochastic knapsack problem and a B&B algorithm," Annals of Operations Research, Springer, vol. 176(1), pages 77-93, April.
    16. Sam Ransbotham & Ishwar Murthy & Sabyasachi Mitra & Sridhar Narasimhan, 2011. "Sequential Grid Computing: Models and Computational Experiments," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 174-188, May.
    17. Daniel Muller & Tshilidzi Marwala, 2019. "Relative Net Utility and the Saint Petersburg Paradox," Papers 1910.09544, arXiv.org, revised May 2020.
    18. Marie Schmidt & Leo Kroon & Anita Schöbel & Paul Bouman, 2017. "The Travelers Route Choice Problem Under Uncertainty: Dominance Relations Between Strategies," Operations Research, INFORMS, vol. 65(1), pages 184-199, February.
    19. repec:cup:judgdm:v:4:y:2009:i:4:p:256-272 is not listed on IDEAS
    20. Raquel M. Gaspar & Paulo M. Silva, 2019. "Investors’ Perspective on Portfolio InsuranceExpected Utility vs Prospect Theories," Working Papers REM 2019/92, ISEG - Lisbon School of Economics and Management, REM, Universidade de Lisboa.
    21. Ma, T. & Fraser-Mackenzie, P.A.F. & Sung, M. & Kansara, A.P. & Johnson, J.E.V., 2022. "Are the least successful traders those most likely to exit the market? A survival analysis contribution to the efficient market debate," European Journal of Operational Research, Elsevier, vol. 299(1), pages 330-345.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:44:y:2019:i:1:p:354-375. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.