IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i3p1791-1809.html

Approximate Nash Equilibria in Large Nonconvex Aggregative Games

Author

Listed:
  • Kang Liu

    (Centre de Mathématiques Appliquées, Ecole Polytechnique, 91128 Palaiseau Cedex, France; Inria Saclay Center, 91120 Palaiseau, France)

  • Nadia Oudjane

    (Research & Development, EDF Lab Paris-Saclay, 91120 Palaiseau, France; Finance for Energy Market Research Centre, France)

  • Cheng Wan

    (Research & Development, EDF Lab Paris-Saclay, 91120 Palaiseau, France; Finance for Energy Market Research Centre, France)

Abstract

This paper shows the existence of O ( 1 / n γ ) -Nash equilibria in n -player noncooperative sum-aggregative games in which the players’ cost functions, depending only on their own action and the average of all players’ actions, are lower semicontinuous in the former, whereas γ -Hölder continuous in the latter. Neither the action sets nor the cost functions need to be convex. For an important class of sum-aggregative games, which includes congestion games with γ equal to one, a gradient-proximal algorithm is used to construct O ( 1 / n ) -Nash equilibria with at most O ( n 3 ) iterations. These results are applied to a numerical example concerning the demand-side management of an electricity system. The asymptotic performance of the algorithm when n tends to infinity is illustrated.

Suggested Citation

  • Kang Liu & Nadia Oudjane & Cheng Wan, 2023. "Approximate Nash Equilibria in Large Nonconvex Aggregative Games," Mathematics of Operations Research, INFORMS, vol. 48(3), pages 1791-1809, August.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:3:p:1791-1809
    DOI: 10.1287/moor.2022.1321
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1321
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1321?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. Madeleine Udell & Stephen Boyd, 2016. "Bounding duality gap for separable problems with linear constraints," Computational Optimization and Applications, Springer, vol. 64(2), pages 355-378, June.
    2. J. David Pérez-Castrillo & Thierry Verdier, 1992. "A general analysis of rent-seeking games," Springer Books, in: Roger D. Congleton & Arye L. Hillman & Kai A. Konrad (ed.), 40 Years of Research on Rent Seeking 1, pages 133-148, Springer.
    3. M. Pappalardo, 1986. "On the Duality Gap in Nonconvex Optimization," Mathematics of Operations Research, INFORMS, vol. 11(1), pages 30-35, February.
    4. Foucart, Renaud & Wan, Cheng, 2018. "Strategic decentralization and the provision of global public goods," Journal of Environmental Economics and Management, Elsevier, vol. 92(C), pages 537-558.
    5. Achille Basile & Maria Gabriella Graziano & Marialaura Pesce, 2016. "Oligopoly And Cost Sharing In Economies With Public Goods," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 57, pages 487-506, May.
    6. Martin Jensen, 2010. "Aggregative games and best-reply potentials," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 43(1), pages 45-66, April.
    7. Starr, Ross M, 1969. "Quasi-Equilibria in Markets with Non-Convex Preferences," Econometrica, Econometric Society, vol. 37(1), pages 25-38, January.
    8. Stella Dafermos, 1980. "Traffic Equilibrium and Variational Inequalities," Transportation Science, INFORMS, vol. 14(1), pages 42-54, February.
    9. Myerson, Roger B. & Weber, Robert J., 1993. "A Theory of Voting Equilibria," American Political Science Review, Cambridge University Press, vol. 87(1), pages 102-114, March.
    10. Achille Basile & Maria Gabriella Graziano & Marialaura Pesce, 2016. "Oligopoly And Cost Sharing In Economies With Public Goods," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 57(2), pages 487-506, May.
    11. Thomas Palfrey & Howard Rosenthal, 1983. "A strategic calculus of voting," Public Choice, Springer, vol. 41(1), pages 7-53, January.
    12. J. P. Aubin & I. Ekeland, 1976. "Estimates of the Duality Gap in Nonconvex Optimization," Mathematics of Operations Research, INFORMS, vol. 1(3), pages 225-245, August.
    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. Enis Chenchene & Hui Huang & Jinniao Qiu, 2025. "A Consensus-based Algorithm for Non-convex Multiplayer Games," Journal of Optimization Theory and Applications, Springer, vol. 206(2), pages 1-30, August.

    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. Thomas Kerdreux & Igor Colin & Alexandre d’Aspremont, 2023. "Stable Bounds on the Duality Gap of Separable Nonconvex Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 48(2), pages 1044-1065, May.
    2. François Durand & Antonin Macé & Matias Nunez, 2019. "Analysis of Approval Voting in Poisson Games," Working Papers halshs-02049865, HAL.
    3. Costel Andonie & Daniel Diermeier, 2022. "Electoral Institutions with impressionable voters," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(3), pages 683-733, October.
    4. Bhowmik, Anuj & Saha, Sandipan, 2022. "On blocking mechanisms in economies with club goods," MPRA Paper 114928, University Library of Munich, Germany.
    5. Gama, Adriana & Rietzke, David, 2019. "Monotone comparative statics in games with non-monotonic best-replies: Contests and Cournot oligopoly," Journal of Economic Theory, Elsevier, vol. 183(C), pages 823-841.
    6. Antonio Merlo, 2005. "Whither Political Economy? Theories, Facts and Issues," PIER Working Paper Archive 05-033, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 01 Dec 2005.
    7. Wu, Haoyu & Tang, Ao, 2024. "An even tighter bound for the Shapley–Folkman–Starr theorem," Journal of Mathematical Economics, Elsevier, vol. 114(C).
    8. Costel Andonie & Daniel Diermeier, 2024. "Attentiveness in elections with impressionable voters," Public Choice, Springer, vol. 201(1), pages 123-143, October.
    9. S. Flåm & L. Koutsougeras, 2010. "Private information, transferable utility, and the core," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(3), pages 591-609, March.
    10. Herrade Igerseim & Antoinette Baujard & Jean-François Laslier, 2016. "La question du vote. Expérimentations en laboratoire et In Situ," L'Actualité Economique, Société Canadienne de Science Economique, vol. 92(1-2), pages 151-189.
    11. Jens Großer & Arthur Schram, 2010. "Public Opinion Polls, Voter Turnout, and Welfare: An Experimental Study," American Journal of Political Science, John Wiley & Sons, vol. 54(3), pages 700-717, July.
    12. Paul Milgrom, 2011. "Critical Issues In The Practice Of Market Design," Economic Inquiry, Western Economic Association International, vol. 49(2), pages 311-320, April.
    13. Xefteris, Dimitrios, 2019. "Strategic voting when participation is costly," Games and Economic Behavior, Elsevier, vol. 116(C), pages 122-127.
    14. Anuj Bhowmik, 2025. "Characterizations of equilibrium allocations in an economy with public goods and infinitely many commodities," Papers 2509.24437, arXiv.org.
    15. Thomas R. Palfrey, 2005. "Laboratory Experiments in Political Economy," Working Papers 91, Princeton University, Department of Economics, Center for Economic Policy Studies..
    16. Chiara Donnini & Marialaura Pesce, 2023. "Fairness and formation rules of coalitions," International Journal of Economic Theory, The International Society for Economic Theory, vol. 19(4), pages 933-960, December.
    17. Meirowitz, Adam & Shotts, Kenneth W., 2009. "Pivots versus signals in elections," Journal of Economic Theory, Elsevier, vol. 144(2), pages 744-771, March.
    18. Mariam Arzumanyan, 2025. "Exploring voter turnout dynamics in polarized elections: A group-rule utilitarian framework," Rationality and Society, , vol. 37(2), pages 230-263, May.
    19. Chilton, John, 1998. "Strategic Poll Responses When Elections Create Mandates," Public Choice, Springer, vol. 94(1-2), pages 21-47, January.
    20. Achille Basile & Robert P. Gilles & Maria Gabriella Graziano & Marialaura Pesce, 2021. "The Core of economies with collective goods and a social division of labour," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(3), pages 1085-1119, April.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    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:inm:ormoor:v:48:y:2023:i:3:p:1791-1809. 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.