Оптимальные стратегии для игроков. Решение графических игр заданными платежными матрицами, страница 4

11. Абсцисса q⁰ минимальной точки (удовлетворяющая равенству ) является вероятностью случайного выбора игроком В чистой стратегии В₂ в оптимальной смешанной стратегии q⁰ = (1 – q⁰, q⁰).

12. Ордината минимальной точки верхней огибающей является ценой игры.

13. Верхний из нижних концов отрезков а_i1a_i2, i = 1, 2, …, m является нижней ценой игры в чистых стратегиях a.

14. Нижний из концов верхней огибающей (лежащих на перпендикулярах) является верхней ценой игры в чистых стратегиях b.

15. Элемент матрицы А, изображающая точка которого является нижним концом отрезка, на котором она лежит, и верхней на перпендикуляре, на котором она лежит, является седловой точкой игры.

В этом случае чистая стратегия игрока А, номер которой совпадает с первым индексом седловой точки, является оптимальной.

Теорема 15. Если через минимальную точку верхней огибающей отрезков а_i1a_i2, i = 1, 2, …, m порождаемых чистыми стратегиями A_i, i = 1, 2, …, m игрока А, проходят два каких-либо отрезка  и , i₁ ¹ i₂,  i₁, i₂ Î {1, 2, …, m}, то абсцисса точки М  , и, следовательно, , а цена игры .

Теорема 16. Пусть через минимальную точку М верхней огибающей отрезков а_i1a_i2, i = 1, 2, …, m порождаемых чистыми стратегиями А_i, i = 1, 2, …, m игрока А, проходят два каких-либо отрезка  и ,  i₁ ¹ i₂,  i₁, i₂ Î {1, 2, …, m}. Для того чтобы смешанная стратегия  игрока А, где , , P_i = 0, i Î {1, 2, …, m} \ {i₁, i₂}, была оптимальной, необходимо и достаточно, чтобы отрезки  и  имели разные наклоны.

Следствие. Если в условиях теоремы 16

1. Отрезок  не является  горизонтальным, т.е. имеет ненулевой наклон, то чистая стратегия  игрока А является активной.

2. Отрезок  не является горизонтальным, т.е. имеет ненулевой наклон, то чистая стратегия  игрока А является активной.

3. Ни один из отрезков  и   не является горизонтальным, то стратегии  и  игрока А  являются активными.

4. Отрезок  горизонтален, то стратегия  оптимальна.

5. Отрезок  горизонтален, то стратегия  оптимальна.

Пример 24. Найти решение игры 5´2 с матрицей

Решение. На рис. 35 минимальные точки верхней огибающей заполняют отрезок [М₁ М₂]. Поэтому q⁰ = (1 – q⁰, q⁰),  и геометрически выражается отрезком . Так как этот отрезок не содержит ни одного из концов отрезка [0, 1], то чистые стратегии игрока В не являются оптимальными стратегиями,  и  являются крайними оптимальными стратегиями. Цена игры `g равна ординате точек М Î [М<sub>1</sub>, М<sub>2</sub>]: `g = 2.

Рис. 35

Значения  и `g = 2, найденные графически, подтверждаются результатом вычисления по формулам:

,                                   (1)

,                  (2)

.                                             (3)

В самом деле, так как через минимальную точку М₁ верхней огибающей проходят два отрезка а₁₁а₁₂ и а₄₁а₄₂, то по формуле (1) при i₁ = 1 и i₂ =4 будем иметь: .

Так как через минимальную точку М₂ верхней огибающей проходят два отрезка а₂₁а₂₂ и а₄₁а₄₂, то по формуле (1) при i₁ = 2 и i₂ = 4  имеем: .

По формуле (3) при i₁ = 1 и i₂ = 4,

.

Поскольку отрезок а₄₁а₄₂, проходящий через минимальную точку М₁ (и все остальные минимальные точки), горизонтален, то стратегия А₄ игрока А является оптимальной.

11.12. Взаимосвязь матричных игр и линейного программирования

1.  Сведение матричной игры к двойственной задаче линейного программирования

Теорема 17. Решение матричной игры m´n с матрицей

А=	Bj Ai В1 В2 ¼ Вn A1 а11 a12 ¼ a1n A2 а21 a22 ¼ a2n ¼ ¼ ¼ ¼ ¼ Am am1 am2 ¼ amn