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

Faire und effiziente Allokation unteilbarer gemischter Manna

Grundinformationen

  • Paper-ID: 2507.03946
  • Titel: Fair and Efficient Allocation of Indivisible Mixed Manna
  • Autoren: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
  • Klassifizierung: cs.GT (Informatik - Spieltheorie)
  • Veröffentlichungsdatum: 15. Oktober 2025 (arXiv-Preprint Version 2)
  • Paper-Link: https://arxiv.org/abs/2507.03946v2

Zusammenfassung

Dieses Paper untersucht das Problem der fairen Allokation unteilbarer gemischter Manna (mixed manna) zwischen Agenten mit additiven Bewertungen. Gemischte Manna sind Güter, deren Wert positiv, negativ oder null sein kann. Das Paper etabliert theoretische Garantien dafür, dass Fairness (basierend auf einer Relaxation der Neidfreiheit) und Pareto-Effizienz gleichzeitig erreicht werden können. Konkret basiert die Fairness-Garantie auf dem Konzept der „Neidfreiheit nach k Umverteilungen" (EFR-k): Eine Allokation A ist EFR-k, wenn es eine Teilmenge R von höchstens k Gütern gibt, sodass für jeden Agenten i durch Umverteilung der Güter in R eine neidfreie Allokation A^i für i erreichbar ist.

Forschungshintergrund und Motivation

Problemdefinition

Faire Allokation ist ein Problem, das in realen Szenarien wie Vermögensaufteilung, Aufgabenzuweisung, Grenzstreitigkeiten und Schuldenteilung häufig auftritt. Wenn die beteiligten Agenten persönliche Präferenzen haben, ist die Frage „Wer bekommt was?" sowohl praktisch dringend als auch theoretisch reichhaltig.

Forschungsherausforderungen

  1. Komplexität gemischter Manna: Im Gegensatz zu reinen Gütern (goods) oder Aufgaben (chores) kann das Vorzeichen des Wertes von Gütern in gemischter Manna je nach Agent unterschiedlich sein, was die Allokation komplexer macht.
  2. Abwägung zwischen Fairness und Effizienz: In der Einstellung unteilbarer Güter kann traditionelle Neidfreiheit (envy-freeness) nicht garantiert werden, daher müssen geeignete Relaxationen gesucht werden.
  3. Einschränkungen bestehender Methoden:
    • Für Aufgabenverteilung ist die Existenz von EF1 und Pareto-optimalen Allokationen selbst im Fall von vier Agenten ungelöst
    • Für gemischte Manna bleibt dieses Problem selbst für drei Agenten offen
    • Bestehende marktbasierte Methoden lassen sich nicht direkt auf negative Bewertungen verallgemeinern

Forschungsmotivation

Das Paper zielt darauf ab, durch Einführung des EFR-k-Konzepts theoretische Garantien für faire und effiziente Allokation gemischter Manna bereitzustellen und effektive Rechenalgorithmen zu entwickeln.

Kernbeiträge

  1. Theoretische Existenzgarantien: Es wird bewiesen, dass für die Allokation gemischter Manna an n Agenten mit additiven Bewertungen immer eine EFR-(n-1) und Pareto-optimale Allokation existiert.
  2. Algorithmische Berechenbarkeit: Wenn die Anzahl der Agenten n fest ist, kann eine EFR-(n-1) und Pareto-optimale Allokation in polynomialer Zeit berechnet werden.
  3. Unabhängige EFR-Ergebnisse:
    • EFR-(n-1) Allokationen gemischter Manna können in polynomialer Zeit berechnet werden
    • Wenn alle Güter Waren sind, existieren EFR-⌊n/2⌋-Allokationen und können effizient berechnet werden
  4. Straffheitsergebnisse:
    • Für Aufgaben ist die (n-1)-Schranke streng
    • Für Waren ist die ⌊n/2⌋-Schranke streng
  5. Technische Innovationen: Erstmalige Anwendung des Knaster-Kuratowski-Mazurkiewicz (KKM)-Theorems in der diskreten fairen Allokation.

Methodische Details

Aufgabendefinition

Eingabe:

  • n Agenten, bezeichnet als n = {1,...,n}
  • m unteilbare Güter, bezeichnet als m = {1,...,m}
  • Additive Bewertungsfunktionen {vi}i∈n, wobei vi(t) ∈ ℝ die Bewertung von Agent i für Gut t darstellt

Ausgabe: Allokation A = (A1,...,An), wobei Ai ⊆ m die Menge der Güter ist, die Agent i zugewiesen werden

Ziel: Finden einer Allokation, die gleichzeitig EFR-k und Pareto-optimal ist

Kernkonzepte

EFR-k Definition

Eine Allokation A ist EFR-k, wenn und nur wenn es eine Teilmenge R ⊆ m der Größe höchstens k gibt, sodass für jeden Agenten i durch Umverteilung der Güter in R eine neidfreie Allokation A^i für i erreichbar ist.

Wichtige technische Komponenten

  1. Bewertungsstörung: Um nicht-degenerierte Bedingungen zu erhalten, werden den gegebenen Bewertungen hinreichend kleine additive Störungen hinzugefügt:
    v̄i(t) = vi(t) - εi,t

    wobei εi,t gleichmäßig aus (0,ε) gezogen wird.
  2. Gewichtsversatz: Für jeden Gewichtsvektor w ∈ Δn-1 wird jede Komponente um einen Versatzparameter η > 0 verschoben:
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. KKM-Überdeckung: Für jeden Agenten i wird die Menge definiert als
    Ci := {w ∈ Δn-1 : es existiert eine Allokation Xi ∈ Oη(w) sodass i unter Xi neidfrei ist}

Hauptalgorithmischer Rahmen

Beweisstrategie für Theorem 3.1

  1. Konstruktion gestörter Bewertungen: Sicherung von Nicht-Degenerierungseigenschaften
  2. Definition von KKM-Überdeckungen: Konstruktion einer abgeschlossenen Mengenfamilie {Ci}, die die KKM-Bedingung erfüllt
  3. Anwendung des KKM-Theorems: Erhalt eines Schnittpunkts w* ∈ ∩i Ci
  4. Zählargument: Beweis, dass die Größe der Umverteilungsmenge R höchstens n-1 ist

Algorithmus 1: Konfliktbewusste Auswahlsequenz für Waren

Für den Fall reiner Waren wird ein auf Rundgang basierender Algorithmus entwickelt:

  • Konfliktlösungsphase: Identifikation mehrerer Agenten, die dasselbe Gut am meisten bevorzugen, und Hinzufügen zur Umverteilungsmenge R
  • Auswahlphase: Aktive Agenten wählen ihr bevorzugtestes Gut in lexikographischer Reihenfolge

Technische Innovationspunkte

  1. Neue Anwendung des KKM-Theorems: Erstmalige Anwendung des klassischen KKM-Theorems auf diskrete faire Allokationsprobleme, die einen völlig anderen technischen Weg als bestehende marktbasierte Methoden bietet.
  2. Störungstechnik: Durch sorgfältig gestaltete Bewertungsstörungen wird Nicht-Degenerierung sichergestellt, sodass das Problem der gewichteten Wohlfahrtsmaximierung gute Eigenschaften hat.
  3. Zählargument: Nutzung der Azyklizität bipartiter Graphen zum Beweis von Größenschranken der Umverteilungsmenge.

Experimentelle Einrichtung

Theoretischer Analyserahmen

Da dies ein theoretisches Paper ist, werden die Ergebnisse hauptsächlich durch mathematische Beweise statt empirischer Experimente validiert. Das Paper verwendet den folgenden Analyserahmen:

  1. Existenzbeweise: Verwendung des KKM-Theorems zum Beweis der Existenz von EFR-(n-1) und PO-Allokationen
  2. Straffheitsanalyse: Konstruktion von Gegenbeispielen zum Beweis der Straffheit der Schranken
  3. Algorithmische Komplexität: Analyse der Zeitkomplexität von Algorithmen

Komplexitätsanalyse

  • Feste Agentenzahl: EFR-(n-1) und PO-Allokationen können in m^poly(n) Zeit berechnet werden
  • Allgemeiner Fall: EFR-(n-1)-Allokationen können in polynomialer Zeit berechnet werden
  • Warenfall: EFR-⌊n/2⌋-Allokationen können in polynomialer Zeit berechnet werden

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

Theorem 3.1 (Hauptexistenzresultat)

Jede Instanz fairer Allokation unteilbarer gemischter Manna mit additiven Bewertungen besitzt eine EFR-(n-1) und Pareto-optimale Allokation.

Theorem 4.1 (Berechenbarkeitsergebnis)

Für Allokationsinstanzen gemischter Manna mit fester Agentenzahl kann eine EFR-(n-1) und Pareto-optimale Allokation in polynomialer Zeit berechnet werden.

Theorem 5.1 (Unabhängiges EFR-Ergebnis)

Für Allokationsinstanzen gemischter Manna mit additiven Bewertungen existiert immer eine Allokation, die sowohl EFR-(n-1) als auch EF1 ist, und kann in polynomialer Zeit berechnet werden.

Theorem 5.4 (Verbesserte Schranke für Waren)

Für Allokationsinstanzen reiner Waren berechnet Algorithmus 1 in polynomialer Zeit eine EFR-⌊n/2⌋-Allokation.

Straffheitsergebnisse

Theorem 5.2 (Straffheit für Aufgaben)

Es existiert eine Aufgabenallokationsinstanz ohne EFR-(n-2)-Allokation, was beweist, dass die (n-1)-Schranke streng ist.

Theorem 5.5 (Straffheit für Waren)

Es existiert eine Warenallokationsinstanz ohne EFR-(⌊n/2⌋-1)-Allokation, was beweist, dass die ⌊n/2⌋-Schranke streng ist.

Rechenkomplexitätsergebnisse

Theorem A.1 (Komplexität des Entscheidungsproblems)

Gegeben eine Allokation A und eine positive ganze Zahl k < n-2 ist die Entscheidung, ob A EFR-k ist, NP-vollständig.

Verwandte Arbeiten

Klassische Theorie der fairen Allokation

  • Teilbarer Fall: Klassische Ergebnisse von Varian und Weller zeigen, dass Neidfreiheit und PO gleichzeitig erreichbar sind
  • Unteilbare Waren: Simultane Realisierung von EF1 und PO ist gut etabliert (Nash-Wohlfahrtsmaximierung)

Herausforderungen bei Aufgaben und gemischter Manna

  • Aufgabenallokation: Existenz von EF1+PO ist selbst für vier Agenten ungelöst
  • Gemischte Manna: Existenz von EF1+PO für drei Agenten bleibt offen
  • Methodologische Unterschiede: Es existiert keine Funktion ähnlich Nash-Wohlfahrt, die EF1 für Aufgaben garantiert

Verwandte Relaxationskonzepte

  • EF1: Beseitigung von Neid durch Entfernung eines Gutes
  • EFX: Beseitigung von Neid durch Entfernung eines beliebigen Gutes
  • Fraktionale Allokation: Neidfreiheit mit höchstens (n-1) fraktional allozierten Gütern

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Theoretischer Durchbruch: Erstmalige Bereitstellung simultaner Garantien für Fairness und Effizienz in der allgemeinen Einstellung gemischter Manna
  2. Technische Innovation: Die neue Anwendung des KKM-Theorems in der diskreten fairen Allokation eröffnet neue Forschungsrichtungen
  3. Praktischer Wert: Algorithmische Ergebnisse bieten eine Rechenbasis für praktische Anwendungen

Einschränkungen

  1. Schranken: Die EFR-(n-1)-Schranke ist relativ groß, durchschnittlich müssen etwa 2 Güter pro Agent umverteilt werden
  2. Annahme fester Agenten: Der Polynomialzeit-Algorithmus erfordert feste Agentenzahl
  3. Additive Bewertungsbeschränkung: Ergebnisse gelten nur für additive Bewertungsfunktionen

Zukünftige Richtungen

  1. Verbesserung der Schranken: Suche nach kleineren Umverteilungsmengen R
  2. Erweiterung der Bewertungstypen: Berücksichtigung nicht-additiver Bewertungsfunktionen
  3. Praktische Anwendungen: Anwendung theoretischer Ergebnisse auf konkrete Allokationsszenarien

Tiefgreifende Bewertung

Stärken

  1. Bedeutender theoretischer Beitrag: Löst das grundlegende Problem der fairen und effizienten Allokation gemischter Manna
  2. Neuartige technische Methoden: Die Anwendung des KKM-Theorems zeigt tiefe mathematische Einsichten
  3. Umfassende Ergebnisse: Sowohl Existenz als auch Algorithmen, sowohl Ober- als auch Untergrenzen
  4. Rigorose Beweise: Vollständige mathematische Herleitungen und angemessene Behandlung technischer Details

Schwächen

  1. Begrenzte praktische Anwendbarkeit: Die EFR-(n-1)-Schranke kann in praktischen Anwendungen zu groß sein
  2. Fehlende empirische Bewertung: Als theoretisches Paper fehlt die Leistungsbewertung auf realen Daten
  3. Algorithmeneffizienz: Die m^poly(n)-Komplexität bei fester Agentenzahl kann in der Praxis hoch sein

Auswirkungen

  1. Akademische Auswirkungen: Bedeutender Beitrag zur Theorie der fairen Allokation, wird voraussichtlich häufig zitiert
  2. Methodologischer Wert: Die KKM-Theorem-Anwendung könnte weitere verwandte Forschungen inspirieren
  3. Praktische Perspektiven: Bietet theoretische Grundlagen für die Gestaltung praktischer Allokationssysteme

Anwendungsszenarien

  1. Vermögensaufteilung: Komplexe Aufteilungsszenarien mit Vermögenswerten und Schulden
  2. Aufgabenzuweisung: Allokation mit sowohl attraktiven als auch unattraktiven Aufgaben
  3. Ressourcenverwaltung: Ressourcenallokationsprobleme, die gleichzeitig Erträge und Kosten berücksichtigen müssen

Literaturverzeichnis

Das Paper zitiert wichtige Literatur im Bereich der fairen Allokation, einschließlich:

  • Budish (2011): Einführung des EF1-Konzepts
  • Caragiannis et al. (2019): Beziehung zwischen Nash-Wohlfahrt und EF1+PO
  • Aziz et al. (2022): EF1-Existenz für gemischte Manna
  • Sandomirskiy & Segal-Halevi (2022): Verwandte Ergebnisse zu fraktionalen Allokationen

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Paper, das durch Einführung des EFR-Konzepts und Anwendung des KKM-Theorems wichtige theoretische Garantien für faire und effiziente Allokation gemischter Manna bietet. Obwohl es in praktischer Hinsicht gewisse Einschränkungen gibt, machen seine theoretischen Beiträge und technischen Innovationen es zu einem wichtigen Fortschritt im Bereich der fairen Allokation.