A Shared-Constraint Approach to Multi-Leader Multi-Follower Games
Tóm tắt
Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.
Tài liệu tham khảo
Allaz, B., Vila, J.-L.: Cournot competition, forward markets and efficiency. J. Econ. Theory 59
Arrow, K., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22(3), 265–290 (1954)
Başar, T., Olsder, G.: Dynamic Noncooperative Game Theory. Classics in Applied Mathematics. SIAM, Philadelphia (1999)
DeMiguel, V., Xu H.: A stochastic multiple-meader Stackelberg model: Analysis, computation, and application. Oper. Res. 57(5), 1220–1235 (2009)
Eilenberg, S., Montgomery, D.: Fixed point theorems for multi-valued transformations. Am. J. Math. 68(2), 214–222 (1946)
Escobar, J.F., Jofré, A.: Equilibrium analysis of electricity auctions. Department of Economics Stanford University (2008)
Facchinei, F., Fischer, A., Piccialli, V.: On generalized Nash games and variational inequalities. Oper. Res. Lett. 35(2), 159–164 (2007)
Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. 4OR: A Q. J. Oper. Res. 5(3), 173–210 (2007)
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems I, 1st edn. Springer, New York (2003)
Facchinei, F., Pang, J.-S.: Nash equilibria: The variational approach. In: Convex Optimization in Signal Processing and Communication, chapter 12, pp 443–495. Cambridge University Press, Cambridge (2009)
Flegel, M.L., Kanzow, C, Outrata, J.: Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints (2007)
Fletcher, R, Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of SQP methods for mathematical programs with equilibrium constraints. Technical report, Department of Mathematics, University of Dundee, UK, Numerical Analysis Report NA/209. (2002)
Henrion, R., Outrata, J., Surowiec, T.: A note on the relation between strong and m-stationarity for a class of mathematical programs with equilibrium constraints. Kybernetika 46(3), 423–434 (2010)
Henrion, R., Outrata, J., Surowiec, T.: Analysis of m-stationary points to an EPEC modeling oligopolistic competition in an electricity spot market. ESAIM: Control Optim. Calc. Var. 1(1), 2009
Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15(3), 591–603 (1973)
Hu, X., Ralph, D.: Using EPECs to model bilevel games in restructured electricity markets with locational prices. Oper. Res. 55(5), 809–827 (2007)
Kulkarni, A.A., Shanbhag, U.V.: New insights on generalized Nash games with shared constraints: Constrained and variational equilibria. In: Proceedings of the 48th IEEE Conference on Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009, pp. 151–156 (2009)
Kulkarni, A.A., Shanbhag, U.V.: On the variational equilibrium as a refinement of the generalized Nash equilibrium. Automatica 48(1), 45–55 (2012)
Kulkarni, A.A., Shanbhag, U.V.: Revisiting generalized Nash games and variational inequalities. J. Optim. Theory Appl. 154(1), 1–12 (2012)
Kulkarni, A.A., Shanbhag, U.V.: An existence result for hierarchical Stackelberg v/s Stackelberg games. Accepted Subject to Minor Modifications in the IEEE Transactions on Automatic Control. Available Online: arXiv:1401.0186 (2014)
Leyffer, S., Munson, T.: Solving multi-leader-common-follower games. Optim. Methods Softw. 25(4), 601–623 (2010)
Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124–143 (1996)
Murphy, F., Smeers, Y.: On the impact of forward markets on investments in oligopolistic markets with reference to electricity. Oper. Res. 58(3), 515–528 (2010). Supplementary data available online
Okuguchi, K.: Expectations and stability in oligopoly models. In: Lecture Notes in Economics and Mathematical Systems, p 138. Springer-Verlag, Berlin (1976)
Outrata, J., Kočvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, volume 28 of Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht (1998). Theory, applications and numerical results
Outrata, J.V.: A note on a class of equilibrium problems with equilibrium constraints. Kybernetika 40(5), 585–594 (2004)
Pang, J.-S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2(1), 21–56 (2005)
Pang, J.-S., Scutari, G.: Nonconvex games with side constraints. SIAM J. Optim. 21(4), 1491–1522 (2011)
Rosen, J.B.: Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33(3), 520–534 (1965)
Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: Stationarity, optimality and sensitivity. Math. Oper. Res. 25, 1–22 (2000)
Selten, R.: Reexamination of the perfectness concept for equilibrium points in extensive games. Int. J. Game Theory 4(1), 25–55 (1975)
Shanbhag, U.V., Infanger, G., Glynn, P.W.: A complementarity framework for forward contracting under uncertainty. Oper. Res. 59(810–834) (2011)
Sherali, H.D.: A multiple leader Stackelberg model and analysis. Oper. Res. 32(2), 390–404 (1984)
Sherali, H.D., Soyster, A.L., Murphy, F.H.: Stackelberg-Nash-Cournot equilibria: Characterizations and computations. Oper. Res. 31(2), 253–276 (1983)
Stackelberg, H.V.: The Theory of Market Economy. Oxford University Press, London (1952)
Su, C.-L.: Equilibrium Problems with Equilibrium Constraints. PhD thesis, Department of Management Science and Engineering (Operations Research), Stanford University (2005)
Su, C.-L.: Analysis on the forward market equilibrium model. Oper. Res. Lett. 35(1), 74–82 (2007)
Yao, J., Adler, I., Oren, S.S.: Modeling computing two-settlement oligopolistic equilibrium in a congested electricity network. Oper. Res. 56(1), 34–47 (2008)