Смешанная стратегия игроков . Найти смешанную стратегию игроков.

Моделирование игровой схемы в теории игр . Предприятие имеет возможность самостоятельно планировать объемы выпуска сезонной продукции П 1 , П 2 , П 3 .

Решение матричной игры с использованием графического метода

Решение матричной игры с использованием методов линейного программирования

1. Матричная игра. Использование симплексного метода . Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = 2, которая указывает на максимальную чистую стратегию A 1 .
2. Пример решения матричной игры методом линейного программирования . Решить матричную игру методом линейного программирования.

Дайте графическое представление, приведите к нормальной форме и найдите точное решение позиционной игры со следующей функцией выигрышей:
1-й ход делает игрок А: он выбирает число x из множества двух чисел.
2-й ход делает игрок В: не зная о выборе игрока А на 1-м ходе, он выбирает число y из множества двух чисел.
3-й ход делает игрок А: он выбирает число z из множества двух чисел, зная значения y, выбранное игроком В на 2-м ходе, но не помня собственного выбора x на 1-м ходе.

Игры с природой

1. Статистические игры
   Сельскохозяйственное предприятие может реализовать некоторую продукцию:
   А1) сразу после уборки;
   А2) в зимние месяцы;
   А3) в весенние месяцы.
   Прибыль зависит от цены реализации в данный период времени, затратами на хранение и возможных потерь. Размер прибыли, рассчитанный для разных состояний-соотношений дохода и издержек (S1, S2 и S3), в течение всего периода реализации, представлен в виде матрицы (млн.руб.)
2. Фирма производит платья и костюмы, реализация которых зависит от состояния погоды . Затраты фирмы в течение апреля-мая на единицу продукции составят...
3. Решение задачи про запасы сырья . За некоторый период времени на предприятии потребление исходного сырья в зависимости от его качества составляет в 1 , в 2 , в 3 и в 4 .
4. Стратегии крайнего пессимизма, крайнего оптимизма и оптимизма-пессимизма

Биматричные игры

Дерево решений в теории игр (пример решения задачи).

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

В городе работают три телекомпании: АВС, СВS и NВС . Эти компании могут начинать программу вечерних новостей в 6.30 или в 7.00. 60% телезрителей предпочитают смотреть вечерние новости в 6.30, а 40% — в 7.00. Наиболее популярна программа вечерних новостей у компании АВС , наименьшей популярностью пользуются новости, подготовленные компанией NВС . Доля телезрителей вечерних новостных программ представлена в таблице (NBС, СВS , АВС)

АВС: 6.30
N ВС		СВ S
АВС: 7.00
NB С		СВ S

Найти оптимальные стратегии компаний по времени показа новостных программ

Указание к решению: в игре существует доминируемая стратегия

Из популярного американского блога 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.

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

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

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

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

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

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

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

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

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

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

Некоторые определения игры

Количественная оценка результатов игры называется платежом.

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

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

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

Игра, определяемая матрицей А , имеющейm строк иn столбцов, называется конечной парной игрой размерностиm * n ;

где i =
- стратегия первого игрока, имеющегоmстратегий; j =- стратегия второго игрока, имеющегоnстратегий; ij – выигрыш первого игрока поi -й стратегии при использовании вторымj -й стратегии (или, что то же самое, проигрыш второго по своейj -й стратегии, при использовании первымi -й);

А =  ij – платежная матрица игры.

1.1 Игра с чистыми стратегиями

Нижняя цена игры (для игрока первого)

 = max (min  ij ). (1.2)

i j

Верхняя цена игры (для второго игрока):

= min (max  ij ) . (1.3)

J i

Если  =  , игра называется с седловой точкой (1.4), или игра с чистыми стратегиями. При этомV =  =  называют ценной игры (V - цена игры).

Пример. Дана платежная матрица игры 2 лиц А. Определить оптимальные стратегии для каждого из игроков и цену игры:

(1.4)

max 10 9 12 6

i

min 6

j

- стратегия первого игрока (строки).

Стратегия второго игрока (столбцы).

- цена игры.

Таким образом, игра имеет седловую точку. Стратегия j = 4 – оптимальная для второго игрока, стратегияi =2 - для первого. Имеем игру с чистыми стратегиями.

1.2 Игры со смешанными стратегиями

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

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

Х = (х 1 …х i …х m ) – смешанная стратегия первого игрока.

У = (у 1 …у j …у n ) – смешанная стратегия второго игрока.

x i , у j – относительные частоты (вероятности) использования игроками своих стратегий.

Условия использования смешанных стратегий

. (1.5)

Если Х * = (х 1 * ….х i * …х m *) – оптимальная стратегия, выбранная первым игроком;Y * = (у 1 * …у j * …у n *) – оптимальная стратегия, выбранная вторым игроком, то число является ценой игры.

(1.6)

Для того чтобы число V было ценой игры, ах * иу * - оптимальными стратегиями, необходимо и достаточно выполнение неравенств

(1.7)

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

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

Пример . Найти решение игры, определяемой платежной матрицейА .

А = (1.8)

y 1 y 2 y 3

Решение:

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

Для первого игрока

(1.9)

у 1 +у 2 +у 3 = 1 (1.10)

Освобождаясь от переменной V (цена игры), разделим левую и правую часть выражений (1.9), (1.10) наV . Приняву j /V за новую переменнуюz i , получим новую систему ограничений (1.11) и целевую функцию (1.12)

(1.11)

. (1.12)

Аналогично получим модель игры для второго игрока:

(1.13)

х 1 +х 2 +х 3 = 1 . (1.14)

Приведя модель (1.13), (1.14) к форме без переменной V , получим

(1.15)

, (1.16)

где
.

Если нам необходимо определить стратегию поведения первого игрока, т.е. относительную частоту использования его стратегий (х 1 ….х i …х m ), мы будем использовать модель второго игрока, т.к. эти переменные находятся в его модели выигрыша (1.13), (1.14).

Приведем (1.15), (1.16) к канонической форме

(1.17)

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

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

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

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

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

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

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется 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 и оптимальные смешанные стратегии и .

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

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

.

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

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

Задача:
Матричная игра задана следующей платежной матрицей:

	Стратегии "B"
Стратегии "A"	B 1	B 2
A 1	3	5
A 2	6	3 2

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

Шаг:1

Определим нижнюю цену игры - α

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

Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец (Выделен желтым цветом см. Табл.1).

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

Таблица 1

	Стратегии "B"
Стратегии "A"	B 1	B 2	Минимумы строк
A 1	3	5	3 *
A 2	6	3 2	3 2

В нашем случае нижняя цена игры равна: α = 3 , и для того чтобы гарантировать себе выигрыш не хуже чем 3 мы должны придерживаться стратегии A 1

Шаг:2

Определим верхнюю цену игры - β

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

Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу (Выделена желтым цветом см. Табл.2).

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

Таблица 2

	Стратегии "B"
Стратегии "A"	B 1	B 2	Минимумы строк
A 1	3	5	3 *
A 2	6	3 2	В нашем случае верхняя цена игры равна: β = 5 , и для того чтобы гарантировать себе проигрыш не хуже чем 5 противник (игрок "B") должен придерживаться стратегии B 2 Шаг:3 Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β , платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях. Смешанная стратегия , это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами). Смешанную стратегию игрока "А" будем обозначать S A =

где B 1 , B 2 - стратегии игрока "B", а q 1 , q 2 - соответственно вероятности, с которыми эти стратегии применяются, причем q 1 + q 2 = 1.

Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии S A * и S B * соответственно. Пара оптимальных стратегий образует решение игры.

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

Шаг:4

где: p 1 , p 2 - вероятности (частоты) с которыми применяются соответственно стратегии A 1 и A 2

Из теории игр известно, что если игрок "А" использует свою оптимальную стратегию, а игрок "B" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "В" использует свои активные стратегии. А в нашем случае обе стратегии активные, иначе игра бы имела решение в чистых стратегиях. Поэтому если предположить, что игрок "В" будет пользоваться чистой стратегией B 1 , то средний выигрыш v составит:

k 11 p 1 + k 21 p 2 = v (1)

где: k ij - элементы платежной матрицы.

C другой стороны, если предположить, что игрок "В" будет пользоваться чистой стратегией B 2 , то средний выигрыш составит:

k 12 p 1 + k 22 p 2 = v (2)

Приравняв левые части уравнений (1) и (2) получим:

k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2

А с учетом того, что p 1 + p 2 = 1 имеем:

k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )

Откуда несложно найти оптимальную частоту стратегии A 1 :

p 1 =

k 22 - k 21 k 11 + k 22 - k 12 - k 21

(3)

В данной задаче:

p 1 =

3 2 - 6 3 + 3 2 - 5 - 6

=

9 13

Вероятность р 2 найдем вычитанием р 1 из единицы:

p 2 = 1 - p 1 =

1

-

9 13

=

+

6

·

где: q 1 , q 2 - вероятности (частоты) с которыми применяются соответственно стратегии B 1 и B 2

Из теории игр известно, что если игрок "B" использует свою оптимальную стратегию, а игрок "A" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "А" использует свои активные стратегии. Поэтому если предположить, что игрок "A" будет пользоваться чистой стратегией A 1 , то средний выигрыш v составит:

k 11 q 1 + k 12 q 2 = v (4)

Поскольку цена игры v нам уже известна и учитывая, что q 1 + q 2 = 1 , то оптимальная частота стратегии B 1 может быть найдена как:

q 1 =

v - k 12 k 11 - k 12

(5)

В данной задаче:

q 1 =

51 13 - 5 3 - 5

=

7 13

Вероятность q 2 найдем вычитанием q 1 из единицы:

q 2 = 1 - q 1 =

1

-

7 13

=

6 13

Ответ:

Нижняя цена игры:	α =	3
Верхняя цена игры:	β =	5
Цена игры:	v =	51 13

Оптимальная стратегия игрока "А" :	S A * = A 1 A 2 9 13 4 13
Оптимальная стратегия игрока "B" :	S B * = B 1 B 2 7 13 6 13

Геометрическая интерпретация (графическое решение):

Дадим геометрическую интерпретацию рассмотренной игре. Возьмем участок оси абсцисс единичной длины и проведем через его концы вертикальные прямые a 1 и a 2 соответствующие нашим стратегиям A 1 и A 2 . Предположим теперь, что игрок "B" будет пользоваться стратегией B 1 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 3.Отметим соответствующую ему точку на оси a 1 .
Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 6. Отметим соответствующую ему точку на оси a 2
(см. Рис. 1). Очевидно, если мы будем применять, смешивая в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 3) и (1 , 6), назовем ее линией стратегии B 1 (на Рис.1 показана красным цветом). Абсцисса любой точки на данной прямой равна вероятности p 2 (частоте), с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу k (см. Рис.1).

Рисунок 1.
График зависимости выигрыша k от частоты р 2 , при использовании противником стратегии B 1 .

Предположим теперь, что игрок "B" будет пользоваться стратегией B 2 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 5.Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 3/2 (см. Рис. 2). Аналогично, если мы будем смешивать в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 5) и (1 , 3/2), назовем ее линией стратегии B 2 . Как и в предыдущем случае, абсцисса любой точки на этой прямой равна вероятности, с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу, но только для стратегии B 2 (см. Рис. 2).

Рисунок 2.
v и оптимальной частоты р 2 для игрока "А" .

В реальной игре, когда разумный игрок "В" пользуется всеми своими стратегиями, наш выигрыш будет изменяться по ломаной линии, показанной на Рис.2 красным цветом. Эта линия определяет так называемую нижнюю границу выигрыша . Очевидно, что самая высокая точка этой ломанной соответствует нашей оптимальной стратегии. В данном случае, это точка пересечения линий стратегий B 1 и B 2 . Обратите внимание, что если выбрать частоту p 2 равной ее абсциссе, то наш выигрыш будет оставаться неизменным и равным v при любой стратегии игрока "B", кроме того он будет максимальным который мы можем себе гарантировать. Частота (вероятность) p 2 , в этом случае, есть соответствующая частота нашей оптимальной смешанной стратегии. Кстати из рисунка 2 видна и частота p 1 , нашей оптимальной смешанной стратегии, это длина отрезка [p 2 ; 1] на оси абсцисс. (Это потому, что p 1 + p 2 = 1 )

Совершенно аналогично рассуждая, можно найти и частоты оптимальной стратегии для игрока "В", что иллюстрируется на рисунке 3.

Рисунок 3.
Графическое определение цены игры v и оптимальной частоты q 2 для игрока "В" .

Только для него следует построить так называемую верхнюю границу проигрыша (красная ломаная линия) и искать на ней самую низкую точку, т.к. для игрока "В" цель, это минимизация проигрыша. Аналогично значение частоты q 1 , это длина отрезка [q 2 ; 1] на оси абсцисс.