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

Asignación en Línea de MMS para Tareas

Información Básica

  • ID del Artículo: 2507.14039
  • Título: Online MMS Allocation for Chores
  • Autores: 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)
  • Clasificación: cs.GT (Ciencia de la Computación - Teoría de Juegos)
  • Fecha de Publicación: 11 de octubre de 2025 (arXiv v2)
  • Enlace del Artículo: https://arxiv.org/abs/2507.14039

Resumen

Este artículo estudia el problema de la asignación justa de tareas indivisibles entre n agentes en un entorno en línea. En esta configuración, los elementos llegan secuencialmente y deben asignarse de manera irrevocable a algún agente en el momento de su llegada, con el objetivo de producir una asignación α-MMS. Aunque trabajos recientes han logrado avances bajo supuestos restrictivos, para el caso general, la mejor garantía conocida sigue siendo la trivial n-MMS, mientras que la cota inferior más fuerte es solo 2. Este artículo cierra la brecha en resultados negativos demostrando que para cualquier n fijo y ε, ningún algoritmo puede garantizar una asignación (n-ε)-MMS. Simultáneamente, se propone un algoritmo en línea que garantiza una asignación min{n, O(k), O(log D)}-MMS, donde k es el número máximo de valores de utilidad negativa distintos entre todos los agentes, y D es la razón máxima entre la utilidad negativa máxima y mínima de cualquier agente.

Antecedentes y Motivación de la Investigación

1. Definición del Problema

Este artículo estudia el problema de asignación justa en línea de tareas indivisibles. A diferencia de la asignación tradicional de bienes, las tareas tienen utilidad negativa y los agentes desean asumir la menor cantidad posible de tareas. En la configuración en línea, las tareas llegan secuencialmente y el algoritmo debe asignar inmediatamente cada tarea a algún agente en el momento de su llegada, siendo las decisiones de asignación irrevocables.

2. Importancia de la Investigación

Este problema tiene amplias aplicaciones en la práctica, tales como:

  • Asignación de tareas laborales a empleados en plataformas de servicios en línea
  • Problemas de equilibrio de carga del sistema
  • Garantías de equidad en la programación de recursos

3. Limitaciones de Métodos Existentes

La investigación existente presenta las siguientes limitaciones:

  • Solo logra resultados no triviales bajo supuestos muy restrictivos (como el caso de dos agentes con dos valores)
  • Requiere conocimiento previo de la utilidad negativa total de cada agente
  • Para el caso general, el mejor algoritmo conocido solo puede garantizar la trivial n-MMS

4. Motivación de la Investigación

Este artículo tiene como objetivo:

  • Determinar los límites teóricos del problema de asignación MMS en línea
  • Diseñar algoritmos prácticos aplicables al caso general
  • Proporcionar garantías de rendimiento mejoradas bajo restricciones de parámetros reales

Contribuciones Principales

  1. Caracterización Precisa de Cotas Inferiores Teóricas: Demuestra que para cualquier n fijo y ε > 0, ningún algoritmo puede garantizar una asignación (n-ε)-MMS, cerrando completamente la brecha teórica
  2. Algoritmo en Línea Universal: Propone un algoritmo aplicable al caso general que garantiza una asignación min{n, O(k), O(log D)}-MMS
  3. Análisis Parametrizado: Cuando k (número de valores de utilidad negativa distintos) es constante, el algoritmo logra garantías O(1)-MMS
  4. Caso Optimizado de Dos Valores: Para el caso personalizado de dos valores, proporciona una garantía mejorada de (2+√3) ≈ 3.7-MMS
  5. Nuevas Técnicas de Análisis: Introduce el marco "Stacking Game", transformando el problema en un problema especial de minimización de diferencias

Explicación Detallada de Métodos

Definición de Tareas

  • Entrada: n agentes, m tareas que llegan secuencialmente
  • Restricciones: Cada tarea j tiene utilidad negativa personalizada di(j) para el agente i; las funciones de utilidad negativa son aditivas
  • Salida: Asignación A = (A1, ..., An), donde Ai es el conjunto de tareas asignadas al agente i
  • Objetivo: Lograr una asignación α-MMS, es decir, para todo i, di(Ai) ≤ α · MMSi

Arquitectura del Modelo

1. Marco de Algoritmo de Asignación Generalizada

El algoritmo se basa en una extensión de la idea de asignación por turnos:

  • Mantiene parámetros de presión Hθi para cada tipo de utilidad negativa θ de cada agente i
  • Los parámetros de presión miden el grado de "sobrecarga" del agente en relación con la asignación ideal
  • Estrategia codiciosa: asignar la nueva tarea que llega al agente con la presión más baja del tipo correspondiente

2. Técnica de Redondeo de Valores

  • Redondea la utilidad negativa de cada tarea que llega a la potencia de 2 más cercana
  • Reduce el número de tipos de utilidad negativa distintos
  • Mejora la razón de competencia de O(k²) a O(k)

3. Mecanismo de Actualización de Presión

Cuando llega la tarea j:

  • Si el agente i recibe la tarea j (tipo θ), entonces Hθi aumenta en 1
  • La presión correspondiente Hθi' de otros agentes i' disminuye en 1/(n-1)

Puntos de Innovación Técnica

1. Abstracción de Stacking Game

Abstrae el problema de asignación en línea como un "juego de apilamiento" continuamente simétrico:

  • Mantiene una función no decreciente f en el intervalo (-1/2, 1/2]
  • El adversario elige una unión de intervalos con medida total 1/k
  • El algoritmo aumenta codiciosamente las partes más bajas y disminuye las más altas
  • Demuestra que el adversario no puede hacer que el valor de la función exceda O(k)

2. Construcción Recursiva de Prueba de Cota Inferior

Diseña una construcción recursiva de instancias difíciles:

  • Define T(n', ε) como el número de rondas necesarias para que n' agentes logren (n-ε)-MMS
  • Construye instancias difíciles de T(n'+1) a partir de T(n')
  • Mecanismo de "limpieza" ingenioso que hace que las asignaciones anteriores sean negligibles

Configuración Experimental

Este artículo es principalmente un trabajo teórico sin evaluación experimental en el sentido tradicional, sino que verifica los resultados teóricos mediante pruebas matemáticas.

Métodos de Verificación Teórica

  1. Prueba Constructiva: Demuestra cotas inferiores mediante la construcción explícita de instancias difíciles
  2. Prueba por Inducción: Utiliza inducción matemática para demostrar garantías de rendimiento del algoritmo
  3. Análisis Dual: Analiza el rendimiento del algoritmo a través del problema dual del Stacking Game

Resultados Experimentales

Resultados Teóricos Principales

1. Resultados de Imposibilidad Precisos

Teorema 5: Para cualquier n y ε > 0, ningún algoritmo en línea puede garantizar una asignación (n-ε)-MMS.

Este resultado es preciso, sin constantes ocultas en la notación O grande, coincidiendo completamente con la cota superior trivial.

2. Rendimiento del Algoritmo Universal

Teorema 1: El Algoritmo 1 garantiza una asignación min{n, O(k), O(log D)}-MMS, donde:

  • k es el número máximo de valores de utilidad negativa distintos entre todos los agentes
  • D es la razón máxima entre la utilidad negativa máxima y mínima de cualquier agente

3. Optimización del Caso de Dos Valores

Teorema 6: Para el caso personalizado de dos valores, existe un algoritmo que garantiza una asignación min{n, 2+√3}-MMS, donde 2+√3 ≈ 3.7.

Resultados de Análisis Técnico

1. Límites del Stacking Game

Teorema 3: En el Stacking Game, el adversario no puede obtener una ganancia superior a 2k.

Este resultado es fundamental para el análisis del algoritmo, conduciendo directamente a la razón de competencia O(k).

2. Control de Parámetros de Presión

Mediante análisis del Stacking Game, se demuestra que todos los parámetros de presión Hθi pueden mantenerse dentro del rango O(k), garantizando así el rendimiento del algoritmo.

Trabajo Relacionado

1. Equilibrio de Carga en Línea

El problema de asignación MMS en línea está estrechamente relacionado con el problema clásico de equilibrio de carga en línea:

  • Trabajo pionero de Graham (1969)
  • La razón de competencia óptima actual está en 1.88, 1.92

2. Asignación MMS Fuera de Línea

Investigación sobre asignación MMS en el caso fuera de línea:

  • Mejor cota superior: 15/13 (Garg et al., 2025)
  • Mejor cota inferior: 44/43 (Feige et al., 2021)

3. Asignación Justa en Línea

Otros trabajos sobre asignación justa en línea:

  • Conceptos de equidad basados en envidia
  • Modelo donde los agentes llegan en línea
  • Asignación en línea de bienes

Conclusiones y Discusión

Conclusiones Principales

  1. Caracterización Completa de Límites Teóricos: Demuestra que n-MMS es el límite teórico exacto del problema de asignación de tareas en línea
  2. Diseño de Algoritmos Prácticos: Proporciona un algoritmo universal con buen rendimiento bajo restricciones de parámetros
  3. Contribución de Metodología Técnica: El marco Stacking Game proporciona una nueva herramienta de análisis para este tipo de problemas

Limitaciones

  1. Practicidad de Instancias Difíciles: La construcción de cotas inferiores teóricas requiere razones de utilidad negativa extremas y una gran cantidad de valores de utilidad negativa distintos
  2. Conocimiento Previo del Algoritmo: El algoritmo optimizado para dos valores requiere conocer previamente que cada agente tiene como máximo dos tipos de utilidad negativa
  3. Factores Constantes: Aunque es asintóticamente óptimo, hay espacio para mejorar los factores constantes

Direcciones Futuras

  1. Mejora de Factores Constantes: Optimizar aún más la razón de competencia en casos especiales
  2. Otros Conceptos de Equidad: Extender a otros conceptos de equidad como la ausencia de envidia
  3. Aplicaciones Prácticas: Aplicar resultados teóricos a escenarios concretos de equilibrio de carga y programación de tareas

Evaluación Profunda

Fortalezas

  1. Completitud Teórica: Resuelve completamente un problema abierto importante, proporcionando límites teóricos precisos
  2. Innovación Técnica: La abstracción del Stacking Game unifica elegantemente el análisis bajo diferentes parámetros
  3. Valor Práctico: Proporciona garantías de rendimiento significativamente mejores que los algoritmos triviales en rangos de parámetros razonables
  4. Profundidad de Análisis: La prueba de cota inferior mediante construcción recursiva demuestra un alto nivel técnico

Deficiencias

  1. Falta de Verificación Experimental: Como trabajo puramente teórico, carece de verificación en datos reales
  2. Dependencia de Parámetros: El rendimiento del algoritmo depende fuertemente de los valores de k y D
  3. Análisis de Complejidad: No analiza en detalle la complejidad temporal y espacial del algoritmo

Impacto

  1. Contribución Teórica: Proporciona una base teórica importante para la teoría de asignación justa en línea
  2. Valor Metodológico: La técnica del Stacking Game puede ser aplicable a otros problemas relacionados
  3. Orientación Práctica: Proporciona orientación teórica para el diseño de sistemas reales

Escenarios Aplicables

  1. Programación de Tareas en Línea: Aplicable a sistemas de asignación de tareas que requieren garantías de equidad
  2. Equilibrio de Carga: Puede aplicarse a escenarios de equilibrio de carga en múltiples servidores
  3. Asignación de Recursos: Aplicable a varios problemas de asignación de recursos en línea

Referencias

El artículo cita un amplio trabajo relacionado, incluyendo:

  • Budish (2010): Introducción del concepto MMS
  • Zhou et al. (2023): Trabajo temprano sobre asignación MMS en línea
  • Wang and Wei (2025): Resultados para el caso de dos agentes con dos valores
  • Garg et al. (2025): Avances recientes en asignación MMS fuera de línea

Este artículo realiza contribuciones importantes en los campos de la ciencia teórica de la computación y la teoría algorítmica de juegos. No solo resuelve completamente un problema abierto importante, sino que también proporciona diseño de algoritmos prácticos y técnicas de análisis novedosas. Aunque es principalmente un trabajo teórico, sus resultados tienen una importancia significativa para la orientación de aplicaciones prácticas.