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

Allocation Équitable et Efficace de la Manne Mixte Indivisible

Informations Fondamentales

  • ID de l'article: 2507.03946
  • Titre: Fair and Efficient Allocation of Indivisible Mixed Manna
  • Auteurs: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
  • Classification: cs.GT (Informatique - Théorie des Jeux)
  • Date de publication: 15 octobre 2025 (prépublication arXiv version 2)
  • Lien de l'article: https://arxiv.org/abs/2507.03946v2

Résumé

Cet article étudie le problème de l'allocation équitable de la manne mixte indivisible entre des agents ayant des évaluations additives. La manne mixte désigne des biens dont la valeur peut être positive, négative ou nulle. L'article établit des garanties théoriques selon lesquelles l'équité (basée sur un assouplissement de l'absence d'envie) et l'efficacité de Pareto peuvent être réalisées simultanément. Plus précisément, la garantie d'équité repose sur le concept d'« absence d'envie avec k réallocations » (EFR-k) : une allocation A est EFR-k si, pour chaque agent i, il existe un sous-ensemble R d'au plus k biens tel que la réallocation des biens de R produit une allocation A^i sans envie envers i.

Contexte et Motivation de la Recherche

Définition du Problème

L'allocation équitable est un problème qui apparaît fréquemment dans des scénarios réels tels que le partage de biens, l'attribution de tâches, les différends frontaliers et la répartition des dettes. Lorsque les agents participants ont des préférences personnelles, la question « qui obtient quoi » présente à la fois une urgence pratique et une richesse théorique.

Défis de la Recherche

  1. Complexité de la manne mixte: Contrairement aux biens purs ou aux corvées, la valeur des biens dans la manne mixte peut avoir des signes différents selon les agents, ce qui rend l'allocation plus complexe.
  2. Compromis entre équité et efficacité: Dans le contexte des biens indivisibles, l'absence d'envie traditionnelle (envy-freeness) ne peut pas être garantie, ce qui nécessite de trouver des conditions d'assouplissement appropriées.
  3. Limitations des approches existantes:
    • Pour l'allocation de corvées, l'existence simultanée d'allocations EF1 et Pareto-optimales reste non résolue même pour quatre agents
    • Pour la manne mixte, ce problème reste ouvert même pour trois agents
    • Les approches basées sur le marché ne s'étendent pas directement lorsque les évaluations sont négatives

Motivation de la Recherche

L'article vise à fournir des garanties théoriques pour l'allocation équitable et efficace de la manne mixte en introduisant le concept EFR-k et en développant des algorithmes de calcul efficaces.

Contributions Principales

  1. Garanties d'existence théorique: Démonstration que pour l'allocation de manne mixte entre n agents ayant des évaluations additives, il existe toujours une allocation EFR-(n-1) et Pareto-optimale.
  2. Calculabilité algorithmique: Lorsque le nombre d'agents n est fixe, une allocation EFR-(n-1) et Pareto-optimale peut être calculée en temps polynomial.
  3. Résultats EFR indépendants:
    • L'allocation de manne mixte EFR-(n-1) peut être calculée en temps polynomial
    • Lorsque tous les biens sont des marchandises, une allocation EFR-⌊n/2⌋ existe et peut être calculée efficacement
  4. Résultats de serrage:
    • Pour les corvées, la limite (n-1) est serrée
    • Pour les marchandises, la limite ⌊n/2⌋ est serrée
  5. Innovation technique: Application pour la première fois du théorème de Knaster-Kuratowski-Mazurkiewicz (KKM) en allocation équitable discrète.

Explication Détaillée de la Méthode

Définition de la Tâche

Entrée:

  • n agents, notés n = {1,...,n}
  • m biens indivisibles, notés m = {1,...,m}
  • Fonctions d'évaluation additives {vi}i∈n, où vi(t) ∈ ℝ représente l'évaluation du bien t par l'agent i

Sortie: Allocation A = (A1,...,An), où Ai ⊆ m est l'ensemble des biens alloués à l'agent i

Objectif: Trouver une allocation satisfaisant simultanément EFR-k et Pareto-optimalité

Concepts Fondamentaux

Définition d'EFR-k

Une allocation A est EFR-k si et seulement s'il existe un sous-ensemble R ⊆ m de taille au plus k tel que pour chaque agent i, la réallocation des biens de R produit une allocation A^i sans envie envers i.

Composants Techniques Clés

  1. Perturbation des évaluations: Pour obtenir des conditions non dégénérées, une perturbation additive suffisamment petite est ajoutée aux évaluations données :
    v̄i(t) = vi(t) - εi,t

    où εi,t est tiré uniformément de (0,ε).
  2. Décalage des poids: Pour chaque vecteur de poids w ∈ Δn-1, chaque composante est décalée par un paramètre η > 0 :
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. Couverture KKM: Pour chaque agent i, l'ensemble est défini comme
    Ci := {w ∈ Δn-1 : il existe une allocation Xi ∈ Oη(w) telle que i soit sans envie sous Xi}

Cadre Algorithmique Principal

Approche de Preuve du Théorème 3.1

  1. Construction d'évaluations perturbées: Assurer la propriété de non-dégénérescence
  2. Définition de la couverture KKM: Construire une famille d'ensembles fermés {Ci} satisfaisant la condition KKM
  3. Application du théorème KKM: Obtenir l'intersection w* ∈ ∩i Ci
  4. Argument de comptage: Prouver que la taille de l'ensemble de réallocation R est au plus n-1

Algorithme 1 : Sélection en Séquence Consciente des Conflits pour les Marchandises

Pour le cas des marchandises pures, un algorithme basé sur le tour de rôle est conçu :

  • Phase de résolution des conflits: Identifier les marchandises préférées identiques par plusieurs agents, les ajouter à l'ensemble de réallocation R
  • Phase de sélection: Les agents actifs sélectionnent la marchandise la plus préférée selon l'ordre lexicographique

Points d'Innovation Technique

  1. Nouvelle application du théorème KKM: Application pour la première fois du théorème KKM classique aux problèmes d'allocation équitable discrète, fournissant une voie technique complètement différente des approches basées sur le marché existantes.
  2. Technique de perturbation: Assurer la non-dégénérescence par une perturbation d'évaluation soigneusement conçue, de sorte que le problème de maximisation du bien-être social pondéré possède de bonnes propriétés.
  3. Argument de comptage: Utiliser l'acyclicité des graphes bipartis pour prouver les limites de la taille de l'ensemble de réallocation.

Configuration Expérimentale

Cadre d'Analyse Théorique

Comme il s'agit d'un article théorique, les résultats sont vérifiés principalement par des preuves mathématiques plutôt que par des expériences empiriques. L'article adopte le cadre d'analyse suivant :

  1. Preuve d'existence: Utiliser le théorème KKM pour prouver l'existence d'allocations EFR-(n-1) et PO
  2. Analyse de serrage: Construire des contre-exemples pour prouver le serrage des limites
  3. Complexité algorithmique: Analyser la complexité temporelle des algorithmes

Analyse de Complexité

  • Nombre d'agents fixe: Les allocations EFR-(n-1) et PO peuvent être calculées en temps m^poly(n)
  • Cas général: L'allocation EFR-(n-1) peut être calculée en temps polynomial
  • Cas des marchandises: L'allocation EFR-⌊n/2⌋ peut être calculée en temps polynomial

Résultats Expérimentaux

Résultats Théoriques Principaux

Théorème 3.1 (Résultat d'Existence Principal)

Chaque instance d'allocation équitable de manne mixte indivisible avec évaluations additives admet une allocation EFR-(n-1) et Pareto-optimale.

Théorème 4.1 (Résultat de Calculabilité)

Pour une instance d'allocation de manne mixte avec un nombre fixe d'agents, une allocation EFR-(n-1) et Pareto-optimale peut être calculée en temps polynomial.

Théorème 5.1 (Résultat EFR Indépendant)

Pour chaque instance d'allocation équitable de manne mixte avec évaluations additives, il existe toujours une allocation qui est à la fois EFR-(n-1) et EF1, et peut être calculée en temps polynomial.

Théorème 5.4 (Limite Améliorée pour les Marchandises)

Pour une instance d'allocation équitable de marchandises pures, l'Algorithme 1 calcule une allocation EFR-⌊n/2⌋ en temps polynomial.

Résultats de Serrage

Théorème 5.2 (Serrage pour les Corvées)

Il existe une instance d'allocation de corvées n'admettant pas d'allocation EFR-(n-2), prouvant que la limite (n-1) est serrée.

Théorème 5.5 (Serrage pour les Marchandises)

Il existe une instance d'allocation de marchandises n'admettant pas d'allocation EFR-(⌊n/2⌋-1), prouvant que la limite ⌊n/2⌋ est serrée.

Résultats de Complexité Computationnelle

Théorème A.1 (Complexité du Problème de Décision)

Étant donné une allocation A et un entier positif k < n-2, déterminer si A est EFR-k est NP-complet.

Travaux Connexes

Théorie Classique de l'Allocation Équitable

  • Cas divisible: Les résultats classiques de Varian et Weller montrent que l'absence d'envie et PO peuvent être réalisées simultanément
  • Marchandises indivisibles: La réalisation simultanée d'EF1 et PO dispose d'une théorie mature (maximisation du bien-être social de Nash)

Défis des Corvées et de la Manne Mixte

  • Allocation de corvées: L'existence d'EF1+PO pour quatre agents reste non résolue
  • Manne mixte: L'existence d'EF1+PO pour trois agents reste un problème ouvert
  • Différence méthodologique: Il n'existe pas de fonction analogue au bien-être social de Nash garantissant EF1 pour les corvées

Concepts de Relaxation Connexes

  • EF1: Éliminer l'envie en supprimant un bien
  • EFX: Éliminer l'envie en supprimant un bien arbitraire
  • Allocation fractionnaire: Absence d'envie avec allocation fractionnaire d'au plus (n-1) biens

Conclusion et Discussion

Conclusions Principales

  1. Percée théorique: Première fourniture de garanties simultanées d'équité et d'efficacité pour le cadre général de la manne mixte
  2. Innovation technique: La nouvelle application du théorème KKM en allocation équitable discrète ouvre de nouvelles directions de recherche
  3. Valeur pratique: Les résultats algorithmiques fournissent une base de calcul pour les applications pratiques

Limitations

  1. Limites: La limite EFR-(n-1) est relativement grande, nécessitant en moyenne environ 2 biens à réallouer par agent
  2. Hypothèse d'agents fixes: L'algorithme en temps polynomial nécessite que le nombre d'agents soit fixe
  3. Restriction aux évaluations additives: Les résultats ne s'appliquent qu'aux fonctions d'évaluation additives

Directions Futures

  1. Amélioration des limites: Rechercher des ensembles de réallocation R plus petits
  2. Extension des types d'évaluation: Considérer les fonctions d'évaluation non-additives
  3. Applications pratiques: Appliquer les résultats théoriques à des scénarios d'allocation concrets

Évaluation Approfondie

Avantages

  1. Contribution théorique majeure: Résout le problème fondamental de l'allocation équitable et efficace de la manne mixte
  2. Techniques novatrices: L'application du théorème KKM démontre une perspicacité mathématique profonde
  3. Résultats complets: Comprend à la fois l'existence et les algorithmes, à la fois les bornes supérieures et inférieures
  4. Preuves rigoureuses: Dérivations mathématiques complètes et traitement approprié des détails techniques

Insuffisances

  1. Applicabilité pratique limitée: La limite EFR-(n-1) peut être trop grande pour les applications pratiques
  2. Absence d'évaluation empirique: En tant qu'article théorique, il manque d'évaluation de performance sur des données réelles
  3. Efficacité algorithmique: La complexité m^poly(n) pour un nombre fixe d'agents peut être élevée en pratique

Impact

  1. Impact académique: Contribution importante à la théorie de l'allocation équitable, prévu d'être largement cité
  2. Valeur méthodologique: L'application du théorème KKM peut inspirer davantage de recherches connexes
  3. Perspectives pratiques: Fournit une base théorique pour la conception de systèmes d'allocation réels

Scénarios Applicables

  1. Partage de succession: Scénarios complexes de partage impliquant actifs et dettes
  2. Attribution de tâches: Allocation de tâches comprenant à la fois des tâches attrayantes et peu attrayantes
  3. Gestion des ressources: Problèmes de répartition des ressources nécessitant de considérer simultanément revenus et coûts

Références Bibliographiques

L'article cite d'importantes références dans le domaine de l'allocation équitable, notamment :

  • Budish (2011): Introduction du concept EF1
  • Caragiannis et al. (2019): Relation entre bien-être social de Nash et EF1+PO
  • Aziz et al. (2022): Existence d'EF1 pour la manne mixte
  • Sandomirskiy & Segal-Halevi (2022): Résultats connexes sur l'allocation fractionnaire

Évaluation Générale: Cet article théorique de haute qualité fournit des garanties théoriques importantes pour l'allocation équitable et efficace de la manne mixte en introduisant le concept EFR et en appliquant le théorème KKM. Bien qu'il présente certaines limitations en termes d'applicabilité pratique, ses contributions théoriques et innovations techniques en font un progrès important dans le domaine de l'allocation équitable.