§ 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.

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

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

Рис.1

При каждом фиксированном y₁ первый игрок, выбравший стратегию δ_i, несет потери g_i (y₁). Первый игрок минимизирует свои потери, поэтому мы рассматриваем ломаную (ломаная (рис.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₃)

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

которые имеют следующий смысл: f_J(x₁) – это доход фермера, если он использует чистую стратегию Θ_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.

Задачи к § 6

6.1. Имеется матрица

,

причем а* ≠ а_*. Доказать, что решением игры будет:

.

6.2. Рассмотрите игры 2×4 и 5×2 с матрицами потерь первого игрока соответственно

,     .

Решите эти игры графически.

§ 7.  A – игра порядка 3 ´ 3

Рассмотрим метод решения данной игры на следующем примере: дана матрица потерь первого игрока

        

Поскольку  a^* = 2,   a_* = 0, то простая A–игра не имеет цены. Перейдем   к   отысканию цены       ã   и   оптимальных стратегий x = (x₁, x₂, x₃),   ∑x_i = 1; y = (y₁, y₂, y₃),   ∑y_j = 1 в расширенной A – игре. Для этого рассмотрим три линейных функции

f_j(x₁, x₂) = a_1jx₁ + a_2jx₂ + a_3j(1 – x₁ – x₂),   j = 1, 2, 3,

т.е.

f₁(x₁, x₂) = x₁ + 2x₂ – (1 – x₁ – x₂) = 2x₁ + 3x₂ – 1,

                      f₂(x₁, x₂) = 2x₁ + 0x₂ + (1 – x₁ – x₂) = x₁ – x₂ + 1,

f₃(x₁, x₂) = -3x₁ + x₂ + 2(1 – x₁ – x₂) = -5x₁ – x₂ + 2.

Число f_j(x₁, x₂) равно потерям первого игрока, если он применяет свою смешанную стратегию x = (x₁, x₂, 1 – x₁ – x₂), а второй игрок – чистую стратегию q_j.

Попарно приравниваем эти функции:

f₁(x₁, x₂)  = f₂(x₁, x₂),

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

f₂(x₁, x₂) = f₃(x₁, x₂).

Получаем три линейных уравнения  для переменных x₁, x₂:

l₁: x₁ + 4x₂ = 2,

l₂: 7x₁ + 4x₂ = 3,

l₃: 6x₁ = 1.

На плоскости переменных x₁, x₂ построим эти прямые, предварительно определив область определения:

x₃ = 1 – x₁ – x₂ ³ 0,   Þ   x₁ + x₂ £ 1;   x_i ³ 0

Рис.1

Находим координаты точек, входящих в область определения и находящихся на пересечениях прямых (между собой, а также с границей), затем подставляем их в функции и находим потери. Для более наглядного представления составим таблицу, где первая колонка – это номер точки; следующие три – значения функций f₁,  f₂,  f₃ в этой точке; последняя – значение максимума в этой точке, т.е.

f_­(x₁, x₂) = max{ f₁(x₁, x₂),  f₂(x₁, x₂),  f₃(x₁, x₂)}

Далее находим минимум чисел, стоящих в восьмом столбце; это и будет искомая цена ã в расширенной А–игре (у нас ã = 17/24). Координаты соответствующей точки определяют оптимальную стратегию первого игрока (у нас x = (4/24, 11/24, 9/24)).

Осталось найти оптимальную стратегию y = (y₁, y₂, y₃) второго игрока. Это можно сделать с помощью лемм 2, 3 (§ 4), однако мы поступим иначе.

Возьмем три линейные функции

g_i(y₁, y₂) = a_i1y₁ + a_i2y₂ + a_i3(1 – y₁ – y₂),   i = 1, 2, 3,

т.е.                       g₁(y₁, y₂) = y₁ + 2y₂ – 3(1 – y₁ – y₂),

g₂(y₁, y₂) = 2y₁ + 0y₂ + (1 – y₁ – y₂),

g₃(y₁, y₂) = -y₁ + y₂ + 2(1 – y₁ – y₂),

и составим три линейных уравнения, приравняв их попарно:

g₁(y₁, y₂) =  g₂(y₁, y₂),

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

g₂(y₁, y₂) = g₃(y₁, y₂).

На плоскости переменных y₁, y₂ построим  прямые, соответствующие уравнениям l₁, l₂, l₃, предварительно определив область определения  (y₃ = 1 – y₁ – y₂ ³ 0,   Þ   y₁ + y₂ £ 1;   y_i ³ 0).

l₁: 3y₁ + 6y₂ = 4,

l₂: 7y₁ + 6y₂ = 5,

l_3: 4y₁ = 1.

Рис.2

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

g_¯(y₁, y₂) = min{ g₁(y₁, y₂),  g₂(y₁, y₂),  g₃(y₁, y₂):

Далее находим максимум чисел, стоящих в восьмом столбце (это, очевидно, цена игры ã = 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).

Вам также может быть полезна лекция "О том, как работает Internet".

Задачи к § 7

7.1. Найти графическим методом решения следующих А-игр: