С.В. Вельц
6
1 1
0 1
cont
cont
alarm
cont
P t = P t
– P t ,P =
(6)
Функционал качества:
cont
1 ,
v
t
Q S,D = P t
P S =
(7)
где
,
A
Q S,D = Q S,D
(8)
.
B
Q S,D = Q S,D
(9)
Оптимизация мониторинга.
Модуль оптимизации решает зада-
чу нахождения оптимальной стратегии мониторинга социальной сети
(для игрока Б) и оптимальной стратегии атаки (для игрока А). Эта
задача разбивается на две: нахождение равновесия в смешанных
стратегиях и эффективное нахождение чистых стратегий (максими-
зация функционалов 8 и 9).
Алгоритм поиска равновесия в смешанных стратегиях.
При
применении модели Штекельберга к поставленной задаче возникает
проблема с заданием игры. Рассмотрим упрощенный случай, когда
защитник выбирает
k
узлов из
N
для мониторинга в начальный мо-
мент времени и на протяжении игры они остаются фиксированными.
Аналогично атакующий выбирает
m
узлов, из которых будет начата
атака. В этом случае матрица выигрышей будет иметь размер-
ность
k
N
C
на
m
N
C
. Для значений параметров, которые на
1000,
N >
~ 100,
~ 100
k
m
практике можно считать весьма скромными, дан-
ная задача вычислительно неразрешима. Поэтому требуются специ-
альные методы решения.
Избежать представления игры в нормальной форме можно за счет
подхода на основе двух оракулов [23]. Отличие данной работы от
[24] заключается в использовании нового иерархического алгоритма
в качестве оракулов.
Суть метода двух оракулов заключается в постепенном построе-
нии смешанных стратегий для каждого из игроков, в предположении,
что у нас есть некоторый алгоритм (оракул), который вычислит оп-
тимальную чистую стратегию в ответ на смешанную стратегию про-
тивника.
