Теория игр Основные понятия
Рассматривается игра двух соперников с нулевой суммой, т.е. без посредников, выигрыш одного из игроков составляет проигрыш другого. Игра задается матрицей платежей игрока А:
А=|ai,j|, 1 i n, 1 jm, (1)
где ai,j – выигрыш игрока А и проигрыш игрока В, если игрок А использует свою i-ю стратегию, а игрок В – свою j-ю стратегию,
n – число стратегий игрока А,
m – число стратегий игрока В.
Аналогично может быть задана матрица платежей игрока В
B=|bi,j|, 1 i n, 1 jm, (2)
где bi,j = –ai,j.
Игрок А стремится максимизировать свой выигрыш при самой неблагоприятной для него стратегии игрока В, т.е. оптимальной для него стратегией является стратегия «максимин»:
. (3)
Игрок В стремится минимизировать свой проигрыш при самой неблагоприятной для него стратегии игрока А, т.е оптимальной для него стратегией является стратегия «минимакс»:
. (4)
В общем случае цена игры W, WA – нижняя, а WB – верхняя цена игры
WA W WB. (5)
Если WA= WB, игра называется с простой стратегией или с седловой точкой.
Пример:
Матрица А платежей для игрока А:
-
1
2
3
4
5
min
1
2
6
-4
2
-8
-8
2
-7
-1
-5
1
6
-7
3
5
-9
-6
8
-1
-9
4
8
6
-3
0
5
-3
max
8
6
-3
8
6
Цена игры W=min max{aij}= max min{aij}= -3.
Так как W<0, игра выгодна для игрока B.
Игра 22 со смешанной стратегией, графический метод
При отсутствии седловой точки игрокам приходится использовать различные смешанные стратегии, и оптимизация состоит в определении оптимальных вероятностей или частот использования своих чистых или простых стратегий.
, (6)
где pi – вероятность i-й чистой стратегии игрока А,
qj – вероятность j -й чистой стратегии игрока В.
Оптимальная стратегия игрока А:
. (7)
Оптимальная стратегия игрока В:
. (8)
Цена игры – математическое ожидание выигрыша игрока А
. (9)
Если оба игрока имеют только по две стратегии, то задача легко решается как графически, так и аналитически; графическое решение очень наглядное и позволяет лучше уяснить общий алгоритм решения.
, р2=1–р1; , q2=1–q1.
Пример:
Матрица А платежей для игрока А:
-
Стратегии
игрока
А
Стратегии игрока В
1
2
1
-3
7
р1
2
4
6
р2
q1
q2
Найти графически и аналитически оптимальные стратегии для игроков А (р1, р2) и В (q1, q2), а также цену игры W.
Для игрока А. р2=1– р1. 1) При первой стратегии игрока В: –3р1+4р2= –3р1+4(1–р1)= –7р1+4; 2) При второй стратегии игрока В: 7р1–6р2=13р1–6.
Точка maxmin –7р1+4=13р1–6, откуда р1=1/2=0,5; р2=1– р1=1–0,5=0,5.
Для игрока В. q2=1– q1. 1) –3q1+7q2=–10q1+7; 2) 4q1–6q2=10q1–6.
Точка minmax –10q1+7=10q1–6, откуда q1=13/20=0,65; q2=1– q1=1– 0,65=0,35.
Цена игры W=–7∙0,5+4=13∙0,5–6=–10∙0,65+7=10∙0,65–6=0,5
Для игрока А Для игрока В
minmax
р1
q1
maxmin
В общем случае игры 22
, ,
,
.