Bimatrix game

${\displaystyle \mathbf {A} ={\begin{bmatrix}c&d&e\\f&g&h\\\end{bmatrix}}}$	${\displaystyle \mathbf {B} ={\begin{bmatrix}p&q&r\\s&t&u\\\end{bmatrix}}}$
${\displaystyle {\begin{array}{c|c|c|c}&X&Y&Z\\\hline V&c,p&d,q&e,r\\W&f,s&g,t&h,u\\\end{array}}}$ A payoff matrix converted from A and B where player 1 has two possible actions V and W and player 2 has actions X, Y and Z

In game theory, a bimatrix game is a simultaneous game for two players in which each player has a finite number of possible actions. The name comes from the fact that the normal form of such a game can be described by two matrices - matrix ${\displaystyle A}$ describing the payoffs of player 1 and matrix ${\displaystyle B}$ describing the payoffs of player 2.

Player 1 is often called the "row player" and player 2 the "column player". If player 1 has ${\displaystyle m}$ possible actions and player 2 has ${\displaystyle n}$ possible actions, then each of the two matrices has ${\displaystyle m}$ rows by ${\displaystyle n}$ columns. When the row player selects the ${\displaystyle i}$-th action and the column player selects the ${\displaystyle j}$-th action, the payoff to the row player is ${\displaystyle A[i,j]}$ and the payoff to the column player is ${\displaystyle B[i,j]}$.

The players can also play mixed strategies. A mixed strategy for the row player is a non-negative vector ${\displaystyle x}$ of length ${\displaystyle m}$ such that: ${\textstyle \sum _{i=1}^{m}x_{i}=1}$. Similarly, a mixed strategy for the column player is a non-negative vector ${\displaystyle y}$ of length ${\displaystyle n}$ such that: ${\textstyle \sum _{j=1}^{n}y_{j}=1}$. When the players play mixed strategies with vectors ${\displaystyle x}$ and ${\displaystyle y}$, the expected payoff of the row player is: ${\displaystyle x^{\mathsf {T}}Ay}$ and of the column player: ${\displaystyle x^{\mathsf {T}}By}$.

Nash equilibrium in bimatrix games

Every bimatrix game has a Nash equilibrium in (possibly) mixed strategies. Finding such a Nash equilibrium is a special case of the Linear complementarity problem and can be done in finite time by the Lemke–Howson algorithm.

There is a reduction from the problem of finding a Nash equilibrium in a bimatrix game to the problem of finding a competitive equilibrium in an economy with Leontief utilities.

Related terms

A zero-sum game is a special case of a bimatrix game in which ${\displaystyle A+B=0}$.

A class of bimatrix games where the payoff of each player depend on three additively separable components are “additively separable partially zero-sum bi-matrix games”. In such games the first component depends on the actions chosen by both players, the second component depends only on the action chosen by the concerned player and the third component depends on the action chosen by the other player. The sum of the jointly dependent components of the players at each pair of actions is equal to zero. Such games contain two-person zero-sum (matrix) games as a strict subset. Equilibrium in mixed strategies for such bimatrix games correspond to the solution of a related linear programming problem and its dual.

References