Конкуренция и кооперация в теоретико-игровых моделях на графах

Объектом исследования являются теоретико-игровые модели на графах (транспортные, экономические, информационные, социальные). Целью проекта является разработка методов построения равновесия в теоретико-игровых моделях, определенных на графах, разработка теоретико-игровых методов для анализа структуры больших графов, их применение при анализе профессиональных социальных сетей, а также сравнение конкурентных и кооперативных подходов. Методами исследования являются методы теории кооперативных и некооперативных игр, теории вероятностей и математической статистики, многокритериальных задач, нелинейного программирования, динамического программирования, оптимального управления, численные методы. Были предложены новые теоретико-игровые модели сетей, заданных на графах, которые описывают различные особенности структуры сети и взаимодействия ее участников. Сети могут иметь разную структуру в зависимости от их назначения. В работе рассмотрены коммуникационные, транспортные, социальные сети, системы распределения ресурсов. Данные сети могут быть представлены графом, вершины которого есть компьютеры или участники социальных сетей, а ребра определяются типом взаимодействия между ними. Также исследованы модели, в которых графом можно описать динамику изменения состояний системы. Предложен новый метод вычисления центральности вершин в графе на основе неаддитивных мер и интеграла Шоке. Предложен алгоритм ее вычисления и сделано сравнение с существующими мерами центральности. В качестве приложений разработанных мер центральности для ранжирования корпусов текстов новостного портала предложено использовать методы кооперативной теории игр. Каждому тексту ставится в соответствие вершина некоторого графа, а его структура определяется на основе семантической связности текстов. Предложен алгоритм ранжирования, работа которого проиллюстрирована на численных примерах, связанных с конкретным порталом новостей. Исследованы транспортные задачи на графах с экстерналиями (внешними факторами). Исследован вопрос, как внешние факторы влияют на трафик в равновесии и социальный оптимум в системе. Используя принцип равновесия по Вардропу для транспортной сети с параллельными каналами, в которой функции задержки включают экстерналии, доказано, что существуют такие значения внешних факторов, что равновесный и оптимальный профили стратегий приводят к одинаковым затратам, а цена анархии будет равна 1. Для оценки загруженности транспортной сети были использованы функции задержки полиномиального вида, а также специальное внимание было уделено задержкам типа M/M/k (модель Клейнрока), где поток характеризуется своей интенсивностью. При этом, если в моделях массового обслуживания интенсивность задается как параметр, то в проекте было проведено исследование, в котором параметр интенсивности возникает как решение теоретико-игровой задачи. Стратегиями игроков является время прибытия в систему массового обслуживания в течение определенного периода времени. Показано существование равновесие в данной игре и предложен алгоритм его нахождения на основе рекуррентных уравнений Колмогорова. Доказано существование равновесия по Нэшу в неоднородной игре маршрутизации между транспортными средствами n типов. На основе предложенной модифицированной меры центральности выделены критические, резервные и перегруженные ребра транспортного графа. Предложен алгоритм поиска маршрутов пассажиропотока, вносящих наибольший вклад в центральность загруженных ребер транспортного графа. Предложена оценка числа пассажиров, использующих заданный маршрут и каждую конкретную остановку общественного транспорта в условиях конкуренции нескольких перевозчиков на транспортном графе. Исследована модель дуополии на двустороннем рынке платформ для различных типов агентов при наличии сетевых внешних экстерналий. Найдены значения равновесных цен и функций прибыли платформ для различных сценариев задачи. Предложена теоретико-игровая модель внешнего влияния (управления) на динамику мнений и достигнутый консенсус в социальной сети, в которой агенты связаны между собой через произвольный коммуникационный граф. Найдено равновесие в модели для различных сетевых структур. Исследованы асимметричные и многокритериальные динамические игры. Кооперативное и некооперативное поведение игроков определено в динамической бикритериальной модели управления возобновляемыми ресурсами с асимметричными участниками и векторными функциями выигрышей. Исследованы динамические задачи управления ресурсами, где горизонт планирования разделен на периоды эксплуатации и восстановления. Определены условия, связывающие длительность этих периодов для поддержания устойчивого использования ресурсов. Исследована многошаговая модель, связанная с несимметричным случайным блужданием на целочисленной решетке. На каждом шаге вероятность победы игрока зависит от соотношения побед и поражений на предыдущих шагах. Найдены выигрыши игрока и асимптотическая формула для больших значений продолжительности игры. Представлены численные результаты моделирования значений выигрышей для различных значений продолжительности игры. Рассмотрено применение модели машинного обучения для определения оптимальной стратегии пользователя для победы в аукционе на покупку товара/услуги с использованием задачи наилучшего выбора.