A decomposition method for a class of convex generalized Nash equilibrium problems
- PDF / 2,009,838 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 105 Downloads / 209 Views
A decomposition method for a class of convex generalized Nash equilibrium problems Tangi Migot1 · Monica‑G. Cojocaru1 Received: 13 October 2019 / Revised: 8 October 2020 / Accepted: 2 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we study a numerical approach to compute a solution of the generalized Nash equilibrium problem (GNEP). The GNEP is a potent modeling tool that has been increasingly developing in recent decades. Much of this development has centered around applying variational methods to the so-called GNSC, a useful but restricted subset of GNEP where each player has the same constraint set. One popular approach to solve the GNSC is to use the apparent separability of each player to build a decomposition method. This method has the benefit of being easily implementable and can be parallelized. Our aim in this paper is to show an extension of the decomposition method to a class of convex GNEP. We prove convergence of the proposed algorithm under a full convexity assumption. Then, we show numerical results on some examples to validate our approach and discuss the assumptions. Keywords Nash equilibrium problem · Generalized Nash equilibrium problem · Quasi-variational inequality · Decomposition method
1 Introduction In the early 50’s Nash (1950), Nash introduces a notion of equilibrium, the so-called Nash equilibrium, for non-cooperative N-player games where the payoff function of each player depends on the others’ strategies. Later on, Arrow and Debreu (1954) extended this notion to the generalized Nash equilibrium for games where both the payoff function and the set of feasible strategies depend on others’ strategies. Initially motivated by economic applications, the notion of equilibrium in games has received a vivid interest thanks to its various applications in social science (Downs 1957), biology (Smith and Price 1973), computer science (Pang et al. * Tangi Migot [email protected] Monica‑G. Cojocaru [email protected] 1
University of Guelph, Guelph, Canada
13
Vol.:(0123456789)
T. Migot, M.-G. Cojocaru
2010) or energy problems (Contreras et al. 2004; Hobbs and Pang 2007; Jing-Yuan and Smeers 1999) to cite few among others. These applications have motivated the evolution of the Nash equilibrium concept, and its use, to complex games that now require a deep understanding of theoretical and computational mathematics. The study of numerical methods to compute one (or more) equilibrium of the generalized Nash equilibrium problem (GNEP) started two decades ago in the operational research community. Several approaches have been proposed in the literature: decomposition methods, (quasi)-variational inequality type methods (Aussel and Sagratella 2017; Facchinei et al. 2014; Kanzow and Steck 2019; Pang and Fukushima 2005), penalty methods (Facchinei and Pang 2006), Nikaido Isoda-function type methods (Stein and Sudermann-Merx 2016, see Nikaidô and Isoda 1955 for the definition of the NI function), ordinary differential equation based
Data Loading...
