Mixed complementarity problems for robust optimization equilibrium in bimatrix game. (English) Zbl 1265.91003

The author studies the problem of finding the robust optimization equilibrium of a bimatrix game in which each player attempts to minimize his own cost with either each player’s cost matrix or his opponent’s uncertain strategies. Let \(Y\), \(Z\) denote the sets of mixed strategies of Player one and Player two, \(D_A\), \(D_B\) be bounded sets of matrices and \(Y^U\), \(Z^U\) bounded sets of the opponents’ strategies. Player one solves the problem \[ \min _{y \in Y}\max _{\tilde {A} \in D_A, \tilde {z} \in Z^U}(y^T\tilde {A}\tilde {z}). \tag{1} \] Player two solves the problem \[ \min _{z \in Z}\max _{\tilde {B} \in D_B, \tilde {y} \in Y^U}(\tilde {y}^T\tilde {B}z). \tag{2} \] A pair of strategies (\(\hat {y}, \hat {z}\)) which solve problems (1) and (2), respectively, is called a robust equilibrium for the players. The author proposes a method for finding strategies \(\hat {y}\), \(\hat {z}\) based on linear programming and solving a mixed complementarity problem, which can be solved by methods known from the literature. The proposed procedure reduces the computational complexity as compared with other methods known from the literature, which lead to solving the second-order cone complementarity problem. The last section of the paper contains numerical examples illustrating the theoretical results of the preceding sections.


91A05 2-person games
90C05 Linear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C46 Optimality conditions and duality in mathematical programming
Full Text: DOI Link


[1] M. Aghassi, D. Bertsimas: Robust game theory. Math. Program. 107 (2006), 231–273. · Zbl 1134.91309
[2] A. Ben-Tal, A. Nemirovski: Robust convex optimization. Math. Oper. Res. 23 (1998), 769–805. · Zbl 0977.90052
[3] A. Ben-Tal, A. Nemirovski: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25 (1999), 1–13. · Zbl 0941.90053
[4] A. Ben-Tal, A. Nemirovski: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88 (2000), 411–424. · Zbl 0964.90025
[5] D. Bertsimas, D. Pachamanova, M. Sim: Robust linear optimization under general norms. Oper. Res. Lett. 32 (2004), 510–516. · Zbl 1054.90046
[6] D. Bertsimas, M. Sim: The price of robustness. Oper. Res. 52 (2004), 35–53. · Zbl 1165.90565
[7] D. Bertsimas, M. Sim: Tractable approximations to robust conic optimization problems. Math. Program. 107 (2006), 5–36. · Zbl 1134.90026
[8] X. Chen, M. Sim, P. Sun: A robust optimization perspective of stochastic programming. Oper. Res. 55 (2007), 1058–1071. · Zbl 1167.90608
[9] L. El Ghaoui, F. Oustry, H. Lebret: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18 (1997), 1035–1064. · Zbl 0891.65039
[10] L. El Ghaoui, F. Oustry, H. Lebret: Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9 (1998), 33–52. · Zbl 0960.93007
[11] F. Facchinei, J. S. Pang: Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. I. Springer, New York, 2003. · Zbl 1062.90001
[12] S. Hayashi, N. Yamashita, M. Fukushima: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15 (2005), 593–615. · Zbl 1114.90139
[13] S. Hayashi, N. Yamashita, M. Fukushima: Robust Nash equilibria and second-order cone complementarity problems. J. Nonlinear. Convex Anal. 6 (2005), 283–296. · Zbl 1137.91310
[14] J.C. Harsanyi: Games with incomplete information played by ”Bayesian” playes, Part II. Manage. Sci. 14 (1968), 320–334. · Zbl 0177.48402
[15] B. Holmström, R. Myerson: Efficient and durable decision rules with incomplete information. Econometrica 51 (1983), 1799–1820. · Zbl 0521.90008
[16] G.M. Luo, D.H. Li: Robust optimization equilibrium with deviation measures. Pac. J. Optim. 5 (2009), 427–441. · Zbl 1175.91017
[17] J. Mertens, S. Zamir: Formualation of Bayesian analysis for games with incomplete information. Int. J. Game Theory 14 (1985), 1–29. · Zbl 0567.90103
[18] J.F. Nash jun.: Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36 (1950), 48–49. · Zbl 0036.01104
[19] J. Nash: Non-cooperative games. Ann. Math. 54 (1951), 286–295. · Zbl 0045.08202
[20] A. L. Soyster: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21 (1973), 1154–1157. · Zbl 0266.90046
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.