Основы теории матричных игр. Принятие решений в условиях неопределенности

1. Принятие решений в условиях неопределенности

2.

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

3.

1. Основные понятия теории
матричных игр

4.

• Теория игр, раздел математики, изучающий
формальные модели принятия
оптимальных решений в условиях
конфликта.
• Под конфликтом понимается явление, в
котором участвуют различные стороны,
наделённые различными интересами и
возможностями выбирать доступные для них
действия в соответствии с этими интересами.
• Целью теории игр является выработка
рекомендаций по рациональному образу
действий участников в конфликтных
ситуациях, то есть определение
оптимальной стратегии каждого из них.

5.

• Отдельные математические вопросы, касающиеся
конфликтов, рассматривались начиная с 17 в.
многими учёными.
• Систематическая же математическая теория
стратегических игр была детально разработана в 30-х
годах XX века как средство математического подхода
к явлениям конкурентной экономики.
• В ходе своего развития теория игр переросла эти
рамки и превратилась в общую математическую
теорию конфликтов. Её создателем считается Джон
фон Нейман.
• Первой фундаментальной книгой по теории игр была
изданная в 1944 году работа "Теория игр и
экономическое поведение" (Нейман Д., Моргенштерн
О. М.:Наука,1970).

6.

• В условиях конфликта стремление противника скрыть
свои предстоящие действия порождает
неопределённость. Наоборот, неопределённость при
принятии решений (например, на основе
недостаточных данных) можно интерпретировать как
конфликт принимающего решения субъекта с
природой.
• Игрой называется всякая конфликтная ситуация,
изучаемая в теории игр и представляющая собой
упрощенную, схематизированную модель ситуации.
От реальной конфликтной ситуации игра отличается
тем, что не включает второстепенные,
несущественные для ситуации факторы и ведется по
определенным правилам, которые в реальной
ситуации могут нарушаться.

7.

• Всякая игра включает в себя три элемента: участников
игры – игроков, правила игры, оценку результатов
действий игроков.
• Игроком (лицом, стороной, или коалицией) называется
отдельная совокупность интересов, отстаиваемая в игре.
Если данную совокупность интересов отстаивает несколько
участников игры, то они рассматриваются как один игрок.
• Игроки, имеющие противоположные по отношению друг к
другу интересы, называются противниками. В игре могут
сталкиваться интересы двух или более противников.
• Одна реализация игры называется партией; выбор действия
(в пределах правил) – ходом.
• Ходы бывают личные и случайные. Личный ход
предполагает сознательный выбор того или иного действия,
разрешенного правилами игры, а случайный – не зависит от
воли игрока (например, он может быть определён
подбрасыванием монеты или игральной кости).
• Игры, в которых имеются личные ходы, называются
стратегическими.
• Игры, состоящие только из случайных ходов, называют
азартными.

8.

• Стратегией игрока называется совокупность правил,
определяющих выбор варианта действий при каждом личном ходе
в зависимости от сложившейся ситуации.
• В зависимости от числа стратегий игры делятся на конечные и
бесконечные. Игра называется конечной, если у каждого игрока
имеется в распоряжении только конечное число стратегий. В
противном случае игра называется бесконечной.
• Оптимальной стратегией игрока называется такая, которая
обеспечивает ему наилучшее положение в данной игре, т.е.
максимальный выигрыш. Если игра повторяется неоднократно и
содержит, кроме личных, ещё и случайные ходы, оптимальная
стратегия обеспечивает максимальный средний выигрыш.
• Игра называется игрой с нулевой суммой, если сумма выигрышей
всех игроков равна нулю, т.е. каждый игрок выигрывает только за
счёт других. Самый простой случай – парная игра с нулевой суммой
– называется антагонистической.
• Антагонистической игрой называется система G=<A,B,H>, где A,B
- непустые множества стратегий соответственно первого и второго
игроков; H(a,b) – функция выигрыша игрока A (то есть функция
потерь игрока B), a A, b B. Таким образом, в процессе игры
каждый игрок выбирает свою стратегию, в результате чего
образуется ситуация (a, b), которой соответствует выигрыш Н(a, b)
для первого игрока и – проигрыш Н(a, b) для второго.

9.

• Антагонистические игры, в которых каждый игрок имеет
конечное множество стратегий, называются матричными
играми. Для задания такой игры достаточно выписать так
называемую платежную матрицу, в которой строки
соответствуют стратегиям первого игрока, а столбцы –
стратегиям второго игрока. Элементами матрицы служат
выигрыши первого игрока.
В1
В2
А1
а11
а12
А2
а21
а2m
an1
аnm
...
Вm
а1m
...
Аn

10.

• Рассмотрим простейшую модель – игру, в
которой участвуют два игрока, множество
стратегий каждого игрока конечно, а
выигрыш одного игрока равен проигрышу
другого (бескоалиционная, конечная,
антагонистическая игра двух лиц).

11.

• Такую игру (Г ) называют матричной.
• Она определяется тройкой Г=(X,Y,K),
где
Х – множество стратегий 1-го игрока,
Y – множество стратегий 2-го игрока,
K=K(x,y) – функция выигрыша (выигрыш 1-го
игрока и соответственно проигрыш 2-го
при условии, что 1-й игрок выбрал
стратегию , а 2-й – стратегию ).
Пару (x,y) называют ситуацией в игре Г.

12.

• Пусть 1-й игрок имеет всего m стратегий, а
2-й – n стратегий:
Х=М={1,2, …, m}, Y=N={1,2, …, n}.
• Тогда игра Г полностью определяется
заданием матрицы A aij m n ,
где aij=K(i,j) – выигрыш 1-го игрока при
условии, что он выбрал стратегию (т.е.
строку) i, а 2-й игрок – стратегию (т.е.
столбец) j (эти стратегии называют
чистыми).
• Матрица А называется матрицей игры или
платежной матрицей.

13. Принцип минимакса (максимина)

• Величина max min aij называется
j
i
нижней ценой игры или максиминным
выигрышем (максимином).
max aij называется
• Величина min
j
i
верхней ценой игры или минимаксным
выигрышем (минимаксом).

14.

• Пусть A aij m n– платежная матрица игры Г.
Если 1-й игрок выбрал стратегию i, то в худшем
случае он выиграет min aij .
j
Поэтому он всегда может гарантировать себе
min aij
выигрыш max
j
i
соответствующая стратегия 1-го игрока
называется максиминной.

15.

• Второй игрок, выбрав стратегию j, в худшем
случае проиграет max aij , а значит, может
i
гарантировать себе проигрыш min max aij ,
j
i
• соответствующая стратегия 2-го игрока
называется минимаксной.

16.

Схема:
a12
a1n min a
a11
j 1j
a
a 22
a 2 n min a 2 j
21
j
А
min aij v
max
j
i
a m1
am 2
a mn min a mj
j
max ai1 max ai 2 max ain
i
i i
min max aij v
j
i

17.

• Например,
2 3 4 3
А 3 4 5 5 v 3
4 5 6 5
4
4
6
v 4
• Соответствующие стратегии:
i0=1(максиминная), j0=1,2 (минимаксная).

18.

• Справедливо неравенство:
v v

19.

• Ситуация (i*, j*) называется ситуацией равновесия,
или седловой точкой, если для любых i М , j N ,
выполняется неравенство
aij* ai* j * ai* j
• Соответствующие стратегии i*, j* называются
оптимальными чистыми стратегиями 1-го и 2-го
игроков, а число v ai* j* называется ценой игры.
• Элемент ai* j* является одновременно минимумом
в своей строке и максимумом в своем столбце.

20.

• Ситуация равновесия существует тогда и
только тогда, когда v v (это значение и
является ценой игры v).

21.

• Например,
5 3 1 20 5
А 5
5 4 6 4 v v 4.
4 2 0 5 5
5
5 4 20
• (2,3)-ситуация равновесная, v =4 – цена
игры, i*=2, j*=3 – оптимальные стратегии
1-го и 2-го игроков. Выбрав их, 1-й игрок
обеспечит себе выигрыш не менее 4 ед., а 2й игрок проиграет не более 4 ед. при любом
выборе другого игрока.

22.

• Смешанной стратегией для 1-го игрока
называется упорядоченная система m
действительных чисел x=(x1, x2, …, xm), xi 0 ,
m
xi 1 , которые можно рассматривать как
i 1
относительные
частоты (вероятности), с
которыми 1-й игрок выбирает чистые
стратегии i=1, 2, …, m.
• Аналогично определяется смешанная
стратегия для 2-го игрока: y=(y1, y2, …, yn),
n
yj 0 , y j 1 .
j 1

23.

• Функция выигрыша K(x,y) в ситуации (x,y)
определяется как математическое ожидание
выигрыша 1-го игрока при условии, что 1-й
и 2-й игроки выбрали соответственно
стратегии x=(x1, x2, …, xm) и y=(y1, y2, …, yn):
m n
K ( x, y ) aij xi y j .
i 1 j 1

24.

• Если для некоторых x S mи y* Sn и для
всех x S m и y S n выполняется
неравенство K ( x, y* ) K ( x* , y* ) K ( x* , y) ,
то x*, y* называются оптимальными
смешанными стратегиями игроков,
* *
число v K ( x , y ) называется ценой игры,
пара (x*, y*) – стратегической седловой
точкой
тройка x*, y*, v – решением игры.
*

25.

Свойства оптимальных стратегий.

26.

• 1. Пусть K(x,y) – математическое ожидание
выигрыша в игре ГА с ценой v.
• Тогда, для того чтобы элемент x* S m был
оптимальной стратегией 1-го игрока,
необходимо и достаточно, чтобы для каждого
элемента y S n выполнялось неравенство
v K ( x* , y)
• Аналогично, для того чтобы y* Sn был
оптимальной стратегией 2-го игрока,
необходимо и достаточно, чтобы для каждого
x S m выполнялось неравенство
K ( x, y* ) v

27.

• 2. Пусть K(x,y) – математическое ожидание
выигрыша в игре ГА,
v – действительное число, x* S m , y* Sn .
Тогда, для того чтобы v было ценой игры, а
x* и y* были оптимальными стратегиями
соответственно 1-го и 2-го игроков,
необходимо и достаточно, чтобы для
любых i М и j N выполнялось
неравенство
K (i, y ) v K ( x , j)
*
*

28.

• 3. Если x*, y* – решение m n -игры ГА,
то
max K (i, y ) min K ( x , j ) v
*
i
*
j

29.

• 4. Пусть x* x1, x2 , ..., xm , y* y1, y2 , ..., yn ,
v – решение игры ГА.
• Тогда для любого i М , при котором
K (i, y* ) v , выполняется неравенство xi=0,
а для любого j N , при котором v K ( x* , j) ,
выполняется неравенство yj=0.

30.

• 5. (Лемма о масштабе).
• Если ГА – игра с матрицей A aij m n , а Г А –
игра с матрицей A aij m n , где aij aij , где
α, =const, α>0, то множества оптимальных
стратегий игроков в играх ГА и Г А совпадают,
а v А v A .
• Иначе говоря, две игры, отличающиеся лишь
началом отсчета выигрышей и масштабом их
измерения, стратегически эквивалентны.

31.

2. (2 2 ) - игры

32.

a11 a12
– платежная матрица
• Пусть А
a21 a22
игры Г.
Если она не имеет седловой точки, то
единственное решение игры Г можно
найти

33.

• 1) решив две системы:
a11 y1 a12 y 2 v,
a21 y1 a22 y 2 v,
y y 1;
2
1
a11 x1 a 21 x2 v,
a12 x1 a 22 x2 v,
x x 1;
1 2

34.

• 2) по формулам:
a22 a21
x1
a11 a22 a12 a21
a11 a12
x2
a11 a22 a12 a21
или x2 1 x1
a22 a12
y1
a11 a22 a12 a21
или y2 1 y1
a11a22 a12 a21
v
a11 a22 a12 a21
a11 a21
y2
a11 a22 a12 a21

35.

• 3) в матричном виде:
x
JA*
JA* J T
y
T
A* J T
* T
JA J
v
A
JA* J T
где А – определитель матрицы А,
А* – присоединенная к А матрица
(транспонированная матрица из
алгебраических дополнений),
J 1 1 , y y1 y2 , x x1 x2 ,
JT и yT – транспонированные матрицы J и y.

36.

• Найдем, например, решение игры с
платежной матрицей
3 1
А
2 4
имеет седловой точки.
, которая не

37.

• 1) Составим системы:
3x1 2 x2 v,
x1 4 x2 v,
x x 1.
1 2
3 y1 y 2 v,
2 y1 4 y 2 v,
y y 1.
2
1
• Решив системы, получим:
5
y1
6
y2
1
6
x1
1
3
2
x2
3
7
v
3
7
1 2 * 5 1
• то есть x ; y ; v -решение игры.
6 6
3 3
3
*

38.

• 2) Найдем решение по формулам:
4 2
2 1
x1
3 4 2 1 6 3
1 2
x2 1
3 3
4 1
5
y1
3 4 2 1 6
5 1
y2 1
6 6
3 4 2 1 14 7
v
3 4 2 1 6 3

39.

• 3) Найдем решение в матричном виде:
А 12 2 14
* T
JА J
4 1
А
2 3
*
1
2 4 6
1
1
1
x 2 4
6
3
4 1
2 4
JА 1 1
2 3
*
* T
А J
4 1 1 5
2 3 1 1
1 5 5 6
y
6 1 1 6
2
3
T
14 7
v
6 3