Учебные вопросы:
1. Предмет и задачи теории игр.
1. Предмет и задачи теории игр.
2. Матричные игры:
2. Матричные игры:
2. Матричные игры:
2. Матричные игры:
2. Матричные игры:
2. Матричные игры:
2. Матричные игры:
2. Матричные игры:
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
3. Смешанные стратегии матричных игр
705.72K
Category: mathematicsmathematics

Теория игр и принятие решений

1.

Тема «Теория игр и
принятие решений»

2. Учебные вопросы:

1. Предмет и задачи теории игр.
2. Матричные игры. Равновесная ситуация.
3. Смешанные стратегии матричных игр.
4. Игры с природой.

3. 1. Предмет и задачи теории игр.

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

4. 1. Предмет и задачи теории игр.

Стратегия

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

5. 2. Матричные игры:

Пусть в игре участвуют два игрока. Игрок А имеет m
стратегий, а игрок В – n стратегий.
Обозначим стратегии игрока А как А1,А2,…,Аm , а
стратегии игрока В – как В1 ,В2 …,Вn .
Если игрок А выбрал стратегию Ai , а игрок B –
стратегию Bk , то выигрыш игрока A составит аik , а игрока
B – bik , причем
аik = - bik (1)

6. 2. Матричные игры:

Поэтому при анализе такой игры достаточно рассмотреть выигрыш
только одного игрока, например выигрыш аik игрока А. Зная выигрыш
аik по формуле (1) легко определить выигрыш bik .
Матричные игры называются парными играми с нулевой суммой, в
которых выигрыш одного игрока равен проигрышу другого.
Если известны все значения аik для каждой пары стратегий {Ai Bk },
i =1, 2, …, m, k = 1, 2, …, n, то их удобно записать в виде
прямоугольной таблицы, строки которой соответствуют стратегиям
игрока A , а столбцы – стратегиям игрока В (табл. 1).

7. 2. Матричные игры:

:
2. Матричные игры:
Таблица 1.
A1
A2

Am
B1
B2
а11
a12
а21
а22


аm1
аm2





Bn
а1n
а2n

аmn
Чаще эти выигрыши записывают в виде платежной матрицы (матрицы игр)
размера , поэтому такие игры называются матричными играми :
A=
a11
a 21
...
a
m1
a12
a 22
...
am 2
a1n
... a 2 n
... ...
... a mn
...
Чаще
выигр

8. 2. Матричные игры:

Равновесная ситуация
Пусть матричная игра m×n задана платежной матрицей
A=
a11
a21
...
a
m1
a12
a22
...
am 2
a1n
... a2 n
... ...
... amn
...
(2)
Строки этой матрицы соответствуют стратегиям игрока , а
столбцы – стратегиям игрока . В теории игр предполагается,
что оба игрока действуют разумно, т.е. стремятся к
получению максимального выигрыша, считая, что соперник
действует наилучшим для себя образом.

9. 2. Матричные игры:

Определим оптимальные стратегии каждого из игроков.
Начнем с анализа стратегий игрока А . На стратегию Аi игрока
A игрок B ответит такой стратегией Bk, при которой выигрыш
игрока A будет минимальным. Аналогично игрок B будет
отвечать на все m стратегий игрока A . Другими словами,
найдем в каждой строке матрицы минимальный элемент
(минимальные выигрыши игрока A)
i min аik , i 1,2, , n
k
и запишем их в правом столбце табл. 2.

10. 2. Матричные игры:

Минимальные
выигрыши
игрока А
B1
В2

Вk

Bn
a11
a12
a1k
a1n
a22
a2 k

a21
a2 n
1
2
Ai
ai1
ai 2
aik
ain
i
am1
am 2
amk
amn
m
1
2
k
n
A1
A2

Am
Максимальные
выигрыши
игрока А
Действуя разумно, игрок остановится на той стратегии , для которой
окажется максимальным. Поэтому среди чисел выбираем максимальное
число
max i max min aik
i
i
k
(3)

11. 2. Матричные игры:

Принцип построения стратегии игрока А, основанный на
максимизации минимальных выигрышей, называется принципом
максимина (maxmin).
Проведем анализ стратегий игрока В. Для этого найдем в каждом
столбце матрицы максимальный элемент (максимальные выигрыши
aik , k 1, 2, , n
игрока А ): k max
i
И запишем их в нижней строке табл. 2. Действуя разумно, игрок B
aik
остановится на той стратегии k , для которой k max
i
выбираем минимальное число
k min k min max aik
k
k
(4)
i
Число β называется верхней ценой игры.

12. 2. Матричные игры:

Принцип построения стратегии игрока B, основанный на минимизации
максимальных выигрышей, называется принципом минимакса (minmax).
Нижняя цена игра α и верхняя цена игра β связаны неравенством
α ≤ β.
(5)
Если аi , opt, k , opt или
max min aik min max aik ai , opt, k , opt '
i
k
то ситуация
k
А
i , opt ,
Bk , opt
i
(6)
оказывается равновесной, и ни один игрок не
заинтересован в том, чтобы ее нарушить. В том случае, когда верхняя цена
игры равна нижней, их называют просто ценой игры.
Если α=β, то такую игру называют также игрой с седловой точкой, а
пара оптимальных стратегий Аi , opt, Вk , opt – седловой точкой матрицы. Цена
игры обозначается буквой v. Тогда . v аi , opt, k , opt

13. 3. Смешанные стратегии матричных игр

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

14. 3. Смешанные стратегии матричных игр

.
Таблица 4.
В1
В2
В3
А1
4
1
-3
Минимальн
ые
выигрыши
игрока А
-3
А2
-2
1
3
-2
0
2
-3
-3
4
2
3
А3
Максималь
ные
выигрыши
игрока В
Здесь
2

2

15. 3. Смешанные стратегии матричных игр

Обратимся к общему случаю матричной игры, представленной
в табл. 2. Обозначим через
вероятности, с которыми
игрок А использует в ходе игры свои чистые стратегии A , A ,..., A
1
2
m
Для этих вероятностей выполняются условия:
m
p
i 1
i
1; p1 0, p 2 0,..., p m 0
(8)
Вектор p p( p1 , p2 ,..., pm ) , проекция которого удовлетворяет
условиям (8), полностью определяет характер игры игрока А и
называется его смешанной стратегией. Механизм случайного
выбора чистых стратегий, которым пользуется игрок А,
обеспечивает
стратегий.
ему
бесконечное
множество
смешанных

16. 3. Смешанные стратегии матричных игр

Аналогично, вектор
q q(q1 , q2 ,..., qm )
, проекция которого
удовлетворяет условиям (9),
n
q
k 1
ki
1; q1 0, q 2 0,..., q n 0
(9)
полностью определяет характер игры игрока В и называется
смешанной стратегией игрока В. Игрок В, как и игрок А,
располагает
стратегий.
бесконечным
множеством
смешанных

17. 3. Смешанные стратегии матричных игр

Пусть игроки А и В применяют и
стратегии
p
смешанные
и q соответственно, т.е. игрок А использует
стратегию Ai с вероятностью p i , а игрок В – стратегию Bk с
вероятностью qk. Поскольку события
вероятность
произведению
появления
и
независимы, то
комбинации ( Ai , Bk )
вероятностей
и
равна
, т.е. . При
использовании смешанных стратегий игра приобретает
случайный характер, случайными становятся и величины
выигрышей игроков.

18. 3. Смешанные стратегии матричных игр

Поэтому выигрыш игрока А (проигрыш игрока В)
определяют
его
математическим
рассчитываемым по формуле
ожиданием,
(10)
Функция (10) называется платежной функцией игры с
матрицей, заданной в табл. 5.
Нижней ценой игры называется число
по формуле:
(11)
Верхней ценой игры называется число
по формуле:
, рассчитываемое
(12)
, рассчитываемое

19. 3. Смешанные стратегии матричных игр

Таблица 5.
B1
В2

Вk

Bn
Вероятности
использовани
я чистых
стратегий
игроком А
a1k
a1n
p1
a2 k
a2 n
p2
aik
ain
pi
a11
a12
a21
a22

Ai

ai1
ai 2
Am
am1
am 2
amk
amn
pm
q1
q2
qk
qn
A1
A2
Вероятности
использования
чистых
стратегий
игроком В

20. 3. Смешанные стратегии матричных игр

Оптимальными
смешанными
стратегиями
называются
стратегии,
удовлетворяющие соотношению (сравнить с формулой (6)).
max min E A, p, q min max E A, p, q E A, p opt , q opt . (13)
p
q
q
p
определенную соотношением
Величину
(13), называют ценой игры.
Векторы
p opt
и
q opt
называются
оптимальными
смешанными
стратегиями, если они образуют седловую точку платежной функции игры
E A, p, q
, т.е. удовлетворяют неравенству (сравнить с неравенством (7))
E A, p, q E A, p , q E A, p , q . (14)
opt
opt
opt
opt
Из соотношения (14) следует, что в седловой точке ( p opt , q opt ) платежная
функция E A, p, q достигает максимума по смешанным стратегиям p игрока А
и минимума по смешанным стратегиям q игрока В.

21. 3. Смешанные стратегии матричных игр

Теорема 1. Основная теорема теории матричных игр. (Дж. фон
Нейман).
Для матричной игры с любой матрицей А величины max min E A, p, q и
p
q
min max E A, p, q существуют и равны между собой:
q
p
max min E A, p, q min max E A, p, q .
p
q
q
p
Более того, существует хотя бы одна ситуация в смешанных стратегиях
( p opt , q opt ) , для которой выполняется соотношение
E ( A, p opt , q opt ) max min E A, p, q min max E A, p, q
p
q
q
p
.

22. 3. Смешанные стратегии матричных игр

Пусть
p opt p opt ( p1,opt , p2,opt ,..., pm,opt )
q opt q opt (q1,opt , q2,opt ,..., qn,opt )
,
оптимальные смешанные стратегии и
Оптимальная
смешанная
-
v E ( A, p opt , q opt ) - цена игры.
стратегия
складывается только из тех чистых стратегий
игрока
А
, i 1,2,..., m
(т.е. только те вероятности , могут отличаться от нуля),
n
для которых aik q k ,opt
v
k 1
Аналогично, только те вероятности
отличаться от нуля, для которых a
, k 1,2,..., n
m
i 1
ik
p i ,opt v
могут

23. 3. Смешанные стратегии матричных игр

Графические решения матричных игр
Графический метод применим к тем играм, в которых
хотя бы один игрок имеет две стратегии.
Рассмотрим игру 2×п, представленную в табл. 6. Эта
игра не имеет седловой точки. Согласно теореме имеем
2
v min aik Pi , opt min (a1k Popt a2 k (1 popt ))
1 k n
1 k n
i 1
max min( a
1k
p
p a2k (1 p))
1 k n
(15)

24. 3. Смешанные стратегии матричных игр

Максимум функции
min
(a1k p a2k (1 p))
1 k n
(16) найдем,
построив ее график. Для этого поступаем следующим образом. Построим графики прямых
w k =а 1 k p + a 2 k (1 -p )= ( a 1 k -a 2 k )p + a2k
(17)
для каждого к = 1, 2,..., п в системе координат pOw (рис.1). В
соответствии с требованием (16) на каждой из построенных
прямых определяются и отмечаются наименьшие значения. На
рис. 2 эти значения выделены полужирной ломаной линией. Эта
ломаная огибает снизу все семейство построенных прямых и
называется нижней огибающей семейства.

25. 3. Смешанные стратегии матричных игр

Пример 3. Найти решение игры вида 2×п , приведенной в табл. 7.
Таблица 7.
В1
В2
B3
В4
B5
В6
Вероятности
использования чистых
стратегий игроком А
A1
6
4
3
1
-1
0
p
A2
-2
-1
1
0
5
4
1-p
q1
q2
q3
q4
q5
q6
Вероятности
использования
чистых стратегий
игроком В

26. 3. Смешанные стратегии матричных игр

Р е ш е н и е . Проведем анализ игры на наличие седловой точки.
Нижняя цена игры равна -1, верхняя равна 1. Седловой точки нет. Решение
надо искать в смешанных стратегиях.
Построим график нижней огибающей (16). Предварительно запишем
уравнения прямых (17):
w1 6 p 2(1 p ) 8 p 2;
w2 4 p 1 (1 p ) 5 p 1;
w3 3 p (1 p ) 2 p 1;
w4 p 0 (1 p ) p;
w5 p 5 (1 p ) 6 p 5;
w6 0 p 4(1 p ) 4 p 4.

27. 3. Смешанные стратегии матричных игр

Графики данных прямых, построенных в системе координат p O w ,
представлены на рис.3.
Нижняя огибающая выделена на рис. 3 полужирной ломаной линией.
Точка максимума нижней огибающей лежит на пересечении прямых w4 и w5.
Решая уравнение p - 6 р + 5 , получим p o p t =
5
7
. Цена игры, являющаяся
математическим ожиданием выигрыша игрока А , равна v E A, p opt , q opt
5
7
Таким образом, цена игры и оптимальная стратегия игрока А равны:
v
5
5 2
; P opt ;
7
7 7
English     Русский Rules