13 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Матричные игры: примеры решения задач.

Содержание

Пример решения задачи теории игр в смешанных стратегиях нашим сервисом:

Заметьте! Решение вашей конкретной задачи будет выглядеть аналогично данному примеру, включая все таблицы, поясняющие тексты и рисунки, представленные ниже, но с учетом ваших исходных данных…

Задача:
Матричная игра задана следующей платежной матрицей :

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

Шаг:1

Определим нижнюю цену игры — α

Нижняя цена игры α — это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется «чистой»).

Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец ( Выделен желтым цветом см. Табл.1 ).

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

В нашем случае нижняя цена игры равна: α = 3, и для того чтобы гарантировать себе выигрыш не хуже чем 3 мы должны придерживаться стратегии A1

Шаг:2

Определим верхнюю цену игры — β

Верхняя цена игры β — это минимальный проигрыш, который может гарантировать себе игрок «В», в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию.

Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу ( Выделена желтым цветом см. Табл.2 ).

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

В нашем случае верхняя цена игры равна: β = 5, и для того чтобы гарантировать себе проигрыш не хуже чем 5 противник ( игрок «B») должен придерживаться стратегии B2

Шаг:3
Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β , платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях.

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

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

где A 1 , A 2 — стратегии игрока «A», а p 1 , p 2 — соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p 1 + p 2 = 1.

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

где B 1 , B 2 — стратегии игрока «B», а q 1 , q 2 — соответственно вероятности, с которыми эти стратегии применяются, причем q 1 + q 2 = 1.

Оптимальная смешанная стратегия для игрока «А» та, которая обеспечивает ему максимальный выигрыш. Соответственно для «B» — минимальный проигрыш. Обозначаются эти стратегии S A * и S B * соответственно. Пара оптимальных стратегий образует решение игры.

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

Шаг:4

где: p 1 , p 2 — вероятности (частоты) с которыми применяются соответственно стратегии A1 и A2

Из теории игр известно, что если игрок «А» использует свою оптимальную стратегию, а игрок «B» остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок «В» использует свои активные стратегии. А в нашем случае обе стратегии активные, иначе игра бы имела решение в чистых стратегиях. Поэтому если предположить, что игрок «В» будет пользоваться чистой стратегией B1, то средний выигрыш v составит:

Читать еще:  Литературное чтение. Два Мороза

где: k ij — элементы платежной матрицы.

C другой стороны, если предположить, что игрок «В» будет пользоваться чистой стратегией B2, то средний выигрыш составит:

Шаг:5

Вычислим цену игры подставив р1, р2 в уравнение (1) :

Шаг:6

где: q 1 , q 2 — вероятности (частоты) с которыми применяются соответственно стратегии B1 и B2

Из теории игр известно, что если игрок «B» использует свою оптимальную стратегию, а игрок «A» остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок «А» использует свои активные стратегии. Поэтому если предположить, что игрок «A» будет пользоваться чистой стратегией A1, то средний выигрыш v составит:

Ответ:

Геометрическая интерпретация (графическое решение):

Дадим геометрическую интерпретацию рассмотренной игре. Возьмем участок оси абсцисс единичной длины и проведем через его концы вертикальные прямые a1 и a2 соответствующие нашим стратегиям A 1 и A 2 . Предположим теперь, что игрок «B» будет пользоваться стратегией B 1 в чистом виде. Тогда, если мы (игрок «A») будем использовать чистую стратегию A 1 , то наш выигрыш составит 3.Отметим соответствующую ему точку на оси a1.
Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 6. Отметим соответствующую ему точку на оси a2
(см. Рис. 1). Очевидно, если мы будем применять, смешивая в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 3) и (1 , 6), назовем ее линией стратегии B 1 (на Рис.1 показана красным цветом). Абсцисса любой точки на данной прямой равна вероятности p 2 (частоте), с которой мы применяем стратегию A 2 , а ордината — получаемому при этом выигрышу k (см. Рис.1).

Рисунок 1.
График зависимости выигрыша k от частоты р2, при использовании противником стратегии B 1 .

Предположим теперь, что игрок «B» будет пользоваться стратегией B 2 в чистом виде. Тогда, если мы (игрок «A») будем использовать чистую стратегию A 1 , то наш выигрыш составит 5.Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 3/2 (см. Рис. 2). Аналогично, если мы будем смешивать в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 5) и (1 , 3/2), назовем ее линией стратегии B 2 . Как и в предыдущем случае, абсцисса любой точки на этой прямой равна вероятности, с которой мы применяем стратегию A 2 , а ордината — получаемому при этом выигрышу, но только для стратегии B 2 (см. Рис. 2).

Рисунок 2.
Графическое определение цены игры v и оптимальной частоты р2 для игрока «А».

В реальной игре, когда разумный игрок «В» пользуется всеми своими стратегиями, наш выигрыш будет изменяться по ломаной линии, показанной на Рис.2 красным цветом. Эта линия определяет так называемую нижнюю границу выигрыша. Очевидно, что самая высокая точка этой ломанной соответствует нашей оптимальной стратегии. В данном случае, это точка пересечения линий стратегий B 1 и B 2 . Обратите внимание, что если выбрать частоту p 2 равной ее абсциссе, то наш выигрыш будет оставаться неизменным и равным v при любой стратегии игрока «B», кроме того он будет максимальным который мы можем себе гарантировать. Частота (вероятность) p 2 , в этом случае, есть соответствующая частота нашей оптимальной смешанной стратегии. Кстати из рисунка 2 видна и частота p 1 , нашей оптимальной смешанной стратегии, это длина отрезка [p 2 ; 1] на оси абсцисс. (Это потому, что p 1 + p 2 = 1 )

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

Рисунок 3.
Графическое определение цены игры v и оптимальной частоты q2 для игрока «В».

Только для него следует построить так называемую верхнюю границу проигрыша (красная ломаная линия) и искать на ней самую низкую точку, т.к. для игрока «В» цель, это минимизация проигрыша. Аналогично значение частоты q 1 , это длина отрезка [q 2 ; 1] на оси абсцисс.

Графическое решение матричной игры

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

Читать еще:  В каком городе родился бажов. Павел Бажов: биография

Пусть платежная матрица имеет вид

.

Для произвольной стратегии второго игрока, контролирующего столбцы, имеем выигрыш первого игрока

,

поскольку, как сказано раньше,

, .

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

Рассмотрим прямоугольную систему координат, где по оси абсцисс откладывается единичный отрезок A1A2; точка A1 изображает стратегию A1 , а точка A2 изображает стратегию A2. Все промежуточные точки этого отрезка — смешанные стратегии первого игрока, причем расстояние до правого конца отрезка — это вероятность p1 стратегии A1, расстояние до левого конца отрезка это вероятность p2 стратегии A2. На перпендикулярах х=0 и х=1 откладываем выигрыши при стратегиях A1 и A2 соответственно (Рис.3.1).

Рис. 3.1. Графическое нахождение цены игры

На рис. 3.1 изображен случай для игры 2 3. Из принципа минимакса следует, что надо взять нижнюю огибающую всех прямых, соответствующих стратегиям второго игрока (она показана на рисунке жирной линией), а на этой ломаной, обязательно обращенной выпуклостью вверх, надо найти вершину, имеющую максимальное значение v*. Абсцисса этой точки x* и будет искомым значением p1*.

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

Алгоритм геометрического решения игры 2×N

1. Откладываем горизонтальный отрезок [0,1], каждая точка которого соответствует смешанной стратегии игрока A. В концах этого отрезка проводим два перпендикуляра. Левый соответствует чистой стратегии A1, правый — чистой стратегии A2 игрока A.

2. На левом перпендикуляре от точки 0 его пересечения с горизонтальным отрезком откладываем (как на вертикальной числовой оси) все элементы первой строки платежной матрицы. На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) все элементы второй строки платежной матрицы. При этом масштабы на обоих перпендикулярах должны быть одинаковые, но не обязаны совпадать с масштабом отрезка [0,1].

3. Каждую пару точек, изображающих элементы a1j, a2j, j=1. n, стоящих в j-м столбце платежной матрицы, соединяем отрезком a1j, a2j . Таким образом будут построены n отрезков, представляющих собой графики n линейных функций

4. Находим нижнюю огибающую семейства построенных отрезков a1j, a2j, представляющую собой выпуклую вверх ломаную. Затем находим максимальную точку нижней огибающей. Абсцисса р o этой точки определяет оптимальную смешанную стратегию P o =(1- p o , p o ) игрока A. Ордината наивысшей точки нижней огибающей равна цене игры V.

5. Верхний из концов нижней огибающей, лежащих на перпендикулярах, есть нижняя цена игры в чистых стратегиях, т.е. a.Нижний из верхних концов отрезковa1j, a2j, j=1. n, есть верхняя цена игры в чистых стратегиях b.

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

Пример 4. Графически решить игру:

Действуя по алгоритму геометрического нахождения игры 2×N (рисунок 3.2), находим, что цена игры V=3,5, нижняя цена игры: a=2, верхняя цена игры: b=4, оптимальная стратегия игрока A: P o =(1/2,1/2).

Алгоритм геометрического решения игры М×2

1. Откладываем горизонтальный отрезок [0,1], каждая точка которого

соответствует смешанной стратегии игрока B. В концах этого отрезка проводим два перпендикуляра. Левый соответствует чистой стратегии B1, правый — чистой стратегии B2игрока B.

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

3. Каждую пару точек, изображающих элементы ai1, ai2, i=1. m, стоящих в i-той строке платежной матрицы, соединяем отрезком ai1, ai2 . Таким образом будут построены m отрезков, представляющих собой графики m линейных функций, зависящих от вероятности q: H(Ai,Q)=(ai2-ai1)q+ai1, i=1. m, q Î[0,1].

Читать еще:  Как нарисовать смешариков и их домики. Смешарики

4. Находим верхнюю огибающую семейства построенных отрезков ai1, ai2 , представляющую собой выпуклую вниз ломаную. Затем находим минимальную точку верхней огибающей. Абсцисса q o этой точки определяет оптимальную смешанную стратегию Q o =(1-q o ,q o ) игрока B. Ордината наинизшей точки верхней огибающей равна цене игры V.

5. Верхний из нижних концов отрезков ai1, ai2 есть нижняя цена игры в чистых стратегиях, т.е. a. Нижний из концов верхней огибающей (лежащих на перпендикулярах) есть верхняя цена игры в чистых стратегиях, т.е. b.

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

Пример 5. Графически решить игру:

Действуя по алгоритму геометрического нахождения игры М×2

(рисунок 3.3), находим, что цена игры V=4, нижняя цена игры: a=3, верхняя цена игры: b=5, оптимальная стратегия игрока B: Q o =(2/3, 1/3).

Пример 9. Решить графически игру, заданную платежной матрицей:

Нижняя цена игры равна а11=1,5. Верхняя цена игры равна а21=2, седловая точка отсутствует.

Для игрока А решение представлено на рис. 3.4. Точка N определяет оптимальную стратегию, а ордината — цену игры v. Найдем точку пересечения соответствующих прямых:

Рис. 3.4. Решение матричной игры для игрока А

Следовательно, оптимальная стратегия игрока А заключается в выборе стратегии А1 с вероятностью 0,6 и стратегии А2 с вероятностью 0,4. При этом цена игры v = 1,8.

Для игрока В решение представлено на рис. 3.5. Находя точку пересечения соответствующих прямых, получаем М(0,2; 1,8).

Рис. 3.5. Решение матричной игры для игрока В

Следовательно, оптимальная стратегия игрока В заключается в выборе стратегии В1 с вероятностью 0,8 и стратегии В2 с вероятностью
0,2 = 1 – 0,8. При этом цена игры v = 1,8.

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

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

Проверим наличие седловой точки

Так как , седловой точки нет. Решим матричную игру графически. Построим прямые, соответствующие стратегиям игрока А.

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

Матрица оптимальных стратегий имеет вид

, ,

, ,

, ,

,

Следовательно, решение игры таково:

, ,

Пример 11. Решить матричную игру

Пример решения задачи по теории игр.

Ниже приведено условие задачи и текстовая часть решения. Закачка полного решения, файлы doc и xls в архиве zip, начнется автоматически через 10 секунд.

Фирма пробует различные стратегии организации обслуживания населения (в январе-мае), получая за каждую из них в соответствующем периоде определенную прибыль в млн. руб. (см. платежную матрицу А). Необходимо определить наилучшую стратегию (стратегии) фирмы на будущее:

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

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

3. предполагая, что клиенты в будущем поведут себя непредсказуемо (матрица рисков R )

Определим седловой элемент:

Матрица не имеет седлового элемента:

А ≠ В  51 ≤ v ≤ 69

  1. В данном случае необходимо выбрать одну из предлагаемых пяти стратегий. Т. е. решение матричной игры будет представлено в чистых стратегиях.

Найдем оптимальную стратегию по критерию Лапласа.

А i = m ах1/ n  A ij

А 1 = (256 + 235 + 158 + 64 – 20)/5 = 138,6;

А 2 = ( 148 + 124 + 76 + 122 + 23)/5 = 98,6;

А 3 = ( 102 + 123 + 96 + 88 + 51)/5 = 92;

А 4 = ( 89 + 105 + 171 + 36 – 100)/5 = 60,2;

А 5 = ( 21 + 72 + 127 + 104 + 69)/5 = 78,6.

Оптимальной является стратегия А 1 .

Если ориентироваться на выбор одной из стратегий и на логичное поведение покупателей оптимальной является стратегия А 1 .

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

Источники:

http://www.math-pr.com/exampl_gt2.htm
http://zdamsam.ru/a62273.html
http://easyhelp.su/subjects/ekonomiko_matematicheskie_metody_i_modeli/teoriya_igr/

Ссылка на основную публикацию
Статьи c упоминанием слов:

Adblock
detector