Основная теорема матричных игр фон Неймана. Методы решения матричных игр

Лемма 1 Цена симметричной матричной игры равна нулю, а

множества оптимальных стратегий игроков совпадают.

Доказательство. Справедлива цепочка равенств

(при доказательстве равенств производится перемена обозначений p на q

и i на j ).

Пусть p ⁰  — оптимальная стратегия игрока 1. Тогда

 

Следовательно, p ⁰  — оптимальная стратегия игрока 2. Аналогично, любая оптимальная стратегия игрока 2 является оптимальной стратегией игрока 1.

Теорема1 Решение матричной игры с матрицей

 

эквивалентно решению пары двойственных задач ЛП:

Точнее, если — решение задачи (5) — решение задачи (6), то -цена игры с матрицей А.

p⁰ = vx ⁰ — оптимальная стратегия игрока 1,

q ⁰ = vy⁰ — оптимальная стратегия игрока 2.

Обратно, если p⁰  и q ⁰ — оптимальные стратегии игроков, v — цена игры, то решение задачи (5), а - решение задачи (6).

Доказательство. Задачи (5) и (6) имеют хотя бы по одному допустимому вектору (для (6) нулевой вектор, а для (5) вследствие положительности матрицы A вектор с достаточно большими компонента- ми), значит, они обе имеют решения.

 

Пусть x ⁰ — решение (5), y ⁰ — решение (6), тогда по теореме двойственности

(положительность  этих сумм следует из того, что x ⁰ ¹ 0 ).

 

Положим

 

тогда 

 

Для того чтобы v было ценой игры, а p⁰ , q⁰ — оптимальными стратегиями игроков, необходимо и достаточно, чтобы h(i, q⁰ ) £ v £ h( p⁰ , j)"i, j.(Следствие 1)

 

Пусть теперь v — цена игры с матрицей А, p⁰ и q⁰— оптимальные стратегии игроков. Так как матрица А положительная, то v > 0 . Положим

 и из 

следуют неравенства 

т.е. x ⁰  — допустимый вектор задачи (5); y⁰ — допустимый вектор задачи (6). При этом

  следовательно, x⁰— решение (5), y⁰  — решение (6). Теорема доказана.

Теорема 2 Решение  пары  двойственных задач линейного программирования

эквивалентно  решению симметричной матричной  игры с матрицей

Точнее  если - оптимальная страегия любого игрока в игре с матрицей D и - решение задачи(7) -решение задачи(8).

Обратно, если — решение задачи (7), -решение задачи (8),то

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

Если нет оптимальных стратегий в игре с матрицей D, последняя компонента которых отлична от нуля, то задачи (7), (8) не могут иметь решения. С другой стороны, если существует оптимальная стратегия с отличной от нуля последней компонентой, то существование решения задач (7), (8) уже доказано конструктивно.

Полученные результаты позволяют свести решение игр к решению задач линейного программирования и применить к ним, например, симплекс-метод. Сведением задач линейного программирования к играм пользуются реже.

Наиболее многообещающим, из рассмотренных, выглядит метод Шепли-Сноу, так как он дает полное решение игры. Однако при значительной размерности платежной матрицы приходится решать большое количество систем линейных уравнений. Поэтому метод Шепли-Сноу можно рекомендовать для решения игр небольшой размерности. Наиболее простым в вычислительном плане является метод Брауна, но его сходимость достаточно быстро ухудшается с ростом размерности, поэтому этот метод можно рекомендовать для решения игр средней размерности (порядка нескольких десятков). Для решения игр большой размерности (порядка нескольких сотен или тысяч) предпочтительнее метод сведения их к задачам линейного программирования.