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

Allocazione Online MMS per Compiti

Informazioni Fondamentali

  • ID Articolo: 2507.14039
  • Titolo: Online MMS Allocation for Chores
  • Autori: 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)
  • Classificazione: cs.GT (Informatica - Teoria dei Giochi)
  • Data di Pubblicazione: 11 ottobre 2025 (arXiv v2)
  • Link Articolo: https://arxiv.org/abs/2507.14039

Riassunto

Questo articolo affronta il problema della distribuzione equa di compiti (chores) indivisibili tra n agenti in un ambiente online. In questa configurazione, gli elementi arrivano sequenzialmente e devono essere assegnati irrevocabilmente a un agente al momento dell'arrivo, con l'obiettivo di produrre un'allocazione α-MMS. Sebbene lavori recenti abbiano ottenuto progressi sotto ipotesi restrittive, per il caso generale la migliore garanzia nota rimane banale (n-MMS), mentre il limite inferiore più forte è solo 2. Questo articolo chiude il divario nei risultati negativi dimostrando che per qualsiasi n fisso e ε, nessun algoritmo può garantire un'allocazione (n-ε)-MMS. Contemporaneamente, propone un algoritmo online che garantisce un'allocazione min{n, O(k), O(log D)}-MMS, dove k è il numero massimo di valori di utilità negativa distinti tra tutti gli agenti e D è il rapporto massimo tra l'utilità negativa massima e minima di qualsiasi agente.

Contesto di Ricerca e Motivazione

1. Definizione del Problema

Questo articolo affronta il problema della distribuzione online equa di compiti indivisibili (chores). A differenza della tradizionale allocazione di beni (goods), i compiti hanno utilità negativa e gli agenti desiderano assumere il minor numero possibile di compiti. Nell'impostazione online, i compiti arrivano sequenzialmente e l'algoritmo deve assegnare immediatamente ogni compito a un agente al momento dell'arrivo, con decisioni di allocazione irrevocabili.

2. Importanza della Ricerca

Questo problema ha ampie applicazioni pratiche, ad esempio:

  • Assegnazione online di compiti lavorativi ai dipendenti su piattaforme di servizi
  • Problemi di bilanciamento del carico di sistema
  • Garanzie di equità nella pianificazione delle risorse

3. Limitazioni dei Metodi Esistenti

La ricerca esistente presenta le seguenti limitazioni:

  • Risultati non banali solo sotto ipotesi molto restrittive (ad esempio, il caso a due agenti con due valori)
  • Necessità di conoscere in anticipo l'utilità negativa totale di ogni agente
  • Per il caso generale, il miglior algoritmo noto può garantire solo l'allocazione banale n-MMS

4. Motivazione della Ricerca

Questo articolo mira a:

  • Determinare i limiti teorici del problema di allocazione MMS online
  • Progettare algoritmi pratici applicabili al caso generale
  • Fornire migliori garanzie di prestazione sotto vincoli di parametri reali

Contributi Principali

  1. Caratterizzazione Precisa dei Limiti Teorici: Dimostra che per qualsiasi n fisso e ε > 0, nessun algoritmo può garantire un'allocazione (n-ε)-MMS, chiudendo completamente il divario teorico
  2. Algoritmo Online Universale: Propone un algoritmo applicabile al caso generale che garantisce un'allocazione min{n, O(k), O(log D)}-MMS
  3. Analisi Parametrizzata: Quando k (numero di valori di utilità negativa distinti) è una costante, l'algoritmo raggiunge una garanzia O(1)-MMS
  4. Caso a Due Valori Ottimizzato: Per il caso personalizzato a due valori, fornisce una garanzia migliorata di (2+√3) ≈ 3.7-MMS
  5. Nuove Tecniche di Analisi: Introduce il framework "Stacking Game", trasformando il problema in un problema speciale di minimizzazione delle differenze

Spiegazione Dettagliata dei Metodi

Definizione del Compito

  • Input: n agenti, m compiti che arrivano sequenzialmente
  • Vincoli: Ogni compito j ha un'utilità negativa personalizzata di(j) per l'agente i; le funzioni di utilità negativa sono additive
  • Output: Allocazione A = (A1, ..., An), dove Ai è l'insieme di compiti assegnati all'agente i
  • Obiettivo: Realizzare un'allocazione α-MMS, cioè per tutti i, di(Ai) ≤ α · MMSi

Architettura del Modello

1. Framework Algoritmo di Round-Robin Generalizzato

L'algoritmo si basa su un'estensione dell'idea del round-robin:

  • Mantiene parametri di pressione Hθi per ogni tipo di utilità negativa θ di ogni agente i
  • I parametri di pressione misurano il grado di "sovraccarico" dell'agente rispetto all'allocazione ideale
  • Strategia greedy: assegna il nuovo compito all'agente con la minore pressione del tipo corrispondente

2. Tecnica di Arrotondamento dei Valori

  • Arrotonda l'utilità negativa di ogni compito in arrivo alla potenza di 2 più vicina
  • Riduce il numero di tipi di utilità negativa distinti
  • Migliora il rapporto competitivo da O(k²) a O(k)

3. Meccanismo di Aggiornamento della Pressione

Quando arriva il compito j:

  • Se l'agente i riceve il compito j (tipo θ), allora Hθi aumenta di 1
  • La pressione corrispondente degli altri agenti i' diminuisce di 1/(n-1)

Punti di Innovazione Tecnica

1. Astrazione Stacking Game

Astrae il problema di allocazione online in un continuo "gioco di impilamento" simmetrico:

  • Mantiene una funzione non decrescente f sull'intervallo (-1/2, 1/2]
  • L'avversario sceglie un'unione di intervalli con misura totale 1/k
  • L'algoritmo aumenta avidamente le parti inferiori e diminuisce le parti superiori
  • Dimostra che l'avversario non può far superare il valore della funzione O(k)

2. Prova del Limite Inferiore mediante Costruzione Ricorsiva

Progetta una costruzione ricorsiva di istanze difficili:

  • Definisce T(n', ε) come il numero di round necessari per n' agenti per raggiungere (n-ε)-MMS
  • Costruisce l'istanza difficile di T(n'+1) da T(n')
  • Un meccanismo di "pulizia" intelligente rende trascurabile l'allocazione precedente

Configurazione Sperimentale

Questo articolo è principalmente un lavoro teorico senza valutazione sperimentale nel senso tradizionale, ma verifica i risultati teorici attraverso prove matematiche.

Metodi di Verifica Teorica

  1. Prova Costruttiva: Dimostra i limiti inferiori attraverso la costruzione esplicita di istanze difficili
  2. Prova Induttiva: Utilizza l'induzione matematica per dimostrare le garanzie di prestazione dell'algoritmo
  3. Analisi Duale: Analizza le prestazioni dell'algoritmo attraverso il problema duale dello Stacking Game

Risultati Sperimentali

Risultati Teorici Principali

1. Risultati di Impossibilità Precisi

Teorema 5: Per qualsiasi n e ε > 0, nessun algoritmo online può garantire un'allocazione (n-ε)-MMS.

Questo risultato è preciso, senza costanti nascoste nella notazione O grande, e corrisponde esattamente al limite superiore banale.

2. Prestazioni dell'Algoritmo Universale

Teorema 1: L'Algoritmo 1 garantisce un'allocazione min{n, O(k), O(log D)}-MMS, dove:

  • k è il numero massimo di valori di utilità negativa distinti tra tutti gli agenti
  • D è il rapporto massimo tra l'utilità negativa massima e minima di qualsiasi agente

3. Ottimizzazione del Caso a Due Valori

Teorema 6: Per il caso personalizzato a due valori, esiste un algoritmo che garantisce un'allocazione min{n, 2+√3}-MMS, dove 2+√3 ≈ 3.7.

Risultati dell'Analisi Tecnica

1. Limiti dello Stacking Game

Teorema 3: Nello Stacking Game, l'avversario non può ottenere un guadagno superiore a 2k.

Questo risultato è il nucleo dell'analisi dell'algoritmo e conduce direttamente al rapporto competitivo O(k).

2. Controllo dei Parametri di Pressione

Attraverso l'analisi dello Stacking Game, dimostra che tutti i parametri di pressione Hθi possono essere mantenuti nell'intervallo O(k), garantendo così le prestazioni dell'algoritmo.

Lavori Correlati

1. Bilanciamento del Carico Online

Il problema di allocazione MMS online è strettamente correlato al classico problema di bilanciamento del carico online:

  • Lavoro fondamentale di Graham (1969)
  • Il miglior rapporto competitivo attuale è nell'intervallo 1.88, 1.92

2. Allocazione MMS Offline

Ricerca sull'allocazione MMS nel caso offline:

  • Miglior limite superiore: 15/13 (Garg et al., 2025)
  • Miglior limite inferiore: 44/43 (Feige et al., 2021)

3. Allocazione Online Equa

Altri lavori sull'allocazione online equa:

  • Concetti di equità basati sull'invidia
  • Modello con agenti che arrivano online
  • Allocazione online di beni

Conclusioni e Discussione

Conclusioni Principali

  1. Caratterizzazione Completa dei Limiti Teorici: Dimostra che n-MMS è il limite teorico preciso del problema di allocazione online di compiti
  2. Progettazione di Algoritmi Pratici: Fornisce un algoritmo universale con buone prestazioni sotto vincoli di parametri
  3. Contributo Metodologico Tecnico: Il framework Stacking Game fornisce un nuovo strumento di analisi per questo tipo di problemi

Limitazioni

  1. Praticità delle Istanze Difficili: La costruzione teorica del limite inferiore richiede rapporti di utilità negativa estremi e numerosi valori di utilità negativa distinti
  2. Conoscenza Preliminare dell'Algoritmo: L'algoritmo ottimizzato per il caso a due valori richiede di conoscere in anticipo che ogni agente ha al massimo due tipi di utilità negativa
  3. Fattori Costanti: Sebbene asintoticamente ottimale, i fattori costanti hanno ancora spazio per miglioramenti

Direzioni Future

  1. Miglioramento dei Fattori Costanti: Ulteriore ottimizzazione del rapporto competitivo in casi speciali
  2. Altri Concetti di Equità: Estensione ad altri concetti di equità come l'assenza di invidia
  3. Applicazioni Pratiche: Applicazione dei risultati teorici a scenari concreti di bilanciamento del carico e pianificazione dei compiti

Valutazione Approfondita

Punti di Forza

  1. Completezza Teorica: Risolve completamente un importante problema aperto, fornendo limiti teorici precisi
  2. Innovazione Tecnica: L'astrazione dello Stacking Game unifica elegantemente l'analisi sotto diversi parametri
  3. Valore Pratico: Fornisce garanzie di prestazione significativamente migliori rispetto agli algoritmi banali in intervalli di parametri ragionevoli
  4. Profondità dell'Analisi: La prova del limite inferiore mediante costruzione ricorsiva dimostra un alto livello tecnico

Carenze

  1. Mancanza di Verifica Sperimentale: Come lavoro puramente teorico, manca la verifica su dati reali
  2. Dipendenza dai Parametri: Le prestazioni dell'algoritmo dipendono fortemente dai valori di k e D
  3. Analisi della Complessità: Manca un'analisi dettagliata della complessità temporale e spaziale dell'algoritmo

Impatto

  1. Contributo Teorico: Fornisce una base teorica importante per la teoria dell'allocazione online equa
  2. Valore Metodologico: La tecnica dello Stacking Game potrebbe essere applicabile ad altri problemi correlati
  3. Guida Pratica: Fornisce orientamenti teorici per la progettazione di sistemi reali

Scenari Applicabili

  1. Pianificazione Online dei Compiti: Applicabile a sistemi di assegnazione dei compiti che richiedono garanzie di equità
  2. Bilanciamento del Carico: Può essere applicato a scenari di bilanciamento del carico su più server
  3. Allocazione delle Risorse: Applicabile a vari problemi di allocazione online delle risorse

Bibliografia

L'articolo cita numerosi lavori correlati, tra cui:

  • Budish (2010): Introduzione del concetto MMS
  • Zhou et al. (2023): Lavori iniziali sull'allocazione MMS online
  • Wang and Wei (2025): Risultati per il caso a due agenti con due valori
  • Garg et al. (2025): Progressi recenti nell'allocazione MMS offline

Questo articolo fornisce importanti contributi nel campo dell'informatica teorica e della teoria algoritmica dei giochi. Non solo risolve completamente un importante problema aperto, ma fornisce anche algoritmi pratici e nuove tecniche di analisi innovative. Sebbene sia principalmente un lavoro teorico, i suoi risultati hanno un significato importante per le applicazioni pratiche.