Bimatrix game explained

A=\begin{bmatrix} c&d&e\\ f&g&h\\ \end{bmatrix}	B=\begin{bmatrix} p&q&r\\ s&t&u\\ \end{bmatrix}
\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

describing the payoffs of player 1 and matrix describing the payoffs of player 2.^[1]

Player 1 is often called the "row player" and player 2 the "column player". If player 1 has

possible actions and player 2 has possible actions, then each of the two matrices has rows by columns. When the row player selects the -th action and the column player selects the -th action, the payoff to the row player is and the payoff to the column player is .

The players can also play mixed strategies. A mixed strategy for the row player is a non-negative vector

of length such that: $\backslash sum\_^m\; x\_i\; =\; 1$. Similarly, a mixed strategy for the column player is a non-negative vector of length such that: $\backslash sum\_^n\; y\_j\; =\; 1$. When the players play mixed strategies with vectors and , the expected payoff of the row player is: and of the column player: .

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.^[1]

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.^[2]

Related terms

A zero-sum game is a special case of a bimatrix game in which

.

Notes and References

1. Web site: Bimatrix games . 17 December 2015 . Chandrasekaran, R.
2. Book: 10.1145/1109557.1109629. Leontief economies encode nonzero sum two-player games. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. 659. 2006. Codenotti. Bruno. Saberi. Amin. Varadarajan. Kasturi. Ye. Yinyu. 0898716055.