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, 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.

[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.

[3]

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

[4]

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

[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.

[6]

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

[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.

[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.

[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.

[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.

[11]

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

[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.

[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.

[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.

[15]

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

[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.

[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.

[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.

[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.

[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.

[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.

[22]

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

[23]

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

[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.

[25]

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

[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.

[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.

[28]

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

[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.

[30]

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

[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.

[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.

[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.

[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.

[35]

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

[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.

[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.

[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.

[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.

[40]

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

[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.

[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.

[43]

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

[44]

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

[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.

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.

[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.

[3]

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

[4]

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

[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.

[6]

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

[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.

[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.

[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.

[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.

[11]

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

[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.

[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.

[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.

[15]

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

[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.

[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.

[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.

[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.

[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.

[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.

[22]

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

[23]

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

[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.

[25]

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

[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.

[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.

[28]

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

[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.

[30]

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

[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.

[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.

[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.

[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.

[35]

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

[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.

[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.

[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.

[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.

[40]

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

[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.

[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.

[43]

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

[44]

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

[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.

[1]

Hyeng Keun Koo, Shanjian Tang, Zhou Yang. A Dynkin game under Knightian uncertainty. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5467-5498. doi: 10.3934/dcds.2015.35.5467

[2]

Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-19. doi: 10.3934/jimo.2018089

[3]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309

[4]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223

[5]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

[6]

Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial & Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415

[7]

Xinmin Yang. On symmetric and self duality in vector optimization problem. Journal of Industrial & Management Optimization, 2011, 7 (3) : 523-529. doi: 10.3934/jimo.2011.7.523

[8]

Radu Ioan Boţ, Sorin-Mihai Grad. On linear vector optimization duality in infinite-dimensional spaces. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 407-415. doi: 10.3934/naco.2011.1.407

[9]

Daniel Grieser. A natural differential operator on conic spaces. Conference Publications, 2011, 2011 (Special) : 568-577. doi: 10.3934/proc.2011.2011.568

[10]

Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial & Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921

[11]

Ioannis D. Baltas, Athanasios N. Yannacopoulos. Uncertainty and inside information. Journal of Dynamics & Games, 2016, 3 (1) : 1-24. doi: 10.3934/jdg.2016001

[12]

Jinqiao Duan, Vincent J. Ervin, Daniel Schertzer. Dispersion in flows with obstacles and uncertainty. Conference Publications, 2001, 2001 (Special) : 131-136. doi: 10.3934/proc.2001.2001.131

[13]

Regina S. Burachik, Xiaoqi Yang. Asymptotic strong duality. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 539-548. doi: 10.3934/naco.2011.1.539

[14]

Shiri Artstein-Avidan and Vitali Milman. A characterization of the concept of duality. Electronic Research Announcements, 2007, 14: 42-59. doi: 10.3934/era.2007.14.42

[15]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[16]

Adel Alahmadi, Steven Dougherty, André Leroy, Patrick Solé. On the duality and the direction of polycyclic codes. Advances in Mathematics of Communications, 2016, 10 (4) : 921-929. doi: 10.3934/amc.2016049

[17]

Georgios Konstantinidis. A game theoretic analysis of the cops and robber game. Journal of Dynamics & Games, 2014, 1 (4) : 599-619. doi: 10.3934/jdg.2014.1.599

[18]

Yannick Viossat. Game dynamics and Nash equilibria. Journal of Dynamics & Games, 2014, 1 (3) : 537-553. doi: 10.3934/jdg.2014.1.537

[19]

Jiahua Zhang, Shu-Cherng Fang, Yifan Xu, Ziteng Wang. A cooperative game with envy. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2049-2066. doi: 10.3934/jimo.2017031

[20]

Ying Ji, Shaojian Qu, Fuxing Chen. Environmental game modeling with uncertainties. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 989-1003. doi: 10.3934/dcdss.2019067

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (61)
  • HTML views (349)
  • Cited by (0)

Other articles
by authors

[Back to Top]