Задача 1. Графическое решение матричных игр.

1. Найдем оптимальные стратегии игроков в игре, заданной платежной матрицей

.

Сначала проверим, есть ли в данной игре седловая точка.

Нижняя цена игры равна max {4, 3} = 4.

Верхняя цена этой игры равна min {7, 9, 9, 9} = 7.

Поскольку , то седловой точки у данной игры нет, и решение нужно искать в смешанных стратегиях.

Графически решаются те матричные игры, в которых хотя бы у одного из игроков есть лишь две чистые стратегии. Задача именно этого игрока и решается графически. В задаче 1 у первого игрока две чистых стратегии, а у второго − четыре, поэтому будем решать графически задачу первого игрока.

Смешанная стратегия первого игрока задается вектором . Построения осуществляются следующим образом. На горизонтальной прямой откладывается отрезок единичной длины, характеризующий вероятность применения чистых стратегий первым игроком. Каждой точке этого отрезка сопоставляется смешанная стратегия первого игрока по следующему правилу: расстояние от точки до правого конца отрезка задает величину , а расстояние до левого его конца − величину (см. рисунок 1.1). Для определенных таким образом величин и выполняются соотношения , , поэтому, согласно (5), вектор задает смешанные стратегии первого игрока.

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

На рисунке 1.2 изображены выигрыши первого игрока при применении вторым игроком первой чистой стратегии. Римскими цифрами указано, что второй игрок применяет именно первую чистую стратегию.

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

Аналогичные построения выполняются для остальных чистых стратегий второго игрока (рисунок 1.3). Римские цифры указывают на номер его чистой стратегии.

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

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

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

Выпишем соотношения для нахождения оптимальной смешанной стратегии первого игрока, основываясь на утверждении 1. В нашем примере платежная функция, согласно (7), имеет вид:

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

Итак, пусть , . Тогда .

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

(9)

Решив эту систему, получаем

Теперь найдем оптимальную смешанную стратегию второго игрока. Пусть она задается вектором . Здесь мы учли тот факт, что третья и четвертая чистые стратегии второго игрока являются пассивными. Выпишем величину проигрыша второго игрока, если он применяет свою оптимальную смешанную стратегию, а первый игрок − свои чистые стратегии.

Пусть . Тогда .

Пусть . Тогда .

Применяем утверждение 1, учитывая, что цена игры найдена и равна получим систему уравнений:

Решив эту систему, получаем . Итак, оптимальная смешанная стратегия второго игрока задается вектором .

Ответ к данной задаче запишем в виде:

, .