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

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

    Татьяна М. кандидат наук
    5 (285 отзывов)
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    #Кандидатские #Магистерские
    495 Выполненных работ
    Виктор В. Смоленская государственная медицинская академия 1997, Леч...
    4.7 (46 отзывов)
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выв... Читать все
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выводы).Пишу статьи в РИНЦ, ВАК.Оформление патентов от идеи до регистрации.
    #Кандидатские #Магистерские
    100 Выполненных работ
    Татьяна П. МГУ им. Ломоносова 1930, выпускник
    5 (9 отзывов)
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по и... Читать все
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по истории. Увлекаюсь литературой и темой космоса.
    #Кандидатские #Магистерские
    11 Выполненных работ
    Анна К. ТГПУ им.ЛН.Толстого 2010, ФИСиГН, выпускник
    4.6 (30 отзывов)
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помог... Читать все
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помогала студентам, вышедшим на меня по рекомендации.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Мария Б. преподаватель, кандидат наук
    5 (22 отзыва)
    Окончила специалитет по направлению "Прикладная информатика в экономике", магистратуру по направлению "Торговое дело". Защитила кандидатскую диссертацию по специальнос... Читать все
    Окончила специалитет по направлению "Прикладная информатика в экономике", магистратуру по направлению "Торговое дело". Защитила кандидатскую диссертацию по специальности "Экономика и управление народным хозяйством". Автор научных статей.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Сергей Н.
    4.8 (40 отзывов)
    Практический стаж работы в финансово - банковской сфере составил более 30 лет. За последние 13 лет, мной написано 7 диссертаций и более 450 дипломных работ и научных с... Читать все
    Практический стаж работы в финансово - банковской сфере составил более 30 лет. За последние 13 лет, мной написано 7 диссертаций и более 450 дипломных работ и научных статей в области экономики.
    #Кандидатские #Магистерские
    56 Выполненных работ
    Елена С. Таганрогский институт управления и экономики Таганрогский...
    4.4 (93 отзыва)
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на напис... Читать все
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на написании курсовых и дипломных работ, а также диссертационных исследований.
    #Кандидатские #Магистерские
    158 Выполненных работ
    Дмитрий М. БГАТУ 2001, электрификации, выпускник
    4.8 (17 отзывов)
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал стать... Читать все
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал статьи, патенты, кандидатскую диссертацию, преподавал. Занимаюсь этим с 2003.
    #Кандидатские #Магистерские
    19 Выполненных работ
    Кирилл Ч. ИНЖЭКОН 2010, экономика и управление на предприятии транс...
    4.9 (343 отзыва)
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). С... Читать все
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). Сейчас пишу диссертацию на соискание степени кандидата экономических наук.
    #Кандидатские #Магистерские
    692 Выполненных работы

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

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