Оптимальные чистые стратегии игроков

Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.

Оптимальные чистые стратегии игроков отличаются от смешанных наличием обязательного единичного pi = 1, qi = 1. Например: P(1,0), Q(1,0). Здесь p1 = 1, q1 = 1.

Задача 1
По платёжной матрице найти оптимальные чистые стратегии, используя принцип строгого доминирования. В качестве ответа записать векторы P*, Q*.



R1

R2

R3

R4

S1

3

1

2

5

S2

2

0

0

3

S3

-3

-5

-5

-2

S4

0

-2

-2

1

Решение:

Все задачи решаем с помощью калькулятора Матричная игра.
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки B1 B2 B3 B4 a = min(Ai)
A1 3 1 2 5 1
A2 2 0 0 3 0
A3 -3 -5 -5 -2 -5
A4 0 -2 -2 1 -2
b = max(Bi) 3 1 2 5
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 1.
Седловая точка (1, 2) указывает решение на пару альтернатив (A1,B2). Цена игры равна 1.
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.
Стратегия A1 доминирует над стратегией A2 (все элементы строки 1 больше или равны значениям 2-ой строки), следовательно исключаем 2-ую строку матрицы. Вероятность p2 = 0.
Стратегия A1 доминирует над стратегией A3 (все элементы строки 1 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.
3 1 2 5
0 -2 -2 1

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

Мы свели игру 4 x 4 к игре 2 x 2.
3. Находим решение игры в смешанных стратегиях.
Решим задачу геометрическим методом, который включает в себя следующие этапы:
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).
2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.
Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.
&Rcy;&iecy;&shcy;&iecy;&ncy;&icy;&iecy; &mcy;&acy;&tcy;&rcy;&icy;&chcy;&ncy;&ocy;&jcy; &icy;&gcy;&rcy;&ycy; &gcy;&rcy;&acy;&fcy;&icy;&chcy;&iecy;&scy;&kcy;&icy;&mcy; &mcy;&iecy;&tcy;&ocy;&dcy;&ocy;&mcy;
Максиминной оптимальной стратегии игрока A соответствует точка N, для которой можно записать следующую систему уравнений:
p1 = 1
p2 = 0
Цена игры, y = 1
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений
q1 = 1
q1+q2 = 1
Решая эту систему, находим:
q1 = 1.
Ответ:
Цена игры: y = 1, векторы стратегии игроков:
Q(1, 0), P(1, 0)
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑aijqj ≤ v
∑aijpi ≥ v
M(P1;Q) = (1•1) + (2•0) = 1 = v
M(P2;Q) = (-2•1) + (-2•0) = -2 ≤ v
M(P;Q1) = (1•1) + (-2•0) = 1 = v
M(P;Q2) = (2•1) + (-2•0) = 2 ≥ v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Поскольку из исходной матрицы были удалены строки и столбцы, то найденные векторы вероятности можно записать в виде:
P(1,0,0,0)
Q(0,1,0,0)

Задача 2
По платёжной матрице найти нижнюю и верхнюю цену игры. При наличии седловой точки записать векторы оптимальных чистых стратегий P*, Q*.



R1

R2

R3

S1

-6

-5

0

S2

-8

-3

-2

S3

-3

-2

3

Решение:
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Игроки B1 B2 B3 a = min(Ai)
A1 -6 -5 0 -6
A2 -8 -3 -2 -8
A3 -3 -2 3 -3
b = max(Bi) -3 -2 3

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = -3, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = -3.
Седловая точка (3, 1) указывает решение на пару альтернатив (A3,B1). Цена игры равна -3.
Ответ: P(0,0,1), Q(1,0,0)

Задача 3
По платёжной матрице найти векторы оптимальных стратегий P*, Q*и цену игры. Кто из игроков оказывается в выигрыше?



R1

R2

R3

R4

S1

-6

-6

2

4

S2

2

-2

7

-1

Решение:
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Игроки B1 B2 B3 B4 a = min(Ai)
A1 -6 -6 2 4 -6
A2 2 -2 7 -1 -2
b = max(Bi) 2 -2 7 4

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = -2, которая указывает на максимальную чистую стратегию A2.
Верхняя цена игры b = min(bj) = -2.
Седловая точка (2, 2) указывает решение на пару альтернатив (A2,B2). Цена игры равна -2.
3. Находим решение игры в смешанных стратегиях.
Решим задачу геометрическим методом, который включает в себя следующие этапы:
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).
2. На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.
Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.
Решение матричной игры графическим методом

Максиминной оптимальной стратегии игрока A соответствует точка N, для которой можно записать следующую систему уравнений:
p1 = 0
p2 = 1
Цена игры, y = -2
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B3,B4, которая дает явно больший проигрыш игроку B, и, следовательно, q1 = 0,q3 = 0,q4 = 0.
-2q2 = -2
q2 = 1
Решая эту систему, находим:
q2 = 1.
Ответ:
Цена игры: y = -2, векторы стратегии игроков:
Q(0, 1, 0, 0), P(0, 1)
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑aijqj ≤ v
∑aijpi ≥ v
M(P1;Q) = (-6•0) + (-6•1) + (2•0) + (4•0) = -6 ≤ v
M(P2;Q) = (2•0) + (-2•1) + (7•0) + (-1•0) = -2 = v
M(P;Q1) = (-6•0) + (2•1) = 2 ≥ v
M(P;Q2) = (-6•0) + (-2•1) = -2 = v
M(P;Q3) = (2•0) + (7•1) = 7 ≥ v
M(P;Q4) = (4•0) + (-1•1) = -1 ≥ v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

Задача 4
Дайте развернутый ответ на вопрос
Что такое верхняя цена игры?
Поясните на примере любой из предыдущих задач.

загрузка...