Оптимальные стратегии игры (с седловой точкой). Решение матричной игры

Размещено на http://www.allbest.ru/

1. Найти оптимальные стратегии игры (с седловой точкой)

.

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

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	a = min(Ai)
A1	1	2	2	1
A2	0	4	-1	-1
A3	-1	-2	5	-2
b = max(Bi)	1	4	5

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 1, которая указывает на максимальную чистую стратегию A₁.

Верхняя цена игры b = min(b_j) = 1.

Седловая точка (1, 1) указывает решение на пару альтернатив (A1,B1). Цена игры равна 1.

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

2. 3. . 4. .



Решение матричной игры

Игроки	B1	B2	a = min(Ai)
A1	6	-1	-1
A2	5	-2	-2
A3	3	2	2
A4	-1	3	-1
b = max(Bi)	6	3

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A3.

Верхняя цена игры b = min(bj) = 3.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 2 <= y <= 3. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)

Стратегия A1 доминирует над стратегией A2 (все элементы строки 1 больше или равны значениям 2-ой строки), следовательно, исключаем 2-ую строку матрицы. Вероятность p2 = 0.

6	-1
3	2
-1	3

В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (1). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).

7	0
4	3
0	4

Решим задачу геометрическим методом, который включает в себя следующие этапы:

1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B₁, правый - стратегии B₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂).

2. На левой оси ординат откладываются выигрыши стратегии B₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B₂.

Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока B соответствует точка N, лежащая на пересечении прямых A₂A₂ и A₃A₃, для которых можно записать следующую систему уравнений:

y = 4 + (3 - 4)q₂

y = 0 + (4 - 0)q₂

Откуда

q₁ = ¹/₅

q₂ = ⁴/₅

Цена игры, y = 3¹/₅

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



4p₂ = y

3p₂+4p₃ = y

p₂+p₃ = 1

или

4p₂ = 3¹/₅

3p₂+4p₃ = 3¹/₅

p₂+p₃ = 1

Решая эту систему методом Гаусса, находим:

p₂ = ⁴/₅

p₃ = ¹/₅

Поскольку ранее к элементам матрицы было прибавлено число (1), то вычтем это число из цены игры. Цена игры: y = 3¹/₅ - 1 = 2¹/₅

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1	7	5	6	4	7	4
A2	5	10	4	10	11	4
A3	2	14	2	12	13	2
A4	6	6	5	5	10	5
b = max(Bi)	7	14	6	12	13

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 5, которая указывает на максимальную чистую стратегию A₄.

Верхняя цена игры b = min(b_j) = 6.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 5 ? y ? 6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы

платежный матрица седловой декартовый

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ? a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ? a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

С позиции проигрышей игрока В стратегия B5 доминирует над стратегией B1 (все элементы столбца 5 больше элементов столбца 1), следовательно исключаем 5-ой столбец матрицы. Вероятность q5 = 0.

7	5	6	4
5	10	4	10
2	14	2	12
6	6	5	5

В платежной матрице отсутствуют доминирующие строки.

Мы свели игру 4 x 5 к игре 4 x 4.

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

3. Находим решение игры в смешанных стратегиях

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:



7x₁+5x₂+2x₃+6x₄ ? 1

5x₁+10x₂+14x₃+6x₄ ? 1

6x₁+4x₂+2x₃+5x₄ ? 1

4x₁+10x₂+12x₃+5x₄ ? 1

F(x) = x₁+x₂+x₃+x₄ > min

найти максимум функции Ф(y) при ограничениях:

7y₁+5y₂+6y₃+4y₄ ? 1

5y₁+10y₂+4y₃+10y₄ ? 1

2y₁+14y₂+2y₃+12y₄ ? 1

6y₁+6y₂+5y₃+5y₄ ? 1

Ф(y) = y₁+y₂+y₃+y₄ > max

Решаем эти системы симплексным методом.

Решение симплекс-методом доступно в расширенном режиме.

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

p_i = g*x_i; q_i = g*y_i.

Цена игры: g = 1 : ²/₁₁ = 5¹/₂

p₁ = 5¹/₂ * ³/₂₂ = ³/₄

p₂ = 5¹/₂ * ¹/₂₂ = ¹/₄

p₃ = 5¹/₂ * 0 = 0

p₄ = 5¹/₂ * 0 = 0

Оптимальная смешанная стратегия игрока I:



P = (³/₄; ¹/₄; 0; 0)

q₁ = 5¹/₂ * 0 = 0

q₂ = 5¹/₂ * 0 = 0

q₃ = 5¹/₂ * ³/₂₂ = ³/₄

q₄ = 5¹/₂ * ¹/₂₂ = ¹/₄

Оптимальная смешанная стратегия игрока II:

Q = (0; 0; ³/₄; ¹/₄)

Цена игры: v=5¹/₂

Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijp_i ? v

?a_ijq_j ? v

M(P₁;Q) = (7*0) + (5*0) + (6*³/₄) + (4*¹/₄) = 5.5 ? v

M(P₂;Q) = (5*0) + (10*0) + (4*³/₄) + (10*¹/₄) = 5.5 ? v

M(P₃;Q) = (2*0) + (14*0) + (2*³/₄) + (12*¹/₄) = 4.5 ? v

M(P₄;Q) = (6*0) + (6*0) + (5*³/₄) + (5*¹/₄) = 5 ? v

M(P;Q₁) = (7*³/₄) + (5*¹/₄) + (2*0) + (6*0) = 6.5 > v

M(P;Q₂) = (5*³/₄) + (10*¹/₄) + (14*0) + (6*0) = 6.25 > v

M(P;Q₃) = (6*³/₄) + (4*¹/₄) + (2*0) + (5*0) = 5.5 < v

M(P;Q₄) = (4*³/₄) + (10*¹/₄) + (12*0) + (5*0) = 5.5 < v

4. Проверяем, имеет ли платежная матрица седловую точку

Если да, то выписываем решение игры в чистых стратегиях.

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1	5	10	0	9	4	0
A2	10	5	0	7	6	0
A3	0	12	10	8	7	0
A4	0	15	5	10	1	0
b = max(Bi)	10	15	10	10	7

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 0, которая указывает на максимальную чистую стратегию A₁.

Верхняя цена игры b = min(b_j) = 7.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 0 ? y ? 7. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

5. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ? a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ? a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

6. Находим решение игры в смешанных стратегиях

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

5x₁+10x₂ ? 1

10x₁+5x₂+12x₃+15x₄ ? 1

10x₃+5x₄ ? 1

9x₁+7x₂+8x₃+10x₄ ? 1

4x₁+6x₂+7x₃+x₄ ? 1

F(x) = x₁+x₂+x₃+x₄ > min

найти максимум функции Ф(y) при ограничениях:

5y₁+10y₂+9y₄+4y₅ ? 1

10y₁+5y₂+7y₄+6y₅ ? 1

12y₂+10y₃+8y₄+7y₅ ? 1

15y₂+5y₃+10y₄+y₅ ? 1

Ф(y) = y₁+y₂+y₃+y₄+y₅ > max

Решаем эти системы симплексным методом.

Решение симплекс-методом доступно в расширенном режиме.

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

p_i = g*x_i; q_i = g*y_i.

Цена игры: g = 1: ¹/₅ = 5

p₁ = 5 * 0 = 0

p₂ = 5 * ¹/₁₀ = ¹/₂

p₃ = 5 * ¹/₁₀ = ¹/₂

p₄ = 5 * 0 = 0

Оптимальная смешанная стратегия игрока I:

P = (0; ¹/₂; ¹/₂; 0)

q₁ = 5 * ¹/₁₀ = ¹/₂

q₂ = 5 * 0 = 0

q₃ = 5 * ¹/₁₀ = ¹/₂

q₄ = 5 * 0 = 0

q₅ = 5 * 0 = 0

Оптимальная смешанная стратегия игрока II:

Q = (¹/₂; 0; ¹/₂; 0; 0)



Цена игры: v=5

Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijp_i ? v

?a_ijq_j ? v

M(P₁;Q) = (5*¹/₂) + (10*0) + (0*¹/₂) + (9*0) + (4*0) = 2.5 ? v

M(P₂;Q) = (10*¹/₂) + (5*0) + (0*¹/₂) + (7*0) + (6*0) = 5 = v

M(P₃;Q) = (0*¹/₂) + (12*0) + (10*¹/₂) + (8*0) + (7*0) = 5 = v

M(P₄;Q) = (0*¹/₂) + (15*0) + (5*¹/₂) + (10*0) + (1*0) = 2.5 ? v

M(P;Q₁) = (5*0) + (10*¹/₂) + (0*¹/₂) + (0*0) = 5 = v

M(P;Q₂) = (10*0) + (5*¹/₂) + (12*¹/₂) + (15*0) = 8.5 > v

M(P;Q₃) = (0*0) + (0*¹/₂) + (10*¹/₂) + (5*0) = 5 = v

M(P;Q₄) = (9*0) + (7*¹/₂) + (8*¹/₂) + (10*0) = 7.5 > v

M(P;Q₅) = (4*0) + (6*¹/₂) + (7*¹/₂) + (1*0) = 6.5 > v

7. Решите игру с заданной платежной матрицей, используя симплекс-метод

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

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1	8	6	8	7	8	6
A2	8	6	8	10	5	5
A3	8	7	6	8	7	6
A4	7	8	7	8	6	6
A5	10	6	7	7	7	6
b = max(Bi)	10	8	8	10	8

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 6, которая указывает на максимальную чистую стратегию A₁.

Верхняя цена игры b = min(b_j) = 8.

Что свидетельствует об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 6 ? y ? 8. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

8. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы

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

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ? a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ? a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.

С позиции проигрышей игрока В стратегия B4 доминирует над стратегией B2 (все элементы столбца 4 больше элементов столбца 2), следовательно исключаем 4-ой столбец матрицы. Вероятность q4 = 0.

8	6	8	8
8	6	8	5
8	7	6	7
7	8	7	6
10	6	7	7

Стратегия A1 доминирует над стратегией A2 (все элементы строки 1 больше или равны значениям 2-ой строки), следовательно, исключаем 2-ую строку матрицы. Вероятность p2 = 0.

8	6	8	8
8	7	6	7
7	8	7	6
10	6	7	7

Мы свели игру 5 x 5 к игре 4 x 4.

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

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

9. Находим решение игры в смешанных стратегиях

Математические модели пары двойственных задач линейного программирования можно записать так:

найти минимум функции F(x) при ограничениях:

8x₁+8x₂+7x₃+10x₄ ? 1

6x₁+7x₂+8x₃+6x₄ ? 1

8x₁+6x₂+7x₃+7x₄ ? 1

8x₁+7x₂+6x₃+7x₄ ? 1

F(x) = x₁+x₂+x₃+x₄ > min

найти максимум функции Ф(y) при ограничениях:

8y₁+6y₂+8y₃+8y₄ ? 1

8y₁+7y₂+6y₃+7y₄ ? 1

7y₁+8y₂+7y₃+6y₄ ? 1

10y₁+6y₂+7y₃+7y₄ ? 1

Ф(y) = y₁+y₂+y₃+y₄ > max

Решаем эти системы симплексным методом.

Решение симплекс-методом доступно в расширенном режиме.

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:

p_i = g*x_i; q_i = g*y_i.

Цена игры: g = 1 : ¹/₇ = 7

p₁ = 7 * ¹/₂₁ = ¹/₃

p₂ = 7 * ¹/₂₁ = ¹/₃

p₃ = 7 * ¹/₂₁ = ¹/₃

p₄ = 7 * 0 = 0

Оптимальная смешанная стратегия игрока I:

P = (¹/₃; ¹/₃; ¹/₃; 0)

q₁ = 7 * 0 = 0

q₂ = 7 * ¹/₁₄ = ¹/₂

q₃ = 7 * 0 = 0

q₄ = 7 * ¹/₁₄ = ¹/₂

Оптимальная смешанная стратегия игрока II:

Q = (0; ¹/₂; 0; ¹/₂)

Цена игры: v=7

Проверим правильность решения игры с помощью критерия оптимальности стратегии.

?a_ijp_i ? v

?a_ijq_j ? v

M(P₁;Q) = (8*0) + (6*¹/₂) + (8*0) + (8*¹/₂) = 7 = v

M(P₂;Q) = (8*0) + (7*¹/₂) + (6*0) + (7*¹/₂) = 7 = v

M(P₃;Q) = (7*0) + (8*¹/₂) + (7*0) + (6*¹/₂) = 7 = v

M(P₄;Q) = (10*0) + (6*¹/₂) + (7*0) + (7*¹/₂) = 6.5 ? v

M(P;Q₁) = (8*¹/₃) + (8*¹/₃) + (7*¹/₃) + (10*0) = 7.67 > v

M(P;Q₂) = (6*¹/₃) + (7*¹/₃) + (8*¹/₃) + (6*0) = 7 = v

M(P;Q₃) = (8*¹/₃) + (6*¹/₃) + (7*¹/₃) + (7*0) = 7 = v

M(P;Q₄) = (8*¹/₃) + (7*¹/₃) + (6*¹/₃) + (7*0) = 7 = v

Дана матрица выигрышей в игре с природой

	П1	П2	П3	П4	П5
А1	9	5	10	3	9
А2	6	4	8	4	5
А3	5	6	1	10	9
А4	4	2	9	1	3
А5	10	1	4	3	6
q	0,3	0,3	0,2	0,1	0,1

Найти показатели благоприятности для состояний природы, построить модель рисков. Используя критерий Байеса, по полученным матрицам определить оптимальные стратегии игрока А:

а) по значениям вероятностей появления событий природы q_j;

б) считая состояния природы равновероятными;

в) сравнить полученные результаты и дать им соответствующую трактовку.

10. Критерий Байеса

По критерию Байеса за оптимальные принимается та стратегия (чистая) A_i, при которой максимизируется средний выигрыш a или минимизируется средний риск r.

Считаем значения ?(a_ijp_j)

?(a_1,jp_j) = 9*0.3 + 5*0.3 + 10*0.2 + 3*0.1 + 9*0.1 = 7.4

?(a_2,jp_j) = 6*0.3 + 4*0.3 + 8*0.2 + 4*0.1 + 5*0.1 = 5.5

?(a_3,jp_j) = 5*0.3 + 6*0.3 + 1*0.2 + 10*0.1 + 9*0.1 = 5.4

?(a_4,jp_j) = 4*0.3 + 2*0.3 + 9*0.2 + 1*0.1 + 3*0.1 = 4

?(a_5,jp_j) = 10*0.3 + 1*0.3 + 4*0.2 + 3*0.1 + 6*0.1 = 5

Ai	П1	П2	П3	П4	П5	?(aijpj)
A1	2.7	1.5	2	0.3	0.9	7.4
A2	1.8	1.2	1.6	0.4	0.5	5.5
A3	1.5	1.8	0.2	1	0.9	5.4
A4	1.2	0.6	1.8	0.1	0.3	4
A5	3	0.3	0.8	0.3	0.6	5
pj	0.3	0.3	0.2	0.1	0.1	0

Выбираем из (7.4; 5.5; 5.4; 4; 5) максимальный элемент max=7.4

Вывод: выбираем стратегию N=1.

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

Размещено на Allbest.ru

...