Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

SOLVING MATRIX GAMES IN MIXID STRATEGIES

1
1

Любая конечная матричная игра может быть решена аналитически, графически (графоаналитически), либо ее решение можно сведено к решению пары двойственных задач линейного программирования [1 – 4].

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

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

Смешанная стратегия нашего первого игрокаАзадается m – мерным вектором , где это та вероятность с которой первый игрок точно выберет стратегию i, при этом , так как известно, что вероятности не могут быть отрицательными, и .

Смешанная стратегия нашего второго игрокаВ задаетсяn– мерным вектором , где это та вероятность с которой первый игрок точно выберет стратегиюj, при этом , так как, как говорилось выше, вероятности не могут быть отрицательными, и .

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

Значит средний выигрыш игрокаА равен:

.

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

 

 

1. Аналитическое решение антагонистической игры в смешанных стратегиях

В теории игр большое практическое значение для нахождения оптимальных стратегий в не полностью определенных играх имеет следующая теорема,рассказывающая об активных стратегиях: «Если один из игроков придерживается своей оптимальной стратегии, то его выигрыш остается неизменным и равным цене игры , независимо от того, что делает другой игрок, если он не выходит за рамки своих активных стратегий» [6, c.70].

Рассмотрим не вполне определенную игру .

Пусть будет задана платежная матрица игры А:

.

В соответствии с теоремой Неймана данная игра должна иметь хотя бы одно решение в смешанных стратегиях.

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

, (1.1)

, (1.2)

. (1.3)

Из данной системы уравнений определим :

, (1.4)

, (1.5)

Цена игры будет равна:

. (1.6)

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

, (1.7)

, (1.8)

. (1.9)

Из данной системы уравнений определим :

, (1.10)

, (1.11)

 

 

2. Решение антагонистических игр графическим методом

 

 

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

Первый случай. Рассмотрим игру с матрицей

не имеющей седловой точки. Решение этой игры – смешанные стратегии игроков и .Здесь– вероятность применения первым игрокомАсвоей первой стратегии, – вероятность применения первым игроком Асвоейвторой стратегии, – вероятность применения вторым игроком В своей первой стратегии, – вероятность применения вторым игроком В своей второй стратегии.

Является очевидным то, что

, .

Нам нужно найти решение данной игры графическим методом (рис. 2.1). Построим на оси ОХотрезок с длинойравной единице. Левый конец отрезка (х = 0) соответствует стратегиипервого игрока А, правый (х = 1) – стратегии этого же игрока. Точки внутри отрезка будут соответствовать смешанным стратегиям первого игрокаА, где . Через концы построенного отрезка проведем, перпендикулярные оси ОХ, прямые на которых отложим выигрыш при соответствующих им чистых стратегиях.

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

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

Нижней границей выигрыша, получаемого игрокомАназывается некая ломаная линия, которая состоит из частей отрезков, интерпретирующих стратегии игрока В. Данная ломанаярасположена ниже всех отрезков.[6 - 7].

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

В игре обе стратегии, как можно понять, являются активными стратегиями.

Ломанаяявляет собой нижнюю границу выигрыша (рис. 2.1), который получил игрокА. Точка К, в которой он максимален, определяет цену игры и её решение. Нам следует найти оптимальную стратегию первого игрокаА. Запишем систему уравнений:

Рисунок 2.1. Геометрическая интерпретация решения игры

Приравнивая выражения для из уравнений системы и учитывая, что

,

получим

, , (2.1)

. (2.2)

Составим аналогичную систему:

и учитывая условие:

Можно найти оптимальную стратегию игрока В:

, (2.3)

Пример 2.1. Найти решение игры, заданной матрицей

.

, ,

, .

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

Рисунок 2.2. Геометрическая интерпретация решения игры для примера 2.1.

По рисунку 2.2 и по формулам (2.1) – (2.3) находим оптимальные стратегии и цену игры:

, , , , .

Ответ: оптимальные смешанные стратегии нашей пары игроков соответственно равныи , а цена игры составляет .

Данный ответ можно интерпретировать следующим образом:

­ если первый игрокАс вероятностью 1/3 будет применять первую стратегиюи с вероятностью 2/3 применит вторую стратегию , то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 5/3;

­ если второй игрокВс вероятностью 2/3 будет применять первую стратегиюи с вероятностью 1/3 применит вторую стратегию , то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не больше 5/3.

Второй случай. Рассмотрим игру с матрицей

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

Третий случай. Рассмотрим игру с матрицей

.

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

Выводы

В данной работе рассмотрено решение матричных игр в смешанных стратегиях. Решение проводилось аналитическим, графическим (графоаналитическим) методами. Приведены примеры решения матричных игр графоаналитическим методом.