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

    for a different version of it.

    References listed on IDEAS

    as
    1. Fudenberg, Drew & Levine, David, 1998. "Learning in games," European Economic Review, Elsevier, vol. 42(3-5), pages 631-639, May.
    2. 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.
    3. 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.
    4. Rustichini, Aldo, 1999. "Optimal Properties of Stimulus--Response Learning Models," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 244-273, October.
    5. Sandholm, William H., 2015. "Population Games and Deterministic Evolutionary Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.
    6. Charles F. Manski, 2004. "Statistical Treatment Rules for Heterogeneous Populations," Econometrica, Econometric Society, vol. 72(4), pages 1221-1246, July.
    7. Ross Cressman, 2003. "Evolutionary Dynamics and Extensive Form Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262033054, December.
    8. 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.
    9. Sascha Desmettre & Mogens Steffensen, 2023. "Equilibrium investment with random risk aversion," Mathematical Finance, Wiley Blackwell, vol. 33(3), pages 946-975, July.
    10. Hofbauer, Josef & Sandholm, William H., 2009. "Stable games and their dynamics," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1665-1693.4, July.
    11. 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.
    12. Bernard, Carole & Chen, Jit Seng & Vanduffel, Steven, 2015. "Rationalizing investors’ choices," Journal of Mathematical Economics, Elsevier, vol. 59(C), pages 10-23.
    13. 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.
    14. 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.
    15. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Andr'es Aradillas Fern'andez & Jos'e Blanchet & Jos'e Luis Montiel Olea & Chen Qiu & Jorg Stoye & Lezhi Tan, 2025. "Epsilon-Minimax Solutions of Statistical Decision Problems," Papers 2509.08107, arXiv.org.

    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. Mertikopoulos, Panayotis & Sandholm, William H., 2018. "Riemannian game dynamics," Journal of Economic Theory, Elsevier, vol. 177(C), pages 315-364.
    2. Ewerhart, Christian & Valkanova, Kremena, 2020. "Fictitious play in networks," Games and Economic Behavior, Elsevier, vol. 123(C), pages 182-206.
    3. 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.
    4. Heller, Yuval & Mohlin, Erik, 2019. "Coevolution of deception and preferences: Darwin and Nash meet Machiavelli," Games and Economic Behavior, Elsevier, vol. 113(C), pages 223-247.
    5. Leslie, David S. & Perkins, Steven & Xu, Zibo, 2020. "Best-response dynamics in zero-sum stochastic games," Journal of Economic Theory, Elsevier, vol. 189(C).
    6. Laraki, Rida & Mertikopoulos, Panayotis, 2013. "Higher order game dynamics," Journal of Economic Theory, Elsevier, vol. 148(6), pages 2666-2695.
    7. Izquierdo, Luis R. & Izquierdo, Segismundo S. & Sandholm, William H., 2019. "An introduction to ABED: Agent-based simulation of evolutionary game dynamics," Games and Economic Behavior, Elsevier, vol. 118(C), pages 434-462.
    8. 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.
    9. 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.
    10. 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.
    11. Christian Ewerhart, 2020. "Ordinal potentials in smooth games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(4), pages 1069-1100, November.
    12. 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.
    13. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.
    14. Ed Hopkins, 2002. "Two Competing Models of How People Learn in Games," Econometrica, Econometric Society, vol. 70(6), pages 2141-2166, November.
    15. 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.
    16. Lahkar, Ratul & Mukherjee, Sayan & Roy, Souvik, 2022. "Generalized perturbed best response dynamics with a continuum of strategies," Journal of Economic Theory, Elsevier, vol. 200(C).
    17. Beggs, A.W., 2005. "On the convergence of reinforcement learning," Journal of Economic Theory, Elsevier, vol. 122(1), pages 1-36, May.
    18. Hopkins, Ed, 2007. "Adaptive learning models of consumer behavior," Journal of Economic Behavior & Organization, Elsevier, vol. 64(3-4), pages 348-368.
    19. Pietro Dindo & Jan Tuinstra, 2011. "A Class of Evolutionary Models for Participation Games with Negative Feedback," Computational Economics, Springer;Society for Computational Economics, vol. 37(3), pages 267-300, March.
    20. William Sandholm, 2014. "Probabilistic Interpretations of Integrability for Game Dynamics," Dynamic Games and Applications, Springer, vol. 4(1), pages 95-106, March.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.