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

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

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

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

Теперь обо всём по порядку и подробно.

Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица .

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

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

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

Если первый игрок выбирает i -ю чистую стратегию, а второй игрок - j -ю чистую стратегию, то выигрыш первого игрока составит a ij единиц, а проигрыш второго игрока - также a ij единиц.

Так как a ij + (- a ij ) = 0 , то описанная игра является матричной игрой с нулевой суммой.

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

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

Как происходит выбор стратегии в матричной игре?

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

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

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

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

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

Пример 1.

Наибольший из наименьших элементов строк - 2, это нижняя цена игры, ей соответствует первая строка, следовательно, максиминная стратегия первого игрока первая. Наименьший из наибольших элементов столбцов - 5, это верхняя цена игры, ей соответствует второй столбец, следовательно, минимаксная стратегия второго игрока - вторая.

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

Итак, гарантированный выигрыш первого игрока:

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

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

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

Ещё пример из этой же серии.

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

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

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

Наибольший из наименьших элементов строк - 3, это нижняя цена игры, ей соответствует вторая строка, следовательно, максиминная стратегия первого игрока вторая. Наименьший из наибольших элементов столбцов - 5, это верхняя цена игры, ей соответствует первый столбец, следовательно, минимаксная стратегия второго игрока - первая.

Седловая точка в матричных играх

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

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

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

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

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

Решить задачу на матричную игру самостоятельно, а затем посмотреть решение

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

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

Матричные игры с оптимальной смешанной стратегией

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

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

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

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

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

Если первый игрок использует смешанную стратегию p , а второй игрок - смешанную стратегию q , то имеет смысл математическое ожидание выигрыша первого игрока (проигрыша второго игрока). Чтобы его найти, нужно перемножить вектор смешанной стратении первого игрока (который будет матрицей из одной строки), платёжную матрицу и вектор смешанной стратегии второго игрока (который будет матрицей из одного столбца):

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

Определить математическое ожидание выигрыша первого игрока (проигрыша второго игрока), если смешанная стратегия первого игрока , а смешанная стратегия второго игрока .

Решение. Согласно формуле математического ожидания выигрыша первого игрока (проигрыша второго игрока) оно равно произведению вектора смешанной стратегии первого игрока, платёжной матрицы и вектора смешанной стратегии второго игрока:

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

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

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

В таком случае для функции E существует седловая точка , что означает равенство .

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

Сведение матричной игры к задаче линейного программирования

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

Функция цели в прямой задаче линейного программирования:

Система ограничений в прямой задаче линейного программирования:

Функция цели в двойственной задаче:

Система ограничений в двойственной задаче:

Оптимальный план прямой задачи линейного программирования обозначим

а оптимальный план двойственной задачи обозначим

Линейные формы для соответствующих оптимальных планов обозначим и ,

а находить их нужно как суммы соответствующих координат оптимальных планов.

В соответствии определениям предыдущего параграфа и координатами оптимальных планов, в силе следующие смешанные стратегии первого и второго игроков:

Математики-теоретики доказали, что цена игры следующим образом выражается через линейные формы оптимальных планов:

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

Нам, практикам, остаётся лишь использовать эту формулу для решения матричных игр в смешанных стратегиях. Как и формулы для нахождения оптимальных смешанных стратегий соответственно первого и второго игроков:

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

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

Найти цену игры V и оптимальные смешанные стратегии и .

Решение. Составляем соответствующую данной матричной игре задачу линейного программирования:

Получаем решение прямой задачи:

Находим линейную форму оптимальных планов как сумму найденных координат.

Теория игр как раздел исследования операций – это теория математических моделей принятия оптимальных решений в условиях неопределенности или конфликта нескольких сторон, имеющих различные интересы. Теория игр исследует оптимальные стратегии в ситуациях игрового характера. К ним относятся ситуации, связанные с выбором наивыгоднейших производственных решений системы научных и хозяйственных экспериментов, организацией статистического контроля, хозяйственных взаимоотношений между предприятиями промышленности и других отраслей. Формализуя конфликтные ситуации математически, их можно представить как игру двух, трех и т.д. игроков, каждый из которых преследует цель максимизации своей выгоды, своего выигрыша за счет другого.

Раздел "Теория игр" представлен тремя онлайн-калькуляторами :

Оптимальные стратегии игроков . В таких задачах задана платежная матрица. Требуется найти чистые или смешанные стратегии игроков и, цену игры . Для решения необходимо указать размерность матрицы и метод решения. В сервисе реализованы следующие методы решения игры двух игроков:
1. Минимакс . Если необходимо найти чистую стратегию игроков или ответить на вопрос о седловой точке игры, выберите этот метод решения.
2. Симплекс-метод . Используется для решения игры в смешанных стратегиях методами линейного программирования.
3. Графический метод . Используется для решения игры в смешанных стратегиях. Если есть седловая точка, решение прекращается. Пример: По заданной платежной матрице найти оптимальные смешанные стратегии игроков и цену игры, используя графический метод решения игры.
4. Итерационный метод Брауна-Робинсона . Итеративный метод применяется тогда, когда не применим графический метод и когда практически не приминимы алгебраический и матричный методы. Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
Например, задание может звучать как "указать оптимальные стратегии игроков для игры, заданной платежной матрицей" .
Во всех методах применяется проверка на доминирующие строки и столбцы.
Биматричная игра . Обычно в такой игре задают две матрицы одинакового размера выигрышей первого и второго игроков. Строки этих матриц соответствуют стратегиям первого игрока, а столбцы матриц – стратегиям второго игрока. При этом в первой матрице представлены выигрыши первого игрока, а во второй матрице – выигрыши второго.
Игры с природой . Используется, когда необходимо выбрать управленческое решение по критериям Максимакса, Байеса, Лапласа, Вальда , Сэвиджа , Гурвица .
Для критерия Байеса необходимо также будет ввести вероятности наступления событий. Если они не заданы, оставьте значения по умолчанию (будут равнозначные события).
Для критерия Гурвица укажите уровень оптимизма λ . Если в условиях данный параметр не задан можно использовать значения 0, 0.5 и 1 .

Во многих задачах требуется находить решение средствами ЭВМ. Одним из инструментов служат вышеприведенные сервисы и функции

Из популярного американского блога Cracked.

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

1. Дилемма заключенного

Берто и Роберт были арестованы за ограбление банка, не сумев правильно использовать для побега угнанный автомобиль. Полиция не может доказать, что именно они ограбили банк, но поймала их с поличным в украденном автомобиле. Их развели по разным комнатам и каждому предложили сделку: сдать сообщника и отправить его за решетку на 10 лет, а самому выйти на свободу. Но если они оба сдадут друг друга, то каждый получит по 7 лет. Если же никто ничего не скажет, то оба сядут на 2 года только за угон автомобиля.

Получается, что, если Берто молчит, но Роберт сдает его, Берто садится в тюрьму на 10 лет, а Роберт выходит на свободу.

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

Практическое применение: Выявление социопатов

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

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

Хуже всего то, что все участники дилеммы заключенного действуют так, как будто никогда не слышали ней.

А лучший ход - хранить молчание, и через два года вместе с хорошим другом пользоваться общими деньгами.

2. Доминирующая стратегия

Это ситуация, при которой ваши действия дают наибольший выигрыш, независимо от действий оппонента. Что бы ни происходило - вы всё сделали правильно. Вот почему многие люди при «дилемме заключенного» считают: предательство приводит к «наилучшему» результату независимо от того, что делает другой человек, а игнорирование действительности, свойственное этому методу, заставляет всё выглядеть супер-просто.

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

3. Битва полов

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

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

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

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

Практическое применение: Избегайте острых углов

Конечно, и у этой стратегии есть свои значительные недостатки. Прежде всего, если вы относитесь к вашим свиданиям как к «битве полов», она не сработает. Расстаньтесь, чтобы каждый из вас мог найти человека, который ему понравится. А вторая проблема заключается в том, что в этой ситуации участники настолько не уверены в себе, что не могут этого сделать.

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

4. Равновесие Нэша

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

Давайте быстро поделим 100$. Вы и я решаем, сколько из сотни мы требуем и одновременно озвучиваем суммы. Если наша общая сумма меньше ста, каждый получает то, что хотел. Если общее количество больше ста, тот, кто попросил наименьшее количество, получает желаемую сумму, а более жадный человек получает то, что осталось. Если мы просим одинаковую сумму, каждый получает 50 $. Сколько вы попросите? Как вы разделите деньги? Существует единственный выигрышный ход.

Требование 51 $ даст вам максимальную сумму независимо от того, что выберет ваш противник. Если он попросит больше, вы получите 51 $. Если он попросит 50 $ или 51 $, вы получите 50 $. И если он попросит меньше 50 $, вы получите 51 $. В любом случае нет никакого другого варианта, который принесет вам больше денег, чем этот. Равновесие Нэша - ситуация, в которой мы оба выбираем 51 $.

Практическое применение: сначала думайте

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

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

5. Игра в орлянку

В орлянке участвуют Игрок 1 и Игрок 2. Каждый игрок одновременно выбирает орла или решку. Если они угадывают, Игрок 1 получает пенс Игрока 2. Если же нет - Игрок 2 получает монету Игрока 1.

Выигрышная матрица проста…

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

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

Практическое применение: Пенальти

В футболе, хоккее и многих других играх, дополнительное время - это серия пенальти. И они были бы интереснее, если бы строились на том, сколько раз игроки в полной форме смогут сделать «колесо», потому что это, по крайней мере, было бы показателем их физических способностей и на это было бы забавно посмотреть. Вратари не могут чётко определить движение мяча или шайбы в самом начале их движения, потому что, к огромному сожалению, в наших спортивных состязаниях роботы все еще не участвуют. Вратарь должен выбрать левое или правое направление и надеяться, что его выбор совпадет с выбором противника, бьющего по воротам. В этом есть что-то общее с игрой в монетку.

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

Итак, каково же наше заключение согласно теории игр? Игры с мячом должны заканчиваться способом «мультимяча», где каждую минуту игрокам один на один выводится дополнительный мяч/шайба, до получения одной из сторон определенного результата, который был показателем настоящего мастерства игроков, а не эффектным случайным совпадением.

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

Рассмотрим игру с матрицей

Буквой i будем обозначать номер нашей стратегии, буквой - номер стратегии противника.

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

(знак обозначает минимальное значение данного параметра при всех возможных

Выпишем числа (минимумы строк) рядом с матрицей справа в виде добавочного столбца:

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

или. принимая во внимание формулу (4.1),

Величина а называется нижней ценой игры, иначе - максиминным выигрышем или максимином. Та стратегия игрока А, которая соответствует максимину а, называется максиминной стратегией.

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

Очевидно, аналогичное рассуждение можно провести и за противника В. Он (аинтересован в том, чтобы обратить наш выигрыш в минимум; значит, он должен просмотреть все свои стратегии, выделяя для каждой из них максимальное значение выигрыша. Выпишем внизу матрицы (4,2) максимальные значения по столбцам:

и найдем их них минимальное:

(4.4)

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

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

Определим нижнюю и верхнюю цены игры, а также минимаксные стратегии, для трех примеров, рассмотренных в предыдущем параграфе.

Пример 1. (Игра «поиск»). Определяя минимумы строк и максимумы столбцов получим

Так как величины , постоянны и равны соответственно -1 и нижняя и верхняя цены игры также равны -1 и

Любая стратегия игрока А является его максиминной, а игрока В - его минимаксной стратегией. Вывод тривиален: придерживаясь любой из своих стратегий, игрок А может гарантировать, что он проиграет не более 1 руб.; то же может гарантировать и игрок В при любой своей стратегии.

Пример 2. (Игра три пальца»). Выписывая минимумы строк и максимумы столбцов, найдем нижнюю цену игры и верхнюю (выделены в таблице жирным шрифтом). Наша максиминная стратегия (применяя ее систематически, мы гарантируем, что выиграем не меньше -3, т. е. проиграем не больше 3).

Минимаксная стратегия противника - любая из стратегий применяя их систематически, он может гарантировать, что не отдаст более 4. Если мы отступим от своей максиминной стратегии (например, выберем А 2), то противник может нас «наказать» за это, применив и сведя наш выигрыш равным образом и отступление противника от его минимаксной стратегии может быть «наказано» увеличением его проигрыша до 6.

Обратим внимание на то, что минимаксные стратегии в данном случае не устойчивы. Действительно, пусть, например, противник выбрал одну из своих минимаксных стратегий и придерживается ее. Узнав об этом, мы перейдем к стратегии и будем выигрывать 4. На это противник ответит стратегией и будет выигрывать 5; на это мы, в свою очередь, ответим стратегией и будем выигрывать 4, и т. д. Таким образом, положение, при котором оба игрока пользуются своими минимаксными стратегиями, является неустойчивым и может быть нарушено поступившими сведениями о стратегии, которую применяет противная сторона. Однако такая неустойчивость наблюдается не всегда; в этом мы убедимся на следующем примере.

Пример 3. (Игра «вооружение и самолет»). Определяем минимумы строк и максимумы столбцов:

В данном случае нижняя цена игры равна верхней:

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

Таким образом, мы видим, что существуют игры, для которых нижняя цена равна верхней:

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

Общее значение нижней и верхней цены игры

называется чистой ценой игры.

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

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

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

Чистая цена игры v в игре с седловой точкой является тем значением выигрыша, которое в игре против разумного противника игрок А не может увеличить, а игрок В - уменьшить.

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

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

Пример. Сторона А - средства ПВО - обороняет от воздушного налета участок территории, располагая двумя орудиями № 1 и № 2, зоны действия которых не перекрываются (рис. 9.1). Каждое орудие может обстрелять только самолет, проходящий через его зону действия, но для этого оно должно заранее (до входа цели в зону) следить за ней и вырабатывать прицельные данные Если цель обстреляна, она поражается с вероятностью Сторона В располагает двумя самолетами, каждый из которых может быть направлен в любую зону В момент, когда сторона А осуществляет целераспределение (назначает, какому орудию по какой цели стрелять), движение самолета-цели № 1 направлено в зону действия орудия № 1, а цели № 2 - в зону действия орудия № 2. Однако после принятия решения по целераспределению каждая цель может сманеврировать, применив «обманный маневр» (см. пунктирные стрелки на рис 9.1).

Задача стороны А - обратить в максимум, а стороны В - обратить в минимум число пораженных целей Найти решение игры (оптимальные стратегии сторон)

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

Орудия следят за целями «крест-накрест» (каждое - за целью направляющейся к соседу),

Оба орудия следят за целью № 1,

Оба орудия следят за целью № 2 У стороны В (самолеты-цели) тоже четыре стратегии:

Обе целн не меняют направления,

Обе цели применяют обманный маневр.

Первая цель применяет обманный маневр, а вторая нет,

Вторая цель применяет обманный маневр, а первая нет.

Получается игра 4X4, матрица которой дана в таблице:

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

Класс игр, имеющих седловую точку, весьма интересен как с теоретической, так и с практической точки зрения. К нему принадлежат, в частности, все так называемые «игры с полной информацией».

Игрой с полной информацией называется такая игра, в которой каждый игрок при каждом личном ходе знает результаты всех предыдущих ходов - как личных, так и случайных. Примерами игр с полной информацией могут служить: шашки, шахматы, известная игра в «крестики и нолики» и др.

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

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