Материал: Д6903 Алексеев ГВ Системный подход в пищевой инженерии

Определим нижние и верхние чистые цены игры (табл. 3):

v = = = 5.

В данном случае имеем одну седловую точку (A1, B2), а седловой элемент равен 5. Этот элемент является наименьшим в 1-й строке и наибольшим во 2-м столбце. Отклонение игрока А от максиминной стратегии A1 ведет к уменьшению его выигрыша, а отклонение игрока В от минимаксной стратегии B2 ведет к увеличению его проигрыша. Иными словами, если в матричной игре имеется седловой элемент, то наилучшими для игроков являются их минимаксные стратегии. И эти чистые стратегии, образующие седловую точку и выделяющие в матрице игры седловой элемент а12 = 5, есть оптимальные чистые стратегии A1 и B2 игроков А и В.

Если же матричная игра не имеет седловой точки, то решение игры затрудняется. В этих играх < . Применение минимаксных стратегий в таких играх приводит к тому, что для каждого из игроков выигрыш не превышает , а проигрыш – не меньше . Для каждого игрока возникает вопрос увеличения выигрыша (уменьшения проигрыша). Решение находят, применяя смешанные стратегии. Смешанной стратегией первого (второго) игрока называется вектор

р = (p1;... ; рт), где

11

Вектор р (q) означает вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком).

Поскольку игроки выбирают свои чистые стратегии случайно и независимо друг от друга, игра имеет случайный характер и случайной становится величина выигрыша (проигрыша). В таком случае средняя величина выигрыша (проигрыша) – математическое ожидание – является функцией смешанных стратегий p,q:

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

Совокупность оптимальных стратегий и цены игры составляет

решение игры.

Значение платежной функции при оптимальных стратегиях определяет цену игры v, т. е. f(p*,q*) = v.

Если в матричной игре имеем строки (столбцы) с одними и теми же элементами, то строки (столбцы), а соответственно и стратегии игроков А и В называются дублирующими.

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

Платежную матрицу, имеющую отрицательные числа, можно преобразовать в матрицу с положительными числами.

Пример 2. Выполним все возможные упрощения матричной

игры

12

Поскольку соответствующие элементы второй и четвертой строк матрицы игры равны, т. е. имеем две дублирующие строки, опустим, например, четвертую строку:

Сравним соответствующие элементы столбцов.

Элементы первого столбца доминируют над элементами третьего и шестого столбцов, а элементы второго столбца доминируют над соответствующими элементами четвертого столбца. Игроку В невыгодно применять стратегии B3, B4 и B6. Опускаем третий, четвертый и шестой столбцы и получаем матрицу

Элементы второй строки меньше соответствующих элементов третьей строки. Следовательно, игроку А невыгодна стратегия А2. Опуская вторую строку, получаем упрощенную матрицу

4 2 2

3 5 1 .

2 1 5

Если требуется получить матрицу с положительными элементами, то достаточно прибавить к ее элементам, например, число 3.

13

1.3. Решение матричных игр в смешанных стратегиях

Решение матричных игр в смешанных стратегиях может быть найдено либо графически, либо методами линейного программи-

рования. Графический метод применим для решения игр, в которых хоть один игрок имеет две чистые стратегии. Этот метод интересен в том плане, что графически объясняет понятие седловой точки. Методами линейного программирования может быть решена любая игра двух лиц с нулевой суммой.

Рассмотрим игру 2 п, в которой игрок А имеет две стратегии.

Игра предполагает, что игрок А смешивает стратегии А1 и А2 с соответствующими вероятностями p1= р и p2 = 1-p, 0 p 1. Игрок В смешивает стратегии В1, B2, ..., Вп с вероятностями q1, q2, …, qп, где

ка А, соответствующий j-й чистой стратегии игрока В, вычисляется в виде

На плоскости (p, w) эти уравнения описывают прямые. Тем самым каждой чистой стратегии игрока В на этой плоскости соответствует своя прямая. Поэтому сначала на плоскости (р, w) последовательно рисуются все прямые (рис. 1). Затем для каждого значения р, 0 р 1, путем визуального сравнения соответствующих ему значений w на каждой из построенных прямых определяется и отмечается наименьшее из них.

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

14

Рис. 1. Графическое решение игры 2×n

Абсциссой верхней точки полученной ломаной будет значение р*, определяющее оптимальную смешанную стратегию игрока А, а ординатой – цена игры (рис. 1).

Пример 1. Рассмотрим следующую игру 2 3:

Игра не имеет решения в чистых стратегиях ( = 2, = 3), и, следовательно, стратегии должны быть смешанными. Ожидаемые выигрыши игрока А, wА, соответствующие чистым стратегиям игрока В, приведены в следующей табл. 4.

На рис. 2 изображены три прямые линии, соответствующие чистым стратегиям игрока В. Чтобы определить наилучший результат из наихудших, построена нижняя огибающая трех указанных прямых (изображенная на рис. 1 толстыми линейными сегментами), которая представляет минимальный (наихудший) выигрыш для игрока А независимо от того, что делает игрок В. Максимум (наилучшее) нижней огибающей соответствует максиминному ре-

шению в точке p = 0,5. Это значение pопределяется из уравнения

2+p = 6-7p, отвечающего пересечению прямых 2 и 3 (табл. 5). Следовательно, оптимальным решением для игрока является

смешивание стратегий В2 и В3 с вероятностями 0,5 и 0,5 соответственно.

15