Задачи к § 4

4.1. Рассмотреть А-игру с матрицей потерь первого игрока:

а) найти а^*, а_* и убедиться, что в простой А-игре нет цены;

б) составить систему линейных уравнений и неравенств для ã, x = (x₁, x₂, x₃), y = (y₁, y₂, y₃) в расширенной А-игре;

в) найти решение ã, x, y в расширенной А-игре.

4.2. Для матрицы

решить задачу 4.1.

§ 5. Доминирующие и полезные стратегии

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

Предположим, что для двух чистых стратегий δ_l и δ_k первого игрока имеет место следующее неравенство:

.

В этом случае нет смысла применять стратегию δ_k (т.к. для первого игрока это проигрыш и стратегия с наибольшим проигрышем должна быть отброшена) и δ_l – доминирующая стратегия по отношению к стратегии δ_k..

Аналогичным образом определяется стратегия второго игрока. Пусть для двух чистых стратегий второго игрока θ_l и θ_k имеет место неравенство:

.

Тогда θ_l – доминирующая стратегия второго игрока (для второго игрока это выигрыш и отбрасывается стратегия с наименьшим выигрышем).

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

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

Пусть имеется А = (а_ij), i = 1,…,n; j = 1,…,m – матрица потерь первого игрока. Каждой стратегии δ_i первого игрока ставим в соответствие точку с_i = (a_i1, a_i2,…,a_im) в m-мерном пространстве, где координатами являются потери.

Игра, заданная множеством точек {с₁,c₂,…,c_n} называется S-игрой. Сначала первый игрок выбирает одну из точек с_i. Независимо от первого игрока второй выбирает координату точки, например а_i2, при этом говорят, что потери первого игрока составляют а_i2.

Если у второго игрока имеется две стратегии, то S-игра допускает наглядную интерпретацию. Предположим, что матрица игры выглядит следующим образом:

1 0

2 3

-1 1

0 -1

1 2

А =

S-игра: с₁ = (1,0);

с₂ = (2,3);

с₃ = (-1,1);

с₄ = (0,-1);

с₅ = (1,2).

Рис.1

Отмечаем точки на плоскости и соединяем их прямыми линиями для получения выпуклого множества (рис.1). Точки этого множества определяются так:

S = ₁c₁+₂c₂+₃c₃+₄c₄ , где .

Теорема 1. Любая смешанная стратегия первого игрока может быть представлена точкой, принадлежащей выпуклой оболочке S* и наоборот.

Выпуклая оболочка S* конечного множества (с₁,…,с_n) является выпуклым многогранником в n-мерном пространстве. Точка S_o, являющаяся граничной, будет принадлежать обязательно одной из его граней, вершины которой и будут соответствовать полезной стратегии первого игрока. Учитывая, что число вершин любой грани не может превышать общего числа его вершин (то есть числа n ) и не может превышать размерности пространства (то есть числа m) приходим к выводу, что число полезных стратегий первого игрока не превышает min{n,m}.

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

Доказательства этих теорем можно найти в [ ].

§ 6. А-игры порядка 2 × 2, 2 × m, n × 2

А-игра порядка 2 × 2. Рассмотрим А-игру порядка 2×2, которая задается матрицей потерь первого игрока.

Для решения этой игры следует сначала найти верхнюю и нижнюю цены в простой А-игре:

Рассмотрим вариант, когда а* ≠ a_*. В этом случае, оптимальные стратегии игроков следует искать среди смешанных стратегий: x = (x₁,x₂), y = (y₁,y₂).

Согласно леммам § 4 для их нахождения составим систему:

a₁₁ x₁ + a₂₁ x₂ ≤ ã, a₁₁ y₁ + a₁₂ y₂ ≥ ã,

a₁₂ x₁ + a₂₂ x₂ ≤ ã, a₂₁ y₁ + a₂₂ y₂ ≥ ã,

x₁ + x₂ = 1, y₁ + y₂ = 1.

Введем обозначение: d = a₁₁ + a₂₂ – a₁₂ – a_21.

Лемма 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. Фермер может выращивать две культуры (т.е. имеет две чистые стратегии θ₁, θ₂). Состояния погоды можно считать стратегиями природы:

δ₁ = {лето жаркое, сухое};

δ₂ = {лето жаркое, влажное};

δ₃ = {лето теплое, сухое};

δ₄ = {лето теплое, влажное};

δ₅ = {лето холодное, сухое};

δ₆ = {лето холодное, влажное}.

Пусть матрица доходов фермера (т.е. матрица потерь природы, которую считаем первым игроком) имеет вид:

Требуется найти цену игры ã и оптимальные стратегии x = (x₁, x₂, x₃, x₄, x₅, x₆) и y = (y₁, y₂) первого и второго игроков соответственно.

Сравнивая строки в матрице потерь видим, что четвертая стратегия доминирует над третьей. Третью строку вычеркиваем, а вместо x₃ подставляем 0.

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

Э ти линейные функции имеют вид:

При каждом фиксированном y₁ первый игрок, выбравший стратегию δ_i, несет потери g_i (y₁). Первый игрок минимизирует свои потери, поэтому мы рассматриваем ломаную (ломаная (рис.1) выделена жирной чертой).

Рис.1

Mаксимизируя далее доходы второго игрока, находим

Таким образом, мы графически построили оптимальную стратегию второго игрока y = (y₁, 1–y₁), где y₁ есть точка пересечения функций g₄(y₁), g₆(y₁); цена игры ã есть значение функций g₄, g₆ в точке их пересечения. Составим уравнение для y₁:

4y₁ + 3(1–y₁) = 3y₁ + 6(1-y₁).

Находим: ã = g₄(0,75) = g₆(0,75) = 3,75.

Итак, стратегия y = (3/4, 1/4) второго игрока является оптимальной.

Определим оптимальную стратегию первого игрока. На рис.1 видно, что для i = 1, 2, 3, 5 выполняются строгие неравенства g_i(0,75) > ã. Это значит, что в силу леммы 3 (§4) справедливо x₁ = x₂ = x₃ = = x₅ = 0. Решением будет являться вектор x = (0,0,0,x₄,0,x₆). Воспользуемся условием

.

Найдем x₄, x₆.

x = (0, 0, 0, x₄, 0, 1–x₄)

1∙0 +2∙0 + 4∙0 +3x₄ + 12∙0 + 6(1– x₄) = 3,75

3x_4­ + 6 – 6x₄ = 3,75

x₄ = 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 га больше этой нормы на 30%};

θ₃ = {количество удобрений на 1 га меньше нормы на 40%}.

Для природы рассмотрим два вида погоды:

δ₁ = {лето сухое};

δ₂ = {лето влажное}.

Предположим, что матрица потерь первого игрока (доходов второго игрока – фермера) имеет вид:

.

Нетрудно вычислить: ã* = 4, ã_* = 2,5, ã* ≠ ã_* .

Рассмотрим смешанные стратегии игроков:

x = (x₁, x₂), y = (y₁, y₂, y₃)

Составим функции:

которые имеют следующий смысл: – это доход фермера, если он использует чистую стратегию Θ_j, а природа отвечает ему смешанной стратегией x = (x₁, 1–x₁). Эти линейные функции имеют вид

Рис.2

Максимизируя функции f_j(x₁), получаем функцию (см. рис. 2)

которая определяет максимальный доход фермера при стратегии природы (x₁, x₂), где x₂ = 1–x₁.

Поэтому цена игры такова:

.

Как видно из рис.2 цена игры ã есть значение функций f₁, f₂ в точке их пересечения. Составим уравнение для x₁:

2x₁ + 2 = –2x₁ +4

x₁ = 1/2.

Оптимальной стратегией первого игрока будет x = (1/2, 1/2), а ценой игры ã = f₁(1/2) = 3. Для нахождения оптимальной стратегии второго игрока воспользуемся леммой 3 §4

.

По второй части леммы 3 (§3):

f₃(1/2)<3 => y₃ = 0.

Следовательно, оптимальная стратегия второго игрока будет иметь вид: y = (y₁, y₂, 0) = (y₁, 1– y₁, 0). Составим уравнение

4y₁ + 2(1– y₁) + 3∙0 = 3,

y₁ = 1/2.

Итак, получили решение:

x = (1/2, 1/2), y = (1/2, 1/2, 0), ã = 3.