Тема: ЦЕНТРАЛЬНОСТЬ ИГРОКОВ В КОАЛИЦИОННОЙ ИГРЕ

Теория графов применяется при решении многих практических задач, например, логистики, маршрутизации данных в интернете и химии. Одним из важных значений при решении практических задач является центральность вершины. Центральность вершины в графе - это некоторый класс значений, который показывает важность соответствующей вершины. Для выяснения того, насколько заданная вершина значима в графе, применяется несколько различных метрик центральности, которые употребляются в зависимости от типа задачи. Всего существует четыре основных класса центральности [9], [11]:
1. Степень вершины - показывает со сколькими вершинами она смежна.
2. Closeness - насколько близко ко всем остальным вершинам графа находится вершина (относительно расстояния).
3. Betweenness - важность вершины относительно связи между другими вершинами. Если удалить важную вершину, то минимальное расстояние между другими вершинами графа увеличится или граф перестанет быть связным.
4. Вычисление центральности относительно соседних вершин и соседей их соседей (используя собственный вектор матрицы смежности).
В моей работе я застрагиваю первые три класса метрик центральности.
Коалиционная (или кооперативная) игра - это тип игры, в которой игроки объединяются в коалиции для получения большего выигрыша в сравнении с тем выигрышем, который каждый игрок получил бы, действуя в одиночку. Первоначально теорию игр (в частности коалиционные игры) использовали для объяснения поведения игроков в экономике при различных ситуациях, а также поиска наилучшего поведения. В данный момент теория игр используется в различных областях науки для анализа поведение людей и животных.
В моей работе рассматривается коалиционная игра, заданная на графе. Впервые такая задача была поставлена в статье [2]. Граф в этом случае показывает возможность объединиться в коалицию с каким-либо игроками. Я рассматриваю связные коалиции, то есть у каждого игрока есть связь с другими игроками, как минимум через других игроков. Функцией выигрыша в рассматриваемой задаче является центральность игрока в графе. Подсчет выигрыша игрока происходит следующим образом: удаляются любые связи игрока с игроками из других коалиций и подсчитывается его центральность. При переходе игрока в другую коалицию все связи игрока с игроками из прошлой коалиции разрываются и восстанавливаются связи с игроками из коалиции, в которую он переходит.
Одна из задач в коалиционной (кооперативной) теории игр заключается в нахождении устойчивой коалиционной структуры, то есть такого разбиения игроков, при котором в своей коалиции игрок получит выигрыш не меньше, чем в любой другой коалиции в этом разбиении. Впервые устойчивость коалиционных структур была представлена в статьях [4], [8] и была основана на равновесии по Нэшу [10] для некооперативных игр.
В моей работе я исследую различные типы графов и различные разбиения игроков на коалиции для поиска устойчивых коалиционных структур относительно метрик центральности. Необходимо ответить на два вопроса:
1. Является ли заданная коалиционная структура на графе устойчивой?
2. Существует ли устойчивые коалиционные структуры в заданном графе? Если да, то найти их.
Работа имеет следующую структуру:
• Во 2 главе представлена формальная постановка задачи и вводятся необходимые определения.
• В 3 главе представлены основные теоретические результаты моей работы.
• В 4 главе показаны практические результаты работы: разработка алгоритма, его оптимизация и численный эксперимент для сравнения времени работы алгоритмов.
Купить

Результами данной работы являются:
1. Доказательство теоретических утверждений для метрик центральности степень вершины, Closeness, Betweenness. Метрики степень вершины и Closeness схожи между с собой с точки зрения доказанных утверждений, метрика Betweenness сильно отличается от двух других.
2. Реализован алгоритм для проверки устойчивости коалиционной структуры в графе и алгоритм поиска устойчивой коалиционной структуры в граф, а также посчитана их сложность.
3. Были оптимзированы базовые алгоритмы из пункта 2, проведен численный эксперимент для подтверждения правильности способов оптимизации.
Ближайшими перспективами данного исследования являются:
1. Доказательство утверждений для других типов графов для рассмотренных метрик.
2. Исследовать метрику центральности относительно соседей (Katz centrality).
3. Поиск дальнейших методов оптимизации алгоритмов для проверки устойчивости коалиционной структуры в графе и поиска устойчивой коалиционной структуры в графе.

Купить