Доминирование в матричных играх

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

Пусть задана матричная игра с платежной матрицей А, а смешанные стратегии игроков представлены в виде x = (x₁, x₂,... x_m) и y = (y₁, y₂,... y_n). Вектор х' строго доминирует вектор х"(вектор x" строго доминируется вектором x'), если справедливо: x_i' > x_i", i=1:m. Если неравенство нестрогое, то и доминирование является нестрогим.

Теорема. Если строка с номером r в матрице А строго доминируется выпуклой линейной комбинацией всех остальных строк, то она входит с нулевой вероятностью в любую оптимальную смешанную стратегию первого игрока.

Если x~, y~- пара оптимальных смешанных стратегий игры с матрицей A, то удалив из вектора x~ нулевую координату с номером r получим пару оптимальных смешанных стратегий x`~,y~ игры с матрицей A`, полученной из матрицы A вычеркиванием строки с номером r.

Обратное утверждение тоже верно. Если x`~,y~- пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве r-той координаты вектора x`~ ноль и сдвинув на одно место вправо все координаты вектора x~ с номерами r, r+1... m-1, получим пару оптимальных смешанных стратегий x~,y~ игры с матрицей A.

Теорема. Если строка с номером r в матрице А нестрого доминируется выпуклой линейной комбинацией всех остальных строк, то существует оптимальная смешанная стратегия первого игрока x~, у которой r-тая координата равна нулю.

Любая пара x`~,y~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой координаты с номером r в вектор x`~ и сдвигом координат этого вектора с номерами r, r+1,...m-1 на одно место вправо.

Во всех этих случаях значение игры с матрицей А совпадает со значением игры с матрицей А~.

Теорема. Если столбец с номером s в матрице А строго доминирует выпуклую линейную комбинацию всех остальных столбцов, то он входит с нулевой вероятностью в любую оптимальную смешанную стратегию второго игрока.

Если x~,y~ - пара оптимальных смешанных стратегий в игре с матрицей А, то удалив из вектора y~ нулевую координату с номером s, получим пару оптимальных смешанных стратегий x~,y`~ игры с матрицей A`, полученной из матрицы А вычеркиванием столбца с номером s.

Обратное: если x~,y`~ - пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве координаты с номером s вектора y`~ ноль и сдвинув все координаты с номерами s, s+1,... n-1 на одно место вправо получим пару x~,y~ оптимальных смешанных стратегий в игре с матрицей А.

Теорема. Если столбец с номером s в матрице А нестрого доминирует выпуклую линейную комбинацию всех остальных столбцов, то существует такая оптимальная смешанная стратегия y~ второго игрока, в которой координата с номером s равна нулю и любая пара x~,y`~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой s-той координаты и сдвигом координат с номерами s, s+1,... n-1 вектора y`~ вправо на одно место.

Таким образом, если строка матрицы А доминируется какой-либо другой (то есть она меньше) или линейной выпуклой комбинацией всех остальных строк, то ее можно вычеркнуть и решать задачу с меньшей матрицей, а решение исходной задачи получить добавив нули вместо недостающих координат в векторе первого игрока.

Если столбец матрицы А доминирует какой-либо другой (то есть он больше) или выпуклую линейную комбинацию всех остальных столбцов, то ее можно вычеркнуть, решить игру с меньшим количеством столбцов и получить оптимальные смешанные стратегии добавлением нулей вместо недостающих координат в векторе второго игрока.

Поиск по сайту: