Биматричная игра

$\mathbf {A} ={\begin{bmatrix}c&d&e\\f&g&h\\\end{bmatrix}}$	$\mathbf {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 и B , где у игрока 1 есть два возможных действия V и W , а у игрока 2 есть действия X , Y и Z.

В теории игр биматричная игра — это одновременная игра двух игроков, в которой каждый игрок имеет конечное число возможных действий. Название происходит от того, что нормальную форму такой игры можно описать двумя матрицами — матрицей $A$ описывающее выигрыши игрока 1 и матрицы $B$ описывающих выигрыши игрока 2.

Игрока 1 часто называют «игроком строки», а игрока 2 — «игроком столбца». Если у игрока 1 есть $m$ возможные действия, и у игрока 2 есть $n$ возможные действия, то каждая из двух матриц имеет $m$ строки по $n$ столбцы. Когда игрок в ряду выбирает $i$-th действие и игрок столбца выбирает $j$-м действии выигрыш рядному игроку равен $A[i,j]$ и выигрыш для игрока в столбце равен $B[i,j]$.

Игроки также могут использовать смешанные стратегии . Смешанная стратегия для игрока по ряду представляет собой неотрицательный вектор $x$ длины $m$ такой, что: ${\textstyle \sum _{i=1}^{m}x_{i}=1}$. Аналогично, смешанная стратегия для игрока-столбца представляет собой неотрицательный вектор $y$ длины $n$ такой, что: ${\textstyle \sum _{j=1}^{n}y_{j}=1}$. Когда игроки играют в смешанные стратегии с векторами $x$ и $y$, ожидаемый выигрыш игрока в ряду равен: $x^{\mathsf {T}}Ay$ и игрока колонки: $x^{\mathsf {T}}By$.

Равновесие Нэша в биматричных играх

Каждая биматричная игра имеет равновесие Нэша в (возможно) смешанных стратегиях. Нахождение такого равновесия по Нэшу является частным случаем проблемы линейной дополнительности и может быть выполнено за конечное время с помощью алгоритма Лемке – Хаусона .

Происходит сведение от задачи нахождения равновесия Нэша в биматричной игре к задаче нахождения конкурентного равновесия в экономике с леонтьевскими полезностями .

Связанные термины

Игра с нулевой суммой — это частный случай биматричной игры, в которой $A+B=0$.