IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2021i1p81-d711850.html
   My bibliography  Save this article

A Nikaido Isoda-Based Hybrid Genetic Algorithm and Relaxation Method for Finding Nash Equilibrium

Author

Listed:
  • Napat Harnpornchai

    (Center of Excellence in Econometrics, Faculty of Economics, Chiang Mai University, Chiang Mai 50200, Thailand)

  • Wiriyaporn Wonggattaleekam

    (Department of Agricultural Economy and Development, Faculty of Agriculture, Chiang Mai University, Chiang Mai 50200, Thailand)

Abstract

Nash Equilibrium (NE) plays a crucial role in game theory. The relaxation method in conjunction with the Nikaido–Isoda (NI) function, namely the NI-based relaxation method, has been widely applied to the determination of NE. Genetic Algorithm (GA) with adaptive penalty is introduced and incorporated in the original NI-based relaxation method. The GA enhances the capability in the optimization step for computing the optimum response function. The optimization of the non-convex and non-concave NI function is made possible by GA. The proposed method thus combines the advantageous feature of the GA in its optimization capability and that of the relaxation method in its implementation simplicity together. The applicability of the method is shown through the illustrative examples, including the generalized Nash Equilibrium problem with nonlinear payoff functions and coupled constraints, the game with multiple strategic variables for individual players, and the non-differentiable payoff functions. All test example results suggest the appropriate crossover and mutation rate to be 0.05 and 0.002 for use in GA. These numbers are closed to the recommended values by DeJong. The proposed method shows its capability of finding correct NEs in all test examples.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:10:y:2021:i:1:p:81-:d:711850
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/1/81/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/1/81/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Feng He & Wei Zhang & Guoqiang Zhang, 2016. "A Differential Evolution Algorithm Based on Nikaido-Isoda Function for Solving Nash Equilibrium in Nonlinear Continuous Games," PLOS ONE, Public Library of Science, vol. 11(9), pages 1-17, September.
    2. 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.
    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. 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. Faranak Emtehani & Nasim Nahavandi & Farimah Mokhatab Rafiei, 2023. "Trade credit financing for supply chain coordination under financial challenges: a multi-leader–follower game approach," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 9(1), pages 1-39, December.
    3. Francisco Facchinei & Christian Kanzow, 2010. "Generalized Nash Equilibrium Problems," Annals of Operations Research, Springer, vol. 175(1), pages 177-211, March.
    4. 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.
    5. Giancarlo Bigi & Mauro Passacantando, 2016. "Gap functions for quasi-equilibria," Journal of Global Optimization, Springer, vol. 66(4), pages 791-810, December.
    6. 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).
    7. 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.
    8. 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.
    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. 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.
    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.

    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:gam:jmathe:v:10:y:2021:i:1:p:81-:d:711850. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.