Generalized Nash equilibrium problems. (English) Zbl 1211.91162

Facchinei, Francisco; Kanzow, Christian

4OR 5, No. 3, 173-210 (2007).

Summary: The generalized Nash equilibrium problem is an important model that has its roots in the economic sciences but is being fruitfully used in many different fields. In this survey paper we aim at discussing its main properties and solution algorithms, pointing out what could be useful topics for future research in the field.

MSC:

91B52	Special types of economic equilibria
90C33	Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
91A10	Noncooperative games
91-02	Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance

Keywords:

generalized Nash equilibrium problem; equilibrium; jointly convex constraints; Nikaido-Isoda-function; variational inequality; quasi-variational inequality

Software:

PATH Solver

References:

[1]	Adida E, Perakis G (2006a) Dynamic pricing and inventory control: uncertainty and competition. Part A: existence of Nash equilibrium. Technical Report, Operations Research Center, Sloan School of Management, MIT · Zbl 1134.90002
[2]	Adida E, Perakis G (2006b) Dynamic pricing and inventory control: uncertainty and competition. Part B: an algorithm for the normalized Nash equilibrium. Technical Report, Operations Research Center, Sloan School of Management, MIT · Zbl 1134.90002
[3]	Altman E and Wynter L (2004). Equilibrium games and pricing in transportation and telecommunication networks. Netw Spat Econ 4: 7–21 · Zbl 1094.91003
[4]	Altman E, Pourtallier O, Haurie A and Moresino F (2000). Approximating Nash equilibria in nonzero-sum games. Int Game Theory Rev 2: 155–172 · Zbl 0981.91002
[5]	Antipin AS (2000a). Solution methods for variational inequalities with coupled contraints. Computat Math Math Phys 40: 1239–1254 · Zbl 0999.65055
[6]	Antipin AS (2000b). Solving variational inequalities with coupling constraints with the use of differential equations. Differential Equations 36: 1587–1596 · Zbl 1016.49011
[7]	Antipin AS (2001). Differential equations for equilibrium problems with coupled constraints. Nonlinear Anal 47: 1833–1844 · Zbl 1042.90616
[8]	Arrow KJ and Debreu G (1954). Existence of an equilibrium for a competitive economy. Econometrica 22: 265–290 · Zbl 0055.38007
[9]	Aubin JP (1993). Optima and equilibria. Springer, Berlin
[10]	Aubin JP and Frankowska H (1990). Set-valued analysis. Birkhäuser, Boston · Zbl 0713.49021
[11]	Başar T, Olsder GJ (1989) Dynamic noncooperative game theory, 2nd edn. Academic Press, London (reprinted in SIAM Series ”Classics in Applied Mathematics”, 1999)
[12]	Bassanini A, La Bella A and Nastasi A (2002). Allocation of railroad capacity under competition: a game theoretic approach to track time pricing. In: Gendreau, M and Marcotte, P (eds) Transportation and networks analysis: current trends, pp 1–17. Kluwer, Dordrecht · Zbl 1048.90059
[13]	Baye MR, Tian G and Zhou J (1993). Characterization of existence of equilibria in games with discontinuous and non-quasiconcave payoffs. Rev Econ Stud 60: 935–948 · Zbl 0798.90137
[14]	Bensoussan A (1974). Points de Nash dans le cas de fonctionnelles quadratiques et jeux differentiels lineaires a N personnes. SIAM J Control 12: 460–499 · Zbl 0286.90066
[15]	Berridge S, Krawczyk JB (1997) Relaxation algorithms in finding Nash equilibria. Economic working papers archives, http://econwpa.wustl.edu/eprints/comp/papers/9707/9707002.abs
[16]	Bertrand J (1883) Review of ”Théorie mathématique de la richesse sociale” by Léon Walras and ”Recherches sur les principes mathématiques de la théorie des richesses” by Augustin Cournot. J des Savants 499–508
[17]	Breton M, Zaccour G and Zahaf M (2005). A game-theoretic formulation of joint implementation of environmental projects. Eur J Oper Res 168: 221–239 · Zbl 1131.91370
[18]	Cavazzuti E and Pacchiarotti N (1986). Convergence of Nash equilibria. Boll UMI 5B: 247–266 · Zbl 0603.90142
[19]	Cavazzuti E, Pappalardo M and Passacantando M (2002). Nash equilibria, variational inequalities, and dynamical systems. J Optim Theory Appl 114: 491–506 · Zbl 1020.49003
[20]	Chan D and Pang JS (1982). The generalized quasi-variational inequality problem. Math Oper Res 7: 211–222 · Zbl 0502.90080
[21]	Contreras J, Klusch MK and Krawczyk JB (2004). Numerical solution to Nash-Cournot equilibria in coupled constraints electricity markets. IEEE Trans Power Syst 19: 195–206
[22]	Cournot AA (1838). Recherches sur les principes mathématiques de la théorie des richesses. Hachette, Paris
[23]	Dafermos S (1990). Exchange price equilibria and variational inequalities. Math Programming 46: 391–402 · Zbl 0709.90013
[24]	van Damme E (1996). Stability and perfection of Nash equilibria, 2nd edn. Springer, Berlin · Zbl 0899.90167
[25]	Dasgupta P and Maskin E (1986a). The existence of equilibrium in discontinuous economic games, I: theory. Rev Econ Stud 53: 1–26 · Zbl 0578.90098
[26]	Dasgupta P and Maskin E (1986b). The existence of equilibrium in discontinuous economic games, II: applications. Rev Econ Stud 53: 27–41 · Zbl 0578.90099
[27]	Debreu G (1952). A social equilibrium existence theorem. Proc Natl Acad Sci 38: 886–893 · Zbl 0047.38804
[28]	Debreu G (1959). Theory of value. Yale University Press, New Haven · Zbl 0193.20205
[29]	Debreu G (1970). Economies with a finite set of equilibria. Econometrica 38: 387–392 · Zbl 0253.90009
[30]	Dirkse SP and Ferris MC (1995). The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems. Optim Methods Softw 5: 123–156
[31]	Ehrenmann A (2004) Equilibrium problems with equilibrium constraints and their application to electricity markets. Ph.D. Dissertation, Judge Institute of Management, The University of Cambridge, Cambridge
[32]	Facchinei F, Kanzow C (2007) Globally convergent methods for the generalized Nash equilibrium problem based on exact penalization. Technical Report, University of Würzburg, Würzburg, (in press) · Zbl 1211.91162
[33]	Facchinei F and Pang JS (2003). Finite-dimensional variational inequalities and complementarity problems. Springer, New York · Zbl 1062.90002
[34]	Facchinei F and Pang JS (2006). Exact penalty functions for generalized Nash problems. In: Di Pillo, G and Roma, M (eds) Large-scale nonlinear optimization., pp 115–126. Springer, Heidelberg · Zbl 1201.91006
[35]	Facchinei F, Fischer A and Piccialli V (2007a). On generalized Nash games and variational inequalities. Oper Res Lett 35: 159–164 · Zbl 1303.91020
[36]	Facchinei F, Fischer A, Piccialli V (2007b) Generalized Nash equilibrium problems and Newton methods. Math Programming (in press); doi: 10.1007/s10107-007-0160-2 · Zbl 1166.90015
[37]	Facchinei F, Piccialli V, Sciandrone M (2007c) On a class of generalized Nash equilibrium problems. DIS Technical Report, ”Sapienza” Università di Roma, Rome, (in press) · Zbl 1237.91017
[38]	Flåm SD (1993). Paths to constrained Nash equilibria. Appl Math Optim 27: 275–289 · Zbl 0805.90122
[39]	Flåm SD (1994). On variational stability in competitive economies. Set Valued Anal 2: 159–173 · Zbl 0837.90018
[40]	Flåm SD, Ruszczyński A (1994) Noncooperative convex games: computing equilibrium by partial regularization. IIASA Working Paper 94-42, Laxenburg
[41]	Fudenberg D and Tirole J (1991). Game theory. MIT Press, Cambridge · Zbl 0596.90015
[42]	Fukushima M (2007). A class of gap functions for quasi-variational inequality problems. J Ind Manage Optim 3: 165–171 · Zbl 1170.90487
[43]	Fukushima M and Pang JS (2005). Quasi-variational inequalities, generalized Nash equilibria and multi-leader-follower games. Comput Manage Sci 2: 21–56 · Zbl 1115.90059
[44]	Gabriel S, Smeers Y (2006) Complementarity problems in restructured natural gas markets, in Recent Advances in Optimization. Lectures Notes in Economics and Mathematical Systems 563, Springer, Heidelberg, pp 343–373 · Zbl 1101.90396
[45]	Gabriel SA, Kiet S and Zhuang J (2005). A mixed complementarity-based equilibrium model of natural gas markets. Oper Res 53: 799–818 · Zbl 1165.91449
[46]	Garcia CB and Zangwill WI (1981). Pathways to solutions, fixed points and equilibria. Prentice-Hall, New Jersey · Zbl 0512.90070
[47]	Gürkan G, Pang JS (2006) Approximations of Nash equilibria. Technical Report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy
[48]	Harker PT (1991). Generalized Nash games and quasi-variational inequalities. Eur J Oper Res 54: 81–94 · Zbl 0754.90070
[49]	Harker PT and Hong S (1994). Pricing of track time in railroad operations: an internal market approach. Transport Res B 28: 197–212
[50]	Haurie A and Krawczyk JB (1997). Optimal charges on river effluent from lumped and distributed sources. Environ Model Assess 2: 93–106
[51]	von Heusinger A, Kanzow C (2006) Optimization reformulations of the generalized Nash equilibrium problem using Nikaido–Isoda-type functions. Technical Report, Institute of Mathematics, University of Würzburg, Würzburg · Zbl 1170.90495
[52]	von Heusinger A, Kanzow C (2007) SC1 optimization reformulations of the generalized Nash equilibrium problem. Technical Report, Institute of Mathematics, University of Würzburg, Würzburg · Zbl 1154.91356
[53]	Hobbs B and Pang JS (2007). Nash-Cournot equilibria in electric power markets with piecewise linear demand functions and joint constraints. Oper Res 55: 113–127 · Zbl 1167.91356
[54]	Hobbs B, Helman U, Pang JS (2001) Equilibrium market power modeling for large scale power systems. IEEE Power Engineering Society Summer Meeting. pp 558–563
[55]	Hotelling H (1929). Game theory for economic analysis. Econ J 39: 41–47
[56]	Hu X, Ralph D (2006) Using EPECs to model bilevel games in restructured electricity markets with locational prices. Technical Report CWPE 0619 · Zbl 1167.91357
[57]	Ichiishi T (1983). Game theory for economic analysis. Academic, New York · Zbl 0522.90104
[58]	Jiang H (2007). Network capacity management competition, Technical Report. Judge Business School at University of Cambridge, UK
[59]	Jofré A and Wets RJB (2002). Continuity properties of Walras equilibrium points. Ann Oper Res 114: 229–243 · Zbl 1026.91031
[60]	Kesselman A, Leonardi S, Bonifaci V (2005) Game-theoretic analysis of internet switching with selfish users. In: Proceedings of the first international workshop on internet and network economics. WINE 2005, Lectures Notes in Computer Science 3828:236–245
[61]	Kočvara M and Outrata JV (1995). On a class of quasi-variational inequalities. Optim Methods Softw 5: 275–295
[62]	Krawczyk JB (2000) An open-loop Nash equilibrium in an environmental game with coupled constraints. In: Proceedings of the 2000 symposium of the international society of dynamic games. Adelaide, pp 325–339
[63]	Krawczyk JB (2005). Coupled constraint Nash equilibria in environmental games. Resour Energy Econ 27: 157–181
[64]	Krawczyk JB (2007). Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems. Comput Manage Sci 4: 183–204 · Zbl 1134.91303
[65]	Krawczyk JB and Uryasev S (2000). Relaxation algorithms to find Nash equilibria with economic applications. Environ Model Assess 5: 63–73
[66]	Laffont J and Laroque G (1976). Existence d’un équilibre général de concurrence imparfait: Une introduction. Econometrica 44: 283–294 · Zbl 0365.90029
[67]	Leyffer S, Munson T (2005) Solving multi-leader-follower games. Argonne National Laboratory Preprint ANL/MCS-P1243-0405, Illinois · Zbl 1201.90187
[68]	Margiocco M, Patrone F and Pusilli Chicco L (1997). A new approach to Tikhonov well-posedness for Nash equilibria. Optimization 40: 385–400 · Zbl 0881.90136
[69]	Margiocco M, Patrone F and Pusilli Chicco L (1999). Metric characterization of Tikhonov well-posedness in value. J Optim Theory Appl 100: 377–387 · Zbl 0915.90271
[70]	Margiocco M, Patrone F and Pusilli Chicco L (2002). On the Tikhonov well-posedness of concave games and Cournot oligopoly games. J Optim Theory Appl 112: 361–379 · Zbl 1011.91004
[71]	Morgan J, Scalzo V (2004) Existence of equilibria in discontinuous abstract economies. Preprint 53-2004, Dipartimento di Matematica e Applicazioni R. Caccioppoli · Zbl 1090.91006
[72]	Morgan J, Scalzo V (2007) Variational stability of social Nash equilibria. Int Game Theory Rev 9 (in press) · Zbl 1280.91010
[73]	Munson TS, Facchinei F, Ferris MC, Fischer A and Kanzow C (2001). The semismooth algorithm for large scale complementarity problems. INFORMS J Comput 13: 294–311 · Zbl 1238.90123
[74]	Myerson RB (1991). Game theory. Analysis of conflict. Harvard University Press, Cambridge · Zbl 0729.90092
[75]	Nash JF (1950). Equilibrium points in n-person games. Proc Natl Acad Sci 36: 48–49 · Zbl 0036.01104
[76]	Nash JF (1951). Non-cooperative games. Ann Math 54: 286–295 · Zbl 0045.08202
[77]	Neumann J (1928). Zur Theorie der Gesellschaftsspiele. Math Ann 100: 295–320 · JFM 54.0543.02
[78]	Morgenstern O and Neumann J (1944). Theory of games and economic behavior. Princeton University Press, Princeton · Zbl 0063.05930
[79]	Nikaido H (1975). Monopolistic competition and effective demand. Princeton University Press, Princeton · Zbl 0395.90001
[80]	Nikaido H and Isoda K (1955). Note on noncooperative convex games. Pac J Math 5: 807–815 · Zbl 0171.40903
[81]	Nishimura K and Friedman J (1981). Existence of Nash equilibrium in n person games without quasi-concavity. Int Econ Rev 22: 637–648 · Zbl 0478.90086
[82]	Outrata JV, Kočvara M and Zowe J (1998). Nonsmooth approach to optimization problems with equilibrium constraints. Kluwer, Dordrecht · Zbl 0947.90093
[83]	Pang JS (2002) Computing generalized Nash equilibria. Manuscript
[84]	Pang JS and Qi L (1993). Nonsmooth equations: motivation and algorithms. SIAM J Optim 3: 443–465 · Zbl 0784.90082
[85]	Pang JS and Yao JC (1995). On a generalization of a normal map and equation. SIAM J Control Optim 33: 168–184 · Zbl 0827.90131
[86]	Pang JS, Scutari G, Facchinei F, Wang C (2007) Distributed power allocation with rate contraints in Gaussian frequency-selective interference channels. DIS Technical Report 05-07, ”Sapienza” Università di Roma, Rome
[87]	Puerto J, Schöbel A, Schwarze S (2005) The path player game: introduction and equilibria. Preprint 2005-18, Georg-August University of Göttingen, Göttingen · Zbl 1156.91326
[88]	Qi L (1993). Convergence analysis of some algorithms for solving nonsmooth equations. Math Oper Res 18: 227–244 · Zbl 0776.65037
[89]	Qi L and Sun J (1993). A nonsmooth version of Newton’s method. Math Programming 58: 353–367 · Zbl 0780.90090
[90]	Rao SS, Venkayya VB and Khot NS (1988). Game theory approach for the integrated design of structures and controls. AIAA J 26: 463–469 · Zbl 0663.73063
[91]	Reny PJ (1999). On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica 67: 1026–1056 · Zbl 1023.91501
[92]	Robinson SM (1993a). Shadow prices for measures of effectiveness. I. Linear model. Oper Res 41: 518–535 · Zbl 0800.90666
[93]	Robinson SM (1993b). Shadow prices for measures of effectiveness. II. General model. Oper Res 41: 536–548 · Zbl 0800.90667
[94]	Rockafellar RT and Wets RJB (1998). Variational analysis. Springer, Berlin
[95]	Rosen JB (1965). Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33: 520–534 · Zbl 0142.17603
[96]	Schmit LA (1981). Structural synthesis–its genesis and development. AIAA J 19: 1249–1263
[97]	Scotti SJ (1995) Structural design using equilibrium programming formulations. NASA Technical Memorandum 110175
[98]	Stoer J and Bulirsch R (2002). Introduction to numerical analysis, 3rd edn. Springer, New York · Zbl 1004.65001
[99]	Sun LJ and Gao ZY (2007). An equilibrium model for urban transit assignment based on game theory. Eur J Oper Res 181: 305–314 · Zbl 1121.90029
[100]	Tian G and Zhou J (1995). Transfer continuities, generalizations of the Weierstrass and maximum theorems: a full characterization. J Math Econ 24: 281–303 · Zbl 0895.90035
[101]	Tidball M and Zaccour G (2005). An environmental game with coupling constraints. Environ Model Assess 10: 153–158
[102]	Uryasev S and Rubinstein RY (1994). On relaxation algorithms in computation of noncooperative equilibria. IEEE Trans Automatic Control 39: 1263–1267 · Zbl 0811.90117
[103]	Vincent TL (1983). Game theory as a design tool. ASME J Mech Trans Autom Design 105: 165–170
[104]	Vives X (1994). Nash equilibrium with strategic complementarities. J Math Econ 19: 305–321 · Zbl 0708.90094
[105]	Walras L (1900) Éléments d’économie politique pure. Lausanne
[106]	Wei JY and Smeers Y (1999). Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices. Oper Res 47: 102–112 · Zbl 1175.91080
[107]	Zhou J, Lam WHK and Heydecker BG (2005). The generalized Nash equilibrium model for oligopolistic transit market with elastic demand. Transport Res B 39: 519–544