Bimatrix game

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 matrixes - matrix A describing the payoffs of player 1 and matrix B 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 m possible actions and player 2 n possible actions, then each of the two matrixes has m rows by n columns. when the row player selects the $i$ -th action and the column player selects the $j$ -th action, the payoff to the row player is $A[i,j]$ and the payoff to the column player is $B[i,j]$ .

The players can also play mixed strategies. A mixed strategy for the row player is a non-negative vector x of length m such that: $\sum _{i=1}^{m}x_{i}=1$ . Similarly, a mixed strategy for the column player is a non-negative vector y of length m such that: $\sum _{j=1}^{m}y_{j}=1$ . When the players play mixed strategies with vectors x and y, the expected payoff of the row player is: $x^{T}Ay$ and of the column player: $x^{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.^[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 $A+B=0$ .

References

1 2 Chandrasekaran, R. "Bimatrix games" (PDF). Retrieved 17 December 2015.
↑ Codenotti, Bruno; Saberi, Amin; Varadarajan, Kasturi; Ye, Yinyu (2006). "Leontief economies encode nonzero sum two-player games". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. p. 659. doi:10.1145/1109557.1109629. ISBN 0898716055.

This article is issued from Wikipedia - version of the 10/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.