Доминирующие и полезные стратегии
Иногда применение некоторых из чистых стратегий нецелесообразно и при определении оптимальных смешанных стратегий их не следует учитывать. Те чистые стратегии, которые входят в состав оптимальной смешанной стратегии, называются полезными стратегиями.
Предположим, что для двух чистых стратегий δl и δk первого игрока имеет место следующее неравенство:
.
В этом случае нет смысла применять стратегию δk (т.к. для первого игрока это проигрыш и стратегия с наибольшим проигрышем должна быть отброшена) и δl – доминирующая стратегия по отношению к стратегии δk..
Аналогичным образом определяется стратегия второго игрока. Пусть для двух чистых стратегий второго игрока θl и θk имеет место неравенство:
.
Тогда θl – доминирующая стратегия второго игрока (для второго игрока это выигрыш и отбрасывается стратегия с наименьшим выигрышем).
Предположим, что в рассматриваемой игре ни одна из стратегий не доминирует над другими. В этой ситуации пытаемся ответить на вопрос: все ли стратегии являются полезными, то есть входят в оптимальную смешанную стратегию?
Пусть у второго игрока имеется конечное число стратегий, то исходная игра сводится к так называемой S-игре. Попытаемся вывести понятие «S-игра».
Пусть имеется А = (аij), i = 1,…,n; j = 1,…,m – матрица потерь первого игрока. Каждой стратегии δi первого игрока ставим в соответствие точку сi = (ai1,ai2,…,aim) в m-мерном пространстве, где координатами являются потери.
Игра, заданная множеством точек {с1,c2,…,cn} называется S-игрой. Сначала первый игрок выбирает одну из точек сi. Независимо от первого игрока второй выбирает координату точки, например аi2, при этом говорят, что потери первого игрока составляют аi2.
Если у второго игрока имеется две стратегии, то S-игра допускает наглядную интерпретацию. Предположим, что матрица игры выглядит следующим образом:
 |
S-игра: с1 = (1,0);
с2 = (2,3);
с3 = (-1,1);
с4 = (0,-1);
с5 = (1,2).
Рис.1
Отмечаем точки на плоскости и соединяем их прямыми линиями для получения выпуклого множества (рис.1). Точки этого множества определяются так:
S = l1c1+l2c2+l3c3+l4c4 , где 
.
Теорема 1. Любая смешанная стратегия первого игрока может быть представлена точкой, принадлежащей выпуклой оболочке S* и наоборот.
Выпуклая оболочка S* конечного множества (с1,…,сn) является выпуклым многогранником в n-мерном пространстве. Точка So, являющаяся граничной, будет принадлежать обязательно одной из его граней, вершины которой и будут соответствовать полезной стратегии первого игрока. Учитывая, что число вершин любой грани не может превышать общего числа его вершин (то есть числа n ) и не может превышать размерности пространства (то есть числа m) приходим к выводу, что число полезных стратегий первого игрока не превышает min{n,m}.
Теорема 2.Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш игроков остается неизменным и равным цене ã, независимо от того, какую смешанную стратегию применяет другой игрок, если только он не выходит за пределы своих полезных стратегий.
Доказательства этих теорем можно найти в [ ].
§ 6. А-игры порядка 2 × 2, 2 × m, n × 2
А-игра порядка 2 × 2.Рассмотрим А-игру порядка 2×2, которая задается матрицей потерь первого игрока.
Для решения этой игры следует сначала найти верхнюю и нижнюю цены в простой А-игре:
 |
Рассмотрим вариант, когда а* ≠ a*. В этом случае, оптимальные стратегии игроков следует искать среди смешанных стратегий: x = (x1,x2), y = (y1,y2).
Согласно леммам § 4 для их нахождения составим систему:
a11 x1 + a21 x2 ≤ ã, a11 y1 + a12 y2 ≥ ã,
a12 x1 + a22 x2≤ ã, a21 y1+ a22 y2 ≥ ã,
x1 + x2= 1, y1 + y2 = 1.
Введем обозначение: d = a11 + a22 – a12 – a21.
Лемма 1.Если а*≠ а*, то d ≠ 0 (докажите самостоятельно).
Если d ≠ 0, то легко проверить (см. задачу 6.1.), что следующие векторы
и число
являются соответственно оптимальными стратегиями и ценой в расширенной А-игре, то есть удовлетворяют приведенным выше системам линейных равенств и неравенств.
Пример 1.Пусть матрица первого игрока имеет вид
Поскольку a* = 0,4; a* = –14, то в простой А-игре нет цены и, стало быть, нет чиcтых оптимальных стратегий. Вычислим константу d.
d = –14 – 10,4 – 0,4 – 0,85 = –25,65
 |
По предложенным выше формулам находим смешанные стратегии и цену игры.
2. А-игра порядка n × 2.Игру порядка n × 2 изучим на следующем примере.
Пример 2.Фермер может выращивать две культуры (т.е. имеет две чистые стратегии θ1, θ2). Состояния погоды можно считать стратегиями природы:
δ1 = {лето жаркое, сухое};
δ2 = {лето жаркое, влажное};
δ3 = {лето теплое, сухое};
δ4 = {лето теплое, влажное};
δ5 = {лето холодное, сухое};
δ6 = {лето холодное, влажное}.
Пусть матрица доходов фермера (т.е. матрица потерь природы, которую считаем первым игроком) имеет вид:
 |
Требуется найти цену игры ã и оптимальные стратегии x = (x1, x2, x3, x4, x5, x6) и y = (y1, y2) первого и второго игроков соответственно.
Сравнивая строки в матрице потерь видим, что четвертая стратегия доминирует над третьей. Третью строку вычеркиваем, а вместо x3 подставляем 0.
Воспользуемся графическим способом решения, для этого составим линейные функции, которые выражают ожидаемые выигрыши фермера, соответствующие чистым стратегиям первого игрока, оставщимися после проведения процедуры доминирования:
Эти линейные функции имеют вид:
При каждом фиксированном y1 первый игрок, выбравший стратегию δi, несет потери gi (y1). Первый игрок минимизирует свои потери, поэтому мы рассматриваем ломаную (ломаная (рис.1) выделена жирной чертой).
Рис.1
Mаксимизируя далее доходы второго игрока, находим
Таким образом, мы графически построили оптимальную стратегию второго игрока y = (y1, 1–y1), где y1 есть точка пересечения функций g4(y1), g6(y1); цена игры ã есть значение функций g4, g6 в точке их пересечения. Составим уравнение для y1:
4y1 + 3(1–y1) = 3y1 + 6(1-y1).
Находим: ã = g4(0,75) = g6(0,75) = 3,75.
Итак, стратегия y = (3/4, 1/4) второго игрока является оптимальной.
Определим оптимальную стратегию первого игрока. На рис.1 видно, что для i = 1, 2, 3, 5 выполняются строгие неравенства gi(0,75) > ã. Это значит, что в силу леммы 3 (§4) справедливо x1 = x2 = x3 = = x5 = 0. Решением будет являться вектор x = (0,0,0,x4,0,x6). Воспользуемся условием
.
Найдем x4, x6.
x = (0, 0, 0, x4, 0, 1–x4)
1∙0 +2∙0 + 4∙0 +3x4 + 12∙0 + 6(1– x4) = 3,75
3x4 + 6 – 6x4 = 3,75
x4 = 0,75
Решение: x = (0, 0, 0, 3/4, 0, 1/4), y = (3/4,1/4), ã = 3,75
Фермер может интерпретировать полученный ответ двояко: в среднем 3 года из 4-х сеять первую культуру, 1 год – вторую, либо в среднем 3/4 площадей отводить под первую культуру, 1/4 под вторую.
3. А-игра порядка 2 × m. Игру порядка 2 × m изучим на следующем примере.
Пример 3.При выращивании картофеля фермер может вносить удобрения в почву по следующей схеме:
θ1 = {количество удобрений на 1 га соответствует определенной норме};
θ2 = {количество удобрений на 1 га больше этой нормы на 30%};
θ3 = {количество удобрений на 1 га меньше нормы на 40%}.
Для природы рассмотрим два вида погоды:
δ1 = {лето сухое};
δ2 = {лето влажное}.
Предположим, что матрица потерь первого игрока (доходов второго игрока – фермера) имеет вид:
.
Нетрудно вычислить: ã* = 4, ã* = 2,5, ã* ≠ ã* .
Рассмотрим смешанные стратегии игроков:
x = (x1, x2), y = (y1, y2, y3)
Составим функции:
которые имеют следующий смысл: 
– это доход фермера, если он использует чистую стратегию Θj, а природа отвечает ему смешанной стратегией x = (x1, 1–x1). Эти линейные функции имеют вид
 |
Рис.2
Максимизируя функции fj(x1), получаем функцию (см. рис. 2)
которая определяет максимальный доход фермера при стратегии природы (x1, x2), где x2 = 1–x1.
Поэтому цена игры такова:
.
Как видно из рис.2 цена игры ã есть значение функций f1, f2 в точке их пересечения. Составим уравнение для x1:
2x1 + 2 = –2x1 +4
x1 = 1/2.
Оптимальной стратегией первого игрока будет x = (1/2, 1/2), а ценой игры ã = f1(1/2) = 3. Для нахождения оптимальной стратегии второго игрока воспользуемся леммой 3 §4
.
По второй части леммы 3 (§3):
f3(1/2)<3 => y3 = 0.
Следовательно, оптимальная стратегия второго игрока будет иметь вид: y = (y1, y2, 0) = (y1, 1– y1, 0). Составим уравнение
4y1 + 2(1– y1) + 3∙0 = 3,
y1 = 1/2.
Итак, получили решение:
x = (1/2, 1/2), y = (1/2, 1/2, 0), ã = 3.
Задачи к § 6
6.1.Имеется матрица
,
причем а* ≠ а*. Доказать, что решением игры будет:
.
6.2.Рассмотрите игры 2×4 и 5×2 с матрицами потерь первого игрока соответственно
, 
.
Решите эти игры графически.
§ 7. A – игра порядка 3 ´ 3
Рассмотрим метод решения данной игры на следующем примере: дана матрица потерь первого игрока
Поскольку a* = 2, a* = 0, то простая A–игра не имеет цены. Перейдем к отысканию цены ã и оптимальных стратегий x = (x1, x2, x3), ∑xi = 1; y = (y1, y2, y3), ∑yj = 1 в расширенной A – игре. Для этого рассмотрим три линейных функции
fj(x1, x2) = a1jx1 + a2jx2 + a3j(1 – x1 – x2), j = 1, 2, 3,
т.е.
f1(x1, x2) = x1 + 2x2 – (1 – x1 – x2) = 2x1 + 3x2 – 1,
f2(x1, x2) = 2x1 + 0x2 + (1 – x1 – x2) = x1 – x2 + 1,
f3(x1, x2) = -3x1 + x2 + 2(1 – x1 – x2) = -5x1 – x2 + 2.
Число fj(x1, x2) равно потерям первого игрока, если он применяет свою смешанную стратегию x = (x1, x2, 1– x1 – x2), а второй игрок – чистую стратегию qj.
Попарно приравниваем эти функции:
f1(x1, x2) = f2(x1, x2),
f1(x1, x2) = f3(x1, x2),
f2(x1, x2) = f3(x1, x2).
Получаем три линейных уравнения для переменных x1, x2:
l1: x1 + 4x2 = 2,
l2: 7x1 + 4x2 = 3,
l3: 6x1 = 1.
На плоскости переменных x1, x2 построим эти прямые, предварительно определив область определения:
x3 = 1 – x1 – x2 ³ 0, Þ x1 + x2 £ 1; xi ³ 0
Находим координаты точек, входящих в область определения и находящихся на пересечениях прямых (между собой, а также с границей), затем подставляем их в функции и находим потери. Для более наглядного представления составим таблицу, где первая колонка – это номер точки; следующие три – значения функций f1, f2, f3 в этой точке; последняя – значение максимума в этой точке, т.е.
f(x1, x2) = max{ f1(x1, x2), f2(x1, x2), f3(x1, x2)}
| N | x1 | x2 | x3 | f1 | f2 | f3 | f |
| -1 | |||||||
| -3 | |||||||
| 3/4 | 1/4 | 5/4 | 5/4 | 5/4 | |||
| 1/2 | 1/2 | 1/2 | 1/2 | 3/2 | 3/2 | ||
| 1/6 | 5/6 | 2/3 | 7/6 | 7/6 | 7/6 | ||
| 3/7 | 4/7 | -1/7 | 10/7 | -1/7 | 10/7 | ||
| 2/3 | 1/3 | 4/3 | 4/3 | -5/3 | 4/3 | ||
| 1/6 | 5/6 | 11/6 | 1/3 | 1/3 | 11/6 | ||
| 1/6 | 11/24 | 3/8 | 17/24 | 17/24 | 17/24 | 17/24 |
Далее находим минимум чисел, стоящих в восьмом столбце; это и будет искомая цена ã в расширенной А–игре (у нас ã = 17/24). Координаты соответствующей точки определяют оптимальную стратегию первого игрока (у нас x = (4/24, 11/24, 9/24)).
Осталось найти оптимальную стратегию y = (y1, y2, y3) второго игрока. Это можно сделать с помощью лемм 2, 3 (§ 4), однако мы поступим иначе.
Возьмем три линейные функции
gi(y1, y2) = ai1y1 + ai2y2 + ai3(1 – y1 – y2), i = 1, 2, 3,
т.е. g1(y1, y2) = y1 + 2y2 – 3(1 – y1 – y2),
g2(y1, y2) = 2y1 + 0y2 + (1 – y1 – y2),
g3(y1, y2) = -y1 + y2 + 2(1 – y1 – y2),
и составим три линейных уравнения, приравняв их попарно:
g1(y1, y2) = g2(y1, y2),
g1(y1, y2) = g3(y1, y2),
g2(y1, y2) = g3(y1, y2).
На плоскости переменных y1, y2 построим прямые, соответствующие уравнениям l1, l2, l3, предварительно определив область определения
(y3 = 1 – y1 – y2 ³ 0, Þ y1 + y2 £ 1; yi ³ 0).
l1: 3y1 + 6y2 = 4,
l2: 7y1 + 6y2 = 5,
l3: 4y1 = 1.
Находим координаты точек, входящих в область определения и находящихся на на пересечениях прямых (между собой, а также с границей), затем подставляем их в функции и находим потери. Заполним следующую таблицу, где
g¯(y1, y2) = min{ g1(y1, y2), g2(y1, y2), g3(y1, y2):
| N | y1 | y2 | y3 | g1 | g2 | g3 | g¯ |
| -3 | -3 | ||||||
| -1 | -1 | ||||||
| 5/7 | 2/7 | -1/7 | 12/7 | -1/7 | -1/7 | ||
| 1/4 | 3/4 | -8/4 | 5/4 | 5/4 | -8/4 | ||
| 2/3 | 1/3 | 1/3 | 1/3 | 4/3 | 1/3 | ||
| 5/6 | 1/6 | 7/6 | 1/6 | 7/6 | 1/6 | ||
| 1/4 | 3/4 | 7/4 | 2/4 | 2/4 | 2/4 | ||
| 2/3 | 1/3 | 4/3 | 4/3 | -1/3 | -1/3 | ||
| 6/24 | 13/24 | 5/24 | 17/24 | 17/24 | 17/24 | 17/24 |
Далее находим максимум чисел, стоящих в восьмом столбце (это, очевидно, цена игры ã = 17/24; попутно получаем проверку вычислений, так как полученное число совпало с найденным ранее). Координаты точки, стоящей в этой строке, соответствуют искомой оптимальной стратегии второго игрока y = (6/24, 13/24, 5/24). Итак, мы получили ответ:
ã = 17/24, x = (4/24, 11/24, 9/24), y = (6/24, 13/24, 5/24).
Задачи к § 7
7.1.Найти графическим методом решения следующих А-игр:
§ 8. Расширенная A – игра и задача линейного программирования
Для любой расширенной А–игры с матрицей А размера n ´ m можно построить пару двойственных задач линейного программирования, эквивалентных А – игре.
Пусть даны: матрица Ā размера 
, вектор-строка b длины 
. Условимся для двух векторов a = (a1, ¼, ak), b = (b1, ¼, bk) длины k писать:
a ³ b, если ai ³ bi для i = 1,¼, k.
Сформулируем пару задач линейного программирования и расширенную А-игру в матричной форме.
Прямая задача линейного программирования
Найти вектор 
, удовлетворяющий следующим условиям:
при ограничениях:
где
Двойственная задача линейного программирования
Найти вектор 
, удовлетворяющий следуюшим условиям:
при ограничениях:
Расширенная А – игра
Найти векторы x = (x1, ¼, xn), y = (y1, ¼, ym) и число ã, удовлетворяющие условиям:
где ek = (1, ¼, 1) и A – матрица размера n ´ m.
Предположим, что матрица A расширенной A–игры имеет только положительные элементы (aij ³ 0) и x, y – оптимальные стратегии игры с положительной ценой ã.
Введем набор элементов, определяющих пару двойственных задач линейного программирования:
Решением этих задач будет:
Прямая задача будет выглядеть:
при ограничениях:
Двойственная задача:
при ограничениях:
Действительно ли 
являются решениями задач?
Проверяем условия:
,
т.е. удовлетворяют необходимым условиям.
Предположим, что есть еще один, претендующий на решение, вектор 
, удовлетворяющий условиям:
,
и такой, что
Обозначим 
. Очевидно, что вектор z удовлетворяет соотношениям
В силу лемм (§4) строгое неравенство здесь невозможно, поэтому вектор не является решением.
Аналогично доказывается и для 
.
Таким образом доказывается, что векторы являются решением пары задач линейного программирования.
Рассмотрим обратную связь. Предположим, что имеется матрица А с положительными элементами и являются решением пары задач линейного программирования.
Тогда оптимальные стратегии имеют вид:
где
Если матрица А имеет неположительные элементы, то прибавляем к каждому элементу этой матрицы положительное число d такое, чтобы новая матрица
была положительной, где
Для матрицы A/ c положительными элементами можно построить пару задач линейного программирования. Для такой матрицы оптимальные стратегии x/, y/ совпадают с оптимальными стратегиями x, y, а цена игры 
.
Задачи к § 8
8.1. Составить пару задач линейного программирования, эквивалентных игре 7.1.
8.2.Рассмотрите игру, в которой два противника А и В ведут борьбу за два стратегических пункта. Под командованием А находятся два полка, под командованием В – три. Обе стороны должны распределить свои силы между двумя пунктами. Пусть n1 и n2 – количество полков, посланных со стороны А на пункты 1 и 2 соответственно. Аналогично пусть m1 и m2 – количество полков, посланных В на пункты 1 и 2. Выигрыш В подсчитывается следующим образом. Если m1 > n1, он получает на первой позиции 2n1+1 очков, если m1 < n1, он теряет на первой позиции 2m1+1 очков. Аналогично осуществляется подсчет на второй позиции. И наконец, если число полков на какой-нибудь позиции с каждой стороны одно и то же, то каждая сторона на этой позиции получает ноль очков. Сформулируйте задачу как расширенную А-игру и решите ее методом линейного программирования.