IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v143y2009i1d10.1007_s10957-009-9553-0.html
   My bibliography  Save this article

Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search

Author

Listed:
  • A. Heusinger

    (University of Würzburg)

  • C. Kanzow

    (University of Würzburg)

Abstract

The generalized Nash equilibrium problem (GNEP) is an extension of the standard Nash game where, in addition to the cost functions, also the strategy spaces of each player depend on the strategies chosen by all other players. This problem is rather difficult to solve and there are only a few methods available in the literature. One of the most popular ones is the so-called relaxation method, which is known to be globally convergent under a set of assumptions. Some of these assumptions, however, are rather strong or somewhat difficult to understand. Here, we present a modified relaxation method for the solution of a certain class of GNEPs. The convergence analysis uses completely different arguments based on a certain descent property and avoids some of the technical conditions for the original relaxation method. Moreover, numerical experiments indicate that the modified relaxation method performs quite well on a number of different examples taken from the literature.

Suggested Citation

  • A. Heusinger & C. Kanzow, 2009. "Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search," Journal of Optimization Theory and Applications, Springer, vol. 143(1), pages 159-183, October.
    • Handle: RePEc:spr:joptap:v:143:y:2009:i:1:d:10.1007_s10957-009-9553-0
    DOI: 10.1007/s10957-009-9553-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-009-9553-0
    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-009-9553-0?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. Steffan Berridge & Jacek Krawczyk, "undated". "Relaxation Algorithms in Finding Nash Equilibrium," Computing in Economics and Finance 1997 159, Society for Computational Economics.
    2. Anna Heusinger & Christian Kanzow, 2009. "Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions," Computational Optimization and Applications, Springer, vol. 43(3), pages 353-377, July.
    3. Krawczyk, Jacek B., 2005. "Coupled constraint Nash equilibria in environmental games," Resource and Energy Economics, Elsevier, vol. 27(2), pages 157-181, June.
    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. Axel Dreves & Christian Kanzow, 2011. "Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems," Computational Optimization and Applications, Springer, vol. 50(1), pages 23-48, September.
    2. J. Y. Bello Cruz & P. S. M. Santos & S. Scheimberg, 2013. "A Two-Phase Algorithm for a Variational Inequality Formulation of Equilibrium Problems," Journal of Optimization Theory and Applications, Springer, vol. 159(3), pages 562-575, December.
    3. Giancarlo Bigi & Mauro Passacantando, 2016. "Gap functions for quasi-equilibria," Journal of Global Optimization, Springer, vol. 66(4), pages 791-810, December.
    4. Xiao, Jiang-Wen & Yang, Yan-Bing & Cui, Shichang & Liu, Xiao-Kang, 2022. "A new energy storage sharing framework with regard to both storage capacity and power capacity," Applied Energy, Elsevier, vol. 307(C).
    5. Francisco Facchinei & Christian Kanzow, 2010. "Generalized Nash Equilibrium Problems," Annals of Operations Research, Springer, vol. 175(1), pages 177-211, March.
    6. Axel Dreves & Anna Heusinger & Christian Kanzow & Masao Fukushima, 2013. "A globalized Newton method for the computation of normalized Nash equilibria," Journal of Global Optimization, Springer, vol. 56(2), pages 327-340, June.
    7. Napat Harnpornchai & Wiriyaporn Wonggattaleekam, 2021. "A Nikaido Isoda-Based Hybrid Genetic Algorithm and Relaxation Method for Finding Nash Equilibrium," Mathematics, MDPI, vol. 10(1), pages 1-17, December.
    8. Jiawang Nie & Xindong Tang & Lingling Xu, 2021. "The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials," Computational Optimization and Applications, Springer, vol. 78(2), pages 529-557, March.
    9. Axel Dreves & Joachim Gwinner, 2016. "Jointly Convex Generalized Nash Equilibria and Elliptic Multiobjective Optimal Control," Journal of Optimization Theory and Applications, Springer, vol. 168(3), pages 1065-1086, March.
    10. Riccardi, R. & Bonenti, F. & Allevi, E. & Avanzi, C. & Gnudi, A., 2015. "The steel industry: A mathematical model under environmental regulations," European Journal of Operational Research, Elsevier, vol. 242(3), pages 1017-1027.
    11. Mauro Passacantando & Danilo Ardagna & Anna Savi, 2016. "Service Provisioning Problem in Cloud and Multi-Cloud Systems," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 265-277, May.

    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. J. Contreras & J. B. Krawczyk & J. Zuccollo, 2016. "Economics of collective monitoring: a study of environmentally constrained electricity generators," Computational Management Science, Springer, vol. 13(3), pages 349-369, July.
    2. Francisco Facchinei & Christian Kanzow, 2010. "Generalized Nash Equilibrium Problems," Annals of Operations Research, Springer, vol. 175(1), pages 177-211, March.
    3. K. Kubota & M. Fukushima, 2010. "Gap Function Approach to the Generalized Nash Equilibrium Problem," Journal of Optimization Theory and Applications, Springer, vol. 144(3), pages 511-531, March.
    4. Nadja Harms & Tim Hoheisel & Christian Kanzow, 2015. "On a Smooth Dual Gap Function for a Class of Player Convex Generalized Nash Equilibrium Problems," Journal of Optimization Theory and Applications, Springer, vol. 166(2), pages 659-685, August.
    5. Contreras, Javier & Krawczyk, Jacek & Zuccollo, James, 2008. "The invisible polluter: Can regulators save consumer surplus?," MPRA Paper 9890, University Library of Munich, Germany.
    6. Bolei Di & Andrew Lamperski, 2022. "Newton’s Method, Bellman Recursion and Differential Dynamic Programming for Unconstrained Nonlinear Dynamic Games," Dynamic Games and Applications, Springer, vol. 12(2), pages 394-442, June.
    7. Contreras, Javier & Krawczyk, Jacek & Zuccollo, James, 2008. "Can planners control competitive generators?," MPRA Paper 10395, University Library of Munich, Germany.
    8. Krawczyk, Jacek & Azzato, Jeffrey, 2006. "NISOCSol an algorithm for approximating Markovian equilibria in dynamic games with coupled-constraints," MPRA Paper 1195, University Library of Munich, Germany.
    9. Han, Deren & Zhang, Hongchao & Qian, Gang & Xu, Lingling, 2012. "An improved two-step method for solving generalized Nash equilibrium problems," European Journal of Operational Research, Elsevier, vol. 216(3), pages 613-623.
    10. Boucekkine, Raouf & Krawczyk, Jacek B. & Vallée, Thomas, 2010. "Towards an understanding of tradeoffs between regional wealth, tightness of a common environmental constraint and the sharing rules," Journal of Economic Dynamics and Control, Elsevier, vol. 34(9), pages 1813-1835, September.
    11. Gürkan, G. & Pang, J.S., 2009. "Approximizations of Nash equilibria," Other publications TiSEM de211d31-d77d-4211-9ca8-2, Tilburg University, School of Economics and Management.
    12. Elnaz Kanani Kuchesfehani & Georges Zaccour, 2015. "S-adapted Equilibria in Games Played Over Event Trees with Coupled Constraints," Journal of Optimization Theory and Applications, Springer, vol. 166(2), pages 644-658, August.
    13. Krawczyk, Jacek B & Townsend, Wilbur, 2014. "NIRA-GUI: A matlab application which solves for couple-constraint nash equibria from a symbolic specification," Working Paper Series 3414, Victoria University of Wellington, School of Economics and Finance.
    14. Francisco Facchinei & Jong-Shi Pang & Gesualdo Scutari, 2014. "Non-cooperative games with minmax objectives," Computational Optimization and Applications, Springer, vol. 59(1), pages 85-112, October.
    15. Axel Dreves & Christian Kanzow, 2011. "Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems," Computational Optimization and Applications, Springer, vol. 50(1), pages 23-48, September.
    16. Flam, Sjur & Ruszczynski, A., 2006. "Computing Normalized Equilibria in Convex-Concave Games," Working Papers 2006:9, Lund University, Department of Economics.
    17. Krawczyk, Jacek & Zuccollo, James, 2006. "NIRA-3: An improved MATLAB package for finding Nash equilibria in infinite games," MPRA Paper 1119, University Library of Munich, Germany.
    18. Jacek B. Krawczyk & Mabel Tidball, 2016. "Economic Problems with Constraints: How Efficiency Relates to Equilibrium," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 18(04), pages 1-19, December.
    19. Masao Fukushima, 2011. "Restricted generalized Nash equilibria and controlled penalty algorithm," Computational Management Science, Springer, vol. 8(3), pages 201-218, August.
    20. Nils Langenberg, 2012. "Interior point methods for equilibrium problems," Computational Optimization and Applications, Springer, vol. 53(2), pages 453-483, 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:143:y:2009:i:1:d:10.1007_s10957-009-9553-0. 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.