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

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

    Ксения М. Курганский Государственный Университет 2009, Юридический...
    4.8 (105 отзывов)
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитыв... Читать все
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитывать все требования и пожелания.
    #Кандидатские #Магистерские
    213 Выполненных работ
    Татьяна С. кандидат наук
    4.9 (298 отзывов)
    Большой опыт работы. Кандидаты химических, биологических, технических, экономических, юридических, философских наук. Участие в НИОКР, Только актуальная литература (пос... Читать все
    Большой опыт работы. Кандидаты химических, биологических, технических, экономических, юридических, философских наук. Участие в НИОКР, Только актуальная литература (поставки напрямую с издательств), доступ к библиотеке диссертаций РГБ
    #Кандидатские #Магистерские
    551 Выполненная работа
    Дмитрий М. БГАТУ 2001, электрификации, выпускник
    4.8 (17 отзывов)
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал стать... Читать все
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал статьи, патенты, кандидатскую диссертацию, преподавал. Занимаюсь этим с 2003.
    #Кандидатские #Магистерские
    19 Выполненных работ
    Ольга Р. доктор, профессор
    4.2 (13 отзывов)
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласован... Читать все
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласованные сроки и при необходимости дорабатываются по рекомендациям научного руководителя (преподавателя). Буду рада плодотворному и взаимовыгодному сотрудничеству!!! К каждой работе подхожу индивидуально! Всегда готова по любому вопросу договориться с заказчиком! Все работы проверяю на антиплагиат.ру по умолчанию, если в заказе не стоит иное и если это заранее не обговорено!!!
    #Кандидатские #Магистерские
    21 Выполненная работа
    Кирилл Ч. ИНЖЭКОН 2010, экономика и управление на предприятии транс...
    4.9 (343 отзыва)
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). С... Читать все
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). Сейчас пишу диссертацию на соискание степени кандидата экономических наук.
    #Кандидатские #Магистерские
    692 Выполненных работы
    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Елена С. Таганрогский институт управления и экономики Таганрогский...
    4.4 (93 отзыва)
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на напис... Читать все
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на написании курсовых и дипломных работ, а также диссертационных исследований.
    #Кандидатские #Магистерские
    158 Выполненных работ
    Мария Б. преподаватель, кандидат наук
    5 (22 отзыва)
    Окончила специалитет по направлению "Прикладная информатика в экономике", магистратуру по направлению "Торговое дело". Защитила кандидатскую диссертацию по специальнос... Читать все
    Окончила специалитет по направлению "Прикладная информатика в экономике", магистратуру по направлению "Торговое дело". Защитила кандидатскую диссертацию по специальности "Экономика и управление народным хозяйством". Автор научных статей.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Андрей С. Тверской государственный университет 2011, математический...
    4.7 (82 отзыва)
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на... Читать все
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на продолжение диссертационной работы... Всегда готов помочь! ;)
    #Кандидатские #Магистерские
    164 Выполненных работы

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

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