Английская Википедия:Bimatrix game

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

<math>\mathbf{A} = \begin{bmatrix} c & d & e \\ f & g & h \\ \end{bmatrix}</math>	<math>\mathbf{B} = \begin{bmatrix} p & q & r \\ s & t & u \\ \end{bmatrix}</math>
<math> \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}</math> 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 <math>A</math> describing the payoffs of player 1 and matrix <math>B</math> describing the payoffs of player 2.

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

The players can also play mixed strategies. A mixed strategy for the row player is a non-negative vector <math>x</math> of length <math>m</math> such that: <math display="inline">\sum_{i=1}^m x_i = 1</math>. Similarly, a mixed strategy for the column player is a non-negative vector <math>y</math> of length <math>n</math> such that: <math display="inline">\sum_{j=1}^n y_j = 1</math>. When the players play mixed strategies with vectors <math>x</math> and <math>y</math>, the expected payoff of the row player is: <math>x^\mathsf{T} A y</math> and of the column player: <math>x^\mathsf{T} B y</math>.

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 <math>A+B = 0</math>.