Сложность биматричного равновесия Нэша: различия между версиями

Биматричной игрой называется некооперативная игра между двумя игроками, в которой игроки имеют m и n вариантов действий (или чистых стратегий), соответственно. Такая игра может быть задана двумя матрицами размера <math>m \times n</math>, <math>\mathbf{A} = \big( a_{i, j} \big)</math> и <math>\mathbf{B} = \big( b_{i, j} \big)</math>. Если первый игрок выбирает действие i, а второй игрок – действие j, то их выигрыш составляет <math>a_{i, j}</math> и <math>b_{i, j}</math>, соответственно. Смешанная стратегия игрока представляет собой распределение вероятностей над его выборами. Обозначим за <math>\mathbb{P}^n</math> множество всех векторов вероятностей в <math>\mathbb{R}^n</math>, то есть неотрицательных векторов, сумма элементов которых равна 1. Теорема Нэша о равновесии в некооперативных играх в приложении к биматричным играм гласит, что для каждой биматричной игры <math>\mathcal{G} = (\mathbf{A}, \mathbf{B})</math> существует пара смешанных стратегий <math>(\mathbf{x}^* \in \mathbb{P}^m, \mathbf{y}^* \in \mathbb{P}^n)</math>, называемая равновесием Нэша, такая, что для всех <math>\mathbf{x}^* \in \mathbb{P}^m</math> и <math>\mathbf{y}^* \in \mathbb{P}^n</math> имеет место соотношение (x*)TAy* > xrAy* и (x*)TBy* > (x*)TBy.