Теоретико-игровые модели поиска на графе

Основные результаты, выносимые на защиту
1. Найдена ситуация равновесия для игры патрулирования с неподвижным прячущимся игроком для разных видов графов.
2. Построена кооперативная модель игры патрулирования в которой патрулирующие игроки подразделяются на слабых и сильных игроков. Найдены значения векторов Шепли, Оуэна и Ауманна-Дрезе для эффективной коалиционной структуры. Доказана супераддитивность характеристической функции игры, показана взаимосвязь вектора Оуэна и Ауманна-Дрезе.
3. Построена многошаговая теоретико-игровая модель поиска двух подвижных игроков на графе. Найдено равновесие по Нэшу в многошаговой игре с предположением, что бюджет, направляемый в группу вершин, имеющих общего родителя, фиксирован. Доказано существование равновесия на каждом шаге, найдено решение одношаговой игры с неэкспоненциальной вероятностью обнаружения.

Математическая модель поиска н. о. на графе
Множество чистых стратегий игрока A:
Индикатор встречи игроков:

1 2 5 6
3
4

Смешанные стратегии игроков P, A соответственно :
Функция выигрыша игрока P

k – число этажей;
2l – количество квартир на этаже.
7 8 9 10 11 12
1 2 3 4 5 6
3, 4, 9, 10 – начало пути игрока P

Теорема 11. Пусть в ситуации равновесия в игре G(Q,T,m) атакующий выбирает всевозможные атаки, а в оптимальных путях патрулирующего в каждый момент времени t каждая вершина встречается один раз. Тогда

Покрытие графа

Вектор Шепли

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

Вектор Оуэна
Теорема 16. Вектор Оуэна, вычисленный для эффективной коалиционной структуры, совпадает с вектором Ауманна-Дрезе.
Утверждение. Вычислительная сложность вектора Оуэна для перчаточной игры с коалиционной структурой полиномиального порядка.1
1Belau 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.

3 2 1

В. В. Гусев, В. В. Мазалов, “Оптимальные стратегии в игре патрулирования на графе”, Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2015, № 2, 61–76.
В. В. Гусев, Ситуация равновесия в игре патрулирования с камерой слежения // Труды Карельского научного центра РАН, № 10. 2015. С. 28-33. DOI: 10.17076/mat145.
В. В. Гусев, Поиск оптимального начального распределения местоположения игроков в игре патрулирования //Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2015, т. 25, вып. 4, с. 453-458 DOI: 10.20537/vm150402.
В. В. Гусев, “Векторы Шепли, Оуэна и Ауманна–Дрезе в игре патрулирования с коалиционной структурой”, МТИП, 8:4 (2016), 30–42.
Список публикаций ВАК по теме диссертации

Список публикаций в сборниках конференций
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.
V. V. Gusev, V. V. Mazalov Optimal Strategies in the Patrol Game on a Graph// NGM, Сборник расширенных тезисов. 2015. p. 12.
V. Gusev Shaply Value, Owen and Aumann-Dreze vectors in Patrolling Game With Coalitional Structure// Game theory and Management. Collecked abstract. 2016. P. 60 .
В. В. Гусев Векторы Шепли, Оуэна и Ауманна–Дрезе в игре патрулирования с коалиционной структурой // ORM VIII Московская международная конференция по исследованию операций. Том 2. 2016. pp 178-179.
V. Gusev Game-Theoretic model of detection of submarines // NGM International Workshop Networking Games and Management. 2016. pp. 18-19.