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

Теория игр Семинар 2:

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

Нижняя цена игры Пусть αi – наименьший выигрыш игрока A при выборе им стратегии Ai для всех возможных стратегий игрока B: Тогда гарантированный выигрыш игрока A при любой стратегии игрока B равен: α – нижняя цена игры.

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

Задача 1 Найдите седловую точку в игре с матрицей выигрышей А. В ответе указать чистую цену игры.

Решение: Найдем минимальные значения каждой строки матрицы А и выберем из них наибольшее для определения нижней цены игры: α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

Найдем верхнюю цену игры. Для этого определим максимальное значение в каждом столбце и выберем наименьшее из них : Найдем верхнюю цену игры. Для этого определим максимальное значение в каждом столбце и выберем наименьшее из них : β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

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

Задача 2 Найдите седловую точку в игре с матрицей выигрышей А. В ответе указать чистую цену игры.

Решение: Нижняя цена игры: α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

Верхняя цена игры: Верхняя цена игры: β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

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

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

Смешанная стратегия SА игрока А – применение чистых стратегий A1 , A2, …, Am с вероятностями р1 , р2, …, рm. Смешанная стратегия SА игрока А – применение чистых стратегий A1 , A2, …, Am с вероятностями р1 , р2, …, рm. Для игрока B аналогично:

Задача 3 Найдите решение игры в смешанных стратегиях. В ответе указать среднюю цену игры.

Решение: Найдем нижнюю и верхнюю цену игры: α = 3, β = 4, α ≠ β Средний выигрыш игрока А равен цене игры v, если он использует оптимальную смешанную стратегию игрок B использует чистую стратегию B1 (т.е. первый столбец платежной матрицы)

Средний выигрыш игрока А также равен цене игры v, если игрок B применяет стратегию B2 (т.е. второй столбец платежной матрицы): Средний выигрыш игрока А также равен цене игры v, если игрок B применяет стратегию B2 (т.е. второй столбец платежной матрицы): Получаем систему:

Решаем систему: Решаем систему:

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

Ответ:

Задача 4 Найдите решение игры в смешанных стратегиях. В ответе указать среднюю цену игры.

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

Решение: Найдем нижнюю и верхнюю цену игры: α = 1,5, β = 2, α ≠ β Система уравнений для игрока А:

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

Ответ:

Задача 3 Найдите решение игры в смешанных стратегиях графическим способом. В ответе указать среднюю цену игры.

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

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

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

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

существует стратегия существует стратегия Ордината точки N равна цене игры v. Найдем уравнения прямой В1В1 Уравнение прямой В2В2.

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

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

Найдем уравнения прямой A1A1 Найдем уравнения прямой A1A1 Уравнение прямой A2A2.

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

Задача 4

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

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

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

существует стратегия существует стратегия Ордината точки N равна цене игры v. Найдем уравнения прямой В1В1 Уравнение прямой В2В2.

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

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

Найдем уравнения прямой A1A1 Найдем уравнения прямой A1A1 Уравнение прямой A2A2.

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

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

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

Задача 5

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

Решение: Найдем нижнюю и верхнюю цену игры: α = 2, β = 3, α ≠ β Cтрока А3 доминируемая относительно строки А1, поэтому для игрока А она не выгодна. Для игрока В не выгодны столбцы В1 и В2 .

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

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

Для игрока В: Для игрока В:

Для игрока В: Для игрока В:

Ответ:

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

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

Решение: Найдем нижнюю и верхнюю цену игры: α = 3, β = 4, α ≠ β Строка А2 доминируемая относительно строки А1 . Строка А4 доминируемая строки А3. Для игрока А они не выгодны. Остается матрица:

Для игрока В при сравнении: Для игрока В при сравнении: В1 и В4 исключим столбец В1; В2 и В4 исключим столбец В2; В3 и В4 исключим столбец В3. Остается матрица:

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

Для игрока В: Для игрока В:

Для игрока В: Для игрока В:

Ответ: Ответ:

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

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

Цель игрока A – максимизировать свой гарантированный выигрыш. Цель игрока A – максимизировать свой гарантированный выигрыш. Рассмотрим Поскольку , то

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

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

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

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

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

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

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

Поскольку и Поскольку и то

Ответ: Ответ:

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

Решение: Найдем нижнюю и верхнюю цену игры: α = 4, β = 6, α ≠ β

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

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

Решим симплекс-методом: Решим симплекс-методом:

Поскольку и Поскольку и то

Ответ: Ответ:

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

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

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

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

Критерий Cэвиджа – использует матрицу рисков В оптимальной стратегии минимизируется максимальный риск (достигается значение S):

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

Критерий Лапласа – все состояния природы Пj, j = 1, …, n, считаются равновероятностными . Оптимальной стратегией считается та, для которой достигается значение L:

Задача 9 Найти оптимальную стратегию игрока, используя критерии оптимальности Вальда, Гурвица, Сэвиджа, Лапласа (коэффициент пессимизма равен 0,3).

Решение: 1. Найдем критерий Вальда. В каждой строке матрицы найдем наименьший элемент, а затем из них выберем строку j с наибольшим из найденных элементов: По критерию Вальда оптимальные стратегии A2 и A3.

2. Найдем критерий Сэвиджа. 2. Найдем критерий Сэвиджа. Для матрицы А построим матрицу рисков R: В каждом столбце выбираем наибольший элемент: 3; 4; 1

Найдем наибольший элемент каждой строки матрицы R, затем среди них выберем минимальный. Найдем наибольший элемент каждой строки матрицы R, затем среди них выберем минимальный. По критерию Сэвиджа оптимальная стратегия A3.

3. Найдем критерий Гурвица. (α = 0,3) 3. Найдем критерий Гурвица. (α = 0,3) По критерию Гурвица оптимальная стратегия A3.

4. Найдем критерий Лапласа. n = 3 4. Найдем критерий Лапласа. n = 3 По критерию Лапласа оптимальная стратегия A3.

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

Задача 10 Найти оптимальную стратегию игрока, используя критерии оптимальности Вальда, Гурвица, Сэвиджа, Лапласа (коэффициент пессимизма равен 0,3).

Решение: 1. Найдем критерий Вальда. В каждой строке матрицы найдем наименьший элемент, а затем из них выберем строку j с наибольшим из найденных элементов: По критерию Вальда оптимальные стратегии A3.

2. Найдем критерий Сэвиджа. 2. Найдем критерий Сэвиджа. Для матрицы А построим матрицу рисков R: В каждом столбце выбираем наибольший элемент: 8; 7; 9

Найдем наибольший элемент каждой строки матрицы R, затем среди них выберем минимальный. Найдем наибольший элемент каждой строки матрицы R, затем среди них выберем минимальный. По критерию Сэвиджа оптимальная стратегия A3.

3. Найдем критерий Гурвица. (α = 0,3) 3. Найдем критерий Гурвица. (α = 0,3) По критерию Гурвица оптимальная стратегия A2.

4. Найдем критерий Лапласа. n = 3 4. Найдем критерий Лапласа. n = 3 По критерию Лапласа оптимальная стратегия A3.

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

Спасибо за внимание!