Центральность игроков в коалиционной игре

Кричевский Антон Олегович
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Рассматривается коалиционная (кооперативная) игра n лиц на связном графе. Каждой вершине соответствует игрок, а наличие связи между игроками показывает возможность организации коалиции между ними.В качестве функции выигрыша в игре рассматривается метрика центральности игрока. Центральность показывает важность вершины, выражаемую вещественным числом. В работе рассматриваются три метрики центральности: степень вершины, Closeness и Betweenness.

Основным предметом исследования является устойчивость коалиционной структуры (разбиения игроков на коалиции). Коалиционная структура устойчива, если выигрыш игрока в текущей коалиции будет не меньше его выигрыша при переходе в любую другую коалицию этого разбиения. В ходе работы дается ответ на два вопроса: является ли заданная коалиционная структура устойчивой в графе и существуют ли устойчивые коалиционные структуры в заданном графе.

В результате для различных графов и метрик центральности были доказаны теоретические результаты об устойчивости коалиционной структуры. Дополнительно реализован алгоритм проверки устойчивости коалиционной структуры и поиска устойчивых коалиционных структур в графе.

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

Работа имеет следющую структуру:
• Во 2 главе представлена формальная постановка задачи и вводятся необходимые определения.
• В 3 главе представлены основные теоретические результаты моей ра- боты.
• В 4 главе показаны практические результаты работы: разработка ал- горитма, его оптимизация и численный эксперимент для сравнения времени работы алгоритмов.

Заказать новую

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

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

    Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Евгений А. доктор, профессор
    5 (154 отзыва)
    Более 40 лет занимаюсь преподавательской деятельностью. Специалист в области философии, логики и социальной работы. Кандидатская диссертация - по логике, докторская - ... Читать все
    Более 40 лет занимаюсь преподавательской деятельностью. Специалист в области философии, логики и социальной работы. Кандидатская диссертация - по логике, докторская - по социальной работе.
    #Кандидатские #Магистерские
    260 Выполненных работ
    Анна К. ТГПУ им.ЛН.Толстого 2010, ФИСиГН, выпускник
    4.6 (30 отзывов)
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помог... Читать все
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помогала студентам, вышедшим на меня по рекомендации.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Дарья Б. МГУ 2017, Журналистики, выпускник
    4.9 (35 отзывов)
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных ко... Читать все
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных компаниях, сейчас работаю редактором. Готова помогать вам с учёбой!
    #Кандидатские #Магистерские
    50 Выполненных работ
    Андрей С. Тверской государственный университет 2011, математический...
    4.7 (82 отзыва)
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на... Читать все
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на продолжение диссертационной работы... Всегда готов помочь! ;)
    #Кандидатские #Магистерские
    164 Выполненных работы
    Шагали Е. УрГЭУ 2007, Экономика, преподаватель
    4.4 (59 отзывов)
    Серьезно отношусь к тренировке собственного интеллекта, поэтому постоянно учусь сама и с удовольствием пишу для других. За 15 лет работы выполнила более 600 дипломов и... Читать все
    Серьезно отношусь к тренировке собственного интеллекта, поэтому постоянно учусь сама и с удовольствием пишу для других. За 15 лет работы выполнила более 600 дипломов и диссертаций, Есть любимые темы - они дешевле обойдутся, ибо в радость)
    #Кандидатские #Магистерские
    76 Выполненных работ
    Дарья П. кандидат наук, доцент
    4.9 (20 отзывов)
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных... Читать все
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных исследований, связанных с журналистикой, филологией и литературой
    #Кандидатские #Магистерские
    33 Выполненных работы
    Кирилл Ч. ИНЖЭКОН 2010, экономика и управление на предприятии транс...
    4.9 (343 отзыва)
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). С... Читать все
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). Сейчас пишу диссертацию на соискание степени кандидата экономических наук.
    #Кандидатские #Магистерские
    692 Выполненных работы
    Александр О. Спб государственный университет 1972, мат - мех, преподав...
    4.9 (66 отзывов)
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальн... Читать все
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальных уравнений. Умею быстро и четко выполнять сложные вычислительные работ
    #Кандидатские #Магистерские
    117 Выполненных работ

    Другие учебные работы по предмету

    Кооперативные игры на гиперграфах
    📅 2019год
    🏢 Санкт-Петербургский государственный университет