Abstract
We consider an n-player finite strategic game. The payoff vector of each player is a random vector whose distribution is not completely known. We assume that the distribution of a random payoff vector of each player belongs to a distributional uncertainty set. We define a distributionally robust chance-constrained game using worst-case chance constraint. We consider two types of distributional uncertainty sets. We show the existence of a mixed strategy Nash equilibrium of a distributionally robust chance-constrained game corresponding to both types of distributional uncertainty sets. For each case, we show a one-to-one correspondence between a Nash equilibrium of a game and a global maximum of a certain mathematical program.
Similar content being viewed by others
References
Adler, I.: The equivalence of linear programs and zero-sum games. Int. J. Game Theory 42(1), 165–177 (2013)
Bazaraa, M., Sherali, H., Shetty, C.: Nonlinear programming theory and algorithms. Wiley, USA, Third edn (2006)
Blau, R.A.: Random-payoff two person zero-sum games. Operat. Res. 22(6), 1243–1251 (1974)
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)
Charnes, A., Cooper, W.W.: Deterministic equivalents for optimizing and satisficing under chance constraints. Operat. Res. 11(1), 18–39 (1963)
Charnes, A., Kirby, M.J.L., Raike, W.M.: Zero-zero chance-constrained games. Theory Prob. Appl. 13(4), 628–646 (1968)
Cheng, J., Delage, E., Lisser, A.: Distributionally robust stochastic knapsack problem. SIAM J. Optim. 24(3), 1485–1506 (2014)
Cheng, J., Leung, J., Lisser, A.: Random-payoff two-person zero-sum game with joint chance constraints. Euro. J. Operat. Res. 252(1), 213–219 (2016)
Cheng, J., Lisser, A.: A second-order cone programming approach for linear programs with joint probabilistic constraints. Operat. Res. Lett. 40(5), 325–328 (2012)
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)
Dantzig, G.B.: A proof of the equivalence of the programming problem and the game problem. In: Koopmans, T.C. (ed.) Activity analysis of production and allocation, pp. 330–335. Wiley, New York (1951)
DeMiguel, V., Xu, H.: A stochastic multiple leader Stackelberg model: analysis, computation, and application. Operat. Res. 57(5), 1220–1235 (2009)
El-Ghaoui, L., Oks, M., Oustry, F.: Worst-case value-at-risk and robust portfolio optimization: a conic programming approach. Operat. Res. 51(4), 543–556 (2003)
Hayashi, S., Yamashita, N., Fukushima, M.: Robust Nash equilibria and second-order cone complementarity problems. J. Nonlin. Conv. Anal. 6(2), 283–296 (2005)
Jadamba, B., Raciti, F.: Variational inequality approach to stochastic Nash equilibrium problems with an application to Cournot oligopoly. J. Optim. Theory Appl. 165(3), 1050–1070 (2015)
Kakutani, S.: A generalization of Brouwer’s fixed point theorem. Duke Math. J. 8(3), 457–459 (1941)
Lee, K.H., Baldick, R.: Solving three-player games by the matrix approach with application to an electric power market. IEEE Trans. Power Syst. 18(4), 1573–1580 (2003)
Lemke, C.E., Howson, J.T.: Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12(2), 413–423 (1964)
Lepore, J.J.: Cournot outcomes under Bertrand-Edgeworth competition with demand uncertainty. J. Math. Econ. 48(3), 177–186 (2012)
Mangasarian, O.L., Stone, H.: Two-person nonzero-sum games and quadratic programming. J. Math. Anal. Appl. 9(3), 348–355 (1964)
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. Elect. Energy Syst. 23(1), 83–96 (2013)
Nash, J.F.: Equilibrium points in n-person games. Proceed. Nat. Acad. Sci. 36(1), 48–49 (1950)
Neumann, J.V.: On the theory of games. Math. Annalen 100(1), 295–320 (1928)
Nishimura, R., Hayashi, S., Fukushima, M.: Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets. J. Global Optim. 53(1), 107–120 (2012)
Polik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49(3), 371–418 (2007)
Prékopa, A.: Stochastic programming. Springer, Netherlands (1995)
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)
Rockafellar, R.T.: Convex analysis. Princeton University Press (1970)
Shapiro, A.: Semi-Infinite Programming: Recent Advances, chap. On duality theory of conic linear problems, pp. 135–165. Springer US, Boston, MA (2001)
Singh, V.V., Jouini, O., Lisser, A.: Existence of Nash equilibrium for chance-constrained games. Oper. Res. Lett. 44(5), 640–644 (2016)
Son, Y.S., Baldick, R., Lee, K.H., Siddiqi, S.: Short-term electricity market auction game analysis: uniform and pay-as-bid pricing. IEEE Trans. Power Syst. 19(4), 1990–1998 (2004)
Song, T.: Systems and management science by extremal methods, chap. On random payoff matrix games, pp. 291–308. Springer US, Boston, MA (1992)
Valenzuela, J., Mazumdar, M.: Cournot prices considering generator availability and demand uncertainty. IEEE Trans. Power Syst. 22(1), 116–125 (2007)
Wambach, A.: Bertrand competition under cost uncertainty. Int. J. Indust. Organ. 17(7), 941–951 (1999)
Wolf, D.D., Smeers, Y.: A stochastic version of a Stackelberg-Nash-Cournot equilibrium model. Manage. Sci. 43(2), 190–197 (1997)
Xu, H., Zhang, D.: Stochastic Nash equilibrium problems: sample average approximation and applications. Comput. Optim. Appl. 55(3), 597–645 (2013)
Acknowledgments
This research was supported by Fondation DIGITEO, SUN Grant No. 2014-0822D.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Singh, V.V., Jouini, O. & Lisser, A. Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium. Optim Lett 11, 1385–1405 (2017). https://doi.org/10.1007/s11590-016-1077-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-016-1077-6