Решение. Обозначим через Х= Х
Скачать 401.15 Kb.
|
Задача 3. Найти оптимальные стратегии и цену игры, заданной платежной матрицей А. Сделать проверку.  Решение. Пусть игрок А располагает 3 личными стратегиями, которые обозначим A1, A2, A3. Пусть у игрока В имеется 4 личных стратегий, обозначим их B1, B2, B3, B4. Таким образом, игра имеет размерность 3 × 4. В результате выбора игроками любой пары стратегий  однозначно определяется исход игры, т. е. выигрыш аij игрока А (положительный или отрицательный) и проигрыш (–аij) игрока В. Рассмотрим игру 3 × 4 с матрицей  и определим наилучшую среди стратегий A1, A2, A3. Выбирая стратегию Аi игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий Bj, для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).Назовем α нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,ɑ=max(min aij)=max(-3; -2; -3)=-2 Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию Bj, он учитывает максимально возможный при этом выигрыш для А. Назовем В верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно, β=min(max aij)= min(4; 2; 1; -1)=-1 Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника. Так как ɑ≠β, то задача не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии. ^ , это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами). Смешанную стратегию игрока А будем обозначать
где A1, A2, A3 - стратегии игрока A, а p1, p2, p3 - соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p1 + p2 + p3 = 1. Аналогично смешанную стратегию игрока В будем обозначать
где B1, B2, B3, B4 - стратегии игрока "B", а q1, q2, q3, q4 - соответственно вероятности, с которыми эти стратегии применяются, причем q1 + q2 + q3 + q4 = 1. Оптимальная смешанная стратегия для игрока А та, которая обеспечивает ему максимальный выигрыш. Соответственно для B - минимальный проигрыш. Обозначаются эти стратегии SA* и SB* соответственно. Пара оптимальных стратегий образует решение игры. В общем случае в оптимальную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них. Такие стратегии называются активными стратегиями. Для определения оптимальных стратегий игроков проведем упрощение платежной матрицы. Сравнивая стратегии A1 и A3 видим, что A1 является заведомо невыгодной относительно A3, поэтому удалим стратегию A1 из платежной матрицы и получим следующую игру.  Сравнивая стратегии B2и B3 видим, что B3 является заведомо невыгодной относительно B2, поэтому удалим стратегию B3 из платежной матрицы и получим следующую игру.  Из полученной матрицы видно, что игроку A следует искать свою оптимальную стратегию смешивая случайным образом стратегии A2и A3. Из теории игр известно, что если игрок А в своей оптимальной смешанной стратегии использует не более чем N активных стратегий, то и оптимальная стратегия игрока B состоит не более чем из N активных стратегий. А в нашем случае у А активных стратегий две и поэтому оптимальная стратегия игрока В представляет собой случайную смесь двух из 3-х стратегий B1, B2, B4. Решим геометрическим методом полученную игровую модель. Возьмем участок оси абсцисс единичной длины и проведем через его концы вертикальные прямые a2 и a3 соответствующие нашим стратегиям A2 и A3. Предположим теперь, что игрок B будет пользоваться стратегией B1 в чистом виде. Тогда, игрок A будет использовать чистую стратегию A2, то наш выигрыш составит -2.Отметим соответствующую ему точку на оси a2. Если же мы будем использовать чистую стратегию A3, то наш выигрыш составит 4. Отметим соответствующую ему точку на оси a3 (рис. 8). Очевидно, если мы будем применять, смешивая в различных пропорциях стратегии A2 и A3 наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , -2) и (1 , 4). Назовем ее линией стратегии B1. Абсцисса любой точки на данной прямой равна вероятности p3 (частоте), с которой мы применяем стратегию A3, а ордината - получаемому при этом выигрышу k (рис.8).  Рисунок 8. График зависимости выигрыша k от частоты р3, при использовании противником стратегии B1. Перейдем теперь к геометрической интерпретации задачи в целом. Аналогичным образом нанесем на график линии всех стратегий игрока B (B1, B2, B4), получим картину показанную на рисунке 9. Из рисунка видно, что если мы (игрок A) будем пользоваться чистой стратегией A2, то разумный противник, для минимизации нашего выигрыша, ответит нам стратегией B1 и наш выигрыш составит -2.  Рисунок 9. Линии стратегий игрока "B" Если же мы будем пользоваться чистой стратегией A3, то игрок В, ответит нам стратегией B2 и наш выигрыш составит -3. А если мы будем применять, смешивая в различных пропорциях стратегии A2 и A3 наш выигрыш будет меняться по ломаной линии, показанной на рисунке 10 красным цветом.  Рисунок 10. Нижняя граница выигрыша, оптимальная частота p3 и цена игры v. Красная ломаная линия определяет так называемую нижнюю границу выигрыша. Выберем на ней точку с максимальной ординатой (рис. 10). Абсцисса этой точки определяет вероятность p3 (частоту), с которой нужно применять стратегию A3 чтобы получить максимальный выигрыш, (вероятность p2 будет соответственно 1 - p3) а ордината цену игры v. То есть, это есть точка нашей оптимальной стратегии. Кроме того из рисунка 10 видны активные стратегии игрока В. Это как раз те стратегии, пересечением которых образуется оптимальная точка. В нашей задаче, это стратегии B1 и B4. Определив две активные стратегии игрока B мы фактически свели исходную задачу к задаче размерностью 2x2:
где: p2, p3 - вероятности (частоты) с которыми применяются соответственно стратегии A2 и A3 Из теории игр известно, что если игрок А использует свою оптимальную стратегию, а игрок B остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок В использует свои активные стратегии. А в нашем случае обе стратегии активные, иначе игра бы имела решение в чистых стратегиях. Поэтому если предположить, что игрок В будет пользоваться чистой стратегией B1, то средний выигрыш v составит: k21p2 + k31p3 = v где: kij - элементы платежной матрицы. C другой стороны, если предположить, что игрок В будет пользоваться чистой стратегией B4, то средний выигрыш составит: k24p2 + k34p3=v Приравняв левые части уравнений получим: k21p2+k31p3=k24p2+k34p3 А с учетом того, чтоp2+p3=1 имеем: k21p2+k31(1-p2)=k24p2+k34(1-p2) Откуда несложно найти оптимальную частоту стратегии A2:  В данной задаче: 
Вероятность р3 найдем вычитанием р2 из единицы: p3=1-p2=1-5/6=1/6 Вычислим цену игры подставив р2, р3 в уравнение: v=k21p2+k31p3=-2*5/6+4*1/6=-10/6+4/6=-6/6=-1
где: q1, q4 - вероятности (частоты) с которыми применяются соответственно стратегии B1 и B4 Из теории игр известно, что если игрок B использует свою оптимальную стратегию, а игрок A остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок А использует свои активные стратегии. Поэтому если предположить, что игрок A будет пользоваться чистой стратегией A2, то средний выигрыш v составит: k21q1 + k24q4 = v Поскольку цена игры v нам уже известна и учитывая, что q1+q4=1, то оптимальная частота стратегии B1 может быть найдена как:  В данной задаче:  Вероятность q4 найдем вычитанием q1 из единицы: q4 =1-q1=1-0=1 Ответ: Нижняя цена игры α =-2, верхняя цена игры : β = -1, цена игры v =-1. Оптимальная стратегия игрока А :  Оптимальная стратегия игрока B : |
Похожие:
 | Обозначим через [меш.] количество мешков с мукой, которые будут перевезены... | | Остаток в формуле Тейлора и его оценка Разность между функцией и её многочленом Тейлора называется -м остатком, или -м остаточным членом; обозначим этот остаток через |
| § 14. Нормальное уравнение прямой. Задача определения расстояния от точки до прямой ... | | Пусть и непрерывное отображение. Можно ли утверждать, у отображения есть неподвижные точки? Рассмотрим модель чистого обмена с видами товаров и потребителями. Обозначим через начальный запас го товара у -го потребителя. Пусть... |
| Нет вакуума (нуля) и бесконечности ... | | Использование wifi роутеров для управления устройствами через Интернет Также в этих работах не рассматривался вопрос об ударенной работе с устройствами через Интернет. Решение представлено только для... |
| § 11. Параметрические уравнения линии Обозначим буквами Х и у координаты некоторой точки М; рассмотрим две функции аргумента t | | В задачах о размещениях полагается ... |
| Как добраться от Москвы до Ельца на машине и далее через Талицу Внимание! Во время половодья в марте-апреле этот удобный и короткий маршрут не действует, по причине затопления моста через р. Сосну.... |  | Решение этих задач и обеспечивается через налогообложение Материалы данного файла могут быть использованы без ограничений для написания собственных работ с целью последующей сдачи в учебных... |