×

zbMATH — the first resource for mathematics

Solving chance-constrained games using complementarity problems. (English) Zbl 1360.91022
Vitoriano, Begoña (ed.) et al., Operations research and enterprise systems. 5th international conference, ICORES 2016, Rome, Italy, February 23–25, 2016. Revised selected papers. Cham: Springer (ISBN 978-3-319-53981-2/pbk; 978-3-319-53982-9/ebook). Communications in Computer and Information Science 695, 52-67 (2017).
Summary: In this paper, we formulate the random bimatrix game as a chance-constrained game using chance constraint. We show that a Nash equilibrium problem, corresponding to independent normally distributed payoffs, is equivalent to a nonlinear complementarity problem. Further, if the payoffs are also identically distributed, a strategy pair where each player’s strategy is the uniform distribution over his action set, is a Nash equilibrium. We show that a Nash equilibrium problem corresponding to independent Cauchy distributed payoffs is equivalent to a linear complementarity problem.
For the entire collection see [Zbl 1366.90002].

MSC:
91A15 Stochastic games, stochastic differential games
Software:
PATH Solver
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bazaraa, M., Sherali, H., Shetty, C.: Nonlinear Programming Theory and Algorithms, 3rd edn. Wiley, New York (2006) · Zbl 1140.90040 · doi:10.1002/0471787779
[2] Blau, R.A.: Random-payoff two person zero-sum games. Oper. Res. 22(6), 1243–1251 (1974) · Zbl 0306.90087 · doi:10.1287/opre.22.6.1243
[3] Cassidy, R.G., Field, C.A., Kirby, M.J.L.: Solution of a satisficing model for random payoff games. Manage. Sci. 19(3), 266–271 (1972) · Zbl 0262.90073 · doi:10.1287/mnsc.19.3.266
[4] Charnes, A., Cooper, W.W.: Deterministic equivalents for optimizing and satisficing under chance constraints. Oper. Res. 11(1), 18–39 (1963) · Zbl 0117.15403 · doi:10.1287/opre.11.1.18
[5] Charnes, A., Kirby, M.J.L., Raike, W.M.: Zero-zero chance-constrained games. Theory Probab. Appl. 13(4), 628–646 (1968) · Zbl 0206.23201 · doi:10.1137/1113079
[6] Cheng, J., Lisser, A.: A second-order cone programming approach for linear programs with joint probabilistic constraints. Oper. Res. Lett. 40(5), 325–328 (2012) · Zbl 1250.90060 · doi:10.1016/j.orl.2012.06.008
[7] Collins, W.D., Hu, C.: Studying interval valued matrix games with fuzzy logic. Soft. Comput. 12, 147–155 (2008) · Zbl 1152.91312 · doi:10.1007/s00500-007-0207-6
[8] Couchman, P., Kouvaritakis, B., Cannon, M., Prashad, F.: Gaming strategy for electric power with random demand. IEEE Trans. Power Syst. 20(3), 1283–1292 (2005) · doi:10.1109/TPWRS.2005.851954
[9] DeMiguel, V., Xu, H.: A stochastic multiple leader stackelberg model: analysis, computation, and application. Oper. Res. 57(5), 1220–1235 (2009) · Zbl 1233.91062 · doi:10.1287/opre.1080.0686
[10] Li, D.-F., Nan, J.-X., Zhang, M.J.: Interval programming models for matrix games with interval payoffs. Optim. Meth. Softw. 27(1), 1–16 (2012) · Zbl 1237.91011 · doi:10.1080/10556781003796622
[11] Ferris, M.C., Munson, T.S.: Complementarity problems in GAMS and the PATH solver. J. Econ. Dyn. Control 24, 165–188 (2000) · Zbl 1002.90070 · doi:10.1016/S0165-1889(98)00092-X
[12] Jadamba, B., Raciti, F.: Variational inequality approach to stochastic Nash equilibrium problems with an application to cournot oligopoly. J. Optim. Theor. Appl. 165(3), 1050–1070 (2015) · Zbl 1316.49012 · doi:10.1007/s10957-014-0673-9
[13] Johnson, N.L., Kotz, S., Balakrishnan, N.: Continuous Univariate Distributions, vol. 1, 2nd edn. Wiley, New York (1994) · Zbl 0811.62001
[14] Katzwer, R.: Lemke-Howson Algorithm for 2-Player Games (2013). File ID: #44279 Version: 1.3
[15] Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Manage. Sci. 11(7), 681–689 (1965) · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681
[16] Lemke, C., Howson, J.: Equilibrium points of bimatrix games. SIAM J. 12, 413–423 (1964) · Zbl 0128.14804
[17] Li, D.F.: Linear programming approach to solve interval-valued matrix games. J. Omega 39(6), 655–666 (2011) · doi:10.1016/j.omega.2011.01.007
[18] Mazadi, M., Rosehart, W.D., Zareipour, H., Malik, O.P., Oloomi, M.: Impact of wind integration on electricity markets: a chance-constrained Nash Cournot model. Int. Trans. Electr. Energy Syst. 23(1), 83–96 (2013) · doi:10.1002/etep.650
[19] Mitchell, C., Hu, C., Chen, B., Nooner, M., Young, P.: A computational study of interval-valued matrix games. In: International Conference on Computational Science and Computational Intelligence (2014) · doi:10.1109/CSCI.2014.66
[20] Munson, T.S.: Algorithms and environments for complementarity. Ph.D. thesis, University of Wisconsin, Madison (2000)
[21] Nash, J.F.: Equilibrium points in n-person games. Proc. Natl. Acad. Sci. 36(1), 48–49 (1950) · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48
[22] Neumann, J.V.: Zur theorie der gesellschaftsspiele. Math. Annalen 100(1), 295–320 (1928) · JFM 54.0543.02 · doi:10.1007/BF01448847
[23] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[24] Prékopa, A.: Stochastic Programming. Springer, Netherlands (1995) · doi:10.1007/978-94-017-3087-7
[25] Ravat, U., Shanbhag, U.V.: On The characterization of solution sets of smooth and nonsmooth convex stochastic Nash games. SIAM J. Optim. 21(3), 1168–1199 (2011) · Zbl 1235.90109 · doi:10.1137/100792644
[26] Schmelzer, S.: COMPASS: a free solver for mixed complementarity problems. Master’s thesis, Universität Wien (2012)
[27] Singh, V.V., Jouini, O., Lisser, A.: Existence of Nash equilibrium for chance-constrained games. Oper. Res. Lett. 44(5), 640–644 (2016) · doi:10.1016/j.orl.2016.07.013
[28] Singh, V.V., Jouini, O., Lisser, A.: Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium. Optim. Lett. (2016). doi: 10.1007/s11590-016-1077-6 · Zbl 1411.91021 · doi:10.1007/s11590-016-1077-6
[29] Song, T.: On random payoff matrix games. In: Phillips, F.Y., Rousseau, J.J. (eds.) Systems and Management Science by Extremal Methods, pp. 291–308. Springer, Heidelberg (1992) · doi:10.1007/978-1-4615-3600-0_19
[30] Valenzuela, J., Mazumdar, M.: Cournot prices considering generator availability and demand uncertainty. IEEE Trans. Power Syst. 22(1), 116–125 (2007) · doi:10.1109/TPWRS.2006.889142
[31] Wolf, D.D., Smeers, Y.: A stochastic version of a Stackelberg-Nash-Cournot equilibrium model. Manage. Sci. 43(2), 190–197 (1997) · Zbl 0889.90046 · doi:10.1287/mnsc.43.2.190
[32] Xu, H., Zhang, D.: Stochastic Nash equilibrium problems: sample average approximation and applications. Comput. Optim. Appl. 55(3), 597–645 (2013) · Zbl 1281.91046 · doi:10.1007/s10589-013-9538-7
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.