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

Биматричной игрой называется некооперативная игра между двумя игроками, в которой игроки имеют 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. Теорема Нэша о равновесии в некооперативных играх в приложении к биматричным играм гласит, что для каждой биматричной игры G = (A, B) существует пара смешанных стратегий (x* 2 Pm,y* 2 Pn), называемая равновесием Нэша, такая, что для всех x 2 Pm и y 2 Pn имеет место (x*)TAy* > xrAy* и (x*)TBy* > (x*)TBy.