Теоретико-игровые модели поиска и патрулирования на графах тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Гусев Василий Васильевич

• Гусев Василий Васильевич
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Гусев Василий Васильевич

Оглавление

Введение

1 Глава 1. Поиск неподвижного объекта на графе

1.1 Постановка задачи

1.2 Значение игры G(Q, T, 1)

1.3 Значение игры G(Q, T, m) для цикла

1.4 Значение игры G(Q, T, m) для звезд

1.5 Значение игры G(Q, T, m) для линейного графа

1.6 Игра G(Q, T, m) для модели жилого дома

1.7 Средняя длина маршрута патрулирующего

1.8 Значение игры G(Q, T, m) для ориентированного графа,

максимальная длина маршрута в котором равна

1.9 Игра патрулирования с камерой слежения

1.10 Значение игры G(Q, T, m) для ориентированного дерева

2 Глава 2. Векторы Шепли, Оуэна и Ауманна - Дрезе в

игре патрулирования с коалиционой структурой

2.1 Теоретико-игровая модель

2.2 Нахождение начального оптимального распределения ме-

стоположения игроков

3

2.3 Игра с двумя патрулирующими и одним атакующим

2.4 Нахождение матрицы перехода

2.5 Кооперативная игра с коалиционной структурой

2.6 Характеристическая функция

2.7 Распределение выигрыша между патрулирующими

2.7.1 Вектор Шепли

2.7.2 Вектор Ауманна-Дрезе

2.7.3 Вектор Оуэна

2.8 Вектор Оуэна для разных коалиционных структур

3 Глава 3. Поиск подвижного объекта

3.1 Постановка задачи

3.2 Одношаговая игра

3.3 Многошаговая игра

3.4 Существование равновесия

3.5 Решение одношаговой игры

3.6 Решение игры для линейного графа

3.7 Решение двухшаговой игры

3.8 Решение многошаговой игры

3.9 Решение одношаговой игры с произвольной вероятностью

обнаружения

4

3.10 Работа с программным комплексом

Заключение

Библиография

Приложения

5

Введение диссертации (часть автореферата) на тему «Теоретико-игровые модели поиска и патрулирования на графах»

Введение

В современной науке представлен ряд работ, посвященных поиску объек-

тов. Так, например, в работах Альперна и др. [1-4] представлены методы

и алгоритмы поиска неподвижного прячущегося, оцениваются вероят-

ности его для разных видов графов. Если бы данные модели являлись

теоретико-игровыми, прикладной характер исследования был бы более

выражен. Моделей поиска с применением аппарата математической тео-

рии игр достаточно много, примерами могут служить работы Бастона и

др. [8,9,21-28,50]. Авторов интересуют не только значение игры, но и вид

оптимальных маршрутов, средняя длина пути, время поиска и другие

характеристики.

На практике ищущих игроков может быть много, вследствие чего

возникают вопросы, связанные с распределением выигрыша (заработ-

ной платы). Работы, связанные с кооперативной теорией игр, могут быть

разделены на два класса: посвященные изучению свойств дележей, на-

пример работы Оуэна и др. [31,32,44] и вычислению выигрышей игроков,

например работы [10,74].

Прячущийся игрок может быть мобильным, что отражено в дина-

мических моделях. В [33-36,38,39,46] осуществляется поиск подвижного

объекта, составляется уравнение Беллмана, которое моделирует процесс

 6

поиска: игра переходит на следующий уровень, если игрок на текущем

отрезке не обнаружен. В [52-55] представлены модели, а также методы

поиска, в которых начальная позиция прячущегося игрока известна иска-

телю, после чего допускаются некоторые ограничения на поиск и состав-

ляется математическая модель. Отметим, что, если подвижных игроков

будет больше одного, то уравнения Беллмана, вероятности обнаружения

и аналитические результаты, представленные в вышеперечисленных ра-

ботах, будут кардинально меняться.

Актуальность темы. Игры поиска представляют собой современ-

ное направление теории игр. Такие игры возникают в военных прило-

жениях, задачах распределения ресурсов, охраны объектов и др. Дан-

ные проблемы широко освещены в работах современных исследовате-

лей. Указанные виды игр рассматриваются как в статической (задача с

неподвижным прячущимся), так и в динамической (задача с подвижным

прячущимся) постановках. Классической задачей теории поиска являет-

ся задача, в которой один участник прячет объект, а другой распределяет

ресурсы так, чтобы его обнаружить. Ищущий заинтересован в миними-

зации времени обнаружения объекта, а прячущий старается это время

максимизировать. Следовательно, задачу поиска можно изучать как иг-

ру с нулевой суммой, в которой под значением игры понимается вероят-

ность, с которой ищущий найдет спрятанный объект. Значительно мень-

 7

ше число работ посвящено задачам патрулирования, которые актуальны

при охране ценных коллекций музеев, художественных галерей, банков и

других объектов. Владельцы недвижимого имущества заинтересованы в

том, чтобы маршруты охранников были оптимальны. В качестве охран-

ника заявлен ищущий или патрулирующий игрок, а прячущий выступа-

ет в роли атакующего, который пытается причинить ущерб охраняемому

объекту. В зависимости от действий и возможностей игроков могут быть

получены различные вариации игры и решены следующие вопросы:

1. При каком минимальном количестве патрулирующих выигрыш в

игре максимален?

2. Как изменятся маршруты патрулирующих, если на местности бу-

дут установлены камеры слежения, добавлены новые маршруты, поменя-

ется алгоритм поиска, расширены или уменьшены допустимые стратегии

игроков (т. е. в игру введены дополнительные параметры)?

3. Как изменится выигрыш патрулирующего, если атакующий пере-

станет быть пассивным и окажет сопротивление?

В некоторых случаях предполагается, что на охраняемой местности

установлена камера слежения, т.е. как только атакующий появится на

объекте, об этом сразу же узнает патрулирующий и направится к ме-

сту атаки. Отметим, что термины "прячущийся объект"и "подвижный

игрок"яляются синонимами.

 8

Если патрулирующих игроков несколько, то стоит поднять вопрос о

справедливом дележе выигрыша (заработной платы). Распределение вы-

игрыша между игроками в кооперативной игре является важной задачей

теории игр. Популярными способами дележа являются C-, N-, K-ядро,

вектор Шепли. Иногда участники игры могут образовывать коалици-

онные структуры, тогда выигрыш каждого игрока можно вычислить,

например, используя вектор Оуэна или Ауманна-Дрезе. Каждый спо-

соб распределения выигрыша обладает своими достоинствами и недо-

статками, следовательно, выбранный способ дележа необходимо четко

аргументировать. Традиционно игры патрулирования исследуются как

некооперативные игры. В данной работе так же рассматривается игра

патрулирования с коалиционной структурой.

Целью диссертационной работы является разработка методов и

алгоритмов для построения решений в теоретико-игровых моделях по-

иска и патрулирования.

Поставленные задачи. 1. Нахождение оптимальных маршрутов

патрулирования для графов различной топологии и нахождение значе-

ния игры. 2. Оптимизация распределения выигрыша между патрулиру-

ющими на основе методов кооперативной теории игр. 3. Нахождение оп-

тимального распределения поисковых ресурсов в динамической модели

поиска нескольких объектов.

 9

Научная новизна работы. Все данные, полученные в ходе иссле-

дования, вводятся в научный оборот впервые. Найдено значение игры

патрулирования для разных видов графов. Сложность нахождения рав-

новесия в рассматриваемой игре заключается в том, что число маршру-

тов патрулирующего при большом количестве вершин графа высоко. В

настоящей работе проводится сравнение выигрыша патрулирующего в

игре без установленных камер слежения с выигрышем патрулирующе-

го при видеосъемке. Получены новые результаты для графа, который

является моделью жилого дома.

Впервые изучены значения вектора Оуэна в кооперативной игре пат-

рулирования с коалиционной структурой. Проведено сравнение значений

вектора Оуэна со значениями вектора Ауманна-Дрезе.

Усовершенствована многошаговая модель поиска подвижного игро-

ка. Предполагаем, что при наличии двух прячущихся игроков функции

выигрышей кардинально меняются. Кроме того, предложено распреде-

ление бюджета по группам вершин, имеющих общего родителя. В данной

модели получены новые результаты, связанные с распределением бюд-

жета, поведением подвижных игроков.

Теоретическая и практическая значимость. Найденные значе-

ния игры патрулирования и оптимальные стратегии охранников могут

быть использованы при выборе места размещения того или иного ценно-

 10

го предмета. Дана прикладная интерпретация значений вектора Оуэна,

которые могут быть использованы при распределении заработной платы,

если с игроками заключен трудовой договор найма. В соответствии с ре-

шением многошаговой игры поиска можно оценивать, какая из вершин

графа более предпочтительна для подвижных игроков и какую долю

бюджета стоит туда направить для эффективного поиска.

Получено свидетельство о государственной регистрации программы

для ЭВМ № 2017614131 "Программа для поиска оптимальных путей в

задаче патрулирования".

Положения, выносимые на защиту.

1. Разработаны методы нахождения оптимальных стратегий в моде-

ли поиска неподвижного объекта для графов различной топологии, в

частности, для ориентированных графов.

2. Предложено для распределения выигрыша в задаче поиска втор-

жения использовать вектор Оуэна и Ауманна-Дрезе.

3. Предложена и исследована многошаговая модель поиска двух по-

движных объектов с фиксированным бюджетом искателя на каждом ша-

ге.

4. Реализован алгоритм сокращения маршрутов и атак игроков в виде

комплекса программ для нахождения равновесных стратегий патрулиру-

ющего и атакующего.

 11

Методы исследования включают: методы динамического програм-

мирования, линейное и нелинейное программирование, теория графов,

методы математической теории игр, дискретный анализ.

Апробация работы. Результаты диссертационной работы были

представлены и обсуждались на научных конференциях: 1. NGM-2015,

International Workshop Networking Games and Management, Petrozavodsk-

2015, Institute of Applied Mathematical Research Karelian Research Centre

of RAS (2015), г. Петрозаводск. 2. Международная научная конференци-

ей «Теория игр и менеджмент – 2015» (GTM-2015), г. Санкт-Петербург.

3. NGM-2016, International Workshop Networking Games and Management,

Petrozavodsk-2016, Institute of Applied Mathematical Research Karelian

Research Centre of RAS (2016), г. Петрозаводск. 4. Международная на-

учная конференцией «Теория игр и менеджмент – 2016» (GTM-2016), г.

Санкт-Петербург. GTM 2016. 5. VIII Moscow International Conference on

Operations Research (ORM 2016). Moscow, October 2016.

Методы исследования включают: методы динамического програм-

мирования, линейное и нелинейное программирование, теория графов,

методы математической теории игр, дискретный анализ.

Публикации. По теме диссертации опубликовано 9 работ, из них 4

статьи в рецензируемых журналах из списка ВАК РФ и 5 работ опубли-

ковано в материалах тезисов докладов.

 12

Личный вклад автора. Все представленные в диссертации резуль-

таты получены автором лично.

Структура и объем диссертации. Работа состоит из введения,

трех глав, разбитых на подразделы, списка литературы и приложения.

Текст содержит 13 рисунков и 21 таблицы. Общий объем диссертации

составляет 139 страниц. Библиографический список включает 75 наиме-

нований.

Содержание работы

Во введении обосновывается актуальность темы исследования, фор-

мулируется цель работы, дается обзор научной литературы по изучаемой

проблеме, приводится краткое содержание глав.

В первой главе рассматривается теоретико-игровая модель патрули-

рования на графе, в котором атакующий имеет m единиц времени для

атаки некоторой вершины графа, а стратегией патрулирующего является

выбор маршрута в графе. Найдены равновесие в игре с нулевой суммой

и средняя длина патрулирования для различных графов.

Рассмотрим игру патрулирования G =< P, A; Q; S1 , S2 ; H >, в ко-

торой P – патрулирующий; A – атакующий; Q =< V, E > – неориен-

тированный граф, где V – множество вершин, E – множество ребер,

n = |V | - количество вершин в графе. Вершины графа Q будем обозна-

чать vj , j = 1, ..., n, запись vj = 0 означает, что vj не является вершиной.

 13

Две разные вершины графа могут соединяться только одним ребром, мо-

жет существовать ребро вида (vk , vk ). Заметим, что граф Q может быть

несвязным.

Множество стратегий патрулирующего S1 представляет маршруты

патрулирования u = vk1 − vk2 − ... − vkT , где ∀j = 1, ..., T : vkj ∈ V, 1 ≤

kj ≤ n, T ≥ 1; ∀t = 1, ..., T − 1 : (vkt , vkt+1 ) ∈ E. Элементы множества S2

(стратегии атакующего), которые будем называть атаками, представим

... − 0} − v| − {z

в виде 0| − {z ... − v} − 0 − ... − 0 t = 1, ..., T − m + 1, или более

t−1 m

кратко w = (t, v), где t момент посещения вершины v.

Функцией выигрыша H(u, w), u ∈ S1 , w ∈ S2 , является вероятность

поимки атакующего игрока патрулирующим игроком:



0, ∀j = 1, ..., m : vk 6= v;

t+j

H(u, w) =

1, ∃j = 1, ..., m : v = v.

kt+j

Если H(u, w) = 1, то будем говорить, что маршрут u ловит атаку w.

Игру G =< P, A; Q; S1 , S2 ; H > для краткости запишем как G (Q, T, m),

где m – время, которое необходимо атакующему для проведения атаки;

T – длина маршрута (m ≤ T ). Нас будут интересовать в данной игре

ситуация равновесия и значение игры.

Лемма 1.1.1. Пусть патрулирующий выбирает путь u ∈ S1 . Тогда

патрулирулирующий ловит не более m (T − m + 1) атак атакующего.

Теорема 1.3.1. Обозначим σk = (k + 1, k + 2, ..., n, 1, 2, ..., k), k =

 14

0, ..., n−1 – перестановку чисел 1, 2, 3, . . . , n; σk (j) – j-й элемент набора

σk . Введем σk0 , где k 0 > n − 1, σk0 (j) = σk0 mod n (j). Если патрулирующий

выбирает маршруты из множества



S1 = vσ0 (j) − vσ1 (j) − vσ2 (j) − ... − vσT −1 (j) |j = 1, ..., n ,

1

с вероятностью n, а атакующий – все стратегии из S2 с вероятно-

1

стью n(T −m+1) , то такой набор стратегий будет ситуацией равновесия

со значением игры H ∗ = min{ m

n , 1}.

Теорема 1.4.1. Пусть T ≥ m + 1; σ0 = (1, 2, 1, 3, ..., 1, n) - упорядо-

ченный набор чисел 2, 3, ..., n и единиц. Пусть σk при 0 < k ≤ 2(n−1)−1

получается из σ0 путем перемещения последних k чисел с конца в на-

чало. Если k > 2(n − 1) − 1, то σk = σk mod 2(n−1) . Если патрулирующий

выбирает маршруты из множества



S1 = vσ0 (j) − vσ1 (j) − vσ2 (j) − ... − vσT −1 (j) |j = 1, ..., 2(n − 1) ,

1

с вероятностью 2(n−1) , а атакующий – атаки из множества

( )

S2 = v|k − {z

... − v}k − 0 − ... − 0, 0 − v|k − {z

... − v}k − 0... − 0|k = 2, ..., n ,

m m

1

с вероятностью 2(n−1) , то такой набор стратегий будет ситуацией

равновесия со значением игры H ∗ = min{ 2(n−1)

m

, 1}.

Во второй главе исследуется модель кооперативной игры патру-

лирования с коалиционной структурой. Показано, что векторы Шепли,

 15

Оуэна и Ауманна-Дрезе в рассматриваемой игре совпадают друг с дру-

гом при нечетном количестве патрулирующих.

Введем характеристическую функцию игры. Зададим ее следующим

образом:

  h i

 1 1 + |K|−1 , P1 ∈ K;

m 2

v(K) = h i ,

1 |K|



m 2 , P1 ∈

/ K.

где |K| — количество патрулирующих в коалиции K ∈ N. Значение ха-

рактеристической функции v(K) равно вероятности поимки атакующего

коалицией K.

Теорема 2.7.1. Вектор Шепли в игре Γ(·) вычисляется по формуле



1

m, i = 1;









φi (v) = 1

2m , i 6= 1, N − нечетно;





N −2





2m(N −1) , i 6= 1, N − четно.

Теорема 2.7.2. Значения Ауманна-Дрезе в игре Γ(·) вычисляется

по формуле



1

m, i = 1;









φπi e = 1

2m , |B(i)|

= 2;







0, |B(i)| = 1, i 6= 1.

 16

Вектор Оуэна, вычисленный для эффективной коалиционной струк-

туры, совпадает с вектором Ауманна-Дрезе.

В третьей главе построена многошаговая модель поиска двух по-

движных обектов. Пусть G = hV, Ei – ориентированное дерево без петель

с фиксированным корнем, где V – множество вершин, E – множество

ребер. Все вершины графа перенумерованы, нулем обозначим корень де-

рева. E = {(i, j)} , i, j ∈ V , где (i, j) ∈ E, – ориентированное ребро гра-

фа G.Если (i, j) ∈ E, то вершину j будем называть потомком вершины

i. Обозначим L = {i|∃j ∈ V : (j, i) ∈ E; ∀l ∈ V : (i, l) ∈

/ E} – множество

листовых вершин G; ∀j ∈ V \ L определим ch(j) = {i|(j, i) ∈ E} – мно-

жество потомков вершины j. Предполагаем, что на множество E есть

два ограничения: 1. ∀j ∈ V, j 6= 0∃!i ∈ V : (i, j) ∈ E; 2. (i, i) ∈

/ E.

Пусть на шаге 1 (последний шаг) первый подвижный объект нахо-

дится в вершине g, второй в вершине l, g, l ∈ v(n − 1), g 6= l. Определим

игру

Γ(1, g, l, Φg , Φl ) = hI, II, III; P (g), Q(l), Ψ(g) ∪ Ψ(l); H1 (·), H2 (·), H3 (·)i ,

где I, II, III – игроки, P (g), Q(l), Ψ(g) ∪ Ψ(l) – множества стратегий

игроков

Определим функции выигрышей игроков на шаге 1.

X

H1 (1, p(g), ϕ(g)) = pi (1 − e−αi ϕi )

i∈ch(g)

 17

X

H2 (1, q(l), ϕ(l)) = qj (1 − e−αj ϕj )

j∈ch(l)

X X

H3 (1, p(g), q(l), ϕ(g), ϕ(l)) = pi qj (1 − e−αi ϕi −αj ϕj ),

i∈ch(g) j∈ch(l)

p(g) ∈ P (g), q(l) ∈ Q(l), ϕ(g) ∈ Ψ(g), ϕ(l) ∈ Ψ(l) (1)

∀i ∈ ch(g), ∀j ∈ ch(l) : pi ≥ 0, qj ≥ 0, ϕi ≥ 0, ϕj ≥ 0; (2)

X X X X

pi = 1, qj = 1, ci ϕi = Φg , cj ϕj = Φl . (3)

i∈ch(g) j∈ch(l) i∈ch(g) j∈ch(l)

Теперь определим игры Γ2 (k, g, l, Φg , Φl ), Γ1 (k, g, Φg ) на шагах 2, 3, ..., n.

Пусть на шаге k = 2, 3, ..., n первый и второй подвижные объекты нахо-

дятся в вершинах g, l, ∈ v(n − k − 1) соответстенно.

Γ(k, g, l, Φg , Φl ) = hI, II, III; P (g), Q(l), Ψ(g) ∪ Ψ(l); H1 (·), H2 (·), H3 (·)i ,

где функции выигрышей игроков имеют вид

X X

−αi ϕi

H1 (k, p(g), ϕ(g)) = pi (1 − e )+ pi e−αi ϕi H1∗ (k − 1, i, Φi ),

i∈ch(g) i∈ch(g)

X X

−αj ϕj

H2 (k, q(l), ϕ(l)) = qj (1 − e )+ qj e−αj ϕj H2∗ (k − 1, j, Φj ),

j∈ch(l) j∈ch(l)

X X

H3 (k, p(g), q(l), ϕ(g), ϕ(l)) = pi qj (1 − e−αi ϕi −αj ϕj )+

i∈ch(g) j∈ch(l)

X X

pi qj e−αi ϕi −αj ϕj H3∗ (k − 1, i, j, Φi , Φj ).

i∈ch(g) j∈ch(j)

 18

Лемма 3.4.1. В играх Γ1 (k, g, Φg ) и Γ2 (k, g, l, Φg , Φl ) существует рав-

новесие по Нэшу.

Теорема 3.5.1. В  игре Γ2 (1, g, l, Φg , Φl ) верны следующие

 равенства



−Φ

H1∗ (1, g, Φg ) = 1 − exp P g ci , H2∗ (1, l, Φl ) = 1 − exp P −Φl cj ,

i∈ch(g) αi j∈ch(l) αj

 

Φ

H3∗ (1, g, l, Φj , Φl ) = 1 − exp − P g ci − P Φl cj

i∈ch(g) αi j∈ch(l) αj

Теорема 3.8.1. Пусть оба подвижных объекта находятся в вершине

g на шаге n. Тогда оптимальные стратегии игроков имеют вид

" P cj #+

Φg /αi 1 j∈M (g) αj lnβj lnβi

ϕ∗i = P cj − P cj + ,

j∈M (j) αj αi j∈M (g) αj αi



ci /αi

P , i ∈ M (g);

j∈M (g) cj /αj

p∗i =

 0, i ∈

/ M (g).

В конце третьей главы приводится описание программного комплек-

са, разработанного для решения задач патрулирования.

 19

1 Глава 1. Поиск неподвижного объекта на

графе

1.1 Постановка задачи

Рассмотрим игру патрулирования G =< P, A; Q; S1 , S2 ; H >, в которой P

– патрулирующий; A – атакующий; Q =< V, E > – неориентированный

граф, где V – множество вершин, E – множество ребер, n = |V | - количе-

ство вершин в графе. Вершины графа Q будем обозначать vj , j = 1, ..., n,

запись vj = 0 означает, что vj не является вершиной. Две разные верши-

ны графа могут соединяться только одним ребром, может существовать

ребро вида (vk , vk ). Заметим, что граф Q может быть несвязным. В при-

мерах вершины графа обозначаются натуральными числами. Основные

определения в игрх на графах можно изучить в [5-9,11-16].

Множество стратегий патрулирующего S1 представляет маршруты

патрулирования u = vk1 − vk2 − ... − vkT , где ∀j = 1, ..., T : vkj ∈ V, 1 ≤

kj ≤ n, T ≥ 1; ∀t = 1, ..., T − 1 : (vkt , vkt+1 ) ∈ E. Элементы множества S2

стратегии атакующего, которые будем называть атаками, представим в

... − 0} − v| − {z

виде 0| − {z ... − v} − 0 − ... − 0 t = 1, ..., T − m + 1, или более

t−1 m

кратко w = (t, v), где t момент посещения вершины v.

 20

Введем индикатор встречи игроков h(u, w), u ∈ S1 , w ∈ S2 :



0, ∀j = 1, ..., m : vk 6= v;

t+j

h(u, w) =

1, ∃j = 1, ..., m : v = v. kt+j

Если h(u, w) = 1, то будем говорить, что маршрут u ловит атаку w.

Введем в расcмотрение смешанные стратегии игроков. Обозначим

x = (x1 , ..., x|S1 | ) и y = (y1 , ..., y|S2 | ) - смешанные стратегии игроков P

P|S1 | P|S2 |

и A соответственно, где xi ≥ 0, i=1 xi = 1, yj ≥ 0, j=1 yj = 1. Обозна-

P|S2 | P|S1 |

чим H(u, y) = j=1 yj h(u, wj ), H(x, w) = i=1 xi h(ui , w),

P|S1 | P|S2 |

H(x, y) = i=1 j=1 xi yj h(ui , wj ).

Игру G =< P, A; Q; S1 , S2 ; H > для краткости запишем как G (Q, T, m)

[63,57,58], где m – время, которое необходимо атакующему для проведе-

ния атаки; T – длина маршрута (m ≤ T ). Нас будут интересовать в

данной игре ситуация равновесия и значение игры. Игры поиска без ис-

пользования методов теории игр можно посмотреть в [1-4,21,25,26,29].

Сетевые игры изложены в [62,72]

Лемма 1.1.1. Пусть патрулирующий выбирает путь u ∈ S1 . Тогда

патрулирулирующий ловит не более m (T − m + 1) атак атакующего.

Д о к а з а т е л ь с т в о. Рассмотрим маршрут u = vk1 − vk2 − ... − vkT .

В первый момент времени патрулирующий находится в вершине vk1 .

В этом случае ловится одна атака vk1 − vk1 − ... − vk1 − 0 − ... − 0. За-

| {z }

m

тем патрулирующий переходит в вершину vk2 . Теперь ловятся две атаки

 21

vk2 − vk2 − ... − vk2 − 0 − ... − 0, 0 − vk2 − vk2 − ... − vk2 − 0 − ... − 0. ыделим

| {z } | {z }

m m

три случая. 1. Пусть патрулирующий находится в вершине vkt (t < m или

t > T − m). Тогда ловятся t атак атакующего. Путь u ловит не более

+ ... + m} + (m − 1) + ... + 2 + 1 атак, что

1 + 2 + ... + (m − 1) + |m + m {z

T −2(m−1)

равно m (T − m + 1). 2. Пусть T = 2(m − 1). Тогда u ловит не более

1 + 2 + ... + (m − 1) + (m − 1) + ... + 2 + 1 = 2(1 + 2 + ... + (m − 1)) =

m(m − 1) = m(T − T + m − 1) = m(T − 2m + 2 + m − 1) = m(T − m + 1)

атак. 3. Пусть T < 2(m − 1). Тогда u ловит не более 2(1 + 2 + ... + (T −

m + 1)) + (T − m + 1) + ... + (T − m + 1) = m(T − m + 1) атак. Во всех

| {z }

T −2(T −m+1)

трех случаях получаем m(T − m + 1) пойманных атак, что и требовалось

доказать.

Следствие 1.1.1. Пусть y – стратегия атакующего, при которой

игрок выбирает атаки из множества S2 c одинаковой вероятностью

1

|S2 | , а x – стратегия патрулирующего, при которой игрок равноверо-

ятно выбирает маршруты из множества {vk1 − vk2 − ... − vkT |∀t =

1, ..., T − m + 1; ∀l, j = t, ..., t + m − 1; vkl 6= vkj , l 6= j}. Тогда

H(u, y) ≤ H(x, y).

Д о к а з а т е л ь с т в о. Стратегии игроков x, y подобраны так, что

m(T −m+1)

H(x, y) = |S2 | . Путь u ловит не более m(T − m + 1) атак (лемма

m(T −m+1)

1.1.1), значит, H(u, y) ≤ |S2 | = H(x, y), что и требовалось доказать.

 22

P|S2 |

Обозначим A = max i=1 H(u, wi ), u0 - точка максимума. Чтобы оце-

u

нить выигрыш игры сверху, докажем следующую лемму.

Лемма 1.1.2. Значение игры H ∗ ≤ A

|S2 | .

Д о к а з а т е л ь с т в о. Пусть атакующий выбирает стратегии из S2 с

вероятностью 1

|S2 | . Обозначим эту стратегию как y. Тогда H(u0 , y) = A

|S2 | .

Поскольку u0 – точка максимума, то ∀u ∈ S1 H(u, y) ≤ H(u0 , y) = A

|S2 | , т.

A

е. maxH(x, y) = |S2 | ;

x

∗ A

H = minmaxH(x, y) ≤ |S2 | .

y x

1.2 Значение игры G(Q, T, 1)

Найдем значение игры когда время атаки равно единице и сформулируем

результат в виде теоремы 1.2.1.

Теорема 1.2.1. В игре G(Q, T, 1) H ∗ = 1

n [61].

Д о к а з а т е л ь с т в о. Пусть x – стратегия патрулирующего, при

которой игрок выбирает маршруты из множества {vk − vk − ... − vk |k =

1

1, ..., n} c вероятностью n и y – стратегия атакующего, при которой игрок

1

выбирает атаки из S2 c вероятностью nT . Поскольку H(x, w) = H(u, y) =

1

H(x, y) = n для ∀u ∈ S1 , w ∈ S2 , то стратегии x, y образуют ситуацию

равновесия(теорема 1.3. из [69]) со значением игры H(x, y) = n1 .

Пример 1.2.1. Пусть дан несвязный граф, который представлен в

виде цикла из трех вершин и одной отдельной вершины. Рассмотрим

 23

игру G(Q, 3, 1). Составим платежную матрицу для маршрутов и атак,

которые выбираются с положительными вероятностями (табл. 1.2.1.).

Таблица 1.2.1 Платежная матрица для маршрутов и атак в

игре G(Q, 3, 1), которые выбираются с положительной

вероятностью

1-0-0

0-1-0

0-0-1

2-0-0

0-2-0

0-0-2

3-0-0

0-3-0

0-0-3

4-0-0

0-4-0

0-0-4

1−1−1 1 1 1 0 0 0 0 0 0 0 0 0

2−2−2 0 0 0 1 1 1 0 0 0 0 0 0

3−3−3 0 0 0 0 0 0 1 1 1 0 0 0

4−4−4 0 0 0 0 0 0 0 0 0 1 1 1

1 1

Патрулирующий выбирает свои маршруты с вероятностью n = 4 ,

1 1

а атакующий – выбирает стратегии с вероятностью nT = 12 . Значение

1

игры H(x, y) = n = 14 .

1.3 Значение игры G(Q, T, m) для цикла

Рассмотрим игру G(Cn , T, m), где Cn – цикл из n вершин. Граф цикл яв-

ляется достаточно прикладным графом, потому что многие сооружения

как раз имеют такую форму. Значение игры для графа цикла и алгоритм

составления оптимальных путей представлены в теореме 1.3.1.

 24

Теорема 1.3.1. Обозначим σk = (k + 1, k + 2, ..., n, 1, 2, ..., k), k =

0, ..., n−1 – перестановку чисел 1, 2, 3, . . . , n; σk (j) – j-й элемент набора

σk . Введем σk0 , где k 0 > n − 1, σk0 (j) = σk0 mod n (j). Если патрулирующий

выбирает маршруты из множества



S1 = vσ0 (j) − vσ1 (j) − vσ2 (j) − ... − vσT −1 (j) |j = 1, ..., n ,

1

с вероятностью n, а атакующий – все стратегии из S2 с вероятно-

1

стью n(T −m+1) , то такой набор стратегий будет ситуацией равновесия

со значением игры H ∗ = min{ m

n , 1}.

Д о к а з а т е л ь с т в о. Пусть x – стратегия патрулирующего, при ко-

торой игрок выбирает маршрут из S1 с вероятностью n1 , а y - стратегия

атакующего, при которой игрок выбирает атаки из S2 c вероятностью

Список литературы диссертационного исследования кандидат наук Гусев Василий Васильевич, 2017 год

Библиография

1. Alpern S., Baston V., Gal. S. Network Search Games With Immobile

Hider, Without a Designated Searcher Starting Point. London: Centre

for Discrete and Applicable Mathematics. 2006-03. 16 p.

2. Alpern, S., Fokkink, R. and Simanjuntak, M. (2016) "Optimal search and

ambush for a hider who can escape the search region European Journal

of Operational Research, 251, 3, 707-714

3. Alpern S., Gal. S. The theory of search games and rendezvous. Boston:

Kluwer Academic Publishers, 2003.

4. Alpern S., Morton A., Papadaki K. Optimizing randomized patrols //

Operational Research Group. 2009. P. 392-419.

5. Auger, J. (1991) An inltration game on k arcs. Nav. Res. Logist. 38,

511-530.

6. Bachrach, Y., Markakis, E., Resnick, E., Procaccia, A. D., Rosenschein,

J. S., Saberi, A., Approximating power indices: theoretical and empirical

analysis // Autonomous Agents and Multi-Agent Systems. 2010. V. 20.

P. 105–122.

7. V.J. Baston and F.A. Bostock: A one-dimensional helicopter-submarine

 129

game. Naval Research Logistics, 36 (1989), 479–490.

8. V.J. Baston and A.Y. Garnaev: A search game with a protector, Naval

Research Logistics, 47 (2000), 85–96.

9. Benkoski S.J., Monticino M.G., Weisinger, J.R. A Survey of the Search

Theory Literature, Naval Research Logistics, 1991, vol. 18, pp. 469–494.

10. Belau J. A Note on the Owen Value for Glove Games// International

Game Theory Review (IGTR). 2015. V. 17, N 4. P. 1550014-1-1550014-

8.

11. Bier, V.M., Azaiez, M.N.: Defending against terrorism, natural disaster,

and all hazards. In: Bier, V.M., Azaiez, M.N. (eds.) Game Theoretic Risk

Analysis of Security Threats, International Series in Operations Research

Management Science, vol. 128, chap. 4, pp. 1–33. Springer, New York

(2009).

12. Brown, G., Carlyle, M., Salmeron, J. and Wood, K. (2006). "Defending

Critical Infrastructure". Interfaces 36, 530-544.

13. Burcher, R.and Rydill, L. Concepts in Submarine Design, University

Press, 1994.

14. Cohen, H., Mathematicsfor Scientists and Engineers, Prentice Hall Inc.,

 130

1992.

15. Devore J. L., Berk K. N. Modern mathematical statistics with applications.

– Cengage Learning, 2007.

16. Danskin J.M. The Theory of Max-Min and its Application to Weapons

Allocation Problems. With 6 figures. Econometrics and Operations Research,

V. Berlin, Heidelberg, New York, Springer-Verlag, 1967, IX p. 126.

17. J.M. Danskin: A helicopter versus submarine search game. Operations

Research, 16 (1968), 509–517.

18. J.N. Eagle and A.R. Washburn: Cumulative search-evasion games. Naval

Research Logistics, 38 (1991), 495–510.

19. Feng Zhao, Hai Jin Automated approach to intrusion detection in vm-

based dynamic execution environment Computing and Informatics, 2012,

vol. 31, pp. 271–297.

20. Fox, C. R., D. Bardolet, et al. . Partition dependence in decision analysis,

resource allocation and consumer choice. Experimental Business Research.

Volume III., 2005.

21. Gal S. Search Games, volume 149 of Mathematics in Science and Engeneering.

– 1980.

 131

22. A. Garnaev. Search games and other applications of game theory. Lecture

Notes in Economics and Mathematical Systems. Vol 485. Budapest: Springer,

2000. 153 p.

23. Garnaev A. Search Games and Other Applications of Game Theory.

Heidelberg, New York, Springer, 2000. 145 p.

24. Gittins J.S. An Application of Control Theory to a Game of Hide and

Seek International Journal of Control, 1979, vol. 30, pp. 981–987.

25. Chew M.C. Optimal Stopping in a discrete Search Problem, Operations

Research, 1973, vol. 21, pp. 741–747.

26. Gal. S.On the Optimality of a Simple Strategy for Searching Graphs //

Internat. Jornal of Game Theory. 2001. Vol. 29. P. 533-542.

27. A.Y. Garnaev: On a Ruckle problem in discrete games of ambush. Naval

Research Logistics, 44 (1997), 353–364.

28. Garnaev A. Search games and other applications of game theory. –

Springer Science Business Media, 2012. – Т. 485.

29. Gordon L. USC student’s computer program enlisted in security efforts

at LAX //Los Angeles Times, October. – 2007. – Т. 1.

 132

30. Joshi S. S., Phoha V. V. Investigating Hidden Markov Models Capabilities

in Anomaly Detection // Proceedings of 43rd Annual Southeast Regional

Conference, Kennesaw, GA, March, 2005, pp. 98—103.

31. Juan J. Vidal-Puga and Gustavo Bergantinos An implementation of the

Owen value// Games and Economic Behavior. 2003. V. 44 N. 2. P. 412-

427.

32. G. Hamiache A new axiomatization of the Owen value for games with

coalition structures // Mathematical Social Sciences. 1999. V. 37. P.

281–305.

33. R. Hohzaki: A search allocation game. European Journal of Operational

Research, 172 (2006), 101–119.

34. R. Hohzaki and K. Iida: A search game with reward criterion. Journal

of the Operations Research Society of Japan, 41 (1998), 629–642.

35. R. Hohzaki and K. Iida: A solution for a two-person zero-sum game

with a concave payoff function. In W. Takahashi and T. Tanaka (eds.):

Nonlinear Analysis and Convex Analysis (World Science Publishing Co.,

London, 1999), 157–166.

36. R. Hohzaki, K. Iida, and T. Komiya: Discrete search allocation game

with energy constraints. Journal of the Operations Research Society of

 133

Japan, 45 (2002), 93–108.

37. Anna B. Khmelnitskaya , Elena B. Yanovskaya Owen coalitional value

without additivity axiom // Mathematical Methods of Operations Research.

2007. V.66. N. 2. P. 255-261.

38. Kras Iida K. Optimal Search and Stop in Continuous Search Process,

Journal of the Operations Research Society of Japan, 1984, vol. 27, pp.

1–30.

39. K. Iida, R. Hohzaki, and S. Furui: A search game for a mobile target

with the conditionally deterministic motion defined by paths. Journal of

the Operations Research Society of Japan, 39 (1996), 501–511.

40. B.O. Koopman: Search and Screening (Pergamon, 1980), 221–227.

41. J.J. Meinardi: A sequentially compounded search game. In Theory of

Games: Techniquea and Applications (The English Universities Press,

London, 1964), 285–299.

42. T. Nakai: A sequential evasion-search game with a goal. Journal of the

Operations Research Society of Japan, 29 (1986), 113–122.

43. T. Nakai: Search models with continuous effort under various criteria.

Journal of the Operations Research Society of Japan, 31 (1988), 335–351.

 134

44. Owen G. Game Theory Academic Press //San Diego. – 1995.

45. Paruchuri, P., J. P. Pearce, et al. (2007). An effcient heuristic approach

for security against multiple adversaries. AAMAS 07, Honolulu, Hawaii,

ACM.

46. W.H. Ruckle: Ambushing random walk II: continuous models. Operations

Research, 29 (1981), 108–120.

47. Ruckle, W. H. (1983). Geometric Games and Their Application. Boston,

Pitman.

48. Sherman, L. and Eck, J. E., (2002). Policing for crime prevention. In:

Evidence-based crime Threats. New York, Springer.

49. L.S. Shapley: Stochastic games. Proceedings of the National Academy of

Sciences of the United States of America, 39 (1953), 1095–1100.

50. L.D. Stone: Theory of Optimal Search (Academic Press, New York,

1975), 136–178.

51. Urrutia, J. (2000). Art gallery and illumination problems. Handbook of

computational geometry. J.-R. Sack and J. Urrutia. Amsterdam, Elsevier.

52. Washburn, A. (2003). Two-person zero-sum games, 3rd edition. Linthicum,

MD, INFORMS.

 135

53. A.R.Washburn: Search-evasion game in a fixed region. Operations Research,

28 (1980), 1290–1298.

54. Washbum, A., and Thomas, L. "Dynamic Search Games Operations Research

Vol. 39, No 3, 415-421, May 1991.

55. A.R.Washburn and R. Hohzaki: The diesel submarine flaming datum

problem. Military Operations Research, 6 (2001), 19–33.

56. Zoroa, N. and P. Zoroa (1993). "Some games of search on a lattice."Naval

Research Logistics 40: 525-541.

57. B. Gusev, V. Mazalov Optimal strategies in the patrol game on a graph//

SING-GTM2015 European Meeting on Game Theory Abstracts. 2015. pp

52-53

58. V. V. Gusev, V. V. Mazalov Optimal Strategies in the Patrol Game on

a Graph// NGM, Сборник расширенных тезисов. 2015. p. 12

59. V. Gusev Shaply Value, Owen and Aumann-Dreze vectors in Patrolling

Game With Coalitional Structure// Game theory and Management. Collecked

abstract. 2016. P. 60

60. V. Gusev Game-Theoretic model of detection of submarines // NGM

International Workshop Networking Games and Management. 2016. pp.

 136

18-19

61. Воробьев Н. Н. Теория игр для экономистов-кибернетиков Л., Изд-во

Ленингр. н-та, 1974. 160 с.

62. Губко М. В., Новиков Д. А., Чхартишвили А. Г. Сетевые игры и

игры на сетях //Труды международной конференции «Сетевые игры

и менеджмент».–Петрозаводск: ИПМИ РАН. – 2009. – С. 13-17.

63. В. В. Гусев, В. В. Мазалов, “Оптимальные стратегии в игре патру-

лирования на графе”, Вестн. С.-Петербург. ун-та. Сер. 10. Прикл.

матем. Информ. Проц. упр., 2015, № 2, 61–76.

64. В. В. Гусев Ситуация равновесия в игре патрулирования с камерой

слежения // Труды Карельского научного центра РАН, № 10. 2015.

С. 28-33. DOI: 10.17076/mat145

65. В. В. Гусев Поиск оптимального начального распределения место-

положения игроков в игре патрулирования //Вестник Удмуртского

университета. Математика. Механика. Компьютерные науки, 2015,

т. 25, вып. 4, с. 453-458DOI: 10.20537/vm150402

66. Василий В. Гусев, “Векторы Шепли, Оуэна и Ауманна–Дрезе в иг-

ре патрулирования с коалиционной структурой”, МТИП, 8:4 (2016),

30–42

 137

67. В. В. Гусев Векторы Шепли, Оуэна и Ауманна–Дрезе в игре патрули-

рования с коалиционной структурой // ORM VIII Московская меж-

дународная конференция по исследованию операций. Том 2. 2016. pp

178-179

68. Н. А. Зенкевич Теоретико-игровая модель управления качеством в

условиях конкуренции // Математическая теория игр и ее приложе-

ния, т.2, вып.4; Управление большими системами, выпуск 31.1, 2010

(соавт. с Гладковой М.А.)

69. Мазалов В. В. Математическая теория игр и приложения: учеб. по-

собие. СПб.: Изд-во «Лань», 2010. 448 с.

70. Владимир В. Морозов, Камиль Д. Шалбузов, “Игровая модель рас-

пределения ресурсов при защите объекта”, МТИП, 5:4 (2013), 66–83;

Autom. Remote Control, 76:11 (2015), 2045–2055

71. Новиков Д. А. Иерархические модели военных действий // Управ-

ление большими системами. 2012. № 37. С. 25 - 62.

72. Новиков Д. А. , “Игры и сети”, МТИП, 2:1 (2010), 107–124; Autom.

Remote Control, 75:6 (2014), 1145–1154

73. Носов В. И., Бернштейн Т. В., Носкова Н. В., Храмова Т. В. Элемен-

ты теории графов. Учебное пособие. — Новосибирск, 2008. — 107с

 138

74. Парилина Е. М., Седаков А. А. Устойчиость коалиционных структур

одной модели банкоской кооперации // Математическая Теория Игр

и ее Приложения, т. 4, в. 4, с. 45-62.

75. Петросян Л. А. и др. Теория игр: Учеб. пособие для ун-тов:/Л. А.

Петросян, Н. А. Зенкевич, Е. А. Семина. - М.: Высш. шк., Книжный

дом «Университет», 1998. - 304 с: ил.

 139

Приложения

Р@@@ий@кАя1 ФшдшРАщшя

ж

йЁ

ЁЁ

ж

ж

ж

ж

ЁЁ

бЁ

ж свидвтвльство

о государственной регистрации программь| для эвм

л} 20176141з\

ж

ж

ж [1рограмма для поиска оптимальнь[х путей в задане

ж патрулирования

ж

ж

ж |1равообладатель :Ф её ер альн о е еосуё ар с!пв енное б го 0экеппно е ж

ж ен кш |1 н !п пр х кшх ж

у нр е эк 0 ен ш шу с па ш тпу ш кл ш 0 н ьп [,а а!п е л' ш !п шч е с

ж ж

шс сл е 0 ан й 1{ ар ат ко 2 о н ау ч н о е о ще н !пр а Ро йс ко й а кш 0 епо ш ш

ж о в ш ь с с с ш

ж

ж наук (п(/) ж

ж ж

ж ж

ж ж

ж

Автор: |усев Басш;пшй 8аспл;пьевшн (&(}) ж

ж ж

ж ж

ж 3аявка хр 2017611282

ж

ж ж

ж !атапосцплени'] 15 февраля20|7 г. ж

ж !ата госуАарственной регистрации

ж в Реестре программ для 39й 06 шпреля 2017 е.

ж

ж Руко в о0штпель Ф е ё ер альной слуэюб ьт

ж по 1/н/пелл ектпуальной собстпв еннос/пш

ж ж

ж (-----> ж

ж

''-1 ф |'[/'1влшев

ж

ж ж

жжжжжжжжжвхжж жжжжжжжжжжжжжжжжжжж

Приложение А. Свидетельство о регистрации программы