Решение. Обозначим через Х= Х




Скачать 401.15 Kb.
НазваниеРешение. Обозначим через Х= Х
страница3/3
Дата публикации27.10.2013
Размер401.15 Kb.
ТипРешение
litcey.ru > География > Решение
1   2   3

Задача 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

Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

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

Так как ɑ≠β, то задача не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.

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

Смешанную стратегию игрока А будем обозначать

SA =




A1

A2

A3

p1

p2

p3










где A1, A2, A3 - стратегии игрока A, а p1, p2, p3 - соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p1 + p2 + p3 = 1.

Аналогично смешанную стратегию игрока В будем обозначать

SB =




B1

B2

B3

B4

q1

q2

q3

q4










где 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).
рис.1 график зависимости выигрыша k от частоты р3 при использовании противником стратегии 1
Рисунок 8. График зависимости выигрыша k от частоты р3, при использовании противником стратегии B1.

Перейдем теперь к геометрической интерпретации задачи в целом. Аналогичным образом нанесем на график линии всех стратегий игрока B (B1, B2, B4), получим картину показанную на рисунке 9. Из рисунка видно, что если мы (игрок A) будем пользоваться чистой стратегией A2, то разумный противник, для минимизации нашего выигрыша, ответит нам стратегией B1 и наш выигрыш составит -2. 
рис.2 линии стратегий игрока b
Рисунок 9. Линии стратегий игрока "B"

Если же мы будем пользоваться чистой стратегией A3, то игрок В, ответит нам стратегией B2 и наш выигрыш составит -3. А если мы будем применять, смешивая в различных пропорциях стратегии A2 и A3 наш выигрыш будет меняться по ломаной линии, показанной на рисунке 10 красным цветом.
рис.3 нижняя граница выигрыша, оптимальная частота p3 и цена игры
Рисунок 10. Нижняя граница выигрыша, оптимальная частота p3 и цена игры v.

Красная ломаная линия определяет так называемую нижнюю границу выигрыша. Выберем на ней точку с максимальной ординатой (рис. 10). Абсцисса этой точки определяет вероятность p3 (частоту), с которой нужно применять стратегию A3 чтобы получить максимальный выигрыш, (вероятность p2 будет соответственно 1 - p3) а ордината цену игры v. То есть, это есть точка нашей оптимальной стратегии.

Кроме того из рисунка 10 видны активные стратегии игрока В. Это как раз те стратегии, пересечением которых образуется оптимальная точка. В нашей задаче, это стратегии B1 и B4. Определив две активные стратегии игрока B мы фактически свели исходную задачу к задаче размерностью 2x2:



SA* =




A2

A3

p2

p3










Данную задачу несложно решить аналитически.
Найдем оптимальную смешанную стратегию для игрока "A":




где: 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:



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






SA* =




A2

A3

p2

p3










Данную задачу несложно решить аналитически.

Найдем оптимальную смешанную стратегию для игрока A:




Вероятность р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

^ Найдем оптимальную смешанную стратегию для игрока B:

SB* =




B1

B4

q1

q4










где: 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 :
1   2   3

Похожие:

Решение. Обозначим через Х= Х iconОбозначим через [меш.] количество мешков с мукой, которые будут перевезены...

Решение. Обозначим через Х= Х iconОстаток в формуле Тейлора и его оценка
Разность между функцией и её многочленом Тейлора называется -м остатком, или -м остаточным членом; обозначим этот остаток через
Решение. Обозначим через Х= Х icon§ 14. Нормальное уравнение прямой. Задача определения расстояния от точки до прямой
...
Решение. Обозначим через Х= Х iconПусть и непрерывное отображение. Можно ли утверждать, у отображения есть неподвижные точки?
Рассмотрим модель чистого обмена с видами товаров и потребителями. Обозначим через начальный запас го товара у -го потребителя. Пусть...
Решение. Обозначим через Х= Х iconНет вакуума (нуля) и бесконечности
...
Решение. Обозначим через Х= Х iconИспользование wifi роутеров для управления устройствами через Интернет
Также в этих работах не рассматривался вопрос об ударенной работе с устройствами через Интернет. Решение представлено только для...
Решение. Обозначим через Х= Х icon§ 11. Параметрические уравнения линии
Обозначим буквами Х и у координаты некоторой точки М; рассмотрим две функции аргумента t
Решение. Обозначим через Х= Х iconВ задачах о размещениях полагается
...
Решение. Обозначим через Х= Х iconКак добраться от Москвы до Ельца на машине и далее через Талицу
Внимание! Во время половодья в марте-апреле этот удобный и короткий маршрут не действует, по причине затопления моста через р. Сосну....
Решение. Обозначим через Х= Х iconРешение этих задач и обеспечивается через налогообложение
Материалы данного файла могут быть использованы без ограничений для написания собственных работ с целью последующей сдачи в учебных...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница