On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method. (English) Zbl 1282.90201
Summary: Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a \(partial\) variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C90 | Applications of mathematical programming |
| 91A10 | Noncooperative games |
| 91A40 | Other game-theoretic models |
Software:
PATH SolverReferences:
| [1] | Alpcan, T., Başar, T.: Distributed algorithms for Nash equilibria of flow control games. In: Advances in Dynamic Games, Annals of the International Society of Dynamic Games, vol. 7, pp. 473-498. Birkhäuser, Boston (2003) · Zbl 1123.91008 |
| [2] | Arrow K.J., Debreu G.: Existence of an equilibrium for a competitive economy. Econometrica 22, 265-290 (1954) · Zbl 0055.38007 · doi:10.2307/1907353 |
| [3] | Bunn D.W., Oliveira F.S.: Modeling the impact of market interventions on the strategic evolution of electricity markets. Oper. Res. 56, 1116-1130 (2008) · Zbl 1167.91398 · doi:10.1287/opre.1080.0565 |
| [4] | Cao M., Ferris M.C.: Lineality removal for copositive-plus normal maps. Commun. Appl. Nonlinear Anal. 2, 1-10 (1995) · Zbl 0857.90125 |
| [5] | Cao M., Ferris M.C.: A pivotal method for affine variational inequalities. Math. Oper. Res. 21, 44-64 (1996) · Zbl 0846.90110 · doi:10.1287/moor.21.1.44 |
| [6] | Contreras, J., Krawczyk, J.B., Zuccollo, J.: Generation games with coupled transmission and emission constraints. In: 2010 7th International Conference on the European Energy Market (EEM), pp. 1-6. (2010) |
| [7] | Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. SIAM Classics in Applied Mathematics 60, Philadelphia (2009). [Originally published by Academic Press, Boston (1992)] · Zbl 0757.90078 |
| [8] | Dirkse S.P., Ferris M.C.: The PATH solver: a non-monotone stabilization scheme for mixed complementarity problems. Optim. Methods Softw. 5, 123-156 (1995) · doi:10.1080/10556789508805606 |
| [9] | Dreves A., Facchinei F., Kanzow C., Sagratella S.: On the solution of the KKT conditions of generalized Nash equilibrium problems. SIAM J. Optim. 21, 1082-1108 (2010) · Zbl 1230.90176 · doi:10.1137/100817000 |
| [10] | Eaves B.C.: The linear complementarity problem. Manag. Sci. 17, 612-634 (1971) · Zbl 0228.15004 · doi:10.1287/mnsc.17.9.612 |
| [11] | Eaves B.C.: Polymatrix games with joint constraints. SlAM J. Appl. Math. 24, 418-423 (1973) · Zbl 0253.90067 · doi:10.1137/0124043 |
| [12] | Eaves, B.C.: A short course in solving equations with PL homotopies. In: Cottle, R.W., Lemke, C.E. (eds.) Nonlinear Programming. SIAM-AMS Proceedings, American Mathematical Society, vol. 9, pp. 73-143. Providence (1976) · Zbl 0343.47048 |
| [13] | Eaves, B. C.; Mangasarian, O. L. (ed.); Meyer, R. R. (ed.); Robinson, S. M. (ed.), Computing stationary points, again, No. 3, 391-405 (1978), New York · Zbl 0458.65057 |
| [14] | Eaves B.C.: Computing stationary points. Math. Program. Study 7, 1-14 (1978) · Zbl 0379.90081 · doi:10.1007/BFb0120778 |
| [15] | Facchinei F., Kanzow C.: Generalized Nash equilibrium problems. 4OR 5, 173-210 (2007) · Zbl 1211.91162 · doi:10.1007/s10288-007-0054-4 |
| [16] | Facchinei F., Kanzow C.: Penalty methods for the solution of generalized Nash equilibrium problems. SIAM J. Optim. 20, 2228-2253 (2010) · Zbl 1211.90228 · doi:10.1137/090749499 |
| [17] | Facchinei F., Pang J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. vols. I and II. Springer, New York (2003) · Zbl 1062.90002 |
| [18] | Facchinei, F.; Pang, J. S.; Eldar, Y. (ed.); Palomar, D. (ed.), Nash equilibria: the variational approach, 443-493 (2009), Cambridge · Zbl 1210.91008 |
| [19] | Ferris M.C., Munson T.S.: Interfaces to PATH 3.0: design, implementation and usage. Comput. Optim. Appl. 12, 207-227 (1999) · Zbl 1040.90549 · doi:10.1023/A:1008636318275 |
| [20] | Fukushima M.: Restricted generalized Nash equilibria and controlled penalty algorithm. Comput. Manag. Sci. 8(3), 201-218 (2011) · Zbl 1253.91010 · doi:10.1007/s10287-009-0097-4 |
| [21] | Haurie A., Krawczyk J.B.: Optimal charges on river effluent from lumped and distributed sources. Environ. Model. Assess. 2, 93-106 (1997) · doi:10.1023/A:1019049008557 |
| [22] | von Heusinger, A., Kanzow, C., Fukushima, M.: Newton’s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation. Math. Program. (2011) in print · Zbl 1237.91021 |
| [23] | Hobbs B.F.: Linear complementarity models of Nash-Cournot competition in bilateral and poolco power markets. IEEE Trans. Power Syst. 16, 194-202 (2001) · doi:10.1109/59.918286 |
| [24] | Hobbs B.F., Pang J.S.: Nash-Cournot equilibria in electric power markets with piecewise linear demand functions and joint constraints. Oper. Res. 55, 113-127 (2007) · Zbl 1167.91356 · doi:10.1287/opre.1060.0342 |
| [25] | Jorgensen S., Martín-Herrán G., Zaccour G.: Dynamic games in the economics and management of pollution. Environ. Model. Assess. 15, 433-467 (2010) · doi:10.1007/s10666-010-9221-7 |
| [26] | Kannan, A., Shanbhag, U.V., Kim, H.M.: Addressing supply-side risk in uncertain power markets: stochastic generalized Nash models, scalable algorithms and error analysis. Optim. Methods Softw (2012). doi:10.1080/10556788.2012.676756 · Zbl 1278.91077 |
| [27] | Kannan A., Shanbhag U.V., Kim H.M.: Strategic behavior in power markets under uncertainty. Energy Syst. 2, 115-141 (2011) · doi:10.1007/s12667-011-0032-y |
| [28] | Krawczyk J.B.: Coupled constraint Nash equilibria in environmental games. Resour. Energy Econ. 27, 157-181 (2005) · doi:10.1016/j.reseneeco.2004.08.001 |
| [29] | Krawczyk J.B.: Numerical solutions to couple-constraint (or generalized): Nash equilibrium problems. Comput. Manag. Sci. 4, 183-204 (2007) · Zbl 1134.91303 · doi:10.1007/s10287-006-0033-9 |
| [30] | Krawczyk J.B., Uryasev S.: Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assess. 5, 63-73 (2000) · doi:10.1023/A:1019097208499 |
| [31] | Kubota K., Fukushima M.: Gap function approach to the generalized Nash equilibrium problem. J. Optim. Theory Appl. 144, 511-531 (2010) · Zbl 1188.91021 · doi:10.1007/s10957-009-9614-4 |
| [32] | Kukarni A.A., Shanbhag U.V.: On the variational equilibrium as a refinement of the generalized Nash equilibrium. Automatica 48, 45-55 (2012) · Zbl 1245.91006 · doi:10.1016/j.automatica.2011.09.042 |
| [33] | Kukarni A.A., Shanbhag U.V.: Revisiting generalized Nash games and variational inequalities. J. Optim. Theory Appl. 154(1), 1-12 (2012) · Zbl 1267.90138 · doi:10.1007/s10957-012-9993-9 |
| [34] | Lemke C.E.: Bimatrix equilibrium points and mathematical programming. Manag. Sci. 11, 681-689 (1965) · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681 |
| [35] | Metzler C., Hobbs B.F., Pang J.S.: Nash-cournot equilibria in power markets on a linearized dc network with arbitrage: formulations and properties. Netw. Spatial Theory 3, 123-150 (2003) · doi:10.1023/A:1023907818360 |
| [36] | Myerson R.B.: Game Theory: Analysis of Conflict. Harvard University Press, Cambridge (1997) · Zbl 0729.90092 |
| [37] | Myerson R.B.: Refinements of the Nash equilibrium concept. Int. J. Game Theory 7, 73-80 (1978) · Zbl 0392.90093 · doi:10.1007/BF01753236 |
| [38] | Nabetani K., Tseng P., Fukushima M.: Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints. Comput. Optim. Appl. 48(3), 423-452 (2011) · Zbl 1220.90136 · doi:10.1007/s10589-009-9256-3 |
| [39] | Nash J.F. Jr: Equilibrium points in n-person games. Proc. Nat. Acad. Sci. 36, 48-49 (1950) · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48 |
| [40] | Nash J.F. Jr: Non-cooperative games. Ann. Math. 54, 286-295 (1951) · Zbl 0045.08202 · doi:10.2307/1969529 |
| [41] | Nisan N., Roughgarden T., Tardos E., Vazirani V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007) · Zbl 1130.91005 · doi:10.1017/CBO9780511800481 |
| [42] | Orda A., Rom R., Shimkin N.: Competitive routing in multiuser communication networks. IEEE ACM Trans. Netw. 1, 510-521 (1993) · doi:10.1109/90.251910 |
| [43] | Pan Y., Pavel L.: Games with coupled propagated constraints in optical network with multi-link topologies. Automatica 45, 871-880 (2009) · Zbl 1162.91326 · doi:10.1016/j.automatica.2008.11.007 |
| [44] | Pang, J.S.: Computing generalized Nash equilibria. Unpublished manuscript (2002). Available on request from the author |
| [45] | Pang, J.S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21-56 (2005). [Erratum, ibid. 6, 373-375 (2009)] · Zbl 1115.90059 |
| [46] | Pang J.S., Han L., Ramadurai G., Ukkusuri S.: A continuous-time dynamic equilibrium model for multi-user class single bottleneck traffic flows. Math. Program. 133(1-2), 437-460 (2012) · Zbl 1295.90094 · doi:10.1007/s10107-010-0433-z |
| [47] | Pang J.S., Scutari G.: Nonconvex games with side constraints. SIAM J. Optim. 21(4), 1491-1522 (2011) · Zbl 1246.91022 · doi:10.1137/100811787 |
| [48] | Pang J.S., Sun J.: Nash-Cournot equilibria with piecewise quadratic costs. Pac. J. Optim. 2, 679-692 (2006) · Zbl 1107.91009 |
| [49] | Pavel L.: A noncooperative game approach to OSNR optimization in optical networks. IEEE Trans. Autom. Control 51, 848-852 (2006) · Zbl 1366.91010 · doi:10.1109/TAC.2006.875009 |
| [50] | Rosen J.: Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33, 520-534 (1965) · Zbl 0142.17603 · doi:10.2307/1911749 |
| [51] | Selten R.: Reexamination of the perfectness concept for equilibrium points in extensive games. Int. J. Game Theory 4, 25-55 (1975) · Zbl 0312.90072 · doi:10.1007/BF01766400 |
| [52] | Tidball M., Zaccour G.: An environmental game with coupling constraints. Environ. Model. Assess. 10, 153-158 (2005) · doi:10.1007/s10666-005-5254-8 |
| [53] | Wei T.Y., Smeers Y.: Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices. Oper. Res. 47, 102-112 (1999) · Zbl 1175.91080 · doi:10.1287/opre.47.1.102 |
| [54] | Yin H., Shanbhag U.V., Mehta P.G.: Nash equilibrium problems with scaled congestion costs and shared constraint. IEEE Trans. Autom. Control 56, 1702-1708 (2011) · Zbl 1368.93635 · doi:10.1109/TAC.2010.2091830 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
