Стабильность при одностороннем отклонении в аддитивно разделимых гедонических играх с ограниченными размерами коалиций

Основная информация

• ID статьи: 2510.12641
• Название: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
• Авторы: Martin Bullinger (University of Bristol), Adam Dunajski (University of Edinburgh), Edith Elkind (Northwestern University), Matan Gilboa (University of Oxford)
• Классификация: cs.GT (Теория игр), cs.DS (Структуры данных и алгоритмы)
• Дата публикации: 14 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.12641

Аннотация

В данной работе исследуется проблема стабильности в аддитивно разделимых гедонических играх (ASHG) при условии, что размеры коалиций ограничены фиксированными границами. Авторы рассматривают четыре классических концепции стабильности, основанные на одностороннем отклонении агента: стабильность по Нэшу (Nash stability), индивидуальная стабильность (individual stability), контрактная стабильность по Нэшу (contractual Nash stability) и контрактная индивидуальная стабильность (contractual individual stability). Для каждой концепции стабильности авторы рассматривают две варианты: одна требует, чтобы коалиция, оставленная отклоняющимся агентом, сохраняла допустимый размер, другая не имеет такого ограничения. Статья предоставляет полную картину существования стабильных результатов при заданных параметрах размера и полностью характеризует вычислительную сложность соответствующих задач существования при наличии только верхней границы.

Исследовательский контекст и мотивация

Важность проблемы

Формирование коалиций является центральной проблемой в многоагентных системах с широким применением в:

• Разделении студентов на группы для проектных работ
• Распределении мест в офисах отделов
• Организации групп для внеклассных мероприятий
• Рассадке гостей на банкетах конференций

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

Ограничения существующих исследований

1. Недостаточное внимание к нижним границам: Предыдущие работы в основном сосредоточены на верхних границах, исследование нижних границ недостаточно
2. Неполный анализ концепций стабильности: Отсутствует систематический анализ различных концепций стабильности при наличии ограничений
3. Неясная вычислительная сложность: Вычислительная сложность различных концепций стабильности при наличии ограничений полностью не охарактеризована

Исследовательская мотивация

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

Основные вклады

1. Полная характеризация существования: Предоставляется полная картина существования для всех рассматриваемых концепций стабильности при заданных параметрах размера
2. Полный анализ вычислительной сложности: При наличии только верхней границы (λ=1) полностью охарактеризована вычислительная сложность всех концепций стабильности
3. Полиномиальные алгоритмы:
   • Полиномиальный алгоритм для контрактной индивидуальной стабильности (CIS)
   • Полиномиальный алгоритм для контрактной стабильности по Нэшу (CNS) при верхней границе 2
   • Полиномиальный алгоритм для CIS* при нижней границе не менее 2
4. Результаты NP-полноты: Доказана NP-полнота задачи определения стабильности в различных случаях
5. Исправление алгоритма: Исправлена ошибка в алгоритме Aziz et al. (2013)

Подробное описание методов

Определение задачи

Входные данные:

• Множество агентов N
• Аддитивно разделимые функции полезности v = (va)a∈N, где va: N{a} → ℝ
• Ограничения на размер коалиции λ ≤ μ (λ — нижняя граница, μ — верхняя граница)

Выходные данные:

• (λ,μ)-разбиение: разбиение коалиций, удовлетворяющее ограничениям на размер
• Определение стабильности: удовлетворяет ли данное разбиение определённой концепции стабильности

Ограничения:

• Каждая коалиция C удовлетворяет λ ≤ |C| ≤ μ
• Отклонения должны быть (λ,μ)-допустимыми или (λ,μ)-осуществимыми

Концептуальная база стабильности

Основные определения

Для полезности агента a в коалиции C: $u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)$

Четыре стандартные концепции стабильности

1. Стабильность по Нэшу (NS): Ни один агент не может улучшить свою полезность путём отклонения
2. Индивидуальная стабильность (IS): Отклонение по Нэшу + согласие членов целевой коалиции
3. Контрактная стабильность по Нэшу (CNS): Отклонение по Нэшу + согласие членов исходной коалиции
4. Контрактная индивидуальная стабильность (CIS): Одновременное удовлетворение условий IS и CNS

Варианты осуществимости

Каждая стандартная концепция имеет соответствующий вариант осуществимости (обозначается *), требующий, чтобы исходная коалиция после отклонения сохраняла допустимый размер.

Ключевые алгоритмы

Алгоритм 1: Алгоритм CIS (исправленная версия)

Входные данные: ASHG (N,v), параметр μ
Выходные данные: (1,μ)-разбиение

1. Инициализация: i←0, A←N
2. while A ≠ ∅:
3.   Выбрать агента a ∈ A
4.   Вычислить полезность создания новой коалиции h
5.   for k ∈ [i]:  // Рассмотреть присоединение к существующей коалиции
6.     Вычислить полезность присоединения к коалиции k: h'
7.     if h < h': Обновить оптимальный выбор
8.   Создать/присоединиться к коалиции согласно оптимальному выбору
9.   Обновить множество доступных агентов A

Алгоритм 3: Алгоритм CIS* (ненулевые оценки)

Для случая нижней границы λ≥2, использующий двухэтапный подход:

1. Этап I: Формирование оптимальной коалиции минимального размера для каждого лидера
2. Этап II: Заполнение оставшихся агентов в обратном порядке

Экспериментальная установка

Теоретическая аналитическая база

Данная работа в основном проводит теоретический анализ, включающий:

1. Доказательства существования: Конструктивные доказательства и контрпримеры
2. Анализ сложности: Доказательства через редукцию и разработка алгоритмов
3. Верификация корректности алгоритмов: Формальная верификация

Методология анализа сложности

• Доказательства NP-полноты: Редукция из классических задач (3-SAT, X3C и др.)
• Полиномиальные алгоритмы: Конструктивная разработка алгоритмов
• Анализ нижних границ: Доказательство несуществования через контрпримеры

Результаты исследования

Результаты существования

Ключевые выводы:

• Симметричные оценки гарантируют существование самой сильной концепции осуществимой стабильности (NS*)
• Даже для простых симметричных оценок стандартные концепции стабильности могут не существовать
• CIS* существует во всех случаях (когда существует допустимое разбиение)

Результаты вычислительной сложности (λ=1)

Конкретная сложность алгоритмов:

• CIS: Полиномиальный алгоритм с временной сложностью O(n³)
• CNS (μ=2): Полиномиальный алгоритм с временной сложностью O(n²)
• NS/IS: NP-полнота доказана редукцией из задачи минимального максимального паросочетания

Результаты для нижней границы λ≥2

Связанные работы

Основы гедонических игр

• Drèze & Greenberg (1980): Введение концепции гедонических игр
• Bogomolnaia & Jackson (2002): Установление аддитивно разделимых гедонических игр

Развитие концепций стабильности

• Sung & Dimitrov (2010): Вычислительная сложность стабильности при одностороннем отклонении
• Aziz et al. (2013): Полиномиальный алгоритм для CIS (в данной работе обнаружена и исправлена ошибка)

Исследования ограниченных коалиций

• Levinger et al. (2024): Групповая стабильность при верхних границах
• Fioravantes et al. (2025): Параметризованный анализ сложности

Заключение и обсуждение

Основные выводы

1. Бинарность существования: Существует фундаментальное различие в существовании между концепциями осуществимой и стандартной стабильности
2. Иерархия сложности: От полиномиальной разрешимости CIS до NP-полноты NS, наблюдается чёткая иерархия сложности
3. Влияние ограничений: Нижние границы существенно влияют на существование и вычислимость стабильности

Ограничения

1. Открытые вопросы: Сложность NS при λ=2, μ=3 остаётся неопределённой
2. Практическое применение: Требуется дальнейшее исследование связи теоретических результатов с практическими сценариями
3. Эффективность алгоритмов: Константные множители в некоторых полиномиальных алгоритмах могут быть значительными

Направления будущих исследований

1. Другие типы игр: Расширение на дробные гедонические игры и другие модели
2. Приближённые алгоритмы: Разработка приближённых алгоритмов для NP-трудных случаев
3. Онлайн-алгоритмы: Рассмотрение формирования коалиций в динамических окружениях

Глубокая оценка

Преимущества

1. Теоретическая полнота: Предоставляется систематическая теоретическая база для стабильности в ограниченных гедонических играх
2. Технические инновации:
   • Искусные конструкции редукций (например, редукция из X3C в CNS)
   • Инновационная разработка алгоритмов (двухэтапный алгоритм CIS*)
   • Исправление ошибок (исправление алгоритма Aziz et al.)
3. Глубина результатов: Предоставляются не только результаты существования, но и конструктивные алгоритмы
4. Ясность изложения: Чёткие определения концепций, полная структура доказательств

Недостатки

1. Отсутствие экспериментальной верификации: Чисто теоретическая работа без верификации на реальных данных
2. Ограниченное практическое руководство: Практическое значение для реальных сценариев требует дальнейшего изучения
3. Сложность некоторых доказательств: Некоторые доказательства NP-полноты довольно сложны и могут быть трудны для понимания

Влияние

1. Академическая ценность: Предоставляет важную теоретическую базу для теории ограниченных коалиционных игр
2. Практическая ценность: Предоставляет алгоритмические инструменты для практических задач формирования коалиций
3. Воспроизводимость: Алгоритмы описаны ясно и легко реализуются и верифицируются

Применимые сценарии

1. Образовательная сфера: Разделение студентов на группы, планирование курсов
2. Организационное управление: Формирование команд, распределение ресурсов
3. Социальный выбор: Коалиции для голосования, формирование групп интересов
4. Компьютерные науки: Кластеризация узлов в распределённых системах

Библиография

1. Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201-230.
2. Aziz, H., Brandt, F., & Seedig, H. G. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316-334.
3. Sung, S. C., & Dimitrov, D. (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635-639.
4. Levinger, C., Hazon, N., Simola, S., & Azaria, A. (2024). Coalition formation with bounded coalition size. In Proceedings of AAMAS 2024.

Общая оценка: Это высококачественная работа в области теоретической информатики, внёсшая значительный вклад в теорию ограниченных коалиционных игр. Теоретическая глубина и технические инновации работы весьма выдающиеся, обеспечивая прочную основу для последующих исследований в этой области. Хотя работе не хватает экспериментальной верификации, учитывая её теоретический характер, это ограничение понятно. Данная работа имеет важное академическое значение для теории игр, разработки алгоритмов и многоагентных систем.