![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Применение оптимальной смешанной стратегии обеспечивает игроку максимальный средний выигрыш (или минимальный средний проигрыш), равный цене игры γ, независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий.
55. Матричные игры.
Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица. Отсюда, кстати, происходит еще одно их название — матричные игры. Каждый элемент платежной матрицы аij содержит числовое значение выигрыша игрока I (проигрыша игрока II), если первый применяет стратегию i, а второй — стратегию j. Термины выигрыш и проигрыш следует понимать в широком смысле, т. к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи, прежде всего, заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.
Классическим примером антагонистической игры является игра с двумя участниками, загадывающими независимо друг от друга числа. Предполагается, что если их сумма оказывается четной, то выигрыш, равный 1, достается первому игроку, а если нечетной, то второму. Положив, что для обоих игроков загадывание нечетного числа является первой стратегией, а четного — второй, можем записать платежную матрицу данной игры:
н/ч | ч | |
н/ч | -1 | |
ч | -1 |
(1)
Строки матрицы (1) соответствуют стратегиям игрока I, столбцы — стратегиям игрока II, а ее элементы — результатам первого игрока. Также из определения игры следует, что элементы данной матрицы, взятые с обратным знаком, соответствуют выигрышам второго игрока.
Более сложная и содержательная платежная матрица может быть получена, если несколько модифицировать предложенную игру. Допустим, что оба участника имеют право загадывать числа от 1 до 4, что составляет их соответствующие стратегии. В случае, если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый — второму. Запишем платежную матрицу для такой игры:
(2)
Некоторая условность и искусственность в постановке проблемы не должны в данном случае нас смущать, так как к подобной форме может быть сведена модель, описывающая, например, соревнование двух фирм за вновь открывшийся рынок сбыта продукции и т. п.
Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица . При выборе игроком I стратегии i его гарантированный доход независимо от действий игрока II составит
. Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т. е. обеспечивал получение
, Такой принцип выбора стратегии получил название «принцип максимина». С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит
, и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить
. В этом суть принципа минимакса.
Можно доказать справедливость следующего соотношения:
£
(3)
Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии
=
(4)
В этом случае говорят, что игра имеет седловую точку. Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии и
, образующие седловую точку, называются оптимальными, а значение
. называют ценой игры. Тройка
считается решением матричной игры с седловой точкой.
Нетрудно заметить, что не всякая игра обладает седловой точкой. В частности, как игра (6.1), так и игра (6.2) седловой точки не имеют. Примером игры, имеющей седловую точку, является игра с платежной матрицей (6.5).
(5)
В данной матрице минимальные (гарантированные) выигрыши первого игрока по строкам равны 1, 5 и (-3). Следовательно, его максиминному выбору будет отвечать стратегия 2, гарантирующая выигрыш 5. Для второго игрока максимальные проигрыши по столбцам матрицы составят 8, 10, 5, 17, поэтому имеет смысл остановиться на стратегии 3, при которой он проиграет только 5. Таким образом, вторая стратегия первого игрока и третья стратегия второго образуют седловую точку со значением 5, т. е. для игры с матрицей (6.5) имеет решение (2; 3; 5).
6.1.4. Смешанные стратегии. Дальнейшее развитие теории матричных игр основывается на исследовании игры как некоторого повторяющегося процесса. Действительно, вряд ли можно дать содержательные рекомендации по такому вопросу, как следует поступать участникам однократно проводимой игры, не имеющей седловой точки. В случае же ее многократных повторов естественной и плодотворной представляется идея рандомизации выбора стратегий игроками, т. е. внесение в процесс выбора элемента случайности. Действительно, систематическое отклонение, например, игрока I от максиминной стратегии с целью увеличения выигрыша может быть зафиксировано вторым игроком и наказано. В то же время абсолютно хаотичный выбор стратегий не принесет в среднем наилучшего результата.
►Смешанной стратегией игрока I в игре с матрицей называется упорядоченный набор действительных чисел xi, iÎ 1: m, удовлетворяющих условиям
(6)
Числа интерпретируются как вероятности применения игроком I стратегий 1,2,..., т, которые, в отличие от смешанных, также называют чистыми стратегиями.
Аналогично вводится понятие смешанных стратегий игрока II, которые определяются как набор чисел уj, jÎ l: n, удовлетворяющих условиям
(7)
Тогда, если игрок I применяет смешанную стратегию х=(х1, х2,..., хт), а игрок II смешанную стратегию у = (у1, у2,…,yn), то математическое ожидание выигрыша игрока I (проигрыша игрока II) определяется соотношением
[2] (8)
В дальнейшем через X будем обозначать множество допустимых смешанных стратегий игрока I, определяемое условием 6.7, а через Y — определяемое условием 6.8 множество допустимых смешанных стратегий игрока П.
К поиску решения игры в смешанных стратегиях, так же как и в п. 6.1.3, могут быть применены критерии максимина-минимакса. В соответствии с ними игрок I будет выбирать свою смешанную стратегию x=(xl, х2,..., хт) таким образом, чтобы максимизировать наименьший средний выигрыш:
(9)
который, как можно доказать, равен
(10)
а игрок II — свою смешанную стратегию так, чтобы минимизировать наибольший средний проигрыш:
(11)
также равный
(12)
По аналогии с (6.3) для любых х е X и г/ € У справедливо неравенство
£
(13)
►Стратегии и
называют оптимальными смешанными стратегиями, если для любых хÎХ и yÎY справедливо равенство
=
(14)
называют ценой игры, и если х* и у* существуют, то говорят, что игра имеет решение в смешанных стратегиях (х*, у*, v).
Справедлива фундаментальная теорема Дж. Неймана, которую мы приведем без доказательства.
Теорема 6.1 (основная теорема матричных игр). Любая матричная игра имеет решение в смешанных стратегиях.
Значение и нетривиальность теоремы (6.1) обусловлены прежде всего тем, что, как было показано в п. 6.1.3, в общем случае матричные игры в чистых стратегиях решения не имеют.
6.1.5. Решение матричных игр методами линейного программирования. Рассмотрим некоторые способы решения матричных игр. Задача, решаемая первым игроком, (10) была сформулирована как максимизация наименьшей из сумм
но если определить некоторое хт+1, для которого выполняется
(15)
то она может быть сведена к задаче линейного программирования:
(16)
при ограничениях
(17)
Проведя аналогичные рассуждения, приходим к тому, что задача минимизации наибольшего ожидаемого проигрыша, решаемая игроком II (12), сводится к задаче линейного программирования
(18)
(19)
Таким образом, мы получаем возможность применять все возможности аппарата линейного программирования для поиска оптимальных стратегий обоих игроков.
Достаточно легко проверить, что задачи (16)-(17) и (18)-(19) образуют двойственную пару. Здесь в определенном смысле мы вернулись к проблемам, уже рассматривавшимся во второй главе, а именно к взаимосвязи между наличием решения у некоторой оптимизационной задачи и существованием седловой точки у соответствующей функции Лагранжа. В данном случае аналогичная связь прослеживается между седловой точкой игры и решением пары задач оптимизации.
56. Решение и геометрическая интерпретация игр 2*2
Игра 2*2 является наиболее простым случаем конечных игр.
B1 | B2 | |
A1 | a11 | a12 |
A2 | a21 | a22 |
В этой игре каждый из игроков обладает только двумя стратегиями. Пусть игра не имеет седловой точки, т.е. a¹b. Требуется найти оптимальные смешанные стратегии игроков =(р1,р2),
=(q1,q2) и цену игры g. В игре 2*2, не имеющей седловой точки, обе стратегии игроков являются активными. Поэтому в соответствии с теоремой от активных стратегиях, если игрок I будет применять свою оптимальную смешанную стратегию, то независимо от действий игрока II, выигрыш его будет равен цене игры g.
Игрок I будет применять стратегию А, с вероятностью р1 и стратегию А2 с вероятностью р2. Если игрок II применяет стратегию В1, то выигрыш игрока I-случайная величина, среднее которой (математическое ожидание) является ценой игры, т.е. определяется уравнением.
а11*р1+а21*р2=g
Если же игрок II будет применить стратегию В2, то выигрыш игрока I не изменится и определяется уравнением
а12*р1+а21*р2=g
Если же игрок II будет применять стратегию В2, то выигрыш игрока I не изменится и определяется уравнением
а12р1+а22р2=g
Принимая во внимание условие р1+р2=1, имеем систему трехлинейных уравнений тремя неизвестными:
Решив эту систему уравнений, находим величины р1, р2, т.е. pA*=(р1,р2) и g. Аналогично определяется оптимальная стратегия игрока II
qB*=(q1, q2) из системы уравнений:
Дадим геометрическую интерпретацию игры 2*2, представленной в табл. Для этого в системе координат xoy на оси абсцисс отложим отрезок [A1, A2], единице, и через концы этого отрезка проведем перпендикулярные к оси абсцисс прямые, на которых будем откладывать выигрыш игрока I. Левый перпендикуляр, совпадающий с осью ординат, соответствует стратегии А1, для которой p1=1, p2=0, а правый равен стратегии А2 для которой p1=0, p2=1. При применение игроком II стратегии В1 выигрыш игрока I будет равен a11, если он применяет стратегию А1, и a21, если он применят стратегию А2. Отложив отрезки, равные a11 и a21, на соответствующих перпендикулярах, получим две точки:
Y
B1
B2
N
B1
γ
B2
pA*
Дата публикования: 2015-03-26; Прочитано: 2388 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!