Bimatrix game

A finite non-cooperative game between two players. A bimatrix game is specified by two matrices $A=\|a_{ij}\|$ and $B=\|B_{ij}\|$ of the same dimension $m\times n$, which are, respectively, the payoff matrices (or gain matrices) of the players I and II. The strategy of player I is the selection of a row, that of player II the selection of a column. If player I chooses $i$ ($1\leq i\leq m$), while player II chooses $j$ ($1\leq j\leq n$), their respective payoffs (gains) will be $a_{ij}$ and $b_{ij}$; if $a_{ij}+b_{ij}=0$ for all $i,j$, the bimatrix game becomes a matrix game. The theory of bimatrix games is the simplest branch of the general theory of non-cooperative games, but even bimatrix games are not always solvable according to Nash or strongly solvable. Various algorithms are available to find equilibrium solutions in bimatrix games: a method of describing the submatrices of $A,B$ yielding all extreme points of the set of equilibrium solutions [1], [2]; and methods which reduce the problem of finding the equilibrium solutions of a bimatrix game to a problem of quadratic programming [3], [4], [5].

References

[1]	N.N. Vorob'ev, "Equilibrium points in bimatrix games" Theory Probab. Appl , 3 : 3 (1958) pp. 297–309 Teor. Veroyatnost. i Primenen. , 3 : 3 (1958) pp. 318–331
[2]	H.W. Kuhn, "An algorithm for equilibrium points in bimatrix games" Proc. Nat. Acad. Sci. USA , 47 (1961) pp. 1657–1662
[3]	H. Mills, "Equilibrium points in infinite games" J. Soc. Ind. Appl. Math. , 8 : 2 (1960) pp. 397–402
[4]	O.L. Mangasarian, "Equilibrium points of bimatrix games" J. Soc. Ind. Appl. Math. , 12 : 4 (1964) pp. 778–780
[5]	C.E. Lemke, J.T. Howson, jr., "Equilibrium points of bimatrix games" J. Soc. Ind. Appl. Math. , 12 : 2 (1964) pp. 413–423