Чистые и смешанные стратегии в теории игр. Игра в чистых стратегиях

Выбор игроком того или иного действия называется ходом . Ходы бывают личные (игрок сознательно принимает то или иное решение) и случайные (исход игры не зависит от воли игрока). Набор правил, которые определяют, какой ход игроку необходимо сделать, называется стратегией . Стратегии бывают чистыми (неслучайные решения игроков) и смешанными (стратегию можно рассматривать как случайную величину).

Седловая точка

В теории игр С. т. (седловой элемент ) - это наибольший элемент столбца матрицы игры , который одновременно является наименьшим элементом соответствующей строки (в игре двух лиц с нулевой суммой ). В этой точке, следовательно, максимин одного игрока равен минимаксу другого; С. т. есть точка равновесия .

Теорема о минимаксе

Стратегия, соответствующая минимаксу, называется минимаксной стратегией .

Принцип, диктующий игрокам выбор наиболее "осторожных" максиминной и минимаксной стратегий, называется принципом минимакса . Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.

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

Функция потерь

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

Оптимальная Смешанная стратегия игрока - это полный набор примене­ния его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями.

Смешанная стратегия игрока - это полный набор примене­ния его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями.

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

2. Цена игры единственна.

Док-во: допустим, что есть 2 цены игры v и , которые достигаются на паре и соответственно, тогда

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

Док-во:
, где

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

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

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

Все задачи решаем с помощью калькулятора Матричная игра .

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

p 1 = 1
p 2 = 0
Цена игры, y = 1
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений
q 1 = 1
q 1 +q 2 = 1
Решая эту систему, находим:
q 1 = 1.
Ответ:
Цена игры: y = 1, векторы стратегии игроков:
Q(1, 0), P(1, 0)

∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (1 1) + (2 0) = 1 = v
M(P 2 ;Q) = (-2 1) + (-2 0) = -2 ≤ v
M(P;Q 1) = (1 1) + (-2 0) = 1 = v
M(P;Q 2) = (2 1) + (-2 0) = 2 ≥ v

Поскольку из исходной матрицы были удалены строки и столбцы, то найденные векторы вероятности можно записать в виде:
P(1,0,0,0)
Q(0,1,0,0)

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

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

Максиминной оптимальной стратегии игрока A соответствует точка N, для которой можно записать следующую систему уравнений:
p 1 = 0
p 2 = 1
Цена игры, y = -2
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B 1 ,B 3 ,B 4 , которая дает явно больший проигрыш игроку B, и, следовательно, q 1 = 0,q 3 = 0,q 4 = 0.
-2q 2 = -2
q 2 = 1
Решая эту систему, находим:
q 2 = 1.
Ответ:
Цена игры: y = -2, векторы стратегии игроков:
Q(0, 1, 0, 0), P(0, 1)
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (-6 0) + (-6 1) + (2 0) + (4 0) = -6 ≤ v
M(P 2 ;Q) = (2 0) + (-2 1) + (7 0) + (-1 0) = -2 = v
M(P;Q 1) = (-6 0) + (2 1) = 2 ≥ v
M(P;Q 2) = (-6 0) + (-2 1) = -2 = v
M(P;Q 3) = (2 0) + (7 1) = 7 ≥ v
M(P;Q 4) = (4 0) + (-1 1) = -1 ≥ v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.

Задача 4
Дайте развернутый ответ на вопрос

Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем сумма вероятностей равна 1: Смешанные стратегии игрока А записываются в виде матрицы или в виде строки SA = (p1, p2, ..., pi, ..., pm) Аналогично смешанные стратегии игрока В обозначаются: , или, SB = (q1, q2, ..., qi, ..., qn), где сумма вероятностей появления стратегий равна 1: Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A , S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: ? ? v ? ? (3.5) где? и? - нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр - теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*A = (p*1, p*2, ..., p*i, ..., p*m) и S*B = (q*1, q*2, ..., q*i, ..., q*n) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной. Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий. Эта теорема имеет большое практическое значение - она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки. Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение - это пара чистых стратегий, соответствующих этой точке. Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*A = (p*1, p*2) и S*B = (q*1, q*2). Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S"A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) - случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника. Пусть игра задана платежной матрицей Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию, а игрок В - чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v: a11 p*1+ a21 p*2= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B2, т.е. a12 p*1+ a22 p*2= v. Учитывая, что p*1+ p*2= 1, получаем систему уравнений для определения оптимальной стратегии S"A и цены игры v: (3.6) Решая эту систему, получим оптимальную стратегию (3.7) и цену игры (3.8) Применяя теорему об активных стратегиях при отыскании SВ*- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е. (3.9) Тогда оптимальная стратегия определяется формулами: (3.10)

Если игра не имеет седловой точки, то возникают затруднения в определении цены игры и оптимальных стратегий игроков. Рассмотрим, например, игру:

В этой игре и . Следовательно, первый игрок может гарантировать себе выигрыш, равный 4, а второй может ограничить свой проигрыш 5. Область между и является как бы ничейной и каждый игрок может попытаться улучшить свой результат за счет этой области. Каковы же должны быть в этом случае оптимальные стратегии игроков?

Если каждый из игроков применяет отмеченную звездочкой стратегию (и ), то выигрыш первого игрока и проигрыш второго будут равны 5. Это невыгодно второму игроку, так как первый выигрывает больше, чем оно может себе гарантировать. Однако если второй игрок каким-либо образом раскроет замысел первого о намерении использовать стратегию , то он может применить стратегию и уменьшить выигрыш первого до 4. Правда, если первый игрок раскроет замысел второго применить стратегию , то, используя стратегию , он увеличит свой выигрыш до 6. Таким образом, возникает ситуация, когда каждый игрок должен хранить в секрете ту стратегию, которую он собирается использовать. Однако, как это сделать? Ведь если партия играется многократно и второй игрок применяет все время стратегию , то первый игрок скоро разгадает замысел второго и, применив стратегию , будет иметь добавочный выигрыш. Очевидно, что второй игрок должен менять стратегию в каждой новой партии, но делать это он должен так, чтобы первый не догадался, какую стратегию применит он в каждом случае.

Для механизма случайного выбора выигрыши и проигрыши игроков будут случайными величинами. Результат игры в этом случае можно оценить средней величиной проигрыша второго игрока. Вернемся к примеру. Так, если второй игрок использует стратегию и случайным образом с вероятностями 0.5; 0.5, то при стратегии первого игрока среднее значение его проигрыша будет:

а при стратегии первого игрока

Следовательно, второй игрок может ограничить свой средний проигрыш значением 4,5 независимо от стратегии, применяемой первым игроком.

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

Дадим более строгое определение чистых и смешанных стратегий.

Пусть имеется игра без седловой точки:

Обозначим частоту использования чистой стратегии первого игрока через , (вероятность использования i-ой стратегии). Аналогично обозначим частоту использования чистой стратегии второго игрока через , (вероятность использования j-ой стратегии). Для игры с седловой точкой существует решение в чистых стратегиях . Для игры без седловой точки существует решение в смешанных стратегиях, то есть когда выбор стратегии осуществляется на основании вероятностей. Тогда

Множество чистых стратегий 1-го игрока;

Множество смешанных стратегий 1-го игрока;

Множество чистых стратегий 2-го игрока;

Множество смешанных стратегий 2-го игрока.

Рассмотрим пример: пусть имеется игра

Второй игрок выбирает вероятность . Оценим средний проигрыш второго игрока при применении им стратегий и соответственно.

Если в игре каждый из противников применяет одну и ту же стратегию, то про эту игру говорят, что она происходит в чистых стратегиях, а стратегии игроков А и В будут называться чистыми стратегиями .В антагонистической игре пара стратегий называется равновесной (устойчивой), если ни одному из игроков невыгодно отступать от своих стратегий.Применять чистые стратегии имеет смысл, если игроки знают о действиях противника. Если этого нет, то идея равновесия нарушается и игра может вестись как получится.Стратегии А1 В1 – устойчивы по отношению к информации о поведении противника.Признаком устойчивости пары стратегий это равенство верхней и нижней цены игры. И случай А1 В1 будет

ν = α = β. ν > 0, то игрок А будет в выигрыше, если ν < 0, то в выигрыше игрок В. Если ν = 0, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.

Теорема: каждая игра с полной информацией имеет седловую точку и следовательно решает в чистых стратегиях, т.е. имеется пара устойчивых стратегий, дающих устойчивый выигрыш равный ν.Если матрица не имеет седловую точку, то цена игры лежит α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии.Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.

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

S A = || p 1 , p 2 …. p m || ,S B = || q1, q2 …. q m || , A: ∑ pi = 1 ,B: ∑ qi = 1

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

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

Предположим что и игрок А и игрок В придерживаются смешанной стратегии. Необходимо определить А: ∑∑ a ij p i q j

Для игрока В ожидаемый проигрыш равен ожидаемому выигрышу игрока А. Выигрыш первого игрока и средний проигрыш второго игрока равны друг другу.

18.Методы решения конечной игры двух лиц порядка m*n.

Предположим, что все элементы платёжной матрицы 0≤aij. Тогда α≤ν≤β. Согласно основной теореме матричных игр, любая матричная игра имеет 2 оптимальные смешанные стратегии.

S A = (p 1 , p 2 , … , p n)

S B = (p 1 , p 2 , … , p n)

Решаем игру для игрока А, при этом предполагая что игрок В использует только чистые стратегии. Тогда

a 11 p 1 + a 21 p 2 + … + a m1 p m ≥ ν: B 1

a 12 p 1 + a 22 p 2 + … + a m2 p m ≥ ν: B 2 (1)

a 1n p 1 + a 2n p 2 + … + a mn p m ≥ ν: B n

X 1 = P 1 /ν , X 2 = P 2 /ν … X m = P m /ν

a 11 X 1 … + a m1 p m ≥ 1

a 1n X 1 … + a m1 p m ≥ 1 (2)

p 1 +p 2 +…+p m =1

X 1 +X 2 +…+X m = 1/ν (3)

L(x) = X 1 +X 2 +…+X m -> min (4)

Определим задачу линейного программирования.

ν = 1/(X 1 0 +X 2 0 …X m 0) (5)

P1 = X 1 0 *ν опт

p2 = X 2 0 *ν опт (6)

min L(x) = ∑x i

∑a ij: 1≤x i (7) (прямая задача)

0≤x i (i=1,2..)

a 11 q 1 + a 21 q 2 + … + a m1 q m < ν: A 1

a 21 q 1 + a 22 q 2 + … + a m2 q m < ν: A 2 (8)

a m1 q 1 + a m2 q 2 + … + a mn q m < ν: A m

Y 1 = q 1 /ν , Y 2 = q 2 /ν … Y m = q m /ν

q 1 +q 2 +…+q n =1

y 1 +y 2 +…+y n =1/ν

L(y)=∑y j -> max

∑a ij , y i ≤1 (i=1,2…) (9) (двойственная задача)

y 1 0 +y 2 0 …y m 0 = 1/ν опт

ν опт = 1/∑y m 0

Q1 = y 1 0 *ν опт

q2 = y 2 0 *ν опт

ν=1/∑x i = 1/∑y i = 1/min L(x) = 1/ max L(y) (11)

1) α = 1, β = 3

2) Нет упрощений.

L(x)=x 1 +x 2 +x 3 => min

x 1 +3x 2 +x 3 >= 1

2x 1 +x 2 +x 3 >=1

3x 1 +x 2 +x 3 >=1

x 1 =2/9, x 2 =2/9, x 3 =1/9

ν=1/(2/9+2/9+1/9)=9/5

p 1 =x 1 *ν=2/5

S A =(2/5, 2/5, 1/5)

двойственная задача

L(y) = y 1 +y 2 +y 3 => max

y 1 +2y 2 +3y 3 ≤ 1 y 1 =2/9

3y 1 +y 2 +y 3 ≤1 => y 2 =2/9 max L(y) = 5/9

y 1 +3y 2 +y 3 ≤1 y 3 =1/9

ν=1/(2/9+2/9+1/9)=9/5

q 1 =y 2 *ν=(2/9)*(9/5)=2/5

q 2 =(2/9)*(9/5)=2/5

q 3 =(1/9)*(9/5)=1/5

S B =(2/5, 2/5, 1/5)

Задача mxn сводится к задаче линейного программирования.

Приближённый метод решения матричных игр mxn (Браун-Робинсон).

Игрок А и игрок В поочерёдно применяют чистые стратегии. Каждый игрок пытается увеличить свой выигрыш, используя максиминые или минимаксные подходы. Минимизируется (максимизируется) не средний выигрыш, а накопленный. В теории показывается, что такой метод неизбежно даст нам оптимальный выигрыш и оптимальные смешанные стратегии.