Решение игры (2хn) и (mx2)

Существует теорема, которая гласит: любая конечная игра с нулевой суммой (mxn) имеет решение, в котром число активных стратегий каждого игрока не превосходит l, где l =min(m,n). Следовательно, у игры (2хn) или (mx2) всегда имеется решение, содержащее не более двух активных стратегий у каждого из игроков. Если эти активные стратегии игроков будут найдены, то игра (2хn) или (mx2) превращается в игру (2х2).

Практическое решение игры (2хn) осуществляется следующим образом:

1. Строится графическое изображение игры;

2. Выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры g;

3. Определяется пара стратегий, пересекающихся в точке оптимума. Эти стратегии являются активными стратегиями игрока В. Таким образом, игра (2хn) сведена к игре (2х2).(см. рис.5). Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них. Решение игры (mx2) осуществляется

аналогично.

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

Цена игры g, которая получается при решении ЗЛП (5)-(7) и (13)-(15) должна быть одной и той же величиной. Будут ли они действительно равны? Положительный ответ на этот вопрос следует из факта, что эти две задачи образуют пару двойственных ЗЛП. Теорема о таких задачах гласит: если одна из ЗЛП двойственной пары имеет решение, то другая задача также имеет решение, причем экстремальные значения целевых функций совпадают.

Покажем, что ЗЛП (13)-(15) имеет решение. Для этого необходимо, чтоб условия (13)-(14) были совместны, т.е. имели хотя бы одно решение, а максимизируемая целевая функция была ограничена сверху.

Действительно, ограничения (13)-(14) совместны, т.к. у_j=0 () удовлетворяют ограничениям (13),(14). Следовательно, множество планов (13),(14) не пустое. В силу условия (13) все значения у_j () ограничены сверху, а это означает ограниченность сверху целевой функции (15). Таким образом ЗЛП (13)-(15) имеет решение. Тогда на основании теоремы о двойственности ЗЛП (5)-(7) тоже имеет решение, причем

,

т.е. в обеих задачах значение цены игры g одинаковое.

Теорема. Любая парная конечная игра с нулевой суммой имеет решение по крайней мере среди смешанных стратегий.

Решение матричной игры () среди смешанных стратегий. Теорема об активных стратегиях.

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

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

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

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

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

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

Отметим, что смешанных стратегии бесчисленное множество, так как вероятностей , удовлетворяющих условиям (1)-(2) ((3)-(4)) бесчисленное множество.

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

Допустим игроки и используют соответственно свои смешанные стратегии и . Тогда среднее значение выигрыша будет равно:

Пусть оптимальными смешанными стратегиями игроков и будут соответственно:

и

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

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

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

Теорема об активных стратегиях.

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

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

и .

Для найденных вероятностей справедливы равенства и . Выигрыш при этом равен цене игры:

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

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

. Но средневзвешенное значение было бы больше . Следовательно .

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

Определение оптимальных смешанных стратегий.

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

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

Определение1. Если в матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующим строкам (столбцам) стратегии называются дублирующими.

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

и .

Очевидно и , при этом цена игры равна:

(7)

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

(8)

Учитывая неравенство (8) можно равенство (7) записать:

(9)

Соотношение (9) выполнимо только тогда, когда неравенства (8) превращаются в равенства. Отсюда следует, что для любой смешанной стратегии выполняется равенство .

Определение2. Если в матрице элементы и хотя бы для одного номера , то стратегия называется доминирующей над стратегией .

Определение3. Если в матрице элементы и хотя бы для одного номера , то стратегия игрока называется доминирующей над стратегией .

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

Пример. Имеется игра () с заданной платежной матрицей. Требуется “редуцировать” эту игру. После “редуцирования” она свелась к игре ()

A B

A B

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

() соответствует выигрыш равной цене игры .

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

Допустим, игрок использует стратегию , а игрок — некоторую стратегию в чистом виде или . В этом случае игрок имеет средний выигрыш:

.

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

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

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

Преобразуем эту ЗЛП к более удобному виду. Для этого предположим, что . Если это условие не выполняется, то прибавляя одну и ту же положительную величину к элементам платежной матрицы, всегда можно этого добиться. В этом случае цена игры . Такое преобразование приводит к изменению решения игры, что следует из следующей теоремы: Оптимальные смешанные стратегии и игроков и в матричной игре с ценой игры будут оптимальными и в матричной игре с ценой игры , где .

Теперь, поделив левую и правую части каждого из неравенств (1)-(3) на величину и обозначив , преобразуем ЗЛП (1)-(4) к виду:

Таким образом определение оптимальной смешанной стратегии свелась к ЗЛП (5)-(7). Пусть она решена и найдены оптимальные значения . Тогда с учетом введенного обозначения и вида целевой функции (7) найдем искомые вероятности и максимальный выигрыш игрока

Определим оптимальную смешанную стратегию игрока .

Пусть игрок использует оптимальную стратегию , а игрок — чистую стратегию

игрок имеет средний выигрыш: .

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

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

Теперь преобразуем ЗЛП (8)-(11). Для этого разделим левые и правые части выражений (8)-(10) на величину и введем обозначим . Тогда ЗЛП (8)-(11) перепишется:

Пусть решение ЗЛП (13)-(15), тогда из введенных обозначений следует

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

Цена игры , которая получается при решении ЗЛП (5)-(7) и (13)-(15) должна быть одной и той же величиной. Будут ли они действительно равны? Положительный ответ на этот вопрос следует из факта, что эти две задачи образуют пару двойственных ЗЛП. Теорема о таких задачах гласит: если одна из ЗЛП двойственной пары имеет решение, то другая задача также имеет решение, причем экстремальные значения целевых функций совпадают.

Покажем, что ЗЛП (13)-(15) имеет решение. Для этого необходимо, чтобы условия (13)-(14) были совместны, то есть имели хотя бы одно решение, а максимизируемая целевая функция была ограничена сверху.

Действительно, ограничения (13)-(14) совместны, так как удовлетворяют ограничениям (13), (15). Следовательно, множество планов (13), (14) не пустое. В силу условия (13) все значения ограничены сверху, а это означает ограниченность сверху целевой функции (15). Таким образом, ЗЛП (13)-(15) имеет решение. Тогда на основании теоремы о двойственности ЗЛП (5)-(7) тоже имеет решение, причем , то есть в обеих задачах значение цены игры одинаковые.

Теорема. Любая парная конечная игра с нулевой суммой имеет решение по крайне мере среди смешанных стратегий.

Дата добавления: 2014-01-14