Теория игр

1. Теория игр

Теория
игр
представляет
собой
математическую
теорию
конфликтных
ситуаций.
Ее цель – выработка рекомендаций по
разумному поведению участников конфликта
Впервые описана в 1944 – в монографии фон
Неймана и Моргеншерна

2.

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

3.

1.
2.
3.
Игра характеризуется:
Множество заинтересованных сторон –
лиц, участников, игроков
Множеством
возможных
действий
(ходов)
для
каждого
игрока
–
стратегий
Интересами игроков, задаваемых с
помощью
функции
выигрыша
–
функции платежа.

4. Игры можно классифицировать

1.
Игры
парные
(2
игрока)
множественные.
2.
По количеству возможных стратегий:
.
конечные (конечное у каждого игрока)
.
бесконечные (хотя бы у одного игрока
бесконечное число стратегий)
и

5.

По свойствам функции платежа:
. антагонистическая
(с
нулевой
суммой) – выигрыш одного =
проигрышу другого,
. игра
с
постоянной
разностью
(участники
выигрывают
и
проигрывают
одновременно,
следовательно выгодно действовать
сообща).
4. По
наличию
предварительной
договоренности
о
совместных
действиях : кооперативные (есть
договоренность) и некооперативные
(договоренности нет).
3.

6.

ОПРЕДЕЛЕНИЯ
Стратегия
–
совокупность
правил,
определяющих
выбор
варианта
действия
игроком в зависимости от ситуации в игре.
Целью
является
отыскание
оптимальной
стратегии для каждого игрока.
Оптимальная стратегия – стратегия, которая
при
многократном
повторении
игры
обеспечивает игроку максимально возможный
выигрыш или минимально возможный проигрыш
независимо от поведения противника.
Выбор одной из возможных стратегий и ее
реализация называется ходом.
Ход – может быть личным (выбор стратегии
сознателен) и случайным.

7. Игру можно описать разными способами

1.
2.
Позиционный – задается в виде дерева
шагов.
Нормальный – задаются допустимые
стратегии для каждого игрока и
функция
выигрыша,
которая
определяет выигрыш или проигрыш для
каждой стратегии. Чаще всего задается
в виде платежной матрицы

8. Конечная парная антагонистическая игра

Два игрока (I и II) обладают конечным
набором стратегий:
I стратегии А1…..Am
II стратегии B1….Bn
Эта игра размерностью n×m.

9.

Предположим, что на некотором ходе
игрок I выбрал стратегию Ai , а игрок II
отвечает стратегией Bj
Тогда W1 (Ai , Bj) – выигрыш, который
получит игрок I при этой паре стратегий.
W2 (Ai , Bj) – выигрыш, который
получит игрок II при этой паре стратегий
Так как игра антагонистическая, то
W1 (Ai , Bj) + W2 (Ai , Bj) =0
Или W1 (Ai , Bj) =- W2 (Ai , Bj) = W (Ai ,
Bj)

10.

Обозначим W (Ai , Bj)=aij тогда
получим платежную матрицу
Каждый положительный элемент это выигрыш I игрока,
каждый отрицательный – проигрыш II

11. Пример

Играют 2 игрока, каждый называет
цифру 1, 2, или 3. Если разница между
цифрами игроков положительная, то
это выигрыш I игрока, если
отрицательная – II игрока, если =0, то
ничья.
I A1=1 A2=2 A3=3
II B1=1 B2=2 B3=3

12.

Запишем платежную матрицу.

13.

Следует найти оптимальную стратегию
для I и II игроков.
Используем основной принцип ТИ:
Какую бы стратегию не выбрал I
игрок, II игрок всегда ответит на нее
такой
стратегией,
при
которой
выигрыш I будет минимальным и
следовательно у II минимальный
проигрыш.

14.

Для поиска лучшей стратегии I игрока найдем
минимальный элемент в каждой строке
платежной матрицы αi =min aij
Среди αi найдем максимальный α=maxαi
α=max (min aij) - нижняя цена игры или
гарантированный выигрыш I (максимин)
Стратегия I игрока, при которой достигается α
называется
максиминой
или
перестраховочной.
При этой стратегии I игроку гарантирован
выигрыш не менее α .

15.

Наилучшая стратегия для II игрока.
Находим максимальный элемент в
каждом столбце матрицы βj=max aij
Среди βj найдем минимальныйβ=min βj
β = min (max aij) верхняя граница
или минимакс.
Стратегия II игрока, при которой
достигается это значение называется
минимаксной или перестраховочной
для II.
Если
II
придерживается
своей
минимаксной стратегии, то он получает
выигрыш не больший, чем β

16.

17.

В ТИ доказано, что α≤β
Существуют игры, в которых α=β=γ чистая цена игры, это игры с седловой
точкой.
Пара оптимальных стратегий (A*I, B*j) для
I и II игроков , при которых достигается
чистая цена игры называется седловой
точкой платежной матрицы.
Если игра содержит седловую точку, то
говорят, что решение находится в
чистых стратегиях.

18. Пример

α=0
β=0
γ=0
Игра содержит
седловую точку
(A3, B3)

19.

Оптимальные чистые стратегии обладают
свойством равновесия: игроки всегда
придерживаются
своих
оптимальных
стратегий, так как это выгодно.
I игрок не может увеличить выигрыш
больше чем γ, а II игрок не может
уменьшить проигрыш и сделать больше γ

20.

Если седловой точки в платежной
матрице нет, то решение игры ищем в
смешанных стратегиях.
Смешанная стратегия – сложная
стратегия, в которой чистые стратегии
игроков применяются с некоторыми
частотами (вероятностями)

21.

I игрок. р1 - вероятность применения
стратегии
А1,…
рiвероятность
применения стратегии
А i … рm
вероятность применения стратегии Аm
pi≥0, i=1…m, ∑ pi=1.
Чистая
стратегия
Аi
называется
активной,
если
вероятность
ее
использования отлична от нуля pi≠0.

22.

II игрок. q1 - вероятность применения
стратегии
B1,…
qjвероятность
применения
стратегии
Bj
…
qn
вероятность применения стратегии Bn
qj≥0, j=1…n, ∑ qj=1.
Чистая
стратегия
Bj
называется
активной,
если
вероятность
ее
использования отлична от нуля qj≠0.

23.

Любая
антагонистическая
парная
конечная игра имеет по крайней мере
одно решение, возможное в смешанных
стратегиях.
Следовательно игра имеет цену γ, α≤ γ ≤ β
Игрок I стремится добиться выигрыша = γ, а
игрок II стремится минимизировать проигрыш
до γ.
Смешанные
стратегии
также
обладают
свойством равновесия, обоим игрокам
выгодно их применять.

24. Теорема фон Неймана

Применение
оптимальных
смешанных стратегий гарантирует
игроку
максимально
возможный
средний
выигрыш
(минимально
возможный средний проигрыш) равный
цене игры γ, независимо от
поведения противника, если игрок не
выходит за пределы своих активных
стратегий.

25. Доказательство

Для I игрока предположим, что
стратегий
активны,
r≤m
следовательно p*A=(p1,….pr,0…0)
r
,
Для II игрока предположим, что s
стратегий
активны,
s≤n
,
следовательно q*B=(q1,….qs,0…0)
Применяя эти стратегии I получит
выигрыш =γ, а II – проигрыш =γ.

26.

Требуется
доказать,
что
I
применяя
оптимальные стратегии независимо от действий
II получит выигрыш =γ.
Пусть
первый
применяет
оптимальные
стратегии А*, а II применяет чистые стратегии
В1…Вs.
Тогда выигрыш I будет γ1… γs.
Так как II не применяет оптимальные стратегии,
то он может получить проигрыш ≥γ:
γ1≥γ…..γs≥γ.

27.

Выразим γ через γ1… γs .
γ=q1γ1+….. +qsγs – средневзвешенное
значение величин γ1… γs (веса- это
вероятности)
Это значение было бы >γ, если бы хотя
бы одно γj >γ следовательно γ1… γs =γ.,
следовательно I независимо от действий
II получит выигрыш =γ.

28. Игра размерностью 2 на 2

В игре 2 участника и
каждый имеет по 2
допустимые
стратегии.
I A 1 A2
II B1 B2
• Если игра содержит седловую точку, то
решение находится в чистых стратегиях.

29.

Предположим, что седловой точки нет, тогда
решение будет находиться в смешанных
стратегиях.
P=(p1,p2) q=(q1,q2) Обе стратегии активны,
иначе - игра с седловой точкой.
Найдем оптимальную стратегию для I игрока.
Согласно теореме, если I игрок будет
придерживаться оптимальной стратегии, то
получит выигрыш =γ независимо от II игрока.
Если II применяет стратегию B1, то I игрок
получит выигрыш a11p1+a21p2=γ
Если II применяет стратегию B2, то I игрок
получит выигрыш a12p1+a22p2=γ

30.

Получаем систему
Решаем и находим p1 p2 γ
B1 : a11 p1 a21 p2
B2 : a12 p1 a22 p2
p1 p2 1

31.

Аналогично для II игрока
A1 : a11 q1 a12q2
A2 : a21q1 a22 q2
q1 q2 1
γ из первой и второй системы совпадают

32. Пример

Дана платежная
матрица
5 1
A
2 3
Проверим наличие седловой точки
5
1
1
1
A 2
3
2 2
1 5 2 3 2 3
α≠β –
седловой
точки нет

33.

5 p1 2 p2
p1 3 p2
p p 1
2
1
1
p1
5
5q1 q2
2q1 3q2
q1 q2 1
2
q1
5
4 p1 p2 0
p1 p2 1
4
13
p2
5
5
3q1 2q2 0
q1 q2 1
3
13
q2
5
5

34. Геометрический метод

а11 а12
Пусть имеется игра с матрицей А
а21 а22
1.
2.
В декартовой системе координат на оси абсцисс
откладывается отрезок равный 1. Точка х=0
соответствует стратегии А1, х=1 – стратегии А2.
На левой оси ординат откладываются выигрыши
стратегии А1, на правой – стратегии А2.

35.

Если игрок II применяет стратегию В1, то его выигрыш при
использовании стратегии А1 и А2 составляет соответственно а 11 и
а21.
Соединим точки В1 В1.
Если игрок I применяет смешанную стратегию, то средний
выигрыш а11р1+а21р2=γ – точка N на прямой В1 В1, абсцисса ее
равна р2.
В1 В1 называют стратегией игрока I при применении стратегий
А1 и А2 с соответствующими вероятностями р1 и р2.
В2
а12
В1
N
В1
а21
а22
В2
γ
а11
р2
А1
р1
А2

36.

Если игрок II применяет стратегию В2, то его выигрыш при
использовании стратегии А1 и А2 составляет соответственно а 12 и
а22. В2 В2 соответствует стратегии игрока II.
Точка пересечения В1 В1 и В2 В2 определяет цену игры γ.
Ординаты точек отрезка В2 В2 равны среднему числу стратегий
А1 и А2 с вероятностями р1 и р2.
Ломаная В1 N В2 – это нижняя граница выигрыша, получаемого
игроком I. В точке N он максимален и составляет γ
В2
а12
В1
N
В1
а21
а22
В2
γ
а11
р2
А1
р1
А2

37. Пример

Найти
оптимальную
смешанную стратегию
руководителю
предприятия
и
гарантированный
средний выигрыш при
выборе
новых
технологий А1 и А2,
если
известны
выигрыши каждого вида
по сравнению со старой
технологией:
I
II
A1
B1
B2
α
1
6
1
A2
3
2
2
β
3
6

38.

Решение
Нижняя цена игры α=max(1,2)=2
Верхняя цена игры β=min(3,6)=3
α ≠ β, седловой точки нет.
Цена игры будет 2≤γ≤3.
Находим решение игры в смешанных
стратегиях геометрическим методом.

39.

В2
а12=6
В1
а21=3
N
В1
γ=8/3
а22=2
В2
а11=1
Р2=5/6
А1
Р1=1/6
А2
a12 (a22 a12 ) p2
5
1
8
p2 , p1 ,
6
6
3
a11 (a21 a11 ) p2

40. Игра размерностью m×n

В ТИ доказано, что в играх размерностью
m×n число активных стратегий равно
min{m,n}
Таким образом, решение игр m×2 и 2×n
сводится к решению игр 2×2.

41. Способы понижения размерности платежной матрицы

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

42.

Если в матрице все элементы некоторой
строки, соответствующие стратегии Ai I
игрока не больше соответствующих
элементов другой строки, то стратегии Ai
называется заведомо невыгодной для I
игрока.
Если в матрице все элементы некоторого
столбца, соответствующие стратегии Bj II
игрока не меньше соответствующих
элементов другого столбца, то стратегию
Bj называется заведомо невыгодной для
II игрока

43.

Рассмотрим платежную матрицу
4 2 4 4 4 2 4
4 3 4 4 4 3 4
A
2 4 9 9
2 4 9
0 1 2 2 0 1 2 A4- заведомо
невыгодная
4 2 4
4 3 4
2 4 9
B4-дублирующая
стратегия
стратегия
4 2
4 3
2 4
B3- заведомо невыгодная стратегия

44. Матричные игры m×n

Рассмотрим игру, которая будет описана
следующей платежной матрицей.

45. Алгоритм решения

содержит ли игра седловую точку?
Да
решение в чистых стратегиях
Нет
Проверяем возможность уменьшения размерности матрицы
Решаем симплекс-методом

46. Находим решение в смешанных стратегиях

I игрок чистые стратегии А1…..Am
II игрок чистые стратегии B1….Bn
Оптимальные смешанные стратегии
,p*B
p*A
Предположим,
что
все
элементы
платежной
матрицы
≥0,
иначе
добавляем к каждому элементу
положительное число, при этом
оптимальные стратегии не меняются, а
цена игры увеличивается на это

47.

Согласно теореме ТИ если I игрок будет
придерживаться оптимальной смешанной
стратегии, то он получит выигрыш ≥γ (цены
игры).
При этом II игрок применяет свои чистые
стратегии
B1
a11 p1 ...... a1m pm
...
Bn
a1n p1 ....... amn pm
p1 ...... pm 1 pi 0 i 1...m

48.

Введем обозначения xi=pi/γ i=1..m
Разделим неравенства на γ
a11 x1 ...... a1m xm 1
...
a1n x1 ....... amn xm 1
p1 ...... pm 1 pi 0 i 1...m

49.

Цель I игрока увеличить выигрыш γ
Так как p1+…+pm=1, то x1+…xm=1/γ
F=x1+…..+xm→min
Получаем задачу линейного
программирования.

50.

Составим аналогичную задачу для II игрока.
Если II игрок
придерживается оптимальной
смешанной стратегии, то он получит проигрыш ≤γ.
При этом I игрок применяет свои чистые стратегии.
a11 q1 ...... a1n qn
A1
...
Am
am1q1 ....... amn qn
q1 ...... qn 1 q j 0
j 1...n

51.

Введем обозначения yi=qj/γ j=1..n
Разделим неравенства на γ
a11 y1 ...... an yn 1
...
am1 y1 ....... amn yn 1
q1 ...... qn 1 q j 0
j 1...n
F1 y1 .... yn max
II игрок стремится уменьшить γ и следовательно F1
надо максимизировать

52.

Таким образом, решение матричных игр m×n
сводится к решению пары двойственных
симметричных задач.
m
F xi min
i 1
n
F1 y j max
j 1
n
m
a
i 1
ij
xi 1
xi 0
j 1..n
i 1..m
a
j 1
ij
y j 1 i 1..m
yj 0
j 1..n

53.

Решая эти задачи найдем оптимальное
решение x*=(x1*.....xm*) y*=(y*1…y*n)
Отсюда найдем цену игры:
1
m
x
i 1
i
pi x
*
i
1
n
y
j 1
j
q j y
*
j

54. Задача

Найти оптимальную стратегию и цену игры
1 2 0
A 1 0 1
2 1 0
1 2 0 0
A 1 0 1 0 0
2 1 0 0
2 2 1 1
нет седловой точки

55.

I игрок
F x1 x2 x3 min
x1 x2 2 x3 1
2 x1
x2
x3 1
1

56.

II игрок
F1 y1 y2 y3 max
y1 2 y2
y1
1
y3 1
2 y1 y2
Решаем симплекс методом
1

57.

F1 y1 y2 y3 max
y1 2 y2
y1
2 y1 y2
y4 1
y3 y 5 1
y6 1

58.

1
базис
ΔC
A0
A1
1
A2
1
A3
0
A4
0
A5
0
A6
A4
0
1
1
2
0
1
0
0
A5
0
1
1
0
1
0
1
0
A6
0
1
2
1
0
0
0
1
0
-1
-1
-1
0
0
0
A2
1
0,5
0,5
1
0
0,5
0
0
A5
0
1
1
0
1
0
1
0
A6
0
0,75
1,5
0
0
-0,5
0
1
0,5
-0,5
0
-1
0,5
0
0
A2
1
0,5
0,5
1
0
0,5
0
0
A3
1
1
1
0
1
0
1
0
A6
0
0,75
1,5
0
0
-0,5
1
1
1,5
0,5
0
0
0,5
1
0

59. Ответ

У*=(0; 0,5; 1)
X*=(0,5; 1; 0)
γ=1/1,5=0,66= 2/3 α≤γ≤β
*
q* =(0;1/3;2/3)
p
B
A=(1/3;2/3;0)

60. Вопросы

1.
2.
3.
4.
5.
6.
7.
Каковы основные термины и определения теории
игр?
Какие классы игр можно выделить?
Определите антагонистическую матричную игру.
Каков принцип минимакса?
Когда следует использовать смешанные стратегии
и как их найти?
Каков геометрический метод решения игры?
Как найти решение с помощью симплекс-метода?