Теория игр
.pdfa11t1 |
|
|
a21t2 |
am1tm |
1, |
|||||||||||
a t |
|
|
a t |
|
a |
m2 |
t |
m |
1, |
|||||||
12 1 |
|
|
|
22 2 |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a2nt2 am ntm |
1, |
|||||||||
a1nt1 |
|
|
||||||||||||||
T |
|
1 |
t |
|
t |
|
|
|
|
t |
|
|
|
|
min |
|
|
2 |
|
m |
|
|
|||||||||||
|
|
v |
1 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
t |
|
|
|
|
|
|
|
|
|
|
|
|
||||
0, |
i 1, m |
|
|
|
|
|
|
|
|
|||||||
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
При построении целевой функции учитываем, что цена игры для первого игрока максимизируется.
Аналогично имеем для второго игрока систему неравенств:
a11y1 |
a12 y2 |
|
a1n yn |
|
v, |
|
|
|
|
|
||||||||||||||||||
a |
y |
a |
22 |
y |
2 |
|
|
a |
2n |
y |
n |
|
v, |
|
|
|
|
|
||||||||||
|
21 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
m1 |
y |
a |
n2 |
y |
2 |
a |
m n |
y |
n |
|
v, |
|
|
|
|
|
|||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
y2 |
|
|
|
ym |
|
|
|
|
|
1. |
|
|
|
|
|
|||||||
y1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
Разделив на цену игры и введя новые переменные u |
|
|
y j |
, получим ЗЛП для |
||||||||||||||||||||||||
j |
v |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
второго игрока: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
a11u1 |
|
|
|
a12u2 |
a1nun |
1, |
|
|
|
|
||||||||||||||||||
a u |
|
|
|
a u |
|
a |
2n |
u |
n |
1, |
|
|
|
|
||||||||||||||
|
21 1 |
|
|
|
|
|
22 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
u |
|
|
|
|
|
|
|
a |
|
|
|
1, |
|
|
|
|
|||||||||||
a |
|
|
|
a |
m2 |
u |
2 |
|
u |
|
|
|
|
|||||||||||||||
|
m1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
m n n |
|
|
|
|
|
||||||
Z |
|
1 |
u1 |
|
u2 |
|
|
um |
|
|
max |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
v |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
j 1, n. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
u j 0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Здесь целевая функция задана на максимум, т.к. цена игры для второго игрока минимизируется.
В результате получили пару симметричных двойственных ЗЛП. Согласно первой теореме двойственности, Tmin Zmax , следовательно, цена игры v имеет одно и тоже значение для обоих игроков.
Понятие об игре с природой (статистические игры)
Здесь один из участников – человек или группа лиц с общей целью – т.н. статистик (игрок А), другой участник – природа (игрок П), или весь комплекс
11
внешних условий, при которых статистику приходится принимать решение. Природа безразлична к выигрышу и не стремится обратить в свою пользу промахи статистика.
Статистик имеет m стратегий A1, A2 ,..., Am ; природа может реализовать n различных состояний П1, П2 ,..., Пn . При этом могут быть известны вероятности p1, p2 ,...pn реализации состояний природы. Если статистик может оценить
применение каждой своей стратегии при любом состоянии природы, то игру можно задать платежной матрицей:
|
П1 |
П2 |
… |
Пn |
A1 |
a11 |
a12 |
… |
a1n |
A2 |
a21 |
a22 |
… |
a2n |
… |
… |
|
|
|
Am |
am1 |
am2 |
… |
amn |
pj |
P1 |
P2 |
… |
Pn |
При упрощении платежной матрицы нельзя отбрасывать те или иные состояния природы, т.к. природа может реализовать любое из своих состояний независимо от того, выгодно это статистику или нет. Природа может даже помогать игроку А.
При выборе оптимальной стратегии статистика пользуются различными критериями. При этом опираются как на платежную матрицу, так и на матрицу рисков.
Риск статистика rij |
max aij aij . Матрица рисков имеет ту же размерность, |
||||
|
|
|
|
i |
|
что и платежная матрица: |
|||||
r |
r |
... |
r |
|
|
|
11 |
12 |
|
1n |
|
r21 |
r22 ... |
r2n |
|||
R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
rm2 ... |
|
|
|
rm1 |
rm n |
Пересчет из платежной матрицы в матрицу рисков производится по столбцам: в каждом столбце платежной матрицы выбирается наибольший элемент, который в матрице рисков заменяют нулем, а остальные элементы столбца матрицы рисков получают вычитанием соответствующих элементов из этого наибольшего элемента.
Если вероятности состояний природы известны, используется критерий Байеса: выбирается та стратегия, которая обеспечивает максимальную величину среднего выигрыша статистика:
|
|
|
n |
|
i |
|
i |
|
|
max ai max |
|
aij p j |
j 1
При неизвестных вероятностях состояний природы применяется принцип недостаточного основания Лапласа, когда все состояния считаются равновероятными:
12
p1 p2 pn 1n
Тогда средний выигрыш по каждой стратегии рассчитывается как среднее арифметическое выигрышей по всем возможным состояниям природы:
|
|
|
1 |
n |
|
max |
|
max |
aij |
||
ai |
|||||
|
|||||
i |
|
i |
n j 1 |
||
|
|
|
Эквивалентный подход заключатся в подборе стратегии, обеспечивающей наименьший средний риск статистика:
|
|
|
n |
|
i |
|
i |
|
|
min ri min |
|
rij p j |
j 1
при известных вероятностях состояний природы и
|
|
|
1 |
n |
|
|
rij |
||||
min |
ri |
min |
|||
|
|||||
i |
|
i |
n j 1 |
||
|
|
|
в случае, если эти вероятности неизвестны. При таком подходе результат будет точно таким же, что и при анализе наибольшего среднего выигрыша.
Если вероятности состояний природы неизвестны, то более широко используются критерии Вальда, Сэвиджа и Гурвица.
Оптимальной по критерию Вальда считается стратегия Аi, которая обеспечивает из всех наименьших выигрышей наибольшее значение. В этом случае из матрицы выигрышей (т.е. платежной матрицы) в каждой строке выбирается наименьший элемент, а затем среди этих элементов выбирается наибольший:
Wmax min aij
ij
По критерию Сэвиджа оптимальной считается стратегия, которая минимизирует величину максимального риска, т.е. из каждой строки матрицы рисков выбирается максимальный элемент, а затем среди этих элементов выбирается строка, в которой находится минимальный элемент:
S min max rij
i j
Оптимально по критерию Гурвица считается стратегия, найденная из условия:
H max |
min a |
1 max a |
|
, |
|||
i |
|
j |
ij |
j |
ij |
|
|
|
|
|
|
|
где 0,1 - «коэффициент пессимизма». При χ=1 имеем критерий Вальда,
или критерий крайнего пессимизма, при χ=0 – критерий «крайнего оптимизма». Рекомендуется выбирать χ между нулем и единицей, из субъективных соображений.
В результате применения нескольких критериев они сравниваются между собой, и в качестве наилучшей выбирается та стратегия статистика, которая чаще других фигурирует в качестве наилучшей.
13