1.6 Игры 2n или m2

В играх порядка 2n первый игрок имеет 2 чистых стратегии, а второй n чистых стратегий, т.е. матрица выигрышей первого игрока имеет вид:

(1.52)

Если такая игра имеет седловую точку, то её легко найти и получить решение.[1]

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

(1.53)

(1.54)

(1.56)

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

(1.56)

Для решения систем (1.56), (1.55), (1.53) целесообразно воспользоваться графическим методом. С целью введем обозначения для левой части неравенства (1.53)

матричный игра математический модель

(1.57)

или, поставив из (1.55) и проведя простые преобразования, получим

(1.58)

где - это средний выигрыш первого игрока при условии, что он применяет свою смешанную стратегию, а второй свою j-ю чистую стратегию.[]

Каждому значению j=1, 2, … , n согласно выражению соответствует прямая линия в прямоугольной системе координат.

Цель второго игрока минимизировать выигрыш первого игрока за счет выбора своих стратегий. Поэтому вычисляем

(1.59)

где - нижняя граница множества ограничений. На рисунке 1.6 график функции изображен жирной линей.

Размещено на http://www.allbest.ru/

Рисунок 1.6 - график функции

Цель первого игрока максимизировать свой выигрыш за счет выбора , т.е. вычислить

(1.60)

На рисунке 1.6 точка означает максимальное значение , которое получается при . Цена игры , так как: [1]

(1.61)

Таким образом графически определяется оптимальная смешанная стратегия первого игрока и пара чистых стратегий второго игрока, которые в пересечении образуют точку На рисунке 1.6 изображены 2-я и 3-я стратегия второго игрока. Для таких стратегий неравенства (1.53) превращаются в равенства. На рисунке 1.6 это стратегии j=2, j=3.

Теперь можно решить систему уравнений

(1.62)

и точно определить значения и (графически они определяются приближенно). Затем положив все значения при тех j, для которых не образуют точку , решая систему уравнений (1.56) Для примера, приведенного на рисунке 1.6, это следующая система:

(1.63)

а остальные Эту систему можно решить, пологая Если при некоторой j=j₀ стратегии второго игрока образуют точку М⁰ и то максимальное значение нижней границы множеств ограничений изображается отрезком, параллельным оси В этом случае первый игрок имеет бесконечно много оптимальных значений а цена игры Этот случай изображен на рисунке 1.7, где и отрезок MN изображают верхнее ограничений, оптимальные значения находятся в пределах У второго игрока имеется чистая оптимальная стратегия j=j₀.

Матричные игры порядка m2 решаются также с помощью графического метода. Матрица выигрышей первого игрока в этом случае имеет вид

(1.64)

Смешанные стратегии соответственно первого и второго игроков определяются аналогично, как в случае игр порядка 2n. Пусть по горизонтальной оси откладывается значение от 0 до 1, по вертикальной - значение среднего выигрыша ) первого игрока при условиях, что первый игрок применяет свою чистую i-ю стратегию (i=1, 2, …, m), второй - свою смешанную стратегию (y₁, 1- y₁ ) =y. Например, при m=4 графически ) могут быть представлены так, как изображено на рисунке 1.7. [1]

Рисунок 1.7 - график функции )

Первый игрок старается максимизировать свой средний выигрыш, поэтому он стремиться найти

(1.65)

Где

(1.66)

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

(1.67)

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

(1.68)

Или

(1.69)

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

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

(1.70)

1.7 Матричный метод решения игр

Обозначения:

; (1.71)

- любая квадратная подматрица матрицы порядка [3]

- матрица (1);

- матрица, транспонированная к ;

- матрица, присоединенная к В;

- (1) матрица полученная из X вычеркиванием элементов, которые соответствуют строкам, вычеркнутым из при получении ;

- (1) матрица полученная из вычеркиванием элементов, которые соответствуют строкам, вычеркнутым из при получении .

Алгоритм:

1. Выберем квадратную подматрицу матрицы порядка () и вычислим

, (1.72)

. (1.73)

2. Если некоторое или , то отбрасываем найденную матрицу и пробуем другую матрицу .

3. Если (), (), вычисляем и строим X и из и , добавляя в соответствующих местах нули.

(1.74)

Проверяем, удовлетворяются ли неравенства

для каждого (1.75)

и неравенства

для каждого (1.76)

Если одно из соотношений не выполнено, то пробуем другое . Если все соотношения справедливы, то X, и искомые решения. [3]