Similar presentations:
Решение игр в смешанных стратегиях
1.
Тема 2. Решение игр в смешанныхстратегиях
Введение
Геометрическое решение игр 2 2, 2 n,
m 2
Приведение антагонистической игры к
паре взаимно двойственных задач
линейного программирования
2.
ВведениеСложная стратегия, состоящая в случайном
применении двух и более чистых стратегий с
смешанной
Наборы вероятностей (частот)
определенными частотами, называется
первого игрока
второго игрока
( p1 , p2 ,..., pm )
(q1 , q2 ,..., qn )
Основная теорема теории игр Дж. фон Неймана
Каждая конечная игра имеет по крайней мере
одно оптимальное решение в смешанных
стратегиях.
3.
1. Геометрическое решение игр 2 2, 2 n, m 21.1. Геометрическое решение игры 2 2
a11a12
A
a21a22
1.2. Геометрическое решение игры 2 n
a11a12...a1n
D
a21a22...a2 n
1.3. Геометрическое решение игры m 2
a11 a12
a21 a 22
Т
...........
a a
m1 m2
4.
1.1. Геометрическое решение игры 2 2Графический метод решения игры
Этап 1. В декартовой системе координат pOH по оси абсцисс откладывается
отрезок, длина которого равна 1. Левый конец отрезка (точка р=0) соответствует
стратегии A1 , правый – стратегии A (р=1).
2
Промежуточные точки оси абсцисс соответствуют вероятностям некоторых
смешанных стратегий ( p1 , p2 )
Этап 2. На левой оси – оси ординат, откладываются выигрыши стратегии
Этап 3. На линии, параллельной оси ординат, из точки 1 откладываются
выигрыши стратегии A
2
Этап 4. Соединяем точки
прямой
'
B2 B2
a11,a21
прямой
'
B1 B1
, точки
a12 ,a22
A1
5.
Интерпретация результатов6.
Для уточнения и проверки результатов графическогорешения можно дополнительно решить системы
a11 a12
A
a21 a22
q1 q 2
для первого игрока
a11 p1 a21 p2
a12 p1 a22 p2
p p 1
2
1
P1
P2
для второго игрока
p1
a22 a21
a11 a22 a21 a12
p2
a11 a12
a11 a22 a21 a12
q1
a22 a12
a11 a22 a12 a21
q2
a11 a21
a11 a22 a12 a21
a11a22 a12a21
a11 a22 a12 a21
a11q1 a12q2
a21q1 a22q2
q q 1
2
1
7.
ПримерИгроки
В1
В2
A1
0,3
0,8
A2
0,7
0,4
Решение
В1
В2
A1
0,3
0,8
Минимумы
строк
0,3
A2
0,7
0,4
0,4
0,7
0,8
Игроки
Максимумы
столбцов
8.
Выводы9.
1.2. Геометрическое решение игры 2 na11a12...a1n
D
a21a22...a2 n
Игроки
В1
q1
p1
A1
A2
a11
p2 1 p1
a21
….
Вn
В2
….
qn
q2
….
a12
a1n
….
a22
a2 n
Найти смешанные стратегии игроков
A
1
2
S (p , p )
B
1
2
n
S (q , q ,..., q )
10.
Пример10 8 6 4 2 3
D
1 2 4 3 12 6
1. Исключим из платежной матрицы заведомо невыгодные стратегии:
Игроки
В1
В2
В3
В4
В5
В6
A1
A2
10
1
8
2
6
4
4
3
2
12
3
6
Игроки
В1
В2
В4
В5
В6
A1
10
8
4
2
3
A2
1
2
3
12
6
11.
2. Определим наличие (отсутствие) седловой точки в игре:Игроки
В1
В2
В4
В5
В6
Минимумы
строк
A1
10
8
4
2
3
2
A2
1
2
3
12
6
1
10
8
4
12
6
Максимумы
столбцов
Ищем решение игры в смешанных стратегиях:
A
1
2
S (p , p )
B
1
2
n
S (q , q ,..., q )
12.
3. Строим график в системе координат pOHИнтерпретация результатов решения
13.
12
4
p , p ,q ,q
4. Определим значения вероятностей
и цены игры
Активные
стратегии А
Игроки
В4
В6
A1
4
3
p1
A2
3
6
p2
Активные
стратегии В
4
6
q
q
игрок А:
4 p1 3 p2
3 p1 6 p2
p1 p2 1
Выводы
6
игрок В:
3 1 15
3 1
S A ; , S B 0;0;0; ;0; ,
4 4
4
4 4
4q4 3q6
3q4 6q6
q4 q6 1
14.
1.3. Геометрическоерешение игры m 2
a11 a12
a21 a 22
Т
...........
a a
m1 m2
Необходимо найти смешанные стратегии игроков:
A
1
2
S ( p , p ,..., pm )
B
1
2
S (q , q )
15.
В2A1
p1
В1
q1
a11
A2
p2
a21
a22
…
…
…
…
pm
am1
Игроки
Am
q2
a12
am 2
Решение проводят с позиций игрока B,
у которого две стратегии
16.
Пример. Задача о выборе минеральных удобрений4 2
A 2 4
3 2.5
Матрица прибылей, млн руб.:
1. В данной игре нет заведомо невыгодных стратегий
(доминирующих, дублирующих).
2. Определим наличие (отсутствие) седловой точки:
Игроки
Минимумы
строк
В1
В2
A1
A2
4
2
2
2
4
2
A3
3
2,5
2,5
4
4
Максимумы
столбцов
17.
3. Строим график в системе координат qOH18.
4. Определим значения вероятностей p1 , p 2 , q1 , q 2и цены игры
Игроки
A1
A2
Активные
стратегии В
Активные
стратегии А
В2
В1
4
2
p1
2
4
p2
1
q
q
2
игрок В:
игрок А:
4 p 2 p
2 p1 4 p2
p1 p2 1
1
2
1 1
1 1
S A ; ;0 , S B ; , 3
2 2
2 2
Выводы
4q1 2q2
2q1 4q2
q1 q2 1
19.
Общая схема решения игр 2 n и m 21. Строят прямые, соответствующие стратегиям игрока В или
А.
2. Находят две стратегии игрока В или А, которым
соответствуют две прямые, пересекающиеся в точке с
максимальной (минимальной) ординатой. Эти стратегии
являются активными в оптимальной смешанной стратегии
игрока В или А.
3. Находят координаты точки пересечения, тем самым
определяя оптимальную стратегию игрока А или В и цену
игры.
4. Оптимальную стратегию другого игрока находят, решая
систему уравнений, включающую его активные стратегии.
20.
2. Приведение антагонистической игры к паревзаимно двойственных задач линейного программирования
m n
Игра порядка
Игрок А
Игрок В
B1
B2
…
Bk
…
Bn
A1
a11
a12
…
a1k
…
a1n
A2
a 21
a 22
…
a 2k
…
a 2n
…
…
…
…
a in
…
…
…
…
Ai
a i1
a i2
…
…
…
…
…
…
…
…
a m1
a m2
…
a mk
…
a mn
Am
A
1
2
S ( p , p ,..., pm )
a1ik
B
1
2
n
S (q , q ,..., q )
21.
Задача игрока АЗадача игрока В
F ( X ) x1 x2 ... xm min
Z (Y ) y1 y2 ... yn max
a11x1 a21x2 ... am1 xm 1
a x a x ... a x 1
22 2
m2 m
12 1
..........................................
a x a x ... a x 1
2n 2
mn m
1n 1
xi 0, i 1,..., m
a11 y1 a12 y2 ... an1 yn 1
a21 y1 a22 y2 ... an 2 yn 1
..........................................
a y a y ... a y 1
mn n
m1 1 m 2 2
y j 0, j 1,..., n
X x1 , x2 ,..., xm
1
2
Y y , y ,..., y
n
1
1
Fmin Z max
pi xi
q j y j
22.
ПримерИгроки
A1
A2
A3
Максимумы
столбцов
В1
В2
В3
A2
3
5
1
1
2
0
A3
0
2
5
Игроки
A1
В1
В2
В3
3
5
1
1
2
0
0
5
2
2
5
5
Минимумы
строк
1
0
0
23.
Задача игрока АЗадача игрока В
F ( X ) x1 x2 x3 min
Z (Y ) y1 y2 y3 max
3 x1 5 x2 1
1x 1x 2 x 1
1
2
3
2 x1 5 x3 1
xi 0, i 1,2,3
3 y1 1 y2 2 y3 1
5 y 1 y 1
1
2
2 y 2 5 y3 1
y j 0, j 1,2,3
1
1
1
5
1
2
Fmin Z max 0
3
5 5
1 2
X 0, ,
5 5
1 1
Y , ,0
10 2
i
i
p x
1 2
S 0, ,
3 3
A
q j y j
1 5
S , ,0
6 6
B
24.
При решении произвольной конечной игры размеm n
рекомендуется придерживаться следующей схем
1. Исключить из платежной матрицы заведомо невыгодные стратегии.
2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли
игра седловую точку. Если седловая точка есть, то соответствующие ей
стратегии игроков будут оптимальными, а цена игры совпадает с верхней
(нижней) ценой.
3. Если седловая точка отсутствует, то решение следует искать в
смешанных стратегиях. Игры размера m n решаются путем сведения к
паре взаимно двойственных задач линейного программирования. Для игр
размера 2 n , m 2 возможно применить графо-аналитический метод
решения.