Решение игр размерности 2´2 и 2´n в смешанных стратегиях

5.1. Игра размерности 2´2.Рассмотрим произвольную матричную игру со следующей платёжной матрицей размерности 2´2 общего вида:

Q = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . (18)

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

Случай 1. У игры есть решение в чистых стратегиях. Тогда в силу утверждения 7 это же самое решение (представленное в виде пары смешанных стратегий, как в примере 6) является решением игры в смешанных стратегиях. На этом поиск решений в смешанных стратегиях за-кончен.

Прежде чем перейти к случаю 2 - отсутствию решения в чистых стратегиях - сформули-руем некоторые простые, но нужные для дальнейшего утверждения.

Утверждение 8.Пусть в матрице (18) есть доминируемые или дублирующие строки или столбцы. Тогда в матричной игре с этой платёжной матрицей есть решение в чистых стратегиях ■

Заметим, что условие утверждения 8 является достаточным, но не необходимым. В игре с матрицей Q = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru есть решение в чистых стратегиях, а доминируемых или дублирующих строк и столбцов нет.

Утверждение 9.Пусть в матрице (18) совпадают элементы одного столбца или одной строки. Тогда в матричной игре с этой платёжной матрицей есть решение в чистых стратегиях ■

Напомним определение функции sgn(x):

sgn(x) = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

Утверждение 10.Пусть в матрице (18)

sgn(q11-q21) = -sgn(q22-q12) (19a)

или

sgn(q11-q12) = -sgn(q22-q21). (19b)

Тогда в матричной игре с этой платёжной матрицей есть решение в чистых стратегиях ■

Случай 2. У игры нет решения в чистых стратегиях. Рассмотрим выражение (9) для выиг-рыша игрока А в игре размерности 2´2:

g(x,y) = x1·y1·q11 + x1·y2·q12 + x2·y1·q21 + x2·y2·q22. (20)

Учитывая, что x1 + x2 = 1, y1 + y2 = 1, положим x = x1, y = y1 и отождествим стратегии игроков с однозначно определяющими их вероятностями x и y. Представим (20) (после простых преобра-зований) в следующем виде:

g(x, y) = mx + n, (21a)

где

m = (q11–q12–q21+q22)·y+(q12 – q22), (22a)

n = (q21–q22)·y+q22. (23a)

Выражение (20) является, в соответствии с определениями, проигрышем игрока В в той же са-мой игре. Представим (20) в виде, аналогичном (21a):

g(x, y) = sy+ t, (21b)

где

s = (q11–q12–q21+q22)·x+(q21 – q22), (22b)

t= (q12–q22)·x+q22. (23b)

Положим

q1 = q11 – q12 – q21 + q22, (24)

q2 = q22–q12, (25)

q3 = q22–q21. (26)

Имеетместо

Утверждение 11. Пусть в игре с платёжной матрицей (18) нет решений в чистых страте-гиях. Тогда

1) q1 ≠ 0, q2 ≠ 0, q3 ≠ 0; (27)

2) sgn(q2) = sgn(q3); (28)

3) 0 <q2¤q1< 1, 0 <q3¤q1< 1 ■ (29)

Все три части утверждения 11 являются следствиями утверждений 8 – 10. В частности, вторые неравенства в формулах (29) следуют из того, что q1 = q11 – q21+ q2 = q11 – q12 + q3 и утверждения 10.

Перейдём к явному построению решения игры в смешанных стратегиях. Начнём с игрока А. Для любой стратегии yигрока В положим

jА(y) = {x| ( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ) (gA(x', y) ≤ gA(x, y))}. (30a)

Другими сдовами, jA(y) – это множество всех стратегий x игрока А, которые максимизирует его выигрыш gA(x, y) при данном y.

Положим

ΦA = {(x, y) | yÎ[0, 1], xÎjA(y)}. (31a)

Множество ΦA назовём графиком игрока А (см. общее определение графика в гл. 1.3)

Поскольку при любом фиксированном yфункция (21а) линейна по x, и при этом 0 ≤ x ≤ 1, то максимум достигается при m≠ 0 на концах отрезка [0, 1] (т.е. при одной из двух чистых страте-гий), а при m = 0 – при всех стратегиях, поскольку в этом случае g(x, y) просто не зависит от x. Представим эти рассуждения геометрически, нарисовав график ΦA игрока А. Из (22а) и (23а) следует, что

g(x, 0) = –x·q2 + q22.

Поэтому

j(0) = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . (32a)

Далее, представим (22а) с учётом обозначений (24) – (26) как

m = q1·y– q2.

Будем увеличивать y от 0 до 1. В силу 3-ей части утверждения 11 q1 иq2 имеют одинаковые знаки. Поэтому при y= y* = q2¤q1 число m = 0, g(x, y*) от x не зависит и, следовательно, мно-жеством jА(y*) является отрезок [0, 1]. Далее, при y>y* число mменяет знак на противопо-ложный. Поэтому, если j(0) = {0}, то j(1) = {1}; если же j(0) = {1}, то j(1) = {0}. Оба случая (при Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru и при Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ) представлены на рис.1.

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

Рис.1

Теперь перейдём к игроку В. Для любой стратегии x игрока А положим

yB(x) = {y| ( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ) (gB(x, y) ≤ gB(x, y Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ))}. (30b)

Другими сдовами, yB(x) – это множество всех стратегий y игрока B, которые минимизируют его выигрыш gB(x, y) при данном x.

Определим график игрока В формулой, аналогичной формуле (31а):

YВ = {(x, y) | xÎ[0, 1], yÎyB(x)}. (31b)

Далее практически повторим все рассуждения относительно графика ΦA применительно к гра-фику YВ (учитывая минимизацию, а не максимизацию). В частности, получим

y(0) = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru (32b)

(различие (32a) и (32b) определяется минимизацией вместо максимизации).

Как и выше, положим x* = q3¤q1. При x = x* коэффициент sпри y в (21b) обращается в 0, так что минимум достигается при любом y от 0 до 1; в этой точке знак sменяется и, соответствен-но, y(x) меняет значение с {0} на {1} или наоборот. Оба случая представлены на рис.2 в тех же координатах, что и на рис.1.

В силу формулы (28), q2< 0 тогда и только тогда, когда q3< 0. Поэтому при изображении обоих графиков в одних и тех же координатах имеется два случая: q2< 0, q3< 0 и q2> 0, q3> 0. Других вариантов не может быть. Эти графики показаны на рис. 3. Из формулы (29) следует, что q1 имеет тот же знак, что q2 иq3. Поэтому левой и правой части рис.3 соответствуют q1< 0 и q1> 0.

Суть дела состоит в том, что найденные смешанные стратегии x* и y* образуют решение исходной матричной игры с платёжной матрицей (18), не имеющей решений в чистых стратеги-ях. Действительно, по построению jА(y) (см. формулу (30a)) для любого yи для любого x' Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru jА(y) выполняется условие

( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru x)g(x, y) ≤ g(x', y). (33a)

В частности, (33a) верно при y = y* и x' = x*, так как при y = y* x' можно выбрать произвольно. Поэтому из (33a) следует, что для любого x

g(x, y*) ≤ g(x*, y*). (34a)

Аналогично, по построению yB(x) для любого xи для любого y' = y(x) выполняется условие

( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru )g(x, y') ≤ g(x, y). (33b)

В частности, (33b) верно при y' = y* и x = x*, так как при x = x* y' можно выбрать произвольно.

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

Рис.2

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

Рис.3

Поэтому из (33b) следует, что для любого y

g(x*, y*) ≤ g(x*, y). (34b)

Неравенства (34a) и (34b) вместе совпадают с двойным неравенством (12), т.е. пара стратегий áx*, y*ñ по определению является решением игры в смешанных стратегиях.

Если «принять на веру» утверждения 8 - 11 (доказательства которых достаточно просты), то вместе с предыдущими рассуждениями они доказывают существование решения в смешан-ных стратегиях любой игры размерности 2´2 для произвольной платёжной матрицы (18). Ко-нечно, этот факт сам по себе непосредственно следует из общего утверждения 6. Однако оно является типичной «теоремой существования», не объясняющей, как находить само решение.

Для игр размерности 2´2 ситуация другая. Числа x* и y* определены в явном виде:

x* = q3¤q1, y* = q2¤q1,

где числа q1, q2и q3выражаются через элементы исходной платёжной матрицы (18) по форму-лам (24) - (26). Переходя обратно от задания смешанной стратегии одним числом (вероятнос-

тью выбора 1-ой стратегии) к её заданию парами чисел (см. текст послеформулы (20)), оконча-

тельно получаем

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , x* = ( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ); (35a)

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , y* = ( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ). (35b)

При взгляде на формулы (35) возникает вопрос – что делать, если входящий в них делитель (24) окажется равным 0? Ведь на 0 делить нельзя! При этом число q1, определяемое формулой (24), действительно может быть равным 0 – например, в платёжной матрице Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . Однако для платёжных матриц без седловой точки (а только такие матрицы здесь и рассматри-ваются) выражение (24) не равно 0 (см. 1-ую часть утверждения 11). Так что на 0 делить не придётся.

Таким образом, полностью решена задача нахождения решения матричной игры размер-ности 2´2 для произвольной платёжной матрицы (18). Если у игры есть решение в чистых стра-тегиях, то оно и является искомым решением. В том и только том случае, если такого решения нет, можно найти решение в смешанных стратегиях по формулам (35).

Пример 7.Рассмотрим матричную игру двух лиц со следующей платёжной матрицей: Q= Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . Найдём её решение. Поскольку у данной игры нет решения в чистых стратегиях, то воспользуемся формулами (35), положив q11 = 6, q12 = 2, q21 = 5, q22 = 8. Получим

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ; Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ;

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1 - Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ; Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1 - Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ; x* = ( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ); y* = ( Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ) ■

Задание 3.Найти решения в следующих матричных играх (см. пример 7)

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

5.2. Игра размерности 2´n.Рассмотрим произвольную матричную игру со следующей платёжной матрицей размерности 2´n общего вида:

Q = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . (36)

Оказывается, что для игр с платёжной матрицей вида (36) решение может быть найдено графо-аналитическим методом. Для простоты решение излагается для n = 4 в следующих двух примерах.

Пример 8. Найдём решение и цену игры с платёжной матрицей Q = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . Преж-де всего проверим наличие (или отсутствие) решения в чистых стратегиях. В данном случае

maximinjqij=max{2, 4} = 4; minjmaxiqij = min{4, 8, 6, 6} = 4.

Так как maximinjqij= minjmaxiqij =q21, то пара чистых стратегий á2, 1ñ является решением дан-ной игры. Как и в примере 6, представим эти чистые стратегии как смешанные:x = (0, 1); y = (1, 0, 0, 0). Ценой игры является общее значение максимина и минимакса, равное q21 = 4 ■

Пример 9. Найти решение и цену игры с платёжной матрицей Q = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . В этом случаета же самаяпроверка даёт

maximinjqij= max{3, 4} = 4; minjmaxiqij = min{6, 8, 6, 6} = 6.

Поскольку в данном случае maximinjqij<minjmaxiqij, то решений в чистых стратегиях нет.

Поэтому можно и нужно искать решение игры в смешанных стратегиях описанным ниже гра-фо-аналитическим методом.

Игрок A имеет только 2 чистых стратегии. Его задача состоит в максимизации своего выигрыша в зависимости от своей смешанной стратегии (x1, x2)

v(x1, x2) = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru (q1j x1 + q2j x2), (37)

где минимум берётся по 4-ём чистым стратегиям игрока B.

Так как x2 = 1 -x1, то, обозначая x1 через x, из (40) получаем выражение

v(x) = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru {(q1j-q2j) x + q2j}. (38)

Таким образом, v(x) является минимумом четырёх линейных функций одной переменной x; можно начертить графики этих функций и затем максимизировать их минимум v(x) графичес-ким методом.

Нетрудно построить графики функций (q1j-q2j) x + q2j, если заметить, что они должны проходить через точки (0, q2j) и (1, q1j). Эти графики изображены на рис.4. В данном случае имеем четыре прямых линии, нижняя огибающая которых v(x) выделена жирным. Высшая точ-ка функции v(x) находится на пересечении прямых y = 2x + 4 и y = -3x + 6, соответствующих 3-му и 4-му столбцам матрицы Q (напомним, что j-ая прямая по построению проходит через точ-ки (0, q2j) и (1, q1j)). Поскольку в данном случае ломаная v(x) состоит только из двух звеньев, со-единённых в точке D, то указанные два столбца находятся сразу. Если же точек, где соединяют-ся звенья ломаной, несколько, то надо взять ту из них, у которой ордината максимальна. Имен-но нахождение такой точки и делается графически. Большой точности в построениях не требу-ется, поскольку всё, что нужно – это найти те два столбца, которые соответствуют двум лини-ям, определяющим эту точку.

Далее для вычисления оптимальных смешанных стратегии надо рассмотреть 2×2 матрицу P, образованную найденными выше двумя столбцами. В данном случае это 3-ий и 4-ый столб-цы, а сама матрица имеет вид:

P = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

(см. исходную матрицу Q). Для этой матрицы найдём решение в смешанных стратегиях спосо-бом, подробно описанном в примере 7. Имеем в данном случае q11= 6, q12= 3,q21= 4, q22= 6. Поэтому в силу формул (35)

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

Рис.4

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru =0,4; Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru =0,6;

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1 - 0,4 =0,6; Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1 -0,6 = 0,4.

Теперь вспоминаем, что в исходной матрице размера 2×4 у игрока A есть две чистых стратегии: выбор 1-й или 2-й строки. В данном случае имеем

x* = (0,4; 0,6).

У игрока B есть четыре чистых стратегии, соответствующие выбору одного из 4-ёх столбцов за-данной матрицы. Однако активными (т.е. отличными от 0) являются только те две стратегии, которые соответствуют выбранным (с помощью рисунка) столбцам. В нашем случае это столб-цы 3 и 4. Вероятность выбора 3-его и 4-го столбца была найдена выше: 0,6 и 0,4. Сама опти-мальная стратегия игрока B имеет вид

y* = (0; 0; 0,6; 0,4).

Цена игры V с исходной матрицей Q совпадает с ценой игры с матрицей P. В силу 3-ьей части утверждения 5 и формулы (9) получаем

V = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ·6 + Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ·3 + Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ·4 + Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru ·6 = 0,4·0,6·6 + 0,4·0,4·3 + 0,6·0,6·4 + 0,6·0,4·6 = 1,44 + 0,48 + 1,44 + 1,44 = 4,8 ■

Задание 4.Найти решение и цену в игре со следующей платёжной матрицей (см. примеры 8 и 9).

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 01 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 02 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 03 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 04 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 05
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 06 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 07 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 08 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 09 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 10
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 11 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 12 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 13 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 14 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 15
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 16 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 17 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 18 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 19 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 20
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 21 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 22 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 23 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 24 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 25
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 26 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 27 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 28 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 29 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 30
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 31 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 32 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 33 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 34 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 35
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 36 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 37 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 38 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 39 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 40
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 41 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 42 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 43 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 44 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 45
Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 46 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 47 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 48 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 49 Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru 50

Во многих случаях удаётся упростить описанный выше поиск решения матричных игр с платёжной матрицей размерности 2´n за счёт предварительного упрощения платёжной матри-цы способами, описанными в разделе 3. Проиллюстрируем это в следующем примере.

Пример 10. Рассмотрим матричную игру двух лиц со следующей платёжной матрицей размера 2´6: Q = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . В данной матрице 1-ый, 3-ий и 4-ый столбцы домини-руемы 2-ым, 5-ым и снова 2-ым столбцами соответственно. После их удаления остаётся матри-ца P = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru , которая больше не упрощается. Номера её столбцов в исходной матрице та-ковы: (2, 5, 6). Далее применим описанный в примере 9 графо-аналитический метод поиска решения к матрице P. Входящие в формулу (38) три линейные функции должны проходить через точки (0, q2j) и (1, q1j) (j = 1, 2, 3). С учётом матрицы Pэти точки таковы:

(0, 2) и (1, 5); (0, 4) и (1, 1); (0, 3) и (1, 3).

Изобразим соответствующие отрезки на рис.5. Функция v(x), определённая формулой (38), пока-зана жирной линией. Эта линия состоит из двух отрезков, пересекающихся в точке D. Сами от-резки соответствуют 1-му и 2-му столбцам матрицы P. Матрица R, образованная этими столбца-ми, такова:R = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru . Аналогично тому, как это делалось в примере 9, находим

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru =0,33; Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru =0,5;

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1 - 0,33 =0,67; Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1- Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru = 1 -0,5 = 0,5.

Поскольку рассмотренные два столбца были 2-ым и 5-ым в исходной матрице Q, получаем

x* = (0,33; 0,67) и y* = (0; 0,5; 0; 0; 0,5; 0) ■

Решение игр размерности 2´2 и 2´n в смешанных стратегиях - student2.ru

Рис.5

Задание 5.Упростить платёжную матрицу и найти решение и цену игры в играх с матри-цами из задания 4 (см. пример 10) ■

Предметный указатель

график

игрока А

игрока В

игр матричных, смешанное расширение

игра

матричная

размерности

2´2

2´n

с нулевой суммой

платёжная матрица

решение игры

в смешанных стратегиях

в чистых стратегиях

решения игры, нахождение

стратегий, удаление

стратегия

доминируемая

дублирующая

смешанная

оптимальная

игрока A

игрока В

оптимальная

игрока A

игрока В

цена игры

верхняя

нижняя

в смешанных стратегиях

Наши рекомендации