Теория игр. Платежная матрица. (Семинар 2) презентация

Содержание

Платежная матрица Пусть игрок A располагает m стратегиями A1 , A2, …, Am и игрок B имеет n стратегий B1 , B2, …, Bn. Выигрыш игрока A при выборе стратегий Ai

Слайд 1 Теория игр
Семинар 2:

Слайд 2Платежная матрица
Пусть игрок A располагает m стратегиями A1 , A2, …,

Am и игрок B имеет n стратегий B1 , B2, …, Bn.
Выигрыш игрока A при выборе стратегий Ai и Bj обозначим aij.
Платежная матрица (матрица игры):







Слайд 3
Нижняя цена игры
Пусть αi – наименьший выигрыш игрока A при выборе

им стратегии Ai для всех возможных стратегий игрока B:

Тогда гарантированный выигрыш игрока A при любой стратегии игрока B равен:


α – нижняя цена игры.







Слайд 4
Верхняя цена игры
Число β – верхняя цена игры:


β - гарантированный проигрыш

игрока B.

Если α = β = v, то v – чистая цена (или цена игры). Тогда пара оптимальных стратегий Ai и Bj, для которой aij = v называется седловой точкой платежной матрицы.






Слайд 5Задача 1
Найдите седловую точку в игре с матрицей выигрышей

А. В ответе указать чистую цену игры.


Слайд 6Решение:
Найдем минимальные значения каждой строки матрицы А и выберем из них

наибольшее для определения нижней цены игры:
α1 = min (0,1; 0,4; 0,2) = 0,1
α2 = min (0,5; 0,4; 0,3) = 0,3
α3 = min (0,3; 0,2; 0,1) = 0,1
α = max (0,1; 0,3; 0,1) = 0,3




Слайд 7Найдем верхнюю цену игры. Для этого определим максимальное значение в каждом

столбце и выберем наименьшее из них :
β1 = max (0,1; 0,5; 0,3) = 0,5
β2 = max (0,4; 0,4; 0,2) = 0,4
β3 = max (0,2; 0,3; 0,1) = 0,3
β = min (0,5; 0,4; 0,3) = 0,3




Слайд 8Получаем: α = β = 0,3
v = 0,3
Седловая точка - (A2B3)

Слайд 9Задача 2
Найдите седловую точку в игре с матрицей выигрышей

А. В ответе указать чистую цену игры.



Слайд 10Решение:
Нижняя цена игры:
α1 = min (2; 10; 25; 0) =

0
α2 = min (13; 14; 19; 6) = 6
α3 = min (-5; 3; -2; -4) = - 5
α4 = min (18; 5; -3; -5) = - 5
α = max (0; 6 ; -5; -5) = 6




Слайд 11Верхняя цена игры:
β1 = max (2; 13; -5; 18)

= 18
β2 = max (10; 14; 3; 5) = 14
β3 = max (25; 19; -2; -3) = 25
β4 = max (0; 6; -4; -5) = 6
β = min (18; 14 ; 25; 6) = 6




Слайд 12Получаем: α = β = 6
v = 6
Седловая точка - (A2B4)

Слайд 13Решение игры в смешанных стратегиях
Если α < β, то применение чистых

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


Слайд 14
Смешанная стратегия SА игрока А – применение чистых стратегий A1 ,

A2, …, Am с вероятностями р1 , р2, …, рm.



Для игрока B аналогично:




Слайд 15Задача 3
Найдите решение игры в смешанных стратегиях. В ответе

указать среднюю цену игры.



Слайд 16
Решение:
Найдем нижнюю и верхнюю цену игры:
α = 3, β =

4, α ≠ β
Средний выигрыш игрока А равен цене игры v, если он использует оптимальную смешанную стратегию

игрок B использует чистую стратегию B1 (т.е. первый столбец платежной матрицы)



Слайд 17
Средний выигрыш игрока А также равен цене игры v, если игрок

B применяет стратегию B2 (т.е. второй столбец платежной матрицы):

Получаем систему:


Слайд 18
Решаем систему:


Слайд 19
Составим аналогичную систему для игрока В:


Слайд 20

Ответ:




Слайд 21Задача 4
Найдите решение игры в смешанных стратегиях. В ответе

указать среднюю цену игры.



Слайд 22
Решение:
Найдем нижнюю и верхнюю цену игры:
α = 1,5, β =

2, α ≠ β



Слайд 23
Решение:
Найдем нижнюю и верхнюю цену игры:
α = 1,5, β =

2, α ≠ β
Система уравнений для игрока А:



Слайд 25
Составим аналогичную систему для игрока В:

Слайд 26



Ответ:


Слайд 27Задача 3
Найдите решение игры в смешанных стратегиях графическим способом.

В ответе указать среднюю цену игры.



Слайд 28
Решение:
Найдем нижнюю и верхнюю цену игры:
α = 3, β =

4, α ≠ β



Слайд 29
Решение:
Найдем нижнюю и верхнюю цену игры:
α = 3, β =

4, α ≠ β
На оси Оx отложим единичный отрезок A1A2.
Прямая x = 0 соответствует стратегии A1 игрока A, а прямая x = 1 соответствует стратегии A2.



Слайд 30В1
В2
В1
y
Пусть игрок В примет стратегию В1.
Отложим на прямых x = 0

и x = 1 соответствующие выигрыши и обозначим точки В1.
Сделаем аналогично для второй стратегии В2 игрока В.

Слайд 31В1
В2
В1
y
Точки, лежащие на ломаной линии В2NВ1 показывают минимальный выигрыш игрока A

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

Слайд 32В1
В2
В1
y
существует стратегия

Ордината точки N равна цене игры v.

Найдем уравнения

прямой В1В1



Уравнение прямой В2В2.



Слайд 33Получаем систему уравнений:







Слайд 34Определим аналогично геометрическим способом оптимальную стратегию игрока В.
Поменяем местами игроков А

и В и вместо максимума найдем минимум верхней границы.

Слайд 35А1
А2
А1
y
Найдем уравнения прямой A1A1



Уравнение прямой A2A2.




Слайд 36Получаем систему уравнений:








Ответ:


Слайд 37Задача 4


Найдите решение игры в смешанных стратегиях графическим способом.

В ответе указать среднюю цену игры.

Слайд 38
Решение:
Найдем нижнюю и верхнюю цену игры:
α = 1,5, β

= 2, α ≠ β



Слайд 39
Решение:
Найдем нижнюю и верхнюю цену игры:
α = 1,5, β

= 2, α ≠ β
На оси Оx отложим единичный отрезок A1A2.
Прямая x = 0 соответствует стратегии A1 игрока A, а прямая x = 1 соответствует стратегии A2.



Слайд 40В1
В2
В1
y
Пусть игрок В примет стратегию В1.
Отложим на прямых x = 0

и x = 1 соответствующие выигрыши и обозначим точки В1.
Сделаем аналогично для второй стратегии В2 игрока В.

Слайд 41В1
В2
В1
y
Точки, лежащие на ломаной линии В1NВ2 показывают минимальный выигрыш игрока A

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

Слайд 42В1
В2
В1
y
существует стратегия

Ордината точки N равна цене игры v.

Найдем уравнения

прямой В1В1



Уравнение прямой В2В2.

Слайд 43Получаем систему уравнений:










Слайд 44Определим аналогично геометрическим способом оптимальную стратегию игрока В.
Поменяем местами игроков А

и В и вместо максимума найдем минимум верхней границы.

Слайд 45А1
А2
А1
y
Найдем уравнения прямой A1A1



Уравнение прямой A2A2.




Слайд 46Получаем систему уравнений:








Ответ:


Слайд 47Если в платежной матрице A все элементы i-й строки не меньше

соответствующих элементов k-й строки, aij ≥ akj , j = 1, 2, …, n, а по крайней мере один строго больше, то i-я строка – доминирующая, а k-я строка – доминирумая.





Доминирующие и доминируемые стратегии

Слайд 48Игроку А не выгодно применять стратегии, которым соответствуют доминируемые строки, а

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





Доминирующие и доминируемые стратегии

Слайд 49Задача 5


Найти решение игры в смешанных стратегиях, предварительно упростив

ее. В ответе указать среднюю цену игры.

Слайд 50Найдем нижнюю и верхнюю цену игры:
α = 2, β =

3, α ≠ β

Решение:

Слайд 51Найдем нижнюю и верхнюю цену игры:
α = 2, β =

3, α ≠ β
Cтрока А3 доминируемая относительно строки А1, поэтому для игрока А она не выгодна.
Для игрока В не выгодны столбцы В1 и В2 .

Решение:

Слайд 52Удаляем не выгодные для игроков А и В стратегии и получаем

матрицу:


Решим полученную задачу аналитическим способом. Для игрока А:

Слайд 53Удаляем не выгодные для игроков А и В стратегии и получаем

матрицу:


Решим полученную задачу аналитическим способом. Для игрока А:

Слайд 55
Для игрока В:

Слайд 56
Для игрока В:


Слайд 57

Ответ:




Слайд 58Задача 6
Найти решение игры в смешанных стратегиях, предварительно упростив

ее. В ответе указать среднюю цену игры.



Слайд 59Найдем нижнюю и верхнюю цену игры:
α = 3, β =

4, α ≠ β

Решение:

Слайд 60Найдем нижнюю и верхнюю цену игры:
α = 3, β =

4, α ≠ β
Строка А2 доминируемая относительно строки А1 .
Строка А4 доминируемая строки А3.
Для игрока А они не выгодны.

Остается матрица:

Решение:

Слайд 61Для игрока В при сравнении:
В1 и В4 исключим столбец В1;
В2 и

В4 исключим столбец В2;
В3 и В4 исключим столбец В3.

Остается матрица:

Слайд 62Решим полученную задачу аналитическим способом. Для игрока А:

Слайд 63
Для игрока В:

Слайд 64
Для игрока В:

Слайд 65


Ответ:



Слайд 66Приведение матричной игры к задаче линейного программирования
Пусть игрок A обладает Ai

стратегиями
i = 1, 2, …, m и игрок B имеет Bj стратегий
j = 1, 2, …, n.
Оптимальная стратегия SA* обеспечивает игроку A при любой стратегии игрока B средний выигрыш, не меньший, чем цена игры v, и при оптимальной стратегии игрока B выигрыш равный цене игры v.







Слайд 67Пусть v > 0, тогда для оптимальной стратегии SA* все средние

выигрыши не меньше цены игры v:




Пусть , тогда:










Слайд 68Цель игрока A – максимизировать свой гарантированный выигрыш.
Рассмотрим



Поскольку

, то








Слайд 69Получаем задачу линейного программирования:





Решением задачи будет оптимальная стратегия SA* игрока A.








Слайд 70Для определения оптимальной стратегии SВ*игрока B следует учесть, что игрок B

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






где







Слайд 71Задача 7
Найти решение игры с помощью линейного программирования.


Слайд 72Найдем нижнюю и верхнюю цену игры:
α = 0, β =

1, α ≠ β

Решение:

Слайд 73Найдем нижнюю и верхнюю цену игры:
α = 0, β =

1, α ≠ β
Решим задачу для второго игрока В с помощью линейного программирования:




где

Решение:

Слайд 74Приведем полученную систему к каноническому виду:





Слайд 75Решим полученную задачу линейного программирования симплекс-методом:







Слайд 78Поскольку и


то




Слайд 79

Ответ:


Слайд 80Задача 8
Найти решение игры с помощью линейного программирования.


Слайд 81Найдем нижнюю и верхнюю цену игры:
α = 4, β =

6, α ≠ β





Решение:

Слайд 82Найдем нижнюю и верхнюю цену игры:
α = 4, β =

6, α ≠ β
Решим задачу для второго игрока В с помощью линейного программирования:




где

Решение:

Слайд 83Приведем полученную систему к каноническому виду:





Слайд 84Решим симплекс-методом:







Слайд 88Поскольку и


то




Слайд 89

Ответ:


Слайд 90Игра с природой
- матричная игра, где игрок взаимодействует с окружающей

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






Слайд 91Игра с природой
Пусть A1 , A2, …, Am - возможные чистые

стратегии игрока A; П1 , П2, …, Пn – возможные состояния природы; aij – выигрыш игрока при применении им своей i-й стратегии при j-м состоянии природы.
Платежная матрица:







Слайд 92Есть другой способ задания матрицы игры с природой – в виде

матрицы рисков
Риск rij игрока A при использовании стратегии Ai и состоянии природы Пj – разность между выигрышем, который получил бы игрок, если бы знал, что состоянием природы будет Пj, и выигрышем, который получит игрок, не зная этого.








Слайд 93Для определения оптимальной стратегии игрока A в игре с природой используется

ряд критериев: Лапласа, Вальда, Сэвиджа, Гурвица.

Критерий Вальда – основан на выборе наилучшей из наихудших стратегий Ai.
Если в матрице А результат аij представляет выигрыш игрока A, при выборе его оптимальной стратегии используется максиминный критерий:










Слайд 94
Критерий Cэвиджа – использует матрицу рисков

В оптимальной стратегии минимизируется максимальный

риск (достигается значение S):










Слайд 95
Критерий Гурвица – при любом выборе стратегии наихудший для игрока А

вариант реализуется с вероятностью α, а наилучший с вероятностью 1-α,
где α – показатель пессимизма (0 ≤ α ≤ 1).
Если аij – выигрыш игрока А, то оптимальной стратегией считается та, в которой достигается значение G:










Слайд 96
Критерий Лапласа – все состояния природы Пj, j = 1, …,

n, считаются равновероятностными .
Оптимальной стратегией считается та, для которой достигается значение L:











Слайд 97Задача 9
Найти оптимальную стратегию игрока, используя критерии оптимальности Вальда,

Гурвица, Сэвиджа, Лапласа (коэффициент пессимизма равен 0,3).


Слайд 981. Найдем критерий Вальда.
В каждой строке матрицы

найдем наименьший элемент, а затем из них выберем строку j с наибольшим из найденных элементов:



По критерию Вальда оптимальные стратегии A2 и A3.




Решение:

Слайд 992. Найдем критерий Сэвиджа.
Для матрицы А построим матрицу рисков R:



В каждом столбце выбираем наибольший элемент: 3; 4; 1




Слайд 100Найдем наибольший элемент каждой строки матрицы R, затем среди них выберем

минимальный.




По критерию Сэвиджа оптимальная стратегия A3.




Слайд 1013. Найдем критерий Гурвица. (α = 0,3)




По критерию Гурвица оптимальная стратегия A3.



Слайд 1024. Найдем критерий Лапласа. n = 3






По критерию Лапласа оптимальная стратегия A3.



Слайд 103
Ответ:
По критерию Вальда оптимальные стратегии A2 и A3.
По критерию

Сэвиджа оптимальная стратегия A3.
По критерию Гурвица оптимальная стратегия A3.
По критерию Лапласа оптимальная стратегия A3.



Слайд 104Задача 10
Найти оптимальную стратегию игрока, используя критерии оптимальности Вальда,

Гурвица, Сэвиджа, Лапласа (коэффициент пессимизма равен 0,3).


Слайд 1051. Найдем критерий Вальда.
В каждой строке матрицы

найдем наименьший элемент, а затем из них выберем строку j с наибольшим из найденных элементов:



По критерию Вальда оптимальные стратегии A3.




Решение:

Слайд 1062. Найдем критерий Сэвиджа.
Для матрицы А построим матрицу рисков R:



В каждом столбце выбираем наибольший элемент: 8; 7; 9




Слайд 107Найдем наибольший элемент каждой строки матрицы R, затем среди них выберем

минимальный.




По критерию Сэвиджа оптимальная стратегия A3.




Слайд 1083. Найдем критерий Гурвица. (α = 0,3)




По критерию Гурвица оптимальная стратегия A2.



Слайд 1094. Найдем критерий Лапласа. n = 3






По критерию Лапласа оптимальная стратегия A3.



Слайд 110
Ответ:
По критерию Вальда оптимальная стратегия A3.
По критерию Сэвиджа оптимальная

стратегия A3.
По критерию Гурвица оптимальная стратегия A2.
По критерию Лапласа оптимальная стратегия A3.



Слайд 111Спасибо за внимание!

Похожие презентации

Изменение величин. (6 класс) 315
matematicheskie rebusy 324
Аттестационная работа. Организация познавательной деятельности на уроках математики в 5 классе 248
Основные понятия алгебры логики 319
Аттестационная работа. Математика за здоровый образ жизни 343
18yanv 246

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика