Решение. 1. Так как не равно , то игра не имеет седловой точки.

1. Так как не равно , то игра не имеет седловой точки.

2. В данной игре нет дублирующих и доминируемых стратегий.

3. Решаем игру путем решения пары двойственных задач линейного программирования.

Математические модели пары двойственных задач линейного программирования будут выглядеть следующим образом:

Прямая (исходная) задача: Найти неотрицательные переменные х 1, х 2, х 3, минимизирующие функцию при ограничениях:

Двойственная задача: Найти неотрицательные переменные у 1, у 2, у 3, максимизирующие функцию , при ограничениях:

Данные задачи решаются, например, симплекс-методом. Поскольку в двойственной задаче ограничения имеют вид «£», то эту задачу решать проще (не нужно вводить искусственные переменные). Оптимальное решение исходной задачи можно будет непосредственно получить из данных симплекс-таблицы для оптимального решения двойственной задачи.

Начальная симплекс-таблица двойственной задачи имеет вид

Последующие симплекс-таблицы приведены ниже:

И, наконец, получаем симплекс-таблицу, которая соответствует оптимальному решению двойственной задачи:

Оптимальное решение двойственной задачи линейного программирования следующее:

.

Находим оптимальную смешанную стратегию игрока В в соответствии с формулами (3.37) и (3.38):

;

.

Следовательно, .

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

Получаем .

Отсюда определим вероятности применения своих активных стратегий игроком А:

.

Следовательно, .

Таким образом, решение игры m ´ n сводится к решению задачи линейного программирования. Нужно заметить, что и, наоборот, – для любой задачи линейного программирования может быть построена эквивалентная ей задача матричной игры. Эта связь задач теории матричных игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения матричных игр, которые при большой размерности задачи могут оказаться проще, чем симплекс-метод.

3.3.9. Приближенный метод решения матричных игр m´ n

Рассмотрим приближенный метод решения матричных игр – метод Брауна-Робинсон (метод итераций). Идея его заключается в следующем. Разыгрывается эксперимент, в котором игроки А и В поочередно применяют друг против друга свои чистые стратегии. Каждый из игроков стремится увеличить свой выигрыш, предполагая, что будущее будет походить на прошлое; при этом считается, что ни один из них не знает своей оптимальной стратегии.

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

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

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

Объясним этот метод на примере игры 3´ 3, платёжная матрица которой приведена ниже. Игра начинается с произвольно выбранной стратегии игрока А, – например, стратегии А ₁ (выбранные стратегии обозначаются звездочкой). Платёжные элементы этой строки переписываются под платёжной матрицей. Игрок В, предполагая, что будущее будет походить на прошлое, выберет стратегию В ₁, при которой его проигрыш минимален. Соответствующий этой стратегии проигрыш обозначен звездочкой. Платёжные элементы стратегии В ₁ переписываются справа от платёжной матрицы. Игрок А, также предполагая, что будущее будет походить на прошлое, выбирает стратегию А ₂ (наибольшее число обозначено звездочкой). Платёжные элементы, соответствующие стратегии А ₂, прибавляются поочередно к элементам предыдущей строки, записанной под матрицей. Далее выбирается наименьший элемент суммарной строки. Ему соответствует стратегия В ₂. Тогда к столбцу, записанному справа от платёжной матрицы, поочередно прибавляются платёжные элементы стратегии В ₂. Этот процесс продолжается до тех пор, пока разрыв между нижней и верхней оценками игры станет небольшим. Если при выборе стратегий на некотором шаге есть несколько альтернатив, то выбирается любая из равноценных стратегий.

В рассматриваемом примере сделано 20 шагов. За эти двадцать шагов игрок А применил свою первую стратегию (количество звездочек в суммарных выигрышах, соответствующейих первой стратегии) 7 раз; вторую – 8 раз; третью – 5 раз. Игрок В применил стратегию В ₁ восемь раз; вторую – 8 раз; третью – 4 раза. Следовательно, приближенные оценки оптимальных стратегий, полученные за 20 итераций, равны:

.

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

Приближенную цену игры определяют как среднеарифметическое между нижней оценкой игры a, равной минимально накопленному выигрышу игрока А, деленному на число шагов k, и верхней оценкой игры b, равной максимальному суммарному проигрышу игрока В, деленному на k:

.

В рассматриваемом примере

.

Точная цена игры n= 1, 8.

Разрыв между a и b отражает неточность оценок относительно оптимальных смешанных стратегий. В примере составляет 2, 8% от цены игры n = 1, 8.

Увеличивая число итераций k, можно найти еще более точные оценки оптимальных смешанных стратегий.

Преимуществом итерационного метода решения матричных игр является то, что объем вычислений с увеличением размерности игры m ´ n растет существенно медленнее, чем в методе линейного программирования (в симплекс-методе).

3.3.10. Качественная оценка элементов платёжной матрицы

Очевидной трудностью при использовании теории игр является задание элементов платёжной матрицы с требуемой точностью. Вместе с тем эту задачу не нужно и переоценивать. Использование, например, свойств 1 и 2 из подраздела 3.3.6 позволяет находить оптимальные стратегии, задавая лишь относительные значения элементов платёжной матрицы. Например, если в платёжной матрице имеется всего три различных значения элементов платёжной матрицы, то в этом случае совершенно не важно, какое значение имеют наименьший и наибольший платёжи. Единственно, что имеет значение – это относительное положение третьего платежа.

Таким образом, теория игр может дать важные результаты даже в тех случаях, в которых точные оценки платёжей затруднены. В частности, имеется слабая форма оценки платёжей, называемая упорядочением. Она заключается в расположении платёжей по порядку их относительной величины. Существуют игровые ситуации, для которых не требуется ничего большего, чем определение порядка расположения платёжей по величине. В других игровых ситуациях знание порядка платёжей позволяет сделать частичные выводы относительно оптимальных стратегий и цены игры.

Пусть, например, платёжи оцениваются как плохие (п); удовлетворительные (у), хорошие (х) или отличные (о), а матрица игры имеет вид

В этой игре a = b = y, т.е. игра решается в чистых стратегиях. Игрок А должен придерживаться своей второй стратегии, а игрок В – стратегии В ₁. Цена игры – “удовлетворительно”.

Пусть игра имеет седловую точку в клетке, отмеченной звездочкой.

Так как седловая точка отмечает наименьшее число в этой строке и наибольшее число в столбце, то все остальные числа в данной строке (столбце) могут быть какими угодно, лишь бы число, отмеченное звездочкой, оставалось наименьшим в строке и наибольшим в столбце.

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

Пример. Решить игру, платёжная матрица которой имеет вид

Как видно, стратегия В ₁ доминирует над стратегией В ₃, далее стратегия А ₁ будет доминировать над стратегией А ₃, а, следовательно, исходную игру можно свести к игре 2´ 2:

Таким образом, игрокам не следует использовать стратегии А ₃ и В ₃. Так как a = у не равняется b = х, то игра не имеет седловой точки и должна решаться в смешанных стратегиях.

Частоты применения своих стратегий игроком А равны:

;

.

Частоты применения своих стратегий игроком В равны:

;

.

Таким образом, частота применения стратегии А ₁ пропорциональна разности между “хорошо” и “удовлетворительно”, а стратегии А ₂ пропорциональна разности между “отлично” и “плохо”. Ясно, что стратегия А ₁ должна применяться реже, чем стратегия А ₂ независимо от того, какие упорядоченные числа будут приписаны этим понятиям.

Положение игрока В несколько более неопределенно. Он должен применять стратегию В ₁ с частотой, пропорциональной разности между “отлично” и “удовлетворительно”, а стратегию В ₂ – с частотой, пропорциональной разности между “хорошо” и “плохо”. Здесь неясно, какая разность больше.

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