Загрузка...

Теория игр — 2 лабораторные работы


Вариант 1

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

Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Игроки B1 B2 a = min(Ai)
A1 1 1 1
A2 3 3 3
A3 7 1 1
A4 2 2 2
A5 3 1 1
A6 4 4 4
A7 5 1 1
A8 4 2 2
A9 5 3 3
A10 6 2 2
b = max(Bi) 7 4

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A6.
Верхняя цена игры b = min(bj) = 4.
Седловая точка (6, 2) указывает решение на пару альтернатив (A6,B2). Цена игры равна 4.

Критерий Ходжа-Лемана.
Для каждой строки рассчитываем значение критерия по формуле:
Wi = u∑aijpj + (1 — u)min(a)ij
Рассчитываем Wi.
W1 = 0.5•1 + (1-0.5)•1 = 1
W2 = 0.5•3 + (1-0.5)•3 = 3
W3 = 0.5•4 + (1-0.5)•1 = 2.5
W4 = 0.5•2 + (1-0.5)•2 = 2
W5 = 0.5•2 + (1-0.5)•1 = 1.5
W6 = 0.5•4 + (1-0.5)•4 = 4
W7 = 0.5•3 + (1-0.5)•1 = 2
W8 = 0.5•3 + (1-0.5)•2 = 2.5
W9 = 0.5•4 + (1-0.5)•3 = 3.5
W10 = 0.5•4 + (1-0.5)•2 = 3
Ai П1 П2 ∑(aijpj) min(aj) Wi
A1 0.5 0.5 1 1 1
A2 1.5 1.5 3 3 3
A3 3.5 0.5 4 1 2.5
A4 1 1 2 2 2
A5 1.5 0.5 2 1 1.5
A6 2 2 4 4 4
A7 2.5 0.5 3 1 2
A8 2 1 3 2 2.5
A9 2.5 1.5 4 3 3.5
A10 3 1 4 2 3
pj 0.5 0.5 0 0 0

Выбираем из (1; 3; 2.5; 2; 1.5; 4; 2; 2.5; 3.5; 3) максимальный элемент max=4
Вывод: выбираем стратегию N=6.
Таким образом, в результате решения статистической игры по различным критериям чаще других рекомендовалась стратегия A6.

Критерий Байеса.
По критерию Байеса за оптимальные принимается та стратегия (чистая) Ai, при которой максимизируется средний выигрыш a или минимизируется средний риск r.
Считаем значения ∑(aijpj)
∑(a1,jpj) = 1•0.5 + 1•0.5 = 1
∑(a2,jpj) = 3•0.5 + 3•0.5 = 3
∑(a3,jpj) = 7•0.5 + 1•0.5 = 4
∑(a4,jpj) = 2•0.5 + 2•0.5 = 2
∑(a5,jpj) = 3•0.5 + 1•0.5 = 2
∑(a6,jpj) = 4•0.5 + 4•0.5 = 4
∑(a7,jpj) = 5•0.5 + 1•0.5 = 3
∑(a8,jpj) = 4•0.5 + 2•0.5 = 3
∑(a9,jpj) = 5•0.5 + 3•0.5 = 4
∑(a10,jpj) = 6•0.5 + 2•0.5 = 4
Ai П1 П2 ∑(aijpj)
A1 0.5 0.5 1
A2 1.5 1.5 3
A3 3.5 0.5 4
A4 1 1 2
A5 1.5 0.5 2
A6 2 2 4
A7 2.5 0.5 3
A8 2 1 3
A9 2.5 1.5 4
A10 3 1 4
pj 0.5 0.5 0

Выбираем из (1; 3; 4; 2; 2; 4; 3; 3; 4; 4) максимальный элемент max=4
Вывод: выбираем стратегию N=3.
Критерий Лапласа.
Если вероятности состояний природы правдоподобны, для их оценки используют принцип недостаточного основания Лапласа, согласно которого все состояния природы полагаются равновероятными, т.е.:
q1 = q2 = … = qn = 1/n.
qi = 1/2
Ai П1 П2 ∑(aij)
A1 0.5 0.5 1
A2 1.5 1.5 3
A3 3.5 0.5 4
A4 1 1 2
A5 1.5 0.5 2
A6 2 2 4
A7 2.5 0.5 3
A8 2 1 3
A9 2.5 1.5 4
A10 3 1 4
pj 0.5 0.5 0

Выбираем из (1; 3; 4; 2; 2; 4; 3; 3; 4; 4) максимальный элемент max=4
Вывод: выбираем стратегию N=3.
Таким образом, в результате решения статистической игры по различным критериям чаще других рекомендовалась стратегия A3.

Вариант 2

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

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 4, которая указывает на максимальную чистую стратегию A2.
Верхняя цена игры b = min(bj) = 6.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 4 ≤ y ≤ 6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
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-ю – доминируемой. Стратегия A2 доминирует над стратегией A4 (все элементы строки 2 больше или равны значениям 4-ой строки), следовательно исключаем 4-ую строку матрицы. Вероятность p4 = 0. 2 5 3 6 4 5 3 7 6 В платежной матрице отсутствуют доминирующие столбцы. Мы свели игру 4 x 3 к игре 3 x 3. Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш. Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I. 3. Находим решение игры в смешанных стратегиях. Математические модели пары двойственных задач линейного программирования можно записать так: найти минимум функции F(x) при ограничениях: 2x1+6x2+3x3 ≥ 1 5x1+4x2+7x3 ≥ 1 3x1+5x2+6x3 ≥ 1 F(x) = x1+x2+x3 → min найти максимум функции Ф(y) при ограничениях: 2y1+5y2+3y3 ≤ 1 6y1+4y2+5y3 ≤ 1 3y1+7y2+6y3 ≤ 1 Ф(y) = y1+y2+y3 → max Решаем эти системы симплексным методом. Решение симплекс-методом доступно в расширенном режиме. Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков: qi = g*yi; pi = g*xi. Цена игры: g = 1 : 1/5 = 5 p1 = 5 • 0 = 0 p2 = 5 • 2/15 = 2/3 p3 = 5 • 1/15 = 1/3 Оптимальная смешанная стратегия игрока I: P = (0; 2/3; 1/3) q1 = 5 • 1/10 = 1/2 q2 = 5 • 1/10 = 1/2 q3 = 5 • 0 = 0 Оптимальная смешанная стратегия игрока II: Q = (1/2; 1/2; 0) Цена игры: v=5 4. Проверим правильность решения игры с помощью критерия оптимальности стратегии. ∑aijqj ≤ v ∑aijpi ≥ v M(P1;Q) = (2•1/2) + (5•1/2) + (3•0) = 3.5 ≤ v M(P2;Q) = (6•1/2) + (4•1/2) + (5•0) = 5 = v M(P3;Q) = (3•1/2) + (7•1/2) + (6•0) = 5 = v M(P;Q1) = (2•0) + (6•2/3) + (3•1/3) = 5 = v M(P;Q2) = (5•0) + (4•2/3) + (7•1/3) = 5 = v M(P;Q3) = (3•0) + (5•2/3) + (6•1/3) = 5.33 ≥ v Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно. Поскольку из исходной матрицы были удалены строки, то найденные векторы вероятности можно записать в виде: P(0,2/3,1/3,0) Q(1/2,1/2,0) Критерий минимаксный Ai П1 П2 mix(aij) A1 1 1 1 A2 3 3 3 A3 7 1 1 A4 2 2 2 A5 3 1 1 A6 4 4 4 A7 5 1 1 A8 4 2 2 A9 5 3 3 A10 6 2 2 Суть критерия, что минимальных вариантов выбираем максимальны й. Ответ: N=6 Критерий максимакса. Критерий максимакса ориентирует статистику на самые благоприятные состояния природы, т.е. этот критерий выражает оптимистическую оценку ситуации. Ai П1 П2 max(aij) A1 1 1 1 A2 3 3 3 A3 7 1 7 A4 2 2 2 A5 3 1 3 A6 4 4 4 A7 5 1 5 A8 4 2 4 A9 5 3 5 A10 6 2 6 Выбираем из (1; 3; 7; 2; 3; 4; 5; 4; 5; 6) максимальный элемент max=7 Вывод: выбираем стратегию N=3. Критерий Ходжа-Лемана. Для каждой строки рассчитываем значение критерия по формуле: Wi = u∑aijpj + (1 - u)min(a)ij Рассчитываем Wi. W1 = 0.5•1 + (1-0.5)•1 = 1 W2 = 0.5•3 + (1-0.5)•3 = 3 W3 = 0.5•4 + (1-0.5)•1 = 2.5 W4 = 0.5•2 + (1-0.5)•2 = 2 W5 = 0.5•2 + (1-0.5)•1 = 1.5 W6 = 0.5•4 + (1-0.5)•4 = 4 W7 = 0.5•3 + (1-0.5)•1 = 2 W8 = 0.5•3 + (1-0.5)•2 = 2.5 W9 = 0.5•4 + (1-0.5)•3 = 3.5 W10 = 0.5•4 + (1-0.5)•2 = 3 Ai П1 П2 ∑(aijpj) min(aj) Wi A1 0.5 0.5 1 1 1 A2 1.5 1.5 3 3 3 A3 3.5 0.5 4 1 2.5 A4 1 1 2 2 2 A5 1.5 0.5 2 1 1.5 A6 2 2 4 4 4 A7 2.5 0.5 3 1 2 A8 2 1 3 2 2.5 A9 2.5 1.5 4 3 3.5 A10 3 1 4 2 3 pj 0.5 0.5 0 0 0 Выбираем из (1; 3; 2.5; 2; 1.5; 4; 2; 2.5; 3.5; 3) максимальный элемент max=4 Вывод: выбираем стратегию N=6. Таким образом, в результате решения статистической игры по различным критериям чаще других рекомендовалась стратегия A3.

Загрузка...