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

Цель: научить решать матричные игры в чистых стратегиях.

Оборудование: практикум, тетрадь для лабораторных и практических работ.

Литература:

1. Плотников А. Д. Математическое программирование: экспресс-курс. - Мн.: Новое знание, 2007. С. 147-156.
2. Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 446-465.

Время выполнения: 2 часа.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Опишите понятие матричной игры.
2. Опишите понятие стратегии матричной игры.
3. Опишите понятие платежной матрицы матричной игры.
4. Опишите правила выбора стратегии в матричной игре.
5. Опишите понятие нижней и верхней цены матричной игры.
6. Опишите понятие седловой точки матричной игры.
7. Опишите процесс поиска решения матричной игры в чистых стратегиях.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:

Матричной игрой в математической теории игр называется игра двух лиц с нулевой суммой, в которой в распоряжении каждого из них имеется конечное множество стратегий. Правила матричной игры определяет платёжная матрица, элементы которой - выигрыши первого игрока, которые являются также проигрышами второго игрока.

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

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

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется m чистых стратегий, а в распоряжении второго игрока - n чистых стратегий.

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

Составим платёжную матрицу:

Сначала определим величину выигрыша первого игрока, если он использует i-ю чистую стратегию. Если первый игрок использует i-ю чистую стратегию, то логично предположить, что второй игрок будет использовать такую чистую стратегию, благодаря которой выигрыш первого игрока был бы минимальным. В свою очередь первый игрок будет использовать такую чистую стратегию, которая бы обеспечила ему максимальный выигрыш. Исходя из этих условий выигрыш первого игрока, который обозначим как v₁, называется максиминным выигрышем или нижней ценой игры.

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

Теперь определим величину проигрыша второго игрока, если он использует j-ю стратегию. В этом случае первый игрок использует такую свою чистую стратегию, при которой проигрыш второго игрока был бы максимальным. Второй игрок должен выбрать такую чистую стратегию, при которой его проигрыш был бы минимальным. Проигрыш второго игрока, который обозначим как v₂, называется минимаксным проигрышем или верхней ценой игры.

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

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

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

В этом случае матричная игра имеет решение в чистых стратегиях.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

Пример. Дана матричная игра с платёжной матрицей

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку? Существует ли решение в чистых стратегиях для данной матричной игры?

Решение.

Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы - наибольшие элементы в столбцах и выберем минимальный из них:

Нижняя цена игры совпадает с верхней ценой игры. Таким образом, цена игры равна 6. То есть . Цена игры равна значению седловой точки . Максиминная стратегия первого игрока - третья чистая стратегия, а минимаксная стратегия второго игрока - вторая чистая стратегия. Данная матричная игра имеет решение в чистых стратегиях.

СОДЕРЖАНИЕ РАБОТЫ:

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Опишите понятие матричной игры.
2. Опишите понятие стратегии матричной игры.
3. Опишите понятие платежной матрицы матричной игры.
4. Опишите правила выбора стратегии в матричной игре.
5. Опишите понятие нижней и верхней цены матричной игры.
6. Опишите понятие седловой точки матричной игры.
7. Опишите процесс поиска решения матричной игры в чистых стратегиях.

ДОМАШНЕЕ ЗАДАНИЕ:

Выучить процесс поиска решения матричной игры в чистых стратегиях.