IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v201y2024i2d10.1007_s10957-024-02415-4.html
   My bibliography  Save this article

Solving Maxmin Optimization Problems via Population Games

Author

Listed:
  • Anne G. Balter

    (Tilburg University)

  • Johannes M. Schumacher

    (University of Amsterdam)

  • Nikolaus Schweizer

    (Tilburg University)

Abstract

Population games are games with a finite set of available strategies and an infinite number of players, in which the reward for choosing a given strategy is a function of the distribution of players over strategies. The paper shows that, in a certain class of maxmin optimization problems, it is possible to associate a population game to a given maxmin problem in such a way that solutions to the optimization problem are found from Nash equilibria of the associated game. Iterative solution methods for maxmin optimization problems can then be derived from systems of differential equations whose trajectories are known to converge to Nash equilibria. In particular, we use a discrete-time version of the celebrated replicator equation of evolutionary game theory, also known in machine learning as the exponential multiplicative weights algorithm. The resulting algorithm can be viewed as a generalization of the Iteratively Reweighted Least Squares (IRLS) method, which is well known in numerical analysis as a useful technique for solving Chebyshev function approximation problems on a finite grid. Examples are provided to show the use of the generalized IRLS method in collective investment and in decision making under model uncertainty.

Suggested Citation

  • Anne G. Balter & Johannes M. Schumacher & Nikolaus Schweizer, 2024. "Solving Maxmin Optimization Problems via Population Games," Journal of Optimization Theory and Applications, Springer, vol. 201(2), pages 760-789, May.
    • Handle: RePEc:spr:joptap:v:201:y:2024:i:2:d:10.1007_s10957-024-02415-4
    DOI: 10.1007/s10957-024-02415-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-024-02415-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-024-02415-4?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. William H. Sandholm, 2001. "Preference Evolution, Two-Speed Dynamics, and Rapid Social Change," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 4(3), pages 637-679, July.
    2. Arjan B. Berkelaar & Roy Kouwenberg & Thierry Post, 2004. "Optimal Portfolio Choice under Loss Aversion," The Review of Economics and Statistics, MIT Press, vol. 86(4), pages 973-987, November.
    3. Rustichini, Aldo, 1999. "Optimal Properties of Stimulus--Response Learning Models," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 244-273, October.
    4. Harsanyi, John C., 1975. "Can the Maximin Principle Serve as a Basis for Morality? A Critique of John Rawls's Theory," American Political Science Review, Cambridge University Press, vol. 69(2), pages 594-606, June.
    5. Ross Cressman, 2003. "Evolutionary Dynamics and Extensive Form Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262033054, December.
    6. Charles F. Manski, 2004. "Statistical Treatment Rules for Heterogeneous Populations," Econometrica, Econometric Society, vol. 72(4), pages 1221-1246, July.
    7. Sascha Desmettre & Mogens Steffensen, 2023. "Equilibrium investment with random risk aversion," Mathematical Finance, Wiley Blackwell, vol. 33(3), pages 946-975, July.
    8. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, December.
    9. Bernard, Carole & Chen, Jit Seng & Vanduffel, Steven, 2015. "Rationalizing investors’ choices," Journal of Mathematical Economics, Elsevier, vol. 59(C), pages 10-23.
    10. Freund, Yoav & Schapire, Robert E., 1999. "Adaptive Game Playing Using Multiplicative Weights," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 79-103, October.
    11. Bian, Baojun & Zheng, Harry, 2015. "Turnpike property and convergence rate for an investment model with general utility functions," Journal of Economic Dynamics and Control, Elsevier, vol. 51(C), pages 28-49.
    12. Basak, Suleyman, 1995. "A General Equilibrium Model of Portfolio Insurance," The Review of Financial Studies, Society for Financial Studies, vol. 8(4), pages 1059-1090.
    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. Guan, Guohui & Liang, Zongxia & Xia, Yi, 2023. "Optimal management of DC pension fund under the relative performance ratio and VaR constraint," European Journal of Operational Research, Elsevier, vol. 305(2), pages 868-886.
    2. Jakub Bielawski & {L}ukasz Cholewa & Fryderyk Falniowski, 2024. "The emergence of chaos in population game dynamics induced by comparisons," Papers 2412.06037, arXiv.org, revised Apr 2025.
    3. Panayotis Mertikopoulos & William H. Sandholm, 2016. "Learning in Games via Reinforcement and Regularization," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1297-1324, November.
    4. Dong, Yinghui & Zheng, Harry, 2019. "Optimal investment of DC pension plan under short-selling constraints and portfolio insurance," Insurance: Mathematics and Economics, Elsevier, vol. 85(C), pages 47-59.
    5. Ianni, A., 2002. "Reinforcement learning and the power law of practice: some analytical results," Discussion Paper Series In Economics And Econometrics 203, Economics Division, School of Social Sciences, University of Southampton.
    6. Zibo Xu, 2013. "The instability of backward induction in evolutionary dynamics," Discussion Paper Series dp633, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    7. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.
    8. Ed Hopkins, 2002. "Two Competing Models of How People Learn in Games," Econometrica, Econometric Society, vol. 70(6), pages 2141-2166, November.
    9. Arthur Charpentier & Romuald Élie & Carl Remlinger, 2023. "Reinforcement Learning in Economics and Finance," Computational Economics, Springer;Society for Computational Economics, vol. 62(1), pages 425-462, June.
    10. Beggs, A.W., 2005. "On the convergence of reinforcement learning," Journal of Economic Theory, Elsevier, vol. 122(1), pages 1-36, May.
    11. Hopkins, Ed, 2007. "Adaptive learning models of consumer behavior," Journal of Economic Behavior & Organization, Elsevier, vol. 64(3-4), pages 348-368.
    12. Zhen Shi & Bas J.M. Werker, 2011. "Economic Costs and Benefits of Imposing Short-Horizon Value-at-Risk Type Regulation," Tinbergen Institute Discussion Papers 11-053/2/DSF17, Tinbergen Institute.
    13. Ewerhart, Christian & Valkanova, Kremena, 2020. "Fictitious play in networks," Games and Economic Behavior, Elsevier, vol. 123(C), pages 182-206.
    14. Anufriev, Mikhail & Kopányi, Dávid & Tuinstra, Jan, 2013. "Learning cycles in Bertrand competition with differentiated commodities and competing learning rules," Journal of Economic Dynamics and Control, Elsevier, vol. 37(12), pages 2562-2581.
    15. Oyarzun, Carlos & Sarin, Rajiv, 2013. "Learning and risk aversion," Journal of Economic Theory, Elsevier, vol. 148(1), pages 196-225.
    16. Saeed Hadikhanloo & Rida Laraki & Panayotis Mertikopoulos & Sylvain Sorin, 2022. "Learning in nonatomic games, part Ⅰ: Finite action spaces and population games," Post-Print hal-03767995, HAL.
    17. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2006. "Stochastic Approximations and Differential Inclusions, Part II: Applications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 673-695, November.
    18. Berkelaar, Arjan & Kouwenberg, Roy, 2009. "From boom 'til bust: How loss aversion affects asset prices," Journal of Banking & Finance, Elsevier, vol. 33(6), pages 1005-1013, June.
    19. Veller, Carl & Hayward, Laura K., 2016. "Finite-population evolution with rare mutations in asymmetric games," Journal of Economic Theory, Elsevier, vol. 162(C), pages 93-113.
    20. Jehiel, Philippe & Samet, Dov, 2005. "Learning to play games in extensive form by valuation," Journal of Economic Theory, Elsevier, vol. 124(2), pages 129-148, October.

    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:spr:joptap:v:201:y:2024:i:2:d:10.1007_s10957-024-02415-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.