2025-11-17T18:43:12.758371

Fair and Efficient Allocation of Indivisible Mixed Manna

Barman, HV, Sethia et al.
We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness -- in terms of a relaxation of envy-freeness -- and Pareto efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to $k$ reallocations (EFR-$k$): An allocation $A$ of the indivisible items is said to be EFR-$k$ if there exists a subset $R$ of at most $k$ items such that, for each agent $i$, we can reassign items from within $R$ (in $A$) and obtain an allocation, $A^i$, which is envy-free for $i$. We establish that, when allocating mixed manna among $n$ agents with additive valuations, an EFR-$(n-1)$ and Pareto optimal (PO) allocation $A$ always exists. Further, the individual envy-free allocations $A^i$, induced by reassignments, are also PO. In addition, we prove that such fair and efficient allocations are efficiently computable when the number of agents, $n$, is fixed. We also obtain positive results focusing on EFR by itself (and without the PO desideratum). Specifically, we show that an EFR-$(n-1)$ allocation of mixed manna can be computed in polynomial time. In addition, we prove that when all the items are goods, an EFR-${\lfloor n/2 \rfloor}$ allocation exists and can be computed efficiently. Here, the $(n-1)$ bound is tight for chores and $\lfloor n/2 \rfloor$ is tight for goods. Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.
academic

Справедливое и эффективное распределение неделимой смешанной манны

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

  • ID статьи: 2507.03946
  • Название: Fair and Efficient Allocation of Indivisible Mixed Manna
  • Авторы: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
  • Классификация: cs.GT (Computer Science - Game Theory)
  • Дата публикации: 15 октября 2025 г. (вторая версия препринта arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2507.03946v2

Аннотация

В данной работе исследуется проблема справедливого распределения неделимой смешанной манны между агентами с аддитивными оценками стоимости. Смешанная манна представляет собой набор благ, стоимость которых может быть положительной, отрицательной или нулевой. Авторы устанавливают теоретические гарантии того, что справедливость (основанная на ослаблении концепции отсутствия зависти) и эффективность по Парето могут быть достигнуты одновременно. В частности, гарантия справедливости основана на концепции "отсутствия зависти при k переделах" (EFR-k): распределение A является EFR-k, если существует подмножество R из не более чем k благ такое, что для каждого агента i путём переделения благ из R можно получить распределение A^i, свободное от зависти к i.

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

Определение проблемы

Справедливое распределение — это проблема, часто возникающая в реальных сценариях, таких как раздел имущества, распределение задач, разрешение пограничных споров и распределение долгов. Когда участвующие агенты имеют личные предпочтения, вопрос "кто получает что" имеет как практическую срочность, так и теоретическую значимость.

Исследовательские вызовы

  1. Сложность смешанной манны: В отличие от чистых благ или работ, знак стоимости благ в смешанной манне может различаться для разных агентов, что делает распределение более сложным.
  2. Компромисс между справедливостью и эффективностью: В условиях неделимых благ традиционное отсутствие зависти не гарантируется, поэтому необходимо найти подходящее ослабление этого условия.
  3. Ограничения существующих методов:
    • Для распределения работ существование EF1 и распределений, оптимальных по Парето, остаётся нерешённым даже для четырёх агентов
    • Для смешанной манны эта проблема остаётся открытой даже для трёх агентов
    • Существующие рыночные методы не распространяются прямо на случаи с отрицательными оценками

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

Работа направлена на предоставление теоретических гарантий справедливого и эффективного распределения смешанной манны путём введения концепции EFR-k и разработки эффективных вычислительных алгоритмов.

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

  1. Теоретические гарантии существования: Доказано, что для распределения смешанной манны между n агентами с аддитивными оценками всегда существует распределение, которое одновременно является EFR-(n-1) и оптимальным по Парето.
  2. Вычислительная реализуемость: Когда количество агентов n фиксировано, распределение, которое является EFR-(n-1) и оптимальным по Парето, может быть вычислено за полиномиальное время.
  3. Независимые результаты EFR:
    • Распределение смешанной манны, которое является EFR-(n-1), может быть вычислено за полиномиальное время
    • Когда все блага являются товарами, существует распределение EFR-⌊n/2⌋ и оно может быть эффективно вычислено
  4. Результаты точности границ:
    • Для работ граница (n-1) является точной
    • Для товаров граница ⌊n/2⌋ является точной
  5. Технические инновации: Впервые применена теорема Кнастера-Куратовского-Мазуркевича (KKM) в дискретном справедливом распределении.

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

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

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

  • n агентов, обозначаемых n = {1,...,n}
  • m неделимых благ, обозначаемых m = {1,...,m}
  • Аддитивные функции оценки {vi}i∈n, где vi(t) ∈ ℝ представляет оценку агентом i блага t

Выходные данные: Распределение A = (A1,...,An), где Ai ⊆ m — набор благ, распределённых агенту i

Цель: Найти распределение, одновременно удовлетворяющее EFR-k и оптимальности по Парето

Основные концепции

Определение EFR-k

Распределение A является EFR-k тогда и только тогда, когда существует подмножество R ⊆ m размером не более k такое, что для каждого агента i путём переделения благ из R можно получить распределение A^i, свободное от зависти к i.

Ключевые технические компоненты

  1. Возмущение оценок: Для получения невырожденных условий к заданным оценкам добавляется достаточно малое аддитивное возмущение:
    v̄i(t) = vi(t) - εi,t

    где εi,t равномерно выбирается из (0,ε).
  2. Смещение весов: Для каждого вектора весов w ∈ Δn-1 каждая компонента смещается на параметр η > 0:
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. KKM-покрытие: Для каждого агента i определяется множество
    Ci := {w ∈ Δn-1 : существует распределение Xi ∈ Oη(w) такое, что i не испытывает зависти при Xi}

Основная схема алгоритма

Схема доказательства теоремы 3.1

  1. Построение возмущённых оценок: Обеспечение свойства невырожденности
  2. Определение KKM-покрытия: Построение семейства замкнутых множеств {Ci}, удовлетворяющих условию KKM
  3. Применение теоремы KKM: Получение пересечения w* ∈ ∩i Ci
  4. Подсчётный аргумент: Доказательство того, что размер множества переделов R не превышает n-1

Алгоритм 1: Последовательность выбора с учётом конфликтов для товаров

Для случая чистых товаров разработан алгоритм на основе циклического выбора:

  • Фаза разрешения конфликтов: Выявление благ, наиболее предпочитаемых несколькими агентами одновременно, и добавление их в множество переделов R
  • Фаза выбора: Активные агенты выбирают наиболее предпочитаемое благо в лексикографическом порядке

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

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

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

Теоретическая аналитическая схема

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

  1. Доказательства существования: Использование теоремы KKM для доказательства существования распределений EFR-(n-1) и PO
  2. Анализ точности границ: Построение контрпримеров для доказательства точности границ
  3. Анализ сложности алгоритмов: Анализ временной сложности алгоритмов

Анализ сложности

  • Фиксированное количество агентов: Распределения EFR-(n-1) и PO могут быть вычислены за время m^poly(n)
  • Общий случай: Распределение EFR-(n-1) может быть вычислено за полиномиальное время
  • Случай товаров: Распределение EFR-⌊n/2⌋ может быть вычислено за полиномиальное время

Экспериментальные результаты

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

Теорема 3.1 (Основной результат существования)

Для каждого экземпляра справедливого распределения неделимой смешанной манны с аддитивными оценками существует распределение, которое одновременно является EFR-(n-1) и оптимальным по Парето.

Теорема 4.1 (Результат вычислимости)

Для экземпляра распределения смешанной манны с фиксированным количеством агентов распределение, которое является EFR-(n-1) и оптимальным по Парето, может быть вычислено за полиномиальное время.

Теорема 5.1 (Независимый результат EFR)

Для экземпляра справедливого распределения смешанной манны с аддитивными оценками всегда существует распределение, которое одновременно является EFR-(n-1) и EF1, и оно может быть вычислено за полиномиальное время.

Теорема 5.4 (Улучшенная граница для товаров)

Для экземпляра справедливого распределения чистых товаров алгоритм 1 вычисляет распределение EFR-⌊n/2⌋ за полиномиальное время.

Результаты точности границ

Теорема 5.2 (Точность границы для работ)

Существует экземпляр распределения работ, для которого не существует распределения EFR-(n-2), что доказывает точность границы (n-1).

Теорема 5.5 (Точность границы для товаров)

Существует экземпляр распределения товаров, для которого не существует распределения EFR-(⌊n/2⌋-1), что доказывает точность границы ⌊n/2⌋.

Результаты вычислительной сложности

Теорема A.1 (Сложность задачи решения)

Задача определения того, является ли распределение A распределением EFR-k при заданном k < n-2, является NP-полной.

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

Классическая теория справедливого распределения

  • Делимый случай: Классические результаты Вариана и Веллера показывают, что отсутствие зависти и оптимальность по Парето могут быть достигнуты одновременно
  • Неделимые товары: Существует развитая теория одновременного достижения EF1 и PO (максимизация социального благосостояния Нэша)

Вызовы в распределении работ и смешанной манны

  • Распределение работ: Существование EF1+PO остаётся нерешённым даже для четырёх агентов
  • Смешанная манна: Существование EF1+PO для трёх агентов остаётся открытой проблемой
  • Методологические различия: Не существует функции, подобной социальному благосостоянию Нэша, которая гарантировала бы EF1 для работ

Связанные концепции ослабления

  • EF1: Устранение зависти путём удаления одного блага
  • EFX: Устранение зависти путём удаления любого блага
  • Дробное распределение: Отсутствие зависти при дробном распределении не более (n-1) благ

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

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

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

Ограничения

  1. Границы: Граница EFR-(n-1) относительно велика, в среднем требуя переделения примерно двух благ на агента
  2. Предположение о фиксированном количестве агентов: Алгоритм полиномиального времени требует фиксированного количества агентов
  3. Ограничение аддитивности: Результаты применимы только к аддитивным функциям оценки

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

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

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

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

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

Недостатки

  1. Ограниченная практическая применимость: Граница EFR-(n-1) может быть слишком велика для практического применения
  2. Отсутствие эмпирической оценки: Как теоретическая работа, отсутствует оценка производительности на реальных данных
  3. Эффективность алгоритмов: Сложность m^poly(n) при фиксированном количестве агентов может быть высокой на практике

Влияние

  1. Академическое влияние: Значительный вклад в теорию справедливого распределения, ожидается широкое цитирование
  2. Методологическая ценность: Применение теоремы KKM может вдохновить дальнейшие исследования в смежных областях
  3. Практические перспективы: Предоставление теоретической основы для проектирования практических систем распределения

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

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

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

Статья цитирует важные работы в области справедливого распределения, включая:

  • Budish (2011): Введение концепции EF1
  • Caragiannis et al. (2019): Связь между социальным благосостоянием Нэша и EF1+PO
  • Aziz et al. (2022): Существование EF1 для смешанной манны
  • Sandomirskiy & Segal-Halevi (2022): Связанные результаты для дробного распределения

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