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

Allocation MMS en Ligne pour les Tâches

Informations Fondamentales

  • ID de l'article: 2507.14039
  • Titre: Online MMS Allocation for Chores
  • Auteurs: 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)
  • Classification: cs.GT (Informatique - Théorie des Jeux)
  • Date de publication: 11 octobre 2025 (arXiv v2)
  • Lien de l'article: https://arxiv.org/abs/2507.14039

Résumé

Cet article étudie le problème de l'allocation équitable de tâches indivisibles (chores) entre n agents dans un environnement en ligne. Dans ce cadre, les tâches arrivent séquentiellement et doivent être allouées de manière irrévocable à un agent au moment de leur arrivée, l'objectif étant de produire une allocation α-MMS. Bien que des travaux récents aient fait des progrès sous des hypothèses restrictives, pour le cas général, la meilleure garantie connue reste triviale (n-MMS), tandis que la borne inférieure la plus forte est seulement 2. Cet article ferme cet écart sur les résultats négatifs en prouvant qu'aucun algorithme ne peut garantir une allocation (n-ε)-MMS pour tout n et ε fixés. Parallèlement, l'article propose un algorithme en ligne garantissant une allocation min{n, O(k), O(log D)}-MMS, où k est le nombre maximal de valeurs d'utilité négative distinctes parmi tous les agents et D est le rapport maximal entre l'utilité négative maximale et minimale de tout agent.

Contexte de Recherche et Motivation

1. Définition du Problème

Cet article étudie le problème de l'allocation équitable en ligne de tâches indivisibles. Contrairement à l'allocation traditionnelle de biens, les tâches possèdent une utilité négative, et les agents souhaitent assumer le moins de tâches possible. Dans le cadre en ligne, les tâches arrivent séquentiellement, et l'algorithme doit allouer immédiatement chaque tâche à un agent à son arrivée, les décisions d'allocation étant irrévocables.

2. Importance de la Recherche

Ce problème présente des applications pratiques étendues, notamment:

  • L'allocation de tâches de travail aux employés sur les plateformes de services en ligne
  • Les problèmes d'équilibrage de charge système
  • Les garanties d'équité dans l'ordonnancement des ressources

3. Limitations des Méthodes Existantes

La recherche existante présente les limitations suivantes:

  • Les résultats non triviaux ne sont obtenus que sous des hypothèses très restrictives (par exemple, le cas à deux agents et deux valeurs)
  • Nécessite la connaissance préalable de l'utilité négative totale de chaque agent
  • Pour le cas général, le meilleur algorithme connu ne peut garantir que la triviale n-MMS

4. Motivation de la Recherche

Cet article vise à:

  • Déterminer les limites théoriques du problème d'allocation MMS en ligne
  • Concevoir des algorithmes pratiques applicables au cas général
  • Fournir de meilleures garanties de performance sous des contraintes de paramètres réalistes

Contributions Principales

  1. Caractérisation Précise des Bornes Théoriques: Preuve que pour tout n et ε > 0 fixés, aucun algorithme ne peut garantir une allocation (n-ε)-MMS, fermant complètement l'écart théorique
  2. Algorithme en Ligne Universel: Proposition d'un algorithme applicable au cas général, garantissant une allocation min{n, O(k), O(log D)}-MMS
  3. Analyse Paramétrée: Lorsque k (nombre de valeurs d'utilité négative distinctes) est constant, l'algorithme réalise une garantie O(1)-MMS
  4. Cas Binaire Optimisé: Pour le cas binaire personnalisé, fourniture d'une garantie améliorée de (2+√3) ≈ 3.7-MMS
  5. Nouvelles Techniques d'Analyse: Introduction du cadre "Stacking Game" transformant le problème en un problème spécial de minimisation des divergences

Détails Méthodologiques

Définition de la Tâche

  • Entrée: n agents, m tâches arrivant séquentiellement
  • Contraintes: Chaque tâche j possède une utilité négative personnalisée d_i(j) pour l'agent i, les fonctions d'utilité négative étant additives
  • Sortie: Allocation A = (A₁, ..., Aₙ), où A_i est l'ensemble des tâches allouées à l'agent i
  • Objectif: Réaliser une allocation α-MMS, c'est-à-dire pour tout i, d_i(A_i) ≤ α · MMS_i

Architecture du Modèle

1. Cadre Algorithmique de Rotation Généralisée

L'algorithme repose sur une extension de l'idée de rotation (round-robin):

  • Maintien d'un paramètre de pression H^θ_i pour chaque type d'utilité négative θ de chaque agent i
  • Le paramètre de pression mesure le degré de "surcharge" de l'agent par rapport à l'allocation idéale
  • Stratégie gloutonne: allouer la nouvelle tâche arrivée à l'agent ayant la pression minimale pour le type correspondant

2. Technique d'Arrondi des Valeurs

  • Arrondir l'utilité négative de chaque tâche arrivée à la puissance de 2 la plus proche
  • Réduire le nombre de types d'utilité négative distincts
  • Améliorer le ratio de compétition de O(k²) à O(k)

3. Mécanisme de Mise à Jour de la Pression

Lorsqu'une tâche j arrive:

  • Si l'agent i reçoit la tâche j (type θ), alors H^θ_i augmente de 1
  • Pour les autres agents i', la pression correspondante H^θ_{i'} diminue de 1/(n-1)

Points d'Innovation Technique

1. Abstraction du Stacking Game

Abstraction du problème d'allocation en ligne en un "jeu d'empilement" continu symétrique:

  • Maintien d'une fonction non décroissante f sur l'intervalle (-1/2, 1/2]
  • L'adversaire choisit une union d'intervalles de mesure totale 1/k
  • L'algorithme élève goulûment les parties inférieures et abaisse les parties supérieures
  • Preuve que l'adversaire ne peut pas faire dépasser la valeur de la fonction au-delà de O(k)

2. Preuve de Borne Inférieure par Construction Récursive

Conception d'une construction récursive d'instances difficiles:

  • Définition de T(n', ε) comme le nombre de tours nécessaires pour n' agents pour atteindre (n-ε)-MMS
  • Construction d'une instance difficile pour T(n'+1) à partir de T(n')
  • Mécanisme de "nettoyage" ingénieux rendant les allocations précédentes négligeables

Configuration Expérimentale

Cet article est principalement un travail théorique sans évaluation expérimentale au sens traditionnel, mais plutôt une vérification des résultats théoriques par preuve mathématique.

Méthodes de Vérification Théorique

  1. Preuve Constructive: Preuve des bornes inférieures par construction explicite d'instances difficiles
  2. Preuve par Induction: Utilisation de l'induction mathématique pour prouver les garanties de performance de l'algorithme
  3. Analyse Duale: Analyse de la performance de l'algorithme via le problème dual du Stacking Game

Résultats Expérimentaux

Résultats Théoriques Principaux

1. Résultats d'Impossibilité Précis

Théorème 5: Pour tout n et ε > 0, aucun algorithme en ligne ne peut garantir une allocation (n-ε)-MMS.

Ce résultat est précis, sans constante cachée dans la notation O, correspondant exactement à la borne supérieure triviale.

2. Performance de l'Algorithme Universel

Théorème 1: L'algorithme 1 garantit une allocation min{n, O(k), O(log D)}-MMS, où:

  • k est le nombre maximal de valeurs d'utilité négative distinctes parmi tous les agents
  • D est le rapport maximal entre l'utilité négative maximale et minimale de tout agent

3. Optimisation du Cas Binaire

Théorème 6: Pour le cas binaire personnalisé, il existe un algorithme garantissant une allocation min{n, 2+√3}-MMS, où 2+√3 ≈ 3.7.

Résultats d'Analyse Technique

1. Limites du Stacking Game

Théorème 3: Dans le Stacking Game, l'adversaire ne peut pas obtenir un gain supérieur à 2k.

Ce résultat est au cœur de l'analyse algorithmique, conduisant directement au ratio de compétition O(k).

2. Contrôle des Paramètres de Pression

Par l'analyse du Stacking Game, preuve que tous les paramètres de pression H^θ_i peuvent être maintenus dans la plage O(k), garantissant ainsi la performance de l'algorithme.

Travaux Connexes

1. Équilibrage de Charge en Ligne

Le problème d'allocation MMS en ligne est étroitement lié au problème classique d'équilibrage de charge en ligne:

  • Travail fondateur de Graham (1969)
  • Meilleur ratio de compétition actuel dans 1.88, 1.92

2. Allocation MMS Hors Ligne

Recherche sur l'allocation MMS dans le cadre hors ligne:

  • Meilleure borne supérieure: 15/13 (Garg et al., 2025)
  • Meilleure borne inférieure: 44/43 (Feige et al., 2021)

3. Allocation Équitable en Ligne

Autres travaux sur l'allocation équitable en ligne:

  • Concepts d'équité basés sur l'absence d'envie
  • Modèle d'arrivée en ligne des agents
  • Allocation en ligne de biens

Conclusion et Discussion

Conclusions Principales

  1. Caractérisation Complète des Limites Théoriques: Preuve que n-MMS est la limite théorique précise du problème d'allocation de tâches en ligne
  2. Conception d'Algorithmes Pratiques: Fourniture d'un algorithme universel performant sous contraintes de paramètres
  3. Contribution Méthodologique: Le cadre du Stacking Game fournit un nouvel outil d'analyse pour ce type de problèmes

Limitations

  1. Praticité des Instances Difficiles: La construction théorique des bornes inférieures nécessite des rapports d'utilité négative extrêmes et un grand nombre de valeurs d'utilité négative distinctes
  2. Connaissance Préalable de l'Algorithme: L'algorithme optimisé pour le cas binaire nécessite de savoir à l'avance que chaque agent a au maximum deux types d'utilité négative
  3. Facteurs Constants: Bien qu'asymptotiquement optimal, les facteurs constants laissent place à l'amélioration

Directions Futures

  1. Amélioration des Facteurs Constants: Optimisation supplémentaire du ratio de compétition dans les cas particuliers
  2. Autres Concepts d'Équité: Extension à d'autres concepts d'équité comme l'absence d'envie
  3. Applications Pratiques: Application des résultats théoriques à des scénarios concrets d'équilibrage de charge et d'ordonnancement de tâches

Évaluation Approfondie

Avantages

  1. Complétude Théorique: Résolution complète d'un problème ouvert important, fournissant des bornes théoriques précises
  2. Innovation Technique: L'abstraction du Stacking Game unifie élégamment l'analyse sous différents paramètres
  3. Valeur Pratique: Fournit des garanties de performance significativement meilleures que l'algorithme trivial dans des plages de paramètres raisonnables
  4. Profondeur d'Analyse: La preuve de borne inférieure par construction récursive démontre un haut niveau technique

Insuffisances

  1. Absence de Vérification Expérimentale: En tant que travail purement théorique, manque de vérification sur données réelles
  2. Dépendance aux Paramètres: La performance de l'algorithme dépend fortement des valeurs de k et D
  3. Analyse de Complexité: Pas d'analyse détaillée de la complexité temporelle et spatiale de l'algorithme

Impact

  1. Contribution Théorique: Fournit une base théorique importante pour la théorie de l'allocation équitable en ligne
  2. Valeur Méthodologique: La technique du Stacking Game peut s'appliquer à d'autres problèmes connexes
  3. Orientation Pratique: Fournit des orientations théoriques pour la conception de systèmes réels

Scénarios d'Application

  1. Ordonnancement de Tâches en Ligne: Applicable aux systèmes d'allocation de tâches nécessitant des garanties d'équité
  2. Équilibrage de Charge: Peut s'appliquer à des scénarios d'équilibrage de charge multi-serveurs
  3. Allocation de Ressources: Applicable à divers problèmes d'allocation de ressources en ligne

Références Bibliographiques

L'article cite de nombreux travaux connexes, notamment:

  • Budish (2010): Introduction du concept MMS
  • Zhou et al. (2023): Travaux précoces sur l'allocation MMS en ligne
  • Wang and Wei (2025): Résultats pour le cas binaire à deux agents
  • Garg et al. (2025): Avancées récentes en allocation MMS hors ligne

Cet article apporte des contributions importantes dans les domaines de l'informatique théorique et de la théorie algorithmique des jeux. Non seulement il résout complètement un problème ouvert important, mais il fournit également une conception algorithmique pratique et des techniques d'analyse novatrices. Bien que principalement un travail théorique, ses résultats ont une importance significative pour les applications pratiques.