2025-11-16T13:10:12.550115

Online MMS Allocation for Chores

Song, Tao, Wang et al.
We study the problem of fair division of indivisible chores among $n$ agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. The goal is to produce an $α$-MMS allocation at the end. Several recent works have investigated this model, but have only succeeded in obtaining non-trivial algorithms under restrictive assumptions, such as the two-agent bi-valued special case (Wang and Wei, 2025), or by assuming knowledge of the total disutility of each agent (Zhou, Bai, and Wu, 2023). For the general case, the trivial $n$-MMS guarantee remains the best known, while the strongest lower bound is still only $2$. We close this gap on the negative side by proving that for any fixed $n$ and $\varepsilon$, no algorithm can guarantee an $(n - \varepsilon)$-MMS allocation. Notably, this lower bound holds precisely for every $n$, without hiding constants in big-$O$ notation, thereby exactly matching the trivial upper bound. Despite this strong impossibility result, we also present positive results. We provide an online algorithm that applies in the general case, guaranteeing a $\min\{n, O(k), O(\log D)\}$-MMS allocation, where $k$ is the maximum number of distinct disutilities across all agents and $D$ is the maximum ratio between the largest and smallest disutilities for any agent. This bound is reasonable across a broad range of scenarios and, for example, implies that we can achieve an $O(1)$-MMS allocation whenever $k$ is constant. Moreover, to optimize the constant in the important personalized bi-valued case, we show that if each agent has at most two distinct disutilities, our algorithm guarantees a $(2 + \sqrt{3}) \approx 3.7$-MMS allocation.
academic

Онлайн-распределение MMS для работ

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

  • ID статьи: 2507.14039
  • Название: Online MMS Allocation for Chores
  • Авторы: Jiaxin Song (University of Illinois Urbana-Champaign), Biaoshuai Tao (Shanghai Jiao Tong University), Wenqian Wang (Shanghai Jiao Tong University), Yuhao Zhang (Shanghai Jiao Tong University)
  • Классификация: cs.GT (Computer Science - Game Theory)
  • Дата публикации: 11 октября 2025 г. (arXiv v2)
  • Ссылка на статью: https://arxiv.org/abs/2507.14039

Аннотация

В данной работе исследуется задача справедливого распределения неделимых работ (chores) между n агентами в онлайн-среде. В этой постановке работы поступают последовательно и должны быть безвозвратно распределены агенту при их поступлении, с целью получить α-MMS распределение. Несмотря на недавние успехи при ограничивающих предположениях, для общего случая известная лучшая гарантия остаётся тривиальной n-MMS, а наиболее сильная нижняя граница составляет всего 2. В данной работе закрывается этот разрыв путём доказательства того, что для любых фиксированных n и ε не существует алгоритма, гарантирующего (n-ε)-MMS распределение. Одновременно предлагается онлайн-алгоритм, гарантирующий min{n, O(k), O(log D)}-MMS распределение, где k — максимальное количество различных отрицательных полезностей среди всех агентов, а D — максимальное отношение между наибольшей и наименьшей отрицательной полезностью любого агента.

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

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

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

2. Значимость исследования

Данная задача имеет широкое применение в реальности, например:

  • Распределение рабочих задач сотрудникам на онлайн-платформах обслуживания
  • Задачи балансировки нагрузки системы
  • Гарантии справедливости при планировании ресурсов

3. Ограничения существующих методов

Существующие исследования имеют следующие ограничения:

  • Нетривиальные результаты получены только при очень ограничивающих предположениях (например, для двух агентов с двумя значениями)
  • Требуется предварительное знание общей отрицательной полезности каждого агента
  • Для общего случая лучший известный алгоритм гарантирует только тривиальную n-MMS

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

Данная работа направлена на:

  • Определение теоретических пределов задачи онлайн-распределения MMS
  • Разработку практических алгоритмов для общего случая
  • Предоставление лучших гарантий производительности при реальных параметрических ограничениях

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

  1. Точная характеристика теоретической нижней границы: Доказано, что для любых фиксированных n и ε > 0 не существует алгоритма, гарантирующего (n-ε)-MMS распределение, полностью закрывая теоретический разрыв
  2. Универсальный онлайн-алгоритм: Предложен алгоритм для общего случая, гарантирующий min{n, O(k), O(log D)}-MMS распределение
  3. Параметризованный анализ: Когда k (количество различных отрицательных полезностей) является константой, алгоритм достигает O(1)-MMS гарантии
  4. Оптимизированный случай двух значений: Для персонализированного случая двух значений предоставлена улучшенная гарантия (2+√3) ≈ 3.7-MMS
  5. Новые методы анализа: Введена структура "Stacking Game", преобразующая задачу в специальную задачу минимизации различий

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

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

  • Входные данные: n агентов, m работ, поступающих последовательно
  • Ограничения: Каждая работа j имеет персонализированную отрицательную полезность d_i(j) для агента i, функция полезности аддитивна
  • Выходные данные: Распределение A = (A₁, ..., Aₙ), где Aᵢ — множество работ, распределённых агенту i
  • Цель: Достичь α-MMS распределения, то есть для всех i: d_i(Aᵢ) ≤ α · MMS_i

Архитектура модели

1. Обобщённая структура алгоритма round-robin

Алгоритм основан на расширении идеи round-robin:

  • Для каждого агента i и каждого типа отрицательной полезности θ поддерживается параметр давления H^θ_i
  • Параметр давления измеряет "перегруженность" агента относительно идеального распределения
  • Жадная стратегия: распределить поступившую работу агенту с минимальным давлением соответствующего типа

2. Техника округления значений

  • Округление отрицательной полезности каждой поступившей работы до ближайшей степени 2
  • Сокращение количества различных типов отрицательной полезности
  • Улучшение коэффициента конкуренции с O(k²) до O(k)

3. Механизм обновления давления

Когда поступает работа j:

  • Если агент i получает работу j (тип θ), то H^θ_i увеличивается на 1
  • Давление других агентов i' соответствующего типа H^θ_i' уменьшается на 1/(n-1)

Технические инновации

1. Абстракция Stacking Game

Абстрагирование задачи онлайн-распределения в непрерывную симметричную "игру укладки":

  • Поддержание неубывающей функции f на интервале (-1/2, 1/2]
  • Противник выбирает объединение интервалов с общей мерой 1/k
  • Алгоритм жадно поднимает более низкие части и опускает более высокие части
  • Доказано, что противник не может заставить значение функции превысить O(k)

2. Доказательство нижней границы через рекурсивную конструкцию

Разработана рекурсивная конструкция сложных примеров:

  • Определение T(n', ε) как количества раундов, необходимых n' агентам для достижения (n-ε)-MMS
  • Конструирование T(n'+1) сложного примера из T(n')
  • Хитрый механизм "очистки" делает предыдущее распределение пренебрежимо малым

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

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

Методы теоретической проверки

  1. Конструктивное доказательство: Доказательство нижних границ путём конкретного построения сложных примеров
  2. Доказательство по индукции: Использование математической индукции для доказательства гарантий производительности алгоритма
  3. Двойственный анализ: Анализ производительности алгоритма через двойственную задачу Stacking Game

Результаты экспериментов

Основные теоретические результаты

1. Точные результаты невозможности

Теорема 5: Для любых n и ε > 0 не существует онлайн-алгоритма, гарантирующего (n-ε)-MMS распределение.

Этот результат точен без скрытых констант в нотации O большое, полностью совпадая с тривиальной верхней границей.

2. Производительность универсального алгоритма

Теорема 1: Алгоритм 1 гарантирует min{n, O(k), O(log D)}-MMS распределение, где:

  • k — максимальное количество различных отрицательных полезностей среди всех агентов
  • D — максимальное отношение между наибольшей и наименьшей отрицательной полезностью любого агента

3. Оптимизация для случая двух значений

Теорема 6: Для персонализированного случая двух значений существует алгоритм, гарантирующий min{n, 2+√3}-MMS распределение, где 2+√3 ≈ 3.7.

Результаты технического анализа

1. Границы Stacking Game

Теорема 3: В Stacking Game противник не может получить выигрыш, превышающий 2k.

Этот результат является ядром анализа алгоритма и непосредственно приводит к коэффициенту конкуренции O(k).

2. Управление параметрами давления

Посредством анализа Stacking Game доказано, что все параметры давления H^θ_i могут быть сохранены в диапазоне O(k), что гарантирует производительность алгоритма.

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

1. Онлайн-балансировка нагрузки

Задача онлайн-распределения MMS тесно связана с классической задачей онлайн-балансировки нагрузки:

  • Пионерская работа Graham (1969)
  • Текущее лучшее соотношение конкуренции находится в диапазоне 1.88, 1.92

2. Автономное распределение MMS

Исследование распределения MMS в автономном случае:

  • Лучшая верхняя граница: 15/13 (Garg et al., 2025)
  • Лучшая нижняя граница: 44/43 (Feige et al., 2021)

3. Онлайн-справедливое распределение

Другие работы по онлайн-справедливому распределению:

  • Концепции справедливости, основанные на зависти
  • Модель с онлайн-поступлением агентов
  • Онлайн-распределение благ

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

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

  1. Полная характеристика теоретических пределов: Доказано, что n-MMS является точным теоретическим пределом задачи онлайн-распределения работ
  2. Разработка практических алгоритмов: Предоставлены универсальные алгоритмы с хорошей производительностью при параметрических ограничениях
  3. Вклад в методологию: Структура Stacking Game предоставляет новый инструмент анализа для подобных задач

Ограничения

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

Будущие направления

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

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

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

  1. Теоретическая полнота: Полное решение важной открытой задачи с предоставлением точных теоретических границ
  2. Техническая инновативность: Абстракция Stacking Game элегантно объединяет анализ при различных параметрах
  3. Практическая ценность: Предоставление значительно лучших гарантий производительности по сравнению с тривиальными алгоритмами при разумных параметрических диапазонах
  4. Глубина анализа: Доказательство нижней границы через рекурсивную конструкцию демонстрирует высокий уровень технического мастерства

Недостатки

  1. Отсутствие экспериментальной проверки: Как чисто теоретическая работа, отсутствует проверка на реальных данных
  2. Зависимость от параметров: Производительность алгоритма сильно зависит от значений k и D
  3. Анализ сложности: Отсутствует подробный анализ временной и пространственной сложности алгоритма

Влияние

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

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

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

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

Статья цитирует богатый набор связанных работ, включая:

  • Budish (2010): Введение концепции MMS
  • Zhou et al. (2023): Ранние работы по онлайн-распределению MMS
  • Wang and Wei (2025): Результаты для случая двух агентов с двумя значениями
  • Garg et al. (2025): Последние достижения в автономном распределении MMS

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