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

Online MMS Allocation für Aufgaben

Grundinformationen

  • Papier-ID: 2507.14039
  • Titel: Online MMS Allocation for Chores
  • Autoren: 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)
  • Klassifizierung: cs.GT (Informatik - Spieltheorie)
  • Veröffentlichungsdatum: 11. Oktober 2025 (arXiv v2)
  • Papierlink: https://arxiv.org/abs/2507.14039

Zusammenfassung

Dieses Papier untersucht das Problem der fairen Verteilung von unteilbaren Aufgaben (Chores) zwischen n Agenten in einer Online-Umgebung. In dieser Einstellung treffen Gegenstände sequenziell ein und müssen bei ihrer Ankunft unwiderruflich einem Agenten zugewiesen werden, mit dem Ziel, eine α-MMS-Verteilung zu erzeugen. Obwohl neuere Arbeiten unter restriktiven Annahmen Fortschritte erzielt haben, bleibt die beste bekannte Garantie für den allgemeinen Fall die triviale n-MMS, während die stärkste untere Schranke nur 2 beträgt. Dieses Papier schließt die Lücke bei negativen Ergebnissen, indem es beweist, dass für jedes feste n und ε kein Algorithmus eine (n-ε)-MMS-Verteilung garantieren kann. Gleichzeitig wird ein Online-Algorithmus vorgestellt, der eine min{n, O(k), O(log D)}-MMS-Verteilung garantiert, wobei k die maximale Anzahl unterschiedlicher negativer Nutzenwerte über alle Agenten ist und D das maximale Verhältnis zwischen dem größten und kleinsten negativen Nutzen eines Agenten darstellt.

Forschungshintergrund und Motivation

1. Problemdefinition

Dieses Papier untersucht das Problem der Online-Fairverteilung von unteilbaren Aufgaben. Im Gegensatz zur traditionellen Verteilung von Gütern haben Aufgaben einen negativen Nutzen, und Agenten möchten so wenig Aufgaben wie möglich übernehmen. In der Online-Einstellung treffen Aufgaben sequenziell ein, und der Algorithmus muss jede Aufgabe bei ihrer Ankunft sofort einem Agenten zuweisen, wobei Zuweisungsentscheidungen unwiderruflich sind.

2. Forschungsbedeutung

Das Problem hat breite praktische Anwendungen, beispielsweise:

  • Zuweisung von Arbeitsaufgaben an Mitarbeiter auf Online-Service-Plattformen
  • Systemlastausgleichsprobleme
  • Fairnessgarantien bei der Ressourcenplanung

3. Einschränkungen bestehender Methoden

Bestehende Forschung weist folgende Einschränkungen auf:

  • Nicht-triviale Ergebnisse nur unter sehr restriktiven Annahmen (z.B. zwei Agenten, zwei Werte)
  • Erfordernis, den Gesamtnutzen jedes Agenten vorab zu kennen
  • Für den allgemeinen Fall kann der beste bekannte Algorithmus nur triviale n-MMS garantieren

4. Forschungsmotivation

Dieses Papier zielt darauf ab:

  • Die theoretischen Grenzen des Online-MMS-Verteilungsproblems zu bestimmen
  • Praktische Algorithmen für den allgemeinen Fall zu entwerfen
  • Bessere Leistungsgarantien unter realen Parameterbeschränkungen bereitzustellen

Kernbeiträge

  1. Präzise Charakterisierung der theoretischen unteren Schranke: Beweis, dass für jedes feste n und ε > 0 kein Algorithmus eine (n-ε)-MMS-Verteilung garantieren kann, wodurch die theoretische Lücke vollständig geschlossen wird
  2. Universeller Online-Algorithmus: Vorstellung eines für den allgemeinen Fall geeigneten Algorithmus, der eine min{n, O(k), O(log D)}-MMS-Verteilung garantiert
  3. Parametrisierte Analyse: Wenn k (Anzahl unterschiedlicher Nutzenwerte) konstant ist, erreicht der Algorithmus eine O(1)-MMS-Garantie
  4. Optimierter Zwei-Wert-Fall: Für den personalisierten Zwei-Wert-Fall wird eine verbesserte (2+√3) ≈ 3,7-MMS-Garantie bereitgestellt
  5. Neue Analysetechniken: Einführung des "Stacking Game"-Rahmens, der das Problem in ein spezielles Varianzminimierungsproblem umwandelt

Methodische Details

Aufgabendefinition

  • Eingabe: n Agenten, m sequenziell ankommende Aufgaben
  • Beschränkungen: Jede Aufgabe j hat für Agent i einen personalisierten negativen Nutzen di(j); Nutzenfunktionen sind additiv
  • Ausgabe: Zuweisung A = (A1, ..., An), wobei Ai die Menge der Aufgaben ist, die Agent i zugewiesen sind
  • Ziel: Erreichung einer α-MMS-Verteilung, d.h. für alle i gilt di(Ai) ≤ α · MMSi

Modellarchitektur

1. Verallgemeinerter Round-Robin-Algorithmus-Rahmen

Der Algorithmus basiert auf einer Erweiterung der Round-Robin-Idee:

  • Wartung von Druckparametern Hθi für jeden Nutzentyp θ jedes Agenten i
  • Druckparameter messen den "Überlastungsgrad" des Agenten relativ zur idealen Verteilung
  • Gierige Strategie: Zuweisung der neu ankommenden Aufgabe an den Agenten mit dem kleinsten entsprechenden Druck

2. Wertrundungstechnik

  • Rundung des negativen Nutzens jeder ankommenden Aufgabe zur nächsten Potenz von 2
  • Reduzierung der Anzahl unterschiedlicher Nutzentypen
  • Verbesserung des Wettbewerbsverhältnisses von O(k²) auf O(k)

3. Druckaktualisierungsmechanismus

Wenn Aufgabe j ankommt:

  • Wenn Agent i Aufgabe j (Typ θ) erhält, erhöht sich Hθi um 1
  • Der entsprechende Druck Hθi' anderer Agenten i' verringert sich um 1/(n-1)

Technische Innovationen

1. Stacking Game-Abstraktion

Abstraktion des Online-Verteilungsproblems als kontinuierliches symmetrisches "Stacking Game":

  • Wartung einer nicht abnehmenden Funktion f auf dem Intervall (-1/2, 1/2]
  • Der Gegner wählt eine Vereinigung von Intervallen mit Gesamtmaß 1/k
  • Der Algorithmus hebt gierig niedrigere Teile an und senkt höhere Teile
  • Beweis, dass der Gegner die Funktionswerte nicht über O(k) treiben kann

2. Rekursive Konstruktion des Unteren-Schranke-Beweises

Entwurf einer rekursiven schwierigen Instanzkonstruktion:

  • Definition von T(n', ε) als Anzahl der Runden, die n' Agenten zur Erreichung von (n-ε)-MMS benötigen
  • Konstruktion von T(n'+1)-schwierigen Instanzen aus T(n')
  • Geschickter "Bereinigungsmechanismus", der frühere Zuweisungen vernachlässigbar macht

Experimentelle Einrichtung

Dieses Papier ist hauptsächlich eine theoretische Arbeit ohne traditionelle experimentelle Bewertung, sondern verifiziert theoretische Ergebnisse durch mathematische Beweise.

Theoretische Verifizierungsmethoden

  1. Konstruktive Beweise: Beweis von Schranken durch explizite Konstruktion schwieriger Instanzen
  2. Induktive Beweise: Verwendung mathematischer Induktion zum Beweis von Algorithmus-Leistungsgarantien
  3. Duale Analyse: Analyse der Algorithmus-Leistung durch das duale Problem des Stacking Game

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

1. Präzise Unmöglichkeitsergebnisse

Theorem 5: Für jedes n und ε > 0 gibt es keinen Online-Algorithmus, der eine (n-ε)-MMS-Verteilung garantieren kann.

Dieses Ergebnis ist präzise, ohne Konstanten, die in Big-O-Notation verborgen sind, und stimmt vollständig mit der trivialen oberen Schranke überein.

2. Universelle Algorithmus-Leistung

Theorem 1: Algorithmus 1 garantiert eine min{n, O(k), O(log D)}-MMS-Verteilung, wobei:

  • k die maximale Anzahl unterschiedlicher Nutzenwerte über alle Agenten ist
  • D das maximale Verhältnis zwischen dem größten und kleinsten Nutzen eines Agenten darstellt

3. Optimierung des Zwei-Wert-Falls

Theorem 6: Für den personalisierten Zwei-Wert-Fall existiert ein Algorithmus, der eine min{n, 2+√3}-MMS-Verteilung garantiert, wobei 2+√3 ≈ 3,7.

Technische Analyseergebnisse

1. Grenzen des Stacking Game

Theorem 3: Im Stacking Game kann der Gegner keinen Gewinn größer als 2k erzielen.

Dieses Ergebnis ist zentral für die Algorithmusanalyse und führt direkt zum O(k)-Wettbewerbsverhältnis.

2. Kontrolle der Druckparameter

Durch Stacking Game-Analyse wird bewiesen, dass alle Druckparameter Hθi im Bereich O(k) gehalten werden können, was die Algorithmus-Leistung garantiert.

Verwandte Arbeiten

1. Online-Lastausgleich

Das Online-MMS-Verteilungsproblem ist eng mit dem klassischen Online-Lastausgleichsproblem verwandt:

  • Bahnbrechendes Werk von Graham (1969)
  • Aktuelles bestes Wettbewerbsverhältnis liegt zwischen 1,88, 1,92

2. Offline-MMS-Verteilung

Forschung zur MMS-Verteilung im Offline-Fall:

  • Beste obere Schranke: 15/13 (Garg et al., 2025)
  • Beste untere Schranke: 44/43 (Feige et al., 2021)

3. Online-Fairverteilung

Andere Arbeiten zur Online-Fairverteilung:

  • Fairnesskonzepte basierend auf Neid
  • Modelle mit online ankommenden Agenten
  • Online-Verteilung von Gütern

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Vollständige Charakterisierung der theoretischen Grenzen: Beweis, dass n-MMS die präzise theoretische Grenze des Online-Aufgabenverteilungsproblems ist
  2. Praktisches Algorithmus-Design: Bereitstellung eines universellen Algorithmus mit guter Leistung unter Parameterbeschränkungen
  3. Methodologischer Beitrag: Das Stacking Game-Framework bietet neue Analysetechniken für solche Probleme

Einschränkungen

  1. Praktikalität schwieriger Instanzen: Die theoretische Konstruktion schwieriger Instanzen erfordert extreme Nutzenverhältnisse und viele unterschiedliche Nutzenwerte
  2. Vorwissen des Algorithmus: Der optimierte Zwei-Wert-Algorithmus erfordert vorherige Kenntnis, dass jeder Agent höchstens zwei Nutzentypen hat
  3. Konstante Faktoren: Obwohl asymptotisch optimal, gibt es noch Raum für Verbesserungen bei Konstanten

Zukünftige Richtungen

  1. Verbesserung von Konstanten: Weitere Optimierung des Wettbewerbsverhältnisses in Spezialfällen
  2. Andere Fairnesskonzepte: Erweiterung auf andere Fairnesskonzepte wie Neidfreiheit
  3. Praktische Anwendungen: Anwendung theoretischer Ergebnisse auf konkrete Lastausgleichs- und Aufgabenplanungsszenarien

Tiefgreifende Bewertung

Stärken

  1. Theoretische Vollständigkeit: Vollständige Lösung eines wichtigen offenen Problems mit präzisen theoretischen Grenzen
  2. Technische Innovativität: Die Stacking Game-Abstraktion vereinheitlicht elegant die Analyse unter verschiedenen Parametern
  3. Praktischer Wert: Bietet unter angemessenen Parametern erheblich bessere Leistungsgarantien als triviale Algorithmen
  4. Analysentiefe: Der rekursive Beweis der unteren Schranke zeigt hohes technisches Niveau

Schwächen

  1. Fehlende experimentelle Validierung: Als rein theoretische Arbeit fehlt die Validierung auf realen Daten
  2. Parameterabhängigkeit: Die Algorithmus-Leistung hängt stark von den Werten von k und D ab
  3. Komplexitätsanalyse: Keine detaillierte Analyse der Zeit- und Raumkomplexität des Algorithmus

Auswirkungen

  1. Theoretischer Beitrag: Bietet wichtige theoretische Grundlagen für die Online-Fairverteilungstheorie
  2. Methodologischer Wert: Die Stacking Game-Technik könnte auf andere verwandte Probleme anwendbar sein
  3. Praktische Anleitung: Bietet theoretische Anleitung für das Design praktischer Systeme

Anwendungsszenarien

  1. Online-Aufgabenplanung: Geeignet für Aufgabenverteilungssysteme, die Fairnessgarantien benötigen
  2. Lastausgleich: Anwendbar auf Multi-Server-Lastausgleichsszenarien
  3. Ressourcenverteilung: Geeignet für verschiedene Online-Ressourcenverteilungsprobleme

Literaturverzeichnis

Das Papier zitiert umfangreiche verwandte Arbeiten, einschließlich:

  • Budish (2010): Einführung des MMS-Konzepts
  • Zhou et al. (2023): Frühe Arbeiten zur Online-MMS-Verteilung
  • Wang and Wei (2025): Ergebnisse für den Zwei-Agenten-Zwei-Wert-Fall
  • Garg et al. (2025): Neueste Fortschritte bei der Offline-MMS-Verteilung

Dieses Papier leistet wichtige Beiträge zur theoretischen Informatik und algorithmischen Spieltheorie. Es löst nicht nur ein wichtiges offenes Problem vollständig, sondern bietet auch praktisches Algorithmus-Design und neuartige Analysetechniken. Obwohl es sich hauptsächlich um theoretische Arbeiten handelt, haben die Ergebnisse wichtige Bedeutung für praktische Anwendungen.