Mixed complementarity problems for robust optimization equilibrium in bimatrix game. (Q1928177)

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.