Теория игр в информационной безопасности

Федеральное государственное бюджетное  
образовательное учреждение высшего образования  
«Московский государственный технический университет имени Н.Э. Баумана  
(национальный исследовательский университет)»
М.А. Басараб, Н.С. Коннова
Теория игр  
в информационной безопасности
Учебно-методическое пособие

УДК 519.8
ББК 22.18
	
Б27 
Издание доступно в электронном виде по адресу
ebooks.bmstu.press/catalog/117/book2060.html
Факультет «Информатика и системы управления»
Кафедра «Информационная безопасность» 
Рекомендовано Научно-методическим советом  
МГТУ им. Н.Э. Баумана в качестве учебно-методического пособия 
Рецензент
руководитель научно-учебного комплекса «Информатика  
и системы управления» МГТУ им. Н. Э. Баумана, д-р техн. наук, 
профессор А.В. Пролетарский
 
Басараб, М.А.
Б27	
	
Теория игр в информационной безопасности : учебно-методическое пособие / М. А. Басараб, Н. С. Коннова. — Москва : 
Издательство МГТУ им. Н. Э. Баумана, 2019. — 80, [4] с. : ил.
ISBN 978-5-7038-5170-8 
Рассмотрены различные методы решения задач теории игр. Приведены методические указания для выполнения лабораторных работ 
и  расчетно-графического домашнего задания по дисциплинам «Теория игр и исследование операций», «Методы теории игр в информационной безопасности».
Пособие предназначено для студентов и магистрантов МГТУ 
им. Н.Э. Баумана, обучающихся по специальностям «Информационная безопасность», «Информационная безопасность автоматизированных систем» и «Компьютерная безопасность», а также студентов 
и аспирантов других специальностей, интересующихся современными 
методами решения практических задач теории игр. 
УДК 519.8
ББК 22.18 
©	 МГТУ им. Н.Э. Баумана, 2019
©	 Оформление. Издательство  
	
МГТУ им. Н.Э. Баумана, 2019 
ISBN 978-5-7038-5170-8 

Предисловие
Настоящее учебно-методическое пособие содержит основные 
сведения по теории игр, а также описания восьми лабораторных работ, необходимых для закрепления изученного материала, с подробным разъяснением хода выполнения каждой работы. 
В лабораторных работах исследуются задачи по принятию решений в условиях неопределенности, теории матричных игр. 
Ряд работ имеет отношение к области информационной безопасности, в частности к выбору оптимального набора средств 
безопасности (задача о покрытии), моделированию действий инсайдера (матричная игра).
При выполнении лабораторных работ целесообразно воспользоваться либо готовыми программными пакетами математического моделирования (MATLAB, MathCAD), электронными 
таблицами (MS Excel), либо собственными программами, написанными на языке программирования высокого уровня. 
В отчете о выполнении каждой лабораторной работы необходимо последовательно и полно представить все основные шаги 
метода (алгоритма), вывод промежуточных результатов и  необходимые комментарии, демонстрирующие понимание сути процедуры. Студент должен быть знаком с таким понятием, как вычислительная сложность метода, уметь провести качественный 
анализ его в сопоставлении с другими методами, быть способным 
лаконично ответить на предложенные контрольные вопросы.
Помимо этого в пособии приведены исходные данные для выполнения расчетно-графического домашнего задания по рассматриваемой тематике. 

Введение
В данном пособии рассматриваются задачи теории игр, где 
ключевым понятием является выбор стратегий поведения участниками конкретной игры. Рассматриваются проблемы выбора 
и принятия решений в условиях конфликта интересов различных 
игроков.
Игра описывается перечнем игроков, набором стратегий для 
каждого игрока и указанием выигрышей, или платежей, игроков 
для каждой комбинации стратегий (ситуации в игре). Существуют 
различные виды игр (индивидуальные и кооперативные, антагонистические и неантагонистические, параллельные и последовательные, конечные и бесконечные, с полной и неполной информацией и т. д.), а также разные формы их задания (нормальная, 
развернутая формы, характеристическая функция и др.). В большинстве рассматриваемых игр, кроме специально оговоренных 
классов, предполагается, что игроки делают свои ходы одновременно, т. е. в условиях неопределенности, неосведомленности 
о выборе стратегии соперником.
В нормальной, или стратегической, форме игра описывается платежной матрицей. Строки определяют стратегии первого 
игрока, столбцы — второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. 
При решении производственных, управленческих, организационно-технических и других задач в области информационной 
безопасности часто приходится иметь дело с проблемой выбора 
одного варианта (оптимального или квазиоптимального) среди 
множества альтернативных решений. 
В зависимости от целевой функции и характера ограничений 
такого рода задачи можно условно разбить на два типа.
1. Задачи оптимизации. Предполагается, что ограничения известны, и необходимо найти экстремальное решение, доставляющее минимум либо максимум функционалу того или иного 
вида. Задачи конечномерной оптимизации с одной целевой функ4

цией называются также задачами математического программирования.
2. Задачи теории игр (принятие решений в условиях неопределенности). Поиск оптимального решения (стратегии) осуществляется при априори неизвестных действиях другого игрока 
(игроков), имеющего собственные интересы, либо состояниях 
внешней среды («игра с Природой»). 

1. МАТРИЧНЫЕ ИГРЫ С НУЛЕВОЙ СУММОЙ. 
СМЕШАННЫЕ СТРАТЕГИИ
В антагонистических играх сумма всех выигрышей равна сумме всех проигрышей для любого хода. Именно поэтому их еще 
называют играми с нулевой суммой. В платежных матрицах таких 
игр, как правило, записывается одно число — оно является как 
выигрышем одного игрока, так и проигрышем другого (или выигрышем с обратным знаком).
Формулировка матричной игры. В общем случае игра двух игроков, A и B, с нулевой суммой записывается в виде матрицы стратегий: 
Стратегии
b1
b2
…
bn
a1
c11
c12
…
c1n
a2
c21
c22
…
c2n
…
…
…
…
…
am
cm1
cm2
…
cmn
Здесь cij  — выигрыш первого игрока (проигрыш второго игрока) 
при реализации ими их стратегий a
i
m
b
j
n
i
j
,
,...,
,
,
,..., ,
=
=
1
1
 
соответственно.
Минимальный гарантированный выигрыш игрока A называется нижней ценой игры. Он равен maxmin
.
i
j
ij
c
 При плохой игре 
игрока В выигрыш может быть и большим. Минимально возможный проигрыш игрока B, равный minmax
,
j
i
ij
c
 называется верхней 
ценой игры. 
Теорема о минимаксе. Пусть (
)
cij  — произвольная матрица 
m
n
× ,  тогда
maxmin
minmax
,
i A
j B
ij
j B
i A
ij
c
c
∈
∈
∈
∈
≤
6

где
A
m B
n
=
=
1
1
,...,
;
,..., .
Если нижняя и верхняя цены игры равны, их значения называются ценой игры.
Теорема о седловой точке. Для (
)
cij  — произвольной матрицы 
m
n
×
 
maxmin
minmax
,
i A
j B
ij
j B
i A
ij
c
c
∈
∈
∈
∈
=
где A
m B
n
=
=
1
1
,
,
, , тогда и только тогда, когда (
)
cij  имеет седловую точку ( ,
),
i
j
0
0
 для которой ci j
0 0  является одновременно минимальным элементом строки и максимальным элементом столбца, 
и maxmin
minmax
i A
j B
ij
j B
i A
ij
i j
c
c
c
∈
∈
∈
∈
=
=
0 0  — цена игры.
Стратегии обоих противников в задачах с седловой точкой называются оптимальными и не зависят от дополнительно полученной информации.
Смешанные стратегии. Если игровая задача не имеет седловой 
точки, то на практике конкурирующие игроки применяют смешанные стратегии, т. е. попеременно используют две и более стратегий. 
По определению,
x * — оптимальная частота выбора стратегии для игрока A,
y * — оптимальная частота выбора стратегии для игрока B, 
если
E x y
E x
y
E x
y
,
*
*,
*
*,
,
(
) ≤
(
) ≤
(
)
где E — математическое ожидание выигрыша.
Рассмотрим произвольную игру с матрицей стратегий
c
c

11
1
n
	
C =







c
c
...
...
...
...
...
.	
(1.1)
m
mn
1


Смешанная стратегия игрока A — это упорядоченная система  m действительных неотрицательных чисел xi,  i
m
= 1,...,
,  такая, что
7

m
xi
i
1
1.
=
∑
=
Обозначим Sm  — множество всех смешанных стратегий игрока A.
Аналогично определяется смешанная стратегия игрока B — 
y j,  j
n
= 1,..., :
n
y j
j
1
1.
=
∑
=
Здесь Sn  — множество всех смешанных стратегий игрока B.
Стратегия игрока A, когда 
x
x
x
x
x
x
i
i
i
m
1
2
1
1
2
0
=
=
=
=
=
=
=
=
−
+
+
...
...
,
а
xi = 1,
называется i-й чистой стратегией. Аналогично определяется j-я 
чистая стратегия игрока B.
Если смешанная стратегия игрока A
X
x
xm
= (
,...,
),
1
а смешанная стратегия игрока B
Y
y
ym
= (
,...,
),
1
то математическое ожидание выигрыша игрока A составляет
n
m
(
,
)
.
=
E X Y
c x y
ij
i
j
i
j
=
= ∑
∑
1
1
Если существуют стратегии
X
Sm
*
,
∈
  Y
Sn
*
,
∈
такие, что для любых X
Sm
∈
,  Y
Sn
∈
 выполняются неравенства
E X Y
E X
Y
E X
Y
,
*
*,
*
*,
,
(
) ≤
(
) ≤
(
)
8

то X
Y
*,
*  называются оптимальными смешанными стратегиями 
игроков A, B; E X
Y
*,
*
(
)  — цена игры для игрока A; X
Y
*,
*  — 
решение игры, или стратегическая седловая точка.
Основная теорема прямоугольных игр (теорема Неймана). 
Пусть задана матрица стратегий (1.1) и выбраны стратегии Х  = 
=
∈
(
,...,
)
,
x
x
S
m
m
1
 Y
y
y
S
m
n
=
∈
(
,...,
)
;
1
 математическое ожидание 
выигрыша игрока A имеет вид
n
m
(
,
)
;
=
E X Y
c x y
ij
i
j
i
j
=
= ∑
∑
1
1
тогда
max min
(
,
)
min max
(
,
)
(
*,
*),
X S
Y S
Y S X S
m
n
n
m
E X Y
E X Y
E X
Y
∈
∈
∈
∈
=
=
где (
*,
*)
X
Y
 — стратегическая седловая точка.
Сведение матричной игры к задаче линейного программирования. 
Рассмотрим прямоугольную игру с нулевой суммой и матрицей 
стратегий (1.1). Пусть 
min
(
,
)
(
),
Y Sn
E X Y
g X
∈
=
тогда для любых X
Sm
∈
,  Y
Sn
∈
 имеем
E X Y
g X
(
,
)
(
).
≥
В частности, для любой чистой стратегии Y j  и любых X
Sm
∈
 
m

E X Y
c x
g X
j
n
(
,
)
(
),
,..., ,
1
=
≥
=
∑
j
ij
i
i
1
=


	
(1.2)
	

m
x
i
m
x
0
1
1.
,
,...,
,
≥
=
=
i
i
∑


1
i
=

Пусть g X
(
)
.
> 0  Разделим почленно обе части неравенства 
(1.2) на g X
(
)  и положим
u
x
g X
i
m
i
i
=
=
(
),
,...,
.
1
9