January  2019, 15(1): 387-400. doi: 10.3934/jimo.2018048

A class of two-stage distributionally robust games

1. 

School of Electrical Engineering and Information, Sichuan University, China

2. 

Department of Mathematics and Statistics, Curtin University, Australia

3. 

School of Business, National University of Singapore, Singapore

* Corresponding author

Received  June 2017 Revised  November 2017 Published  April 2018

An $ N $-person noncooperative game under uncertainty is analyzed, in which each player solves a two-stage distributionally robust optimization problem that depends on a random vector as well as on other players' decisions. Particularly, a special case is considered, where the players' optimization problems are linear at both stages, and it is shown that the Nash equilibrium of this game can be obtained by solving a conic linear variational inequality problem.

Citation: Bin Li, Jie Sun, Honglei Xu, Min Zhang. A class of two-stage distributionally robust games. Journal of Industrial & Management Optimization, 2019, 15 (1) : 387-400. doi: 10.3934/jimo.2018048
References:
[1]

M. Aghassi and D. Bertsimas, Robust game theory, Mathematical Programming, 107 (2006), 231-273.  doi: 10.1007/s10107-005-0686-0.  Google Scholar

[2]

J. AngF. Meng and J. Sun, Two-stage stochastic linear programs with incomplete information on uncertainty, European Journal of Operational Research, 233 (2014), 16-22.  doi: 10.1016/j.ejor.2013.07.039.  Google Scholar

[3]

A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust Optimization, Princeton University Press, Princeton and Oxford, 2009.  Google Scholar

[4]

A. Ben-Tal and A. Nemirovski, Robust optimization--methodology and applications, Mathematical Programming Series B, 92 (2002), 453-480.  doi: 10.1007/s101070100286.  Google Scholar

[5]

A. Bensoussan, Points de Nash dans le cas de fontionnelles quadratiques et jeux differentiels lineaires a N personnes, SIAM Journal on Control, 12 (1974), 460-499.  doi: 10.1137/0312037.  Google Scholar

[6]

D. Bertsimas and R. Freund, Data, Models, and Decisions: The Fundamentals of Management Science, South-Western College Publishing, Cincinnati, 2000. Google Scholar

[7]

X. ChenM. SimJ. Sun and C.-P. Teo, From CVaR to uncertainty set: Implications in joint chance constrained optimization, Operations Research, 58 (2010), 470-485.  doi: 10.1287/opre.1090.0712.  Google Scholar

[8]

X. ChenM. SimP. Sun and J. Zhang, A linear-decision based approximation approach to stochastic programming, Operations Research, 56 (2008), 344-357.  doi: 10.1287/opre.1070.0457.  Google Scholar

[9]

E. Delage and Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-driven problems, Operations Research, 58 (2010), 595-612.  doi: 10.1287/opre.1090.0741.  Google Scholar

[10]

G. Dhaene and J. Bouckaert, Sequential reciprocity in two-player, two-stage games: An experimental analysis, Games and Economic behavior, 70 (2010), 289-303.  doi: 10.1016/j.geb.2010.02.009.  Google Scholar

[11]

J. Dupacova, The minimax approach to stochastic programming and an illustrative application, Stochastics, 20 (1987), 73-88.  doi: 10.1080/17442508708833436.  Google Scholar

[12]

F. FacchineiA. Fischer and V. Piccialli, On generalized Nash games and variational inequalities, Operations Research Letters, 35 (2007), 159-164.  doi: 10.1016/j.orl.2006.03.004.  Google Scholar

[13]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, Annals of Operations Research, 175 (2010), 177-211.  doi: 10.1007/s10479-009-0653-x.  Google Scholar

[14]

F. Facchinei and J. S. Pang, Nash Equilibria: The Variational Approach, In Y. Eldar and D. Palomar, editors, Convex Optimization in Signal Processing and Communications. Cambridge University Press, Cambridge, England, 2010,443-493.  Google Scholar

[15]

F. Facchinei and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003.  Google Scholar

[16]

S. GaoL. Kong and J. Sun, Two-stage stochastic linear programs with moment information on uncertainty, Optimization, 63 (2014), 829-837.  doi: 10.1080/02331934.2014.906598.  Google Scholar

[17]

S. GaoJ. Sun and S. Wu, A semi-infinite programming approach to two-stage stochastic linear programs with high-order moment constraints, Optimization Letters, (2016), 1-11.  doi: 10.1007/s11590-016-1095-4.  Google Scholar

[18]

J. Goh and M. Sim, Distributionally robust optimization and its tractable approximations, Operations Research, 58 (2010), 902-917.  doi: 10.1287/opre.1090.0795.  Google Scholar

[19]

P. T. Harker, Generalized Nash games and quasi-variational inequalities, European Journal of Operational Research, 54 (1991), 81-94.  doi: 10.1016/0377-2217(91)90325-P.  Google Scholar

[20]

P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming Series B, 48 (1990), 161-220.  doi: 10.1007/BF01582255.  Google Scholar

[21]

S. HayashiN. Yamashita and M. Fukushima, Robust Nash equilibria and second-order cone complementarity problems, Journal of Nonlinear and Convex Analysis, 6 (2005), 283-296.   Google Scholar

[22]

R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications, SIAM Review, 35 (1993), 380-429.  doi: 10.1137/1035089.  Google Scholar

[23]

P. Kall and S. W. Wallace, Stochastic Programming, Chichester: Wiley, 1994.  Google Scholar

[24]

A. KannanU. V. Shanbhag and H. M. Kim, Addressing supply-side risk in uncertain power markets: Stochastic Nash models, scalable algorithms and error analysis, Optimization Methods and Software, 28 (2013), 1095-1138.  doi: 10.1080/10556788.2012.676756.  Google Scholar

[25]

H. J. Landau, Moments in Mathematics: Lecture Notes Prepared for the AMS Short Course, American Mathematical Society, San Antonio, Texas, USA, 1987. Google Scholar

[26]

A. LingJ. SunN. Xiu and X. Yang, Two-stage stochastic linear optimization with risk aversion and robustness, European Journal of Operational Research, 256 (2017), 215-229.  doi: 10.1016/j.ejor.2016.06.017.  Google Scholar

[27]

A. LingJ. Sun and X. Yang, Robust tracking error portfolio selection with worst-case downside risk measures, Journal of Economic Dynamics and Control, 39 (2014), 178-207.  doi: 10.1016/j.jedc.2013.11.011.  Google Scholar

[28]

D. Monderer and L. S. Shapley, Potential games, Games and Economic Behavior, 14 (1996), 124-143.  doi: 10.1006/game.1996.0044.  Google Scholar

[29]

J. F. Nash, Equilibrium points in n-person games, Proceedings of the National Academy of Sciences, 36 (1950), 48-49.  doi: 10.1073/pnas.36.1.48.  Google Scholar

[30]

J. F. Nash, Non-cooperative games, Annals of Mathematics, 54 (1951), 286-295.  doi: 10.2307/1969529.  Google Scholar

[31]

R. NishimuraS. Hayashi and M. Fukushima, Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets, Journal of Global Optimization, 53 (2012), 107-120.  doi: 10.1007/s10898-011-9719-9.  Google Scholar

[32]

R. NishimuraS. Hayashi and M. Fukushima, Robust Nash equilibria in N-person noncooperative games: Uniqueness and reformulation, Pacific Journal of Optimization, 5 (2009), 237-259.   Google Scholar

[33]

J. S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Computational Management Science, 2 (2005), 21-56.  doi: 10.1007/s10287-004-0010-0.  Google Scholar

[34]

J. S. PangS. Sen and U. Shanbhag, Two-Stage non-cooperative games with risk-Averse players, Mathematical Programming Series B, 165 (2017), 235-290.  doi: 10.1007/s10107-017-1148-1.  Google Scholar

[35]

R. T. Rockafellar, Conjugate Duality and Optimization, SIAM, Philadelphia, 1974.  Google Scholar

[36]

R. T. Rockafellar and R. J.-B. Wets, Stochastic variational inequalities: Single-stage to multistage, Mathematical Programming Series B, 165 (2017), 331-360.  doi: 10.1007/s10107-016-0995-5.  Google Scholar

[37]

H. Scarf, A min-max solution of an inventory problem, in Studies in The Mathematical Theory of Inventory and Production (eds. K. J. Arrow, S. Karlin and H. E. Scarf), Stanford University Press, (1958), 201-209. Google Scholar

[38]

G. ScutariD. P. PalomarF. Facchinei and J. S. Pang, Convex optimization, game theory, and variational inequality theory, IEEE Signal Processing Magazine, 27 (2010), 35-49.   Google Scholar

[39]

R. M. Sheremeta, Experimental comparison of multi-stage and one-stage contests, Games and Economic Behavior, 68 (2010), 731-747.  doi: 10.1016/j.geb.2009.08.001.  Google Scholar

[40]

M. Sion, On general minimax theorems, Pacific Journal of Mathematics, 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.  Google Scholar

[41]

J. SunL.-Z. Liao and B. Rodrigues, Quadratic two-stage stochastic optimization with coherent measures of risk, Mathematical Programming, 168 (2018), 599-613.  doi: 10.1007/s10107-017-1131-x.  Google Scholar

[42]

J. Sun, K. Tsai and L. Qi, A simplex method for network programs with convex separable piecewise linear costs and its application to stochastic transshipment problems, in: Network Optimization Problems: Algorithms, Applications and Complexity, D. Z. Du and P. M. Pardalos eds. World Scientific Publishing Co. London, (1993), 281-300. Google Scholar

[43]

D. Topkis, Supermodularity and Complementarity, Princeton University Press, New Jersey, 1998  Google Scholar

[44]

W. WiesemmanD. Kuhn and M. Sim, Distributionally robust convex optimization, Operations Research, 62 (2014), 1358-1376.  doi: 10.1287/opre.2014.1314.  Google Scholar

[45]

L. Ye, Indicative bidding and a theory of two-stage auctions, Games and Economic Behavior, 58 (2007), 181-207.  doi: 10.1016/j.geb.2005.12.004.  Google Scholar

show all references

References:
[1]

M. Aghassi and D. Bertsimas, Robust game theory, Mathematical Programming, 107 (2006), 231-273.  doi: 10.1007/s10107-005-0686-0.  Google Scholar

[2]

J. AngF. Meng and J. Sun, Two-stage stochastic linear programs with incomplete information on uncertainty, European Journal of Operational Research, 233 (2014), 16-22.  doi: 10.1016/j.ejor.2013.07.039.  Google Scholar

[3]

A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust Optimization, Princeton University Press, Princeton and Oxford, 2009.  Google Scholar

[4]

A. Ben-Tal and A. Nemirovski, Robust optimization--methodology and applications, Mathematical Programming Series B, 92 (2002), 453-480.  doi: 10.1007/s101070100286.  Google Scholar

[5]

A. Bensoussan, Points de Nash dans le cas de fontionnelles quadratiques et jeux differentiels lineaires a N personnes, SIAM Journal on Control, 12 (1974), 460-499.  doi: 10.1137/0312037.  Google Scholar

[6]

D. Bertsimas and R. Freund, Data, Models, and Decisions: The Fundamentals of Management Science, South-Western College Publishing, Cincinnati, 2000. Google Scholar

[7]

X. ChenM. SimJ. Sun and C.-P. Teo, From CVaR to uncertainty set: Implications in joint chance constrained optimization, Operations Research, 58 (2010), 470-485.  doi: 10.1287/opre.1090.0712.  Google Scholar

[8]

X. ChenM. SimP. Sun and J. Zhang, A linear-decision based approximation approach to stochastic programming, Operations Research, 56 (2008), 344-357.  doi: 10.1287/opre.1070.0457.  Google Scholar

[9]

E. Delage and Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-driven problems, Operations Research, 58 (2010), 595-612.  doi: 10.1287/opre.1090.0741.  Google Scholar

[10]

G. Dhaene and J. Bouckaert, Sequential reciprocity in two-player, two-stage games: An experimental analysis, Games and Economic behavior, 70 (2010), 289-303.  doi: 10.1016/j.geb.2010.02.009.  Google Scholar

[11]

J. Dupacova, The minimax approach to stochastic programming and an illustrative application, Stochastics, 20 (1987), 73-88.  doi: 10.1080/17442508708833436.  Google Scholar

[12]

F. FacchineiA. Fischer and V. Piccialli, On generalized Nash games and variational inequalities, Operations Research Letters, 35 (2007), 159-164.  doi: 10.1016/j.orl.2006.03.004.  Google Scholar

[13]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, Annals of Operations Research, 175 (2010), 177-211.  doi: 10.1007/s10479-009-0653-x.  Google Scholar

[14]

F. Facchinei and J. S. Pang, Nash Equilibria: The Variational Approach, In Y. Eldar and D. Palomar, editors, Convex Optimization in Signal Processing and Communications. Cambridge University Press, Cambridge, England, 2010,443-493.  Google Scholar

[15]

F. Facchinei and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer-Verlag, New York, 2003.  Google Scholar

[16]

S. GaoL. Kong and J. Sun, Two-stage stochastic linear programs with moment information on uncertainty, Optimization, 63 (2014), 829-837.  doi: 10.1080/02331934.2014.906598.  Google Scholar

[17]

S. GaoJ. Sun and S. Wu, A semi-infinite programming approach to two-stage stochastic linear programs with high-order moment constraints, Optimization Letters, (2016), 1-11.  doi: 10.1007/s11590-016-1095-4.  Google Scholar

[18]

J. Goh and M. Sim, Distributionally robust optimization and its tractable approximations, Operations Research, 58 (2010), 902-917.  doi: 10.1287/opre.1090.0795.  Google Scholar

[19]

P. T. Harker, Generalized Nash games and quasi-variational inequalities, European Journal of Operational Research, 54 (1991), 81-94.  doi: 10.1016/0377-2217(91)90325-P.  Google Scholar

[20]

P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming Series B, 48 (1990), 161-220.  doi: 10.1007/BF01582255.  Google Scholar

[21]

S. HayashiN. Yamashita and M. Fukushima, Robust Nash equilibria and second-order cone complementarity problems, Journal of Nonlinear and Convex Analysis, 6 (2005), 283-296.   Google Scholar

[22]

R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications, SIAM Review, 35 (1993), 380-429.  doi: 10.1137/1035089.  Google Scholar

[23]

P. Kall and S. W. Wallace, Stochastic Programming, Chichester: Wiley, 1994.  Google Scholar

[24]

A. KannanU. V. Shanbhag and H. M. Kim, Addressing supply-side risk in uncertain power markets: Stochastic Nash models, scalable algorithms and error analysis, Optimization Methods and Software, 28 (2013), 1095-1138.  doi: 10.1080/10556788.2012.676756.  Google Scholar

[25]

H. J. Landau, Moments in Mathematics: Lecture Notes Prepared for the AMS Short Course, American Mathematical Society, San Antonio, Texas, USA, 1987. Google Scholar

[26]

A. LingJ. SunN. Xiu and X. Yang, Two-stage stochastic linear optimization with risk aversion and robustness, European Journal of Operational Research, 256 (2017), 215-229.  doi: 10.1016/j.ejor.2016.06.017.  Google Scholar

[27]

A. LingJ. Sun and X. Yang, Robust tracking error portfolio selection with worst-case downside risk measures, Journal of Economic Dynamics and Control, 39 (2014), 178-207.  doi: 10.1016/j.jedc.2013.11.011.  Google Scholar

[28]

D. Monderer and L. S. Shapley, Potential games, Games and Economic Behavior, 14 (1996), 124-143.  doi: 10.1006/game.1996.0044.  Google Scholar

[29]

J. F. Nash, Equilibrium points in n-person games, Proceedings of the National Academy of Sciences, 36 (1950), 48-49.  doi: 10.1073/pnas.36.1.48.  Google Scholar

[30]

J. F. Nash, Non-cooperative games, Annals of Mathematics, 54 (1951), 286-295.  doi: 10.2307/1969529.  Google Scholar

[31]

R. NishimuraS. Hayashi and M. Fukushima, Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets, Journal of Global Optimization, 53 (2012), 107-120.  doi: 10.1007/s10898-011-9719-9.  Google Scholar

[32]

R. NishimuraS. Hayashi and M. Fukushima, Robust Nash equilibria in N-person noncooperative games: Uniqueness and reformulation, Pacific Journal of Optimization, 5 (2009), 237-259.   Google Scholar

[33]

J. S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Computational Management Science, 2 (2005), 21-56.  doi: 10.1007/s10287-004-0010-0.  Google Scholar

[34]

J. S. PangS. Sen and U. Shanbhag, Two-Stage non-cooperative games with risk-Averse players, Mathematical Programming Series B, 165 (2017), 235-290.  doi: 10.1007/s10107-017-1148-1.  Google Scholar

[35]

R. T. Rockafellar, Conjugate Duality and Optimization, SIAM, Philadelphia, 1974.  Google Scholar

[36]

R. T. Rockafellar and R. J.-B. Wets, Stochastic variational inequalities: Single-stage to multistage, Mathematical Programming Series B, 165 (2017), 331-360.  doi: 10.1007/s10107-016-0995-5.  Google Scholar

[37]

H. Scarf, A min-max solution of an inventory problem, in Studies in The Mathematical Theory of Inventory and Production (eds. K. J. Arrow, S. Karlin and H. E. Scarf), Stanford University Press, (1958), 201-209. Google Scholar

[38]

G. ScutariD. P. PalomarF. Facchinei and J. S. Pang, Convex optimization, game theory, and variational inequality theory, IEEE Signal Processing Magazine, 27 (2010), 35-49.   Google Scholar

[39]

R. M. Sheremeta, Experimental comparison of multi-stage and one-stage contests, Games and Economic Behavior, 68 (2010), 731-747.  doi: 10.1016/j.geb.2009.08.001.  Google Scholar

[40]

M. Sion, On general minimax theorems, Pacific Journal of Mathematics, 8 (1958), 171-176.  doi: 10.2140/pjm.1958.8.171.  Google Scholar

[41]

J. SunL.-Z. Liao and B. Rodrigues, Quadratic two-stage stochastic optimization with coherent measures of risk, Mathematical Programming, 168 (2018), 599-613.  doi: 10.1007/s10107-017-1131-x.  Google Scholar

[42]

J. Sun, K. Tsai and L. Qi, A simplex method for network programs with convex separable piecewise linear costs and its application to stochastic transshipment problems, in: Network Optimization Problems: Algorithms, Applications and Complexity, D. Z. Du and P. M. Pardalos eds. World Scientific Publishing Co. London, (1993), 281-300. Google Scholar

[43]

D. Topkis, Supermodularity and Complementarity, Princeton University Press, New Jersey, 1998  Google Scholar

[44]

W. WiesemmanD. Kuhn and M. Sim, Distributionally robust convex optimization, Operations Research, 62 (2014), 1358-1376.  doi: 10.1287/opre.2014.1314.  Google Scholar

[45]

L. Ye, Indicative bidding and a theory of two-stage auctions, Games and Economic Behavior, 58 (2007), 181-207.  doi: 10.1016/j.geb.2005.12.004.  Google Scholar

[1]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072

[2]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[3]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[4]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[5]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[6]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[7]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[8]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (319)
  • HTML views (1089)
  • Cited by (1)

Other articles
by authors

[Back to Top]