Если игра не имеет седловой точки, то возникают затруднения в определении цены игры и оптимальных стратегий игроков. Рассмотрим, например, игру:
В этой игре и . Следовательно, первый игрок может гарантировать себе выигрыш, равный 4, а второй может ограничить свой проигрыш 5. Область между и является как бы ничейной и каждый игрок может попытаться улучшить свой результат за счет этой области. Каковы же должны быть в этом случае оптимальные стратегии игроков?
Если каждый из игроков применяет отмеченную звездочкой стратегию (и ), то выигрыш первого игрока и проигрыш второго будут равны 5. Это невыгодно второму игроку, так как первый выигрывает больше, чем оно может себе гарантировать. Однако если второй игрок каким-либо образом раскроет замысел первого о намерении использовать стратегию , то он может применить стратегию и уменьшить выигрыш первого до 4. Правда, если первый игрок раскроет замысел второго применить стратегию , то, используя стратегию , он увеличит свой выигрыш до 6. Таким образом, возникает ситуация, когда каждый игрок должен хранить в секрете ту стратегию, которую он собирается использовать. Однако, как это сделать? Ведь если партия играется многократно и второй игрок применяет все время стратегию , то первый игрок скоро разгадает замысел второго и, применив стратегию , будет иметь добавочный выигрыш. Очевидно, что второй игрок должен менять стратегию в каждой новой партии, но делать это он должен так, чтобы первый не догадался, какую стратегию применит он в каждом случае.
Для механизма случайного выбора выигрыши и проигрыши игроков будут случайными величинами. Результат игры в этом случае можно оценить средней величиной проигрыша второго игрока. Вернемся к примеру. Так, если второй игрок использует стратегию и случайным образом с вероятностями 0.5; 0.5, то при стратегии первого игрока среднее значение его проигрыша будет:
а при стратегии первого игрока
Следовательно, второй игрок может ограничить свой средний проигрыш значением 4,5 независимо от стратегии, применяемой первым игроком.
Таким образом, в ряде случаев оказывается целесообразным не намечать заранее стратегию, а выбирать ту или иную случайным образом, используя какой-либо механизм случайного выбора. Стратегию, основанную на случайном выборе, называют смешанной стратегией , в отличие от намеченных стратегий, которые называются чистыми стратегиями .
Дадим более строгое определение чистых и смешанных стратегий.
Пусть имеется игра без седловой точки:
Обозначим частоту использования чистой стратегии первого игрока через , (вероятность использования i-ой стратегии). Аналогично обозначим частоту использования чистой стратегии второго игрока через , (вероятность использования j-ой стратегии). Для игры с седловой точкой существует решение в чистых стратегиях . Для игры без седловой точки существует решение в смешанных стратегиях, то есть когда выбор стратегии осуществляется на основании вероятностей. Тогда
Множество чистых стратегий 1-го игрока;
Множество смешанных стратегий 1-го игрока;
Множество чистых стратегий 2-го игрока;
Множество смешанных стратегий 2-го игрока.
Рассмотрим пример: пусть имеется игра
Второй игрок выбирает вероятность 
. Оценим средний проигрыш второго игрока при применении им стратегий и соответственно.
теория игра стратегия смешанная
Смешанные стратегии
Если в матричной игре отсутствует седловая точка в чистых стратегиях, то находят верхнюю и нижнюю цены игры. Они показывают, что игрок 1 не получит выигрыша, превосходящего верхнюю цену игры, и что игроку 1 гарантирован выигрыш, не меньший нижней цены игры.
Смешанная стратегия игрока - это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Подведем итоги сказанного и перечислим условия применения смешанных стратегий:
- * игра без седловой точки;
- * игроки используют случайную смесь чистых стратегий с заданными вероятностями;
- * игра многократно повторяется в сходных условиях;
- * при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;
- * допускается осреднение результатов игр.
Применяются следующие обозначения смешанных стратегий.
Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий А 1 , А 2 , ..., А т с соответствующими вероятностями р 1 , р 2, ..., р т.
Для игрока 2
q j -- вероятность применения чистой стратегии B j .
В случае когда р i = 1, для игрока 1 имеем чистую стратегию
Чистые стратегии игрока являются единственно возможными несовместными событиями. В матричной игре, зная матрицу А (она относится и к игроку 1, и к игроку 2), можно определить при заданных векторах и средний выигрыш (математическое ожидание эффекта) игрока 1:
где и - векторы;
p i и q i - компоненты векторов.
Путем применения своих смешанных стратегий игрок 1 стремится максимально увеличить свой средний выигрыш, а игрок 2 - довести этот эффект до минимально возможного значения. Игрок 1 стремится достигнуть
Игрок 2 добивается того, чтобы выполнялось условие
Обозначим и векторы, соответствующие оптимальным смешанным стратегиям игроков 1 и 2, т.е. такие векторы и, при которых будет выполнено равенство
Цена игры - средний выигрыш игрока 1 при использовании обоими игроками смешанных стратегий. Следовательно, решением матричной игры является:
- - оптимальная смешанная стратегия игрока 1;
- - оптимальная смешанная стратегия игрока 2;
Цена игры.
Смешанные стратегии будут оптимальными (и), если образуют седловую точку для функции т.е.
Существует основная теорема математических игр.
Для матричной игры с любой матрицей А величины
существуют и равны между собой: = = .
Следует отметить, что при выборе оптимальных стратегий игроку 1 всегда будет гарантирован средний выигрыш, не меньший чем цена игры, при любой фиксированной стратегии игрока 2 (и, наоборот, для игрока 2). Активными стратегиями игроков 1 и 2 называют стратегии, входящие в состав оптимальных смешанных стратегий соответствующих игроков с вероятностями, отличными от нуля. Значит, в состав оптимальных смешанных стратегий игроков могут входить не все априори заданные их стратегии.
Решить игру - означает найти цену игры и оптимальные стратегии. Рассмотрение методов нахождения оптимальных смешанных стратегий для матричных игр начнем с простейшей игры, описываемой матрицей 22. Игры с седловой точкой специально рассматриваться не будут. Если получена седловая точка, то это означает, что имеются невыгодные стратегии, от которых следует отказываться. При отсутствии седловой точки можно получить две оптимальные смешанные стратегии. Как уже отмечалось, эти смешанные стратегии записываются так:
Значит, имеется платежная матрица
a 11 p 1 + a 21 p 2 = ; (1.16)
a 12 p 1 + a 22 p 2 = ; (1.17)
p 1 + p 2 = 1. (1.18)
a 11 p 1 + a 21 (1 - p 1) = a 12 p 1 + a 22 (1 - p 1); (1.19)
a 11 p 1 + a 21 - a 21 p 1 = a 12 p 1 + a 22 - a 22 p 1 , (1.20)
откуда получаем оптимальные значенияи:
Зная и, находим:
Вычислив, находим и:
a 11 q 1 + a 12 q 2 = ; q 1 + q 2 = 1; (1.24)
a 11 q 1 + a 12 (1 - q 1) = . (1.25)
при a 11 a 12 . (1.26)
Задача решена, так как найдены векторы и цена игры. Имея матрицу платежей А, можно решить задачу графически. При этом методе алгоритм решения весьма прост (рис. 2.1).
- 1. По оси абсцисс откладывается отрезок единичной длины.
- 2. По оси ординат откладываются выигрыши при стратегии А 1 .
- 3. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии a 2 .
- 4. Концы отрезков обозначаются для a 11 -b 11 , a 12 -b 21 , a 22 -b 22 , a 21 -b 12 и проводятся две прямые линии b 11 b 12 и b 21 b 22 .
- 5. Определяется ордината точки пересечения с. Она равна. Абсцисса точки с равна р 2 (р 1 = 1 - р 2).
Рис. 1.1.
Данный метод имеет достаточно широкую область приложения. Это основано на общем свойстве игр тп, состоящем в том, что в любой игре тп каждый игрок имеет оптимальную смешанную стратегию, в которой число чистых стратегий не больше, чем min(m, n). Из этого свойства можно получить известное следствие: в любой игре 2п и т2 каждая оптимальная стратегия и содержит не более двух активных стратегий. Значит, любая игра 2п и т2 может быть сведена к игре 22. Следовательно, игры 2п и т2 можно решить графически. Если матрица конечной игры имеет размерность тп, где т > 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)
| B 1 | B 2 | B 3 | α i | |
| A 1 | ||||
| A 2 | ||||
| A 3 | ||||
| β j |
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 (Браун-Робинсон).
Игрок А и игрок В поочерёдно применяют чистые стратегии. Каждый игрок пытается увеличить свой выигрыш, используя максиминые или минимаксные подходы. Минимизируется (максимизируется) не средний выигрыш, а накопленный. В теории показывается, что такой метод неизбежно даст нам оптимальный выигрыш и оптимальные смешанные стратегии.
| В 1 | В 2 | В 3 | |
| А 1 | |||
| А 2 | |||
| А 3 | |||
| 3 * | 8 * | 9 * | 36 * | ||||||
| 3 * | 4 * | 12 * | 13 * | ||||||
| 7 * | |||||||||
| 1 * | |||
| 3 * | |||
| 4 * | |||
| 6 * | |||
| 9 * | |||
| 10 * | |||
| 12 * | |||
| 34 * |
Выбор игроком того или иного действия называется ходом . Ходы бывают личные (игрок сознательно принимает то или иное решение) и случайные (исход игры не зависит от воли игрока). Набор правил, которые определяют, какой ход игроку необходимо сделать, называется стратегией . Стратегии бывают чистыми (неслучайные решения игроков) и смешанными (стратегию можно рассматривать как случайную величину).
Седловая точка
В теории игр С. т. (седловой элемент ) - это наибольший элемент столбца матрицы игры , который одновременно является наименьшим элементом соответствующей строки (в игре двух лиц с нулевой суммой ). В этой точке, следовательно, максимин одного игрока равен минимаксу другого; С. т. есть точка равновесия .
Теорема о минимаксе
Стратегия, соответствующая минимаксу, называется минимаксной стратегией .
Принцип, диктующий игрокам выбор наиболее "осторожных" максиминной и минимаксной стратегий, называется принципом минимакса . Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.
Игрок выбирает свои действия, предполагая, что противник будет действовать неблагоприятным образом, т.е. будет стараться "навредить".
Функция потерь
Функция потерь – функция, которая в теории статистических решений характеризует потери при неправильном принятии решений на основе наблюдаемых данных. Если решается задача оценки параметра сигнала на фоне помех, то функция потерь является мерой расхождения между истинным значением оцениваемого параметра и оценкой параметра
Оптимальная Смешанная стратегия игрока - это полный набор применения его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями.
Смешанная стратегия игрока - это полный набор применения его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями.
1. Если все элементы строки не больше соответствующих элементов другой строки, то исходная строка может быть вычеркнута из платежной матрицы. Аналогично для столбцов.
2. Цена игры единственна.
Док-во: допустим, что есть 2 цены игры v и , которые достигаются на паре и соответственно, тогда
3. Если ко всем элементам платежной матрицы прибавить одно и то же число, то оптимальные смешанные стратегии не изменятся, а цена игры увеличится на это число.
Док-во:
, где 
4. Если все элементы платежной матрицы умножить на одно и то же число не равное нулю, цена игры умножится на это число, а оптимальные стратегии не изменятся.
Загрузка...