10.3. Матричные игры двух игроков с седловыми точками

 

Пример 10.1. Для начала рассмотрим достаточно простое задание игры. Допустим, первый игрок выбирает один из 4 возможных ходов. А второй игрок, не зная о выборе первого, делает свой выбор (один из 3 возможных). После того, как игроки приняли решение о своих стратегиях, игрок 2 платит игроку 1 сумму, определенную следующей таблицей:

 

 

Если указанная сумма в таблице отрицательна, то первый игрок выплачивает ее второму. Итак, к примеру, если первый игрок выбирает 3-й ход, а второй 1-й, то второй игрок платит первому 3 единицы. А если при таком же выборе первого игрока, второй выберет 2-й ход, то уже первый платит ему 1 единицу.

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

В нашей игре платежная матрица такова:

.

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

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

Желая получить как можно больше от игры, первый игрок сразу обратит внимание на максимально возможный выигрыш в игре. Это – 8 единиц, которые он приобретает, если и он сам и его партнер сделают 1-й ход. Однако стоит ли ему останавливаться на 1-й стратегии? Будучи разумным человеком, первый игрок понимает, что данное решение может привести и к проигрышу 5 единиц, если партнер выбирает 2-й ход, или к ничьей (при 3-м ходе партнера). Поэтому, проанализировав ситуацию, он должен остановиться на 2-м ходе, так как при любом выборе второго игрока первый получает выигрыш, пусть и не такой большой: 3, 1 или 2 единицы. Заметим, что в данной игре 3-й и 4-й ходы первый игрок может не принимать в расчет, потому что каждый элемент 3-й и 4-й строки платежной матрицы меньше или равен соответствующему элементу второй строки (2-го хода). Итак, первый игрок должен выбрать 2-й ход. При этом его минимальный выигрыш составит 1 единицу.

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

Итак, мы нашли стратегии первого и второго игроков в данной игре. Оба игрока должны выбрать 2-й ход. При такой реализации решений второй игрок заплатит первому 1 единицу.

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

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

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

Пример 10.2. Контртеррористическая операция

В ходе проведения контртеррористической операции возникла следующая ситуация. Группа террористов продвигается с запада на восток по одному из трех возможных направлений. Отряду ОМОНа поставлена боевая задача: выйти наперерез террористам, навязать им открытый бой и разгромить группу. ОМОН имеет также три маршрута движения. Пересечение путей движения отряда определит место проведения боя. Таким образом, существуют 9 возможных участков столкновения. Все они располагаются на разных относительных высотах, которые приведены на рис.10.1.

Рис. 10.1. Относительные высоты точек пересечения возможных маршрутов

Отряду милиции выгоднее навязать открытый бой противнику на местности с наименьшей относительной высотой. Террористы чувствуют себя более уверенно в горах. Участки предполагаемой схватки имеют разные высоты (они указаны на рисунке). Необходимо определить какой маршрут движения ОМОНа – оптимален.

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

Как и в прошлом примере укажем матрицу выигрышей для ОМОНа, записывая варианты его действий по строкам, а варианты действий террористов по столбцам.

 

Таким образом, платежная матрица игры:

.

         Для нахождения оптимального решения ОМОНа воспользуемся следующим методом. Для каждого варианта решения найдем наиболее неблагоприятный исход в зависимости от действия противника. Затем из полученных значений выигрышей возьмем самый максимальный. Так мы получим гарантированный выигрыш при всевозможных действиях террористов. Если они будут более «беззаботными», то выигрыш может быть еще больше. (Не забываем, что в данном случае выигрыш  для ОМОНа – это более низкая высота места проведения боя).

         Итак, наиболее неблагоприятные исходы, т.е. наименьшие выигрыши «наших» в различных строках составляют: -4.0; -1.0; -2.0. Максимальный из них -  -1.0. Таким образом, при выборе второго решения – маршрута б – бой произойдет на участке с высотой не выше 1.0 км. Эта высота обеспечивается при выборе террористами 2-го пути. При выборе других направлений движения: 1-го или 3-го высота места предполагаемого боя еще ниже: 0.5 км и 0 км.

         2-й маршрут движения ОМОНа является его чистой стратегией, а цена игры – -1.0 (относительная высота места боя – 1 км) – нижней чистой ценой игры.

         Рассмотрим действия террористов в данной конфликтной ситуации и найдем их оптимальную стратегию поведения. Естественно, что они стремятся как к можно меньшему выигрышу ОМОНа, то есть в данном примере как к можно большим значениям относительной высоты. Поэтому они должны исходить из противоположного алгоритма. Сначала им необходимо найти максимальные элементы в столбцах (максимальные выигрыши ОМОНа для каждого направления движения террористов), а затем выбрать минимальный из них. Это и будет тот выигрыш ОМОНа, добиться больше которого террористы своему противнику не позволят за счет применения своей оптимальной стратегии. Максимальные элементы столбцов: -0.5; -1.0; 0.0, а минимальный из них – -1.0. В данном случае цена игры –1.0 называется чистой верхней ценой игры. Применяя 2-ю стратегию (2-й маршрут), террористы не допустят выигрыша ОМОНа больше, чем -1.0. И относительная высота участка боя будет не ниже 1 км.

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

Предыдущая | Главная | Глава 10 | Следующая