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

Кричевский Антон Олегович
Бесплатно
В избранное
Работа доступна по лицензии 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 экспертов уже готовы начать работу над твоим проектом!

    Мария А. кандидат наук
    4.7 (18 отзывов)
    Мне нравится изучать все новое, постоянно развиваюсь. Могу написать и диссертацию и кандидатскую. Есть опыт в различных сфера деятельности (туризм, экономика, бухучет... Читать все
    Мне нравится изучать все новое, постоянно развиваюсь. Могу написать и диссертацию и кандидатскую. Есть опыт в различных сфера деятельности (туризм, экономика, бухучет, реклама, журналистика, педагогика, право)
    #Кандидатские #Магистерские
    39 Выполненных работ
    Шиленок В. КГМУ 2017, Лечебный , выпускник
    5 (20 отзывов)
    Здравствуйте) Имею сертификат специалиста (врач-лечебник). На данный момент являюсь ординатором(терапия, кардио), одновременно работаю диагностом. Занимаюсь диссертац... Читать все
    Здравствуйте) Имею сертификат специалиста (врач-лечебник). На данный момент являюсь ординатором(терапия, кардио), одновременно работаю диагностом. Занимаюсь диссертационной работ. Помогу в медицинских науках и прикладных (хим,био,эколог)
    #Кандидатские #Магистерские
    13 Выполненных работ
    Татьяна М. кандидат наук
    5 (285 отзывов)
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    #Кандидатские #Магистерские
    495 Выполненных работ
    AleksandrAvdiev Южный федеральный университет, 2010, преподаватель, канд...
    4.1 (20 отзывов)
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    #Кандидатские #Магистерские
    28 Выполненных работ
    Катерина В. преподаватель, кандидат наук
    4.6 (30 отзывов)
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации... Читать все
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации. Опыт работы 7 лет. Всегда на связи и готова прийти на помощь. Вместе удовлетворим самого требовательного научного руководителя. Возможно полное сопровождение: от статуса студента до получения научной степени.
    #Кандидатские #Магистерские
    47 Выполненных работ
    Мария М. УГНТУ 2017, ТФ, преподаватель
    5 (14 отзывов)
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ... Читать все
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ. Большой опыт в написании курсовых, дипломов, диссертаций.
    #Кандидатские #Магистерские
    27 Выполненных работ
    Александра С.
    5 (91 отзыв)
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повы... Читать все
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повышении уникальности текста и оформлении библиографических ссылок по ГОСТу.
    #Кандидатские #Магистерские
    132 Выполненных работы
    Дмитрий М. БГАТУ 2001, электрификации, выпускник
    4.8 (17 отзывов)
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал стать... Читать все
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал статьи, патенты, кандидатскую диссертацию, преподавал. Занимаюсь этим с 2003.
    #Кандидатские #Магистерские
    19 Выполненных работ
    Екатерина С. кандидат наук, доцент
    4.6 (522 отзыва)
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    #Кандидатские #Магистерские
    1077 Выполненных работ

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

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