П.4. Алгоритм нахождения общего решения игры

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

Лемма 5.5. Если векторы

,

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

Доказательство. Если допустить, что не является крайней точкой множества , то найдутся такие точки и число , что будет выполнено равенство . Сравнивая координаты векторов левой и правой частей этого равенства, обнаружим, что если , то и . Тогда , т.к. – смешанные стратегии. Таким образом, , что противоречит принципу выбора точек . Аналогично доказывается, что и – крайняя точка множества . Лемма доказана.

Лемма 5.6. Для того чтобы векторы

, (5.19)

где единица у вектора стоит на -ом, а у вектора – на -ом месте, были оптимальными стратегиями а – ценой игры с матрицей , необходимо и достаточно, чтобы пара была седловой точкой матрицы .

Доказательство. Необходимость. Так как векторы (5.19) являются оптимальными стратегиями а – ценой игры, то согласно теореме 2.2.1 оптимальности выполняются неравенства

т.е. выполняются неравенства

, (5.20)

но это и означает, что пара является седловой точкой матрицы .

Достаточность. Так как пара является седловой точкой матрицы ,

то выполняются неравенства (5.20). А так как для векторов (5.19) выполняются равенства

,

то отсюда и из (5.20) следует

Это силу следствия теоремы 2.2.1 означает, что векторы (5.19) являются оптимальными стратегиями, а число – ценой игры. Лемма доказана.

Леммы 5.5 и 5.6 показывают, что при нахождении крайних точек множеств с использованием теоремы 5.1 можно не исследовать на пригодность подматрицы, являющиеся отдельными элементами матрицы . Вместо этого достаточно найти седловые точки матрицы , если таковые есть, и в соответствии с леммой 5.6 определить цену игры и крайние точки вида (5.19).