Liste der ungelösten Probleme in der fairen Abteilung

Diese Seite listet bemerkenswerte offene Probleme im Zusammenhang mit Faire Division - Ein Feld in der Schnittstelle zwischen Mathematik, Informatik, Politikwissenschaft und Wirtschaft.

Offene Probleme in Faires Kuchenschneider

Abfrage Komplexität von Neidfreies Kuchenschnitt

Im Problem von Neidfreies KuchenschnittEs gibt einen Kuchen, der als Intervall modelliert ist, und ${\ displayStyle n}$ Agenten mit unterschiedlichen Wertmaßnahmen über dem Kuchen. Die Wertmaßnahmen sind nur über Abfragen der Form "Bewertung eines bestimmten Kuchens bewerten" oder "Markieren Sie ein Stück Kuchen mit einem bestimmten Wert". Mit ${\ displayStyle n = 2}$ Agenten, eine beneidungsfreie Abteilung kann mit zwei Abfragen finden teilen und wählen. Mit ${\ displayStyle n> 2}$ Agenten, es gibt mehrere offene Probleme in Bezug auf die Anzahl der erforderlichen Fragen.

1. Nehmen Sie zunächst an, dass der gesamte Kuchen zugewiesen werden muss (d. H. Es gibt es Keine Entsorgung) und Stücke können getrennt werden. Wie viele Fragen sind erforderlich?

• Untergrenze: ${\ displayStyle \ Omega (n^{2})}$;^[1]
• Obere Grenze: ${\ displayStyle o \ links (n^{n^{n^{n^{n^{n}}}}} \ rechts)}}$.^[2]

2. Nehmen Sie als nächstes an, dass ein Kuchen nicht zugewiesen werden kann (d. H. Es gibt da freie Entsorgung), aber die Zuweisung muss sein proportional (zusätzlich zu Neidfrei): Jeder Agent muss mindestens bekommen ${\ displayStyle 1/n}$ des Gesamtkuchenwerts. Teile können immer noch getrennt werden. Wie viele Fragen sind erforderlich?

• Untergrenze: Nicht bekannt (theoretisch kann es polynomial lösbar sein).
• Obere Grenze: ${\ displayStyle (n!)^{2} n^{2}}$.^[2]

3. Als nächstes muss angenommen in Verbindung gebracht. Wie viele Fragen sind erforderlich?

• Zum ${\ displayStyle n = 3}$Es gibt einen Algorithmus mit 54 Abfragen.^[3]
• Zum ${\ displayStyle n \ Geq 4}$Derzeit ist kein endlicher Algorithmus bekannt.

4. Nehmen Sie an, als nächstes müssen die Teile angeschlossen werden, aber die Zuweisung kann nur ungefähr proportional sein (d. H. Einige Agenten können weniger als weniger als erhalten ${\ displayStyle 1/n}$ des Gesamtkuchenwerts). Welcher Wert kann jedem Agenten mit einem endlichen Neidprotokoll garantiert werden?

• Zum ${\ displayStyle n = 3}$Es gibt einen Algorithmus, der 1/3 erreicht, was optimal ist.
• Zum ${\ displayStyle n = 4}$ (Der kleinste offene Fall) Es gibt einen Algorithmus, der 1/7 erreicht.^[3]
• Für jeden ${\ displayStyle n}$Es gibt einen Algorithmus, der erreicht ${\ displayStyle 1/(3n)}$.^[2]

5. Nehmen wir schließlich an, der gesamte Kuchen muss zugewiesen werden, und Teile können getrennt werden, aber die Anzahl der Schnitte (oder Anzahl der Teile pro Agent) sollte so klein wie möglich sein. Wie viele Kürzungen benötigen wir, um eine neidfreie Zuordnung in einer begrenzten Anzahl von Abfragen zu finden??

• Zum ${\ displayStyle N \ Geq 3}$, Ein endlicher Algorithmus existiert nicht für ${\ displayStyle n-1}$ Schnitte (1 Stück pro Agent).^[4]
• Zum ${\ displayStyle n = 3}$, Selfridge -Conway -Verfahren Löst das Problem in der endlichen Zeit mit 5 Schnitten (und höchstens 2 Teilen pro Agent).
• Zum ${\ displayStyle n \ Geq 4}$Das Aziz-Mackenzie-Verfahren löst das Problem in der endlichen Zeit, jedoch mit vielen Schnitten (und vielen Teilen pro Agent).
• Kleinstes offenes Gehäuse: drei Agenten und 3 oder 4 Schnitte; Vier Agenten und 2 Teile pro Agent.

Anzahl der Schnitte für Kuchenschneiden mit unterschiedlichen Ansprüchen

Wenn alle Agenten gleiche Ansprüche haben, a Proportionaler Kuchenschneider kann mit Verwendung implementiert werden ${\ displayStyle n-1}$ Schnitte, was optimal ist.

Wie viele Schnitte sind für die Implementierung eines proportionalen Kuchenschnitts erforderlich ${\ displayStyle n}$ Agenten mit unterschiedlichen Ansprüchen?

• Untergrenze: ${\ displayStyle 2n-2}$;^[5]
• Obere Grenze: ${\ displayStyle 3n-4}$.^[6]
• Kleinstes Open Case: ${\ displayStyle n = 3}$ Agenten mit allen verschiedenen Ansprüchen: ${\ displayStyle 1/7}$, ${\ displayStyle 2/7}$ und ${\ displayStyle 4/7}$.^[5]

Wie viele Schnitte sind für die Implementierung eines erforderlich Neidfreies Kuchenschnitt unter ${\ displayStyle n}$ Agenten mit unterschiedlichen Ansprüchen?

• Untergrenze: ${\ displayStyle 2n-2}$, da neidfrei proportional impliziert.
• Obergrenze: Nicht bekannt.

Faire Aufteilung eines teilweise verbrannten Kuchens

A teilweise verbrannter Kuchen ist eine Metapher zu einem Kuchen, in dem Agenten sowohl positive als auch negative Bewertungen haben können.^[7]

Es gibt immer eine proportionale Aufteilung eines solchen Kuchens.

Was ist die Laufzeitkomplexität bei der Berechnung eines vernetzten-proportional Zuweisung von teilweise verbranntem Kuchen?

Bekannte Fälle:

• Wenn alle Bewertungen positiv sind oder alle Bewertungen negativ sind, die Sogar PAZ-Protokoll findet eine vernetzte proportionale Spaltung mit Verwendung ${\ displayStyle o (n \ log n)}$ Abfragen, und das ist optimal.
• Wenn Bewertungen gemischt werden können, kann ein Miell-Knife-Protokoll verwendet werden, um eine vernetzte proportionale Spaltung zu finden ${\ displayStyle o (n^{2})}$ Abfragen.^{[8]: Thm.5} Kann dies verbessert werden zu ${\ displayStyle o (n \ log n)}$?

Eine beneidungsfreie Aufteilung eines teilweise verbrannten Kuchens wird garantiert existieren, wenn die Anzahl der Agenten die Kraft einer Prime Ganzzahl ist.^[9] Es kann jedoch nicht durch ein endliches Protokoll gefunden werden - es kann nur angenähert werden. Bei einer kleinen positiven Zahl DEine Zuweisung wird genannt D-Envy-frei, wenn für jeden Agenten die Zuweisung neidfrei wird, wenn wir die Schnitte höchstens um verschieben D (Längeneinheiten).

Was ist die Laufzeitkomplexität (als Funktion von d) bei der Berechnung eines verbundenen Anschlusses D-envyfrei Zuteilung eines teilweise verbrannten Kuchens?^[7]

Wahrheitsgemäßes Kuchenschneider

Wahrheitsgemäßes Kuchenschneider ist das Design von wahrheitsgemäße Mechanismen Für faires Kuchenschnitt. Die derzeit bekannten Algorithmen und Unmöglichkeitsergebnisse werden gezeigt hier. Die Hauptfälle, in denen nicht bekannt ist, ob ein deterministischer wahrer wahrer Mechanismus besteht, sind:^[10]

• Es gibt 3 oder mehr Agenten mit stückweise ungleichmäßige Bewertungen, ohne freie Entsorgung.
• Es gibt 2 oder mehr Agenten mit stückweise konstante Bewertungen, mit oder ohne freie Entsorgung (und ohne zusätzliche Anforderungen wie Konnektivität oder Nichtabfall).

Offene Probleme in Faire Allokation unteilbarer Gegenstände

Ungefähr Maximin-Share Gerechtigkeit

Das 1-von-${\ displayStyle n}$ Maximin Share (MMS) eines Agenten ist das größte Versorgungsunternehmen, das der Agent sichtern kann, indem sie die Elemente in die Gegenstände verteilt ${\ displayStyle n}$ Bündel und das schlechteste Bundle erhalten. Für zwei Agenten, teilen und wählen Gibt jedem Agenten zumindest sein 1 von 2 MMs. Zum ${\ displayStyle n> 2}$ Agenten, es ist fast immer, aber nicht immer möglich, jedem Agenten seinen/ihr 1-von- zu geben${\ displayStyle n}$ MMS. Dies wirft verschiedene Arten von Fragen auf.

1. Rechenkomplexität

Was ist die Laufzeitkomplexität der Entscheidung, ob eine bestimmte Instanz eine 1-von-${\ displayStyle n}$ MMS -Zuweisung?^[11][12]

• Obere Grenze: ${\ displaystyle {np}^{np}}$ (welches ist ${\ displaystyle \ sigma _ {2}^{p}}$ - Stufe 2 in der Polynomhierarchie)
• Untergrenze: Keine (so kann es Stufe 2 oder 1 oder sogar 0 der Hierarchie sein).

HINWEIS: Die folgenden Probleme sind bekanntermaßen rechnerisch schwer:

• Berechnung die 1-von- an-${\ displayStyle n}$ Mms eines bestimmten Agenten ist Np-harte Auch wenn alle Agenten additive Präferenzen haben (Reduktion von Partitionsproblem).
• Entscheidung, ob a gegeben Allokation ist 1-von-${\ displayStyle n}$ MMS ist Co-NP vollständig für Agenten mit additiven Vorlieben.

2. Kardinalannäherung

Was ist die größte Fraktion R, so dass es immer eine Zuordnung gibt, die jedem Agenten einen Nutzen von mindestens R-mal seines 1-of-Times gibt${\ displayStyle n}$ Maximin -Aktie?

Bekannte Fälle:

• Für zwei Agenten: ${\ displayStyle r = 1}$ durch Divide-and-Choose.
• Für drei Agenten auch mit additiven Bewertungen: ${\ displayStyle r <1}$. Durch ein sorgfältig gestaltetes Beispiel.^[13]
• Für eine beliebige Anzahl von Agenten mit additiven Bewertungen: ${\ displayStyle r \ Geq 3/4}$.^[14]
• Für eine beliebige Anzahl von Agenten mit Zusatz Negativ Bewertungen (d. H. Für Aufgaben): ${\ displayStyle r \ Geq 9/11}$.^[15]

3. Ordinale Annäherung

Was ist die kleinste Ganzzahl ${\ displayStyle n}$ (als Funktion von ${\ displayStyle n}$) so dass es immer eine Zuteilung unter gibt ${\ displayStyle n}$ Agenten geben jedem Agenten mindestens seinen 1-von- an-${\ displayStyle n}$ MMS?

Bekannte Fälle:

• Für zwei Agenten: ${\ displayStyle n = 2}$. Durch Teilen und Choose.
• Für eine beliebige Anzahl von Agenten mit binären Bewertungen: ${\ displayStyle n = n}$. Von Round-Robin. Es gibt EF1, was 1-von-von- impliziert${\ displayStyle n}$-Mms.
• Zum ${\ displayStyle n> 2}$ Agenten: ${\ displayStyle n> n}$. Durch ein sorgfältig gestaltetes Beispiel.^[13]
• Für eine beliebige Anzahl von Agenten mit additiven Bewertungen: ${\ displayStyle n \ leq 2n-1}$, von Round-Robin. Es gibt EF1, was 1-von-von- impliziert${\ displayStyle (2n-1)}$-Mms.
• Für eine beliebige Anzahl von Agenten mit additiven Bewertungen: ${\ displayStyle n \ leq 2n-2}$, verwenden Neidfreies Matching.^[16]

Die Antwort kann also alles dazwischen sein ${\ displayStyle n+1}$ und ${\ displayStyle 2n-2}$, inklusive. Kleinstes Open Case:

Zum ${\ displayStyle n = 4}$ Agenten mit additiven Bewertungen, gibt es immer eine 1-von-5-Maximin-Share-Allokation?

Notiz: Es gibt immer eine Ungefähres wettbewerbsfähiges Gleichgewicht aus gleichem Einkommen Das garantiert das 1-von- (${\ displayStyle n+1}$) Maximin-Share.^[17] Diese Zuordnung kann jedoch überschüssiges Angebot und - was noch wichtiger - überschüssiger Nachfrage aufweisen: Die Summe der Bündel, die allen Agenten zugewiesen werden, kann etwas größer sein als der Satz aller Gegenstände. Ein solcher Fehler ist bei der Zuweisung von Kurssitzen unter den Schülern angemessen, da ein kleiner überschüssiger Versorgung durch Hinzufügen einer kleinen Anzahl von Sitzen korrigiert werden kann. Das Problem der klassischen Fair Division geht jedoch davon aus, dass Gegenstände möglicherweise nicht hinzugefügt werden.

Neidfrei bis zu einem Artikel

Eine Zuteilung wird genannt EF1 (neidfrei bis zu einem Artikel) Wenn für zwei beliebige Agenten ${\ displayStyle i}$ und ${\ displayStyle j}$und für jede Teilmenge der Größe höchstens eins, die im Bündel von enthalten sind ${\ displayStyle j}$, wenn wir diese Teilmenge aus entfernen ${\ displayStyle j}$Bündel dann ${\ displayStyle i}$ Neidet sich nicht. Eine EF1 -Zuordnung existiert immer und kann von der gefunden werden Neidzyklenalgorithmus. Das Kombinieren mit anderen Eigenschaften wirft einige offene Fragen auf.

Pareto-optimale EF1-Allokation (Waren und Bads)

Wenn alle Artikel gut sind und alle Bewertungen additiv sind, existiert immer ein PO+EF1: Die Zuweisung, die das Produkt von Versorgungsunternehmen maximiert, ist PO+EF1.^[18] Das Finden dieser Maximierung der Allokation ist NP-HART,^[19] Theoretisch kann es jedoch möglich sein, andere PO+EF1 -Zuweisungen zu finden (nicht das Produkt maximieren).

Was ist die Laufzeitkomplexität, eine PO+EF1-Zuordnung von zu finden Waren?

Eine PO+EF1 -Zuweisung von Bads (Aufgaben) Es ist nicht bekannt, dass es existiert, auch wenn alle Bewertungen additiv sind.

Macht eine PO+EF1 -Zuordnung von Bads Immer existieren?

Was ist die Laufzeitkomplexität des Findens? Eine solche Zuteilung, wenn es existiert?

Zusammenhängende EF1 -Zuordnung

Oft werden die Waren beispielsweise in einer Linie in einer Straße bestellt. Jeder Agent möchte einen zusammenhängenden Block erhalten.^[20]

Gibt es immer eine EF1 -Allokation für drei oder mehr Agenten mit additiven Bewertungen?

Bekannte Fälle:

• Für zwei Agenten mit additiv Neidfreies Kuchenschnitt (z. B. gefunden durch teilen und wählen).
• Zum ${\ displayStyle n}$ Agenten mit additiv EF2 Zuordnung (Beweis mit einer Variante von Sperners Lemma).^[21]
• Zum ${\ displayStyle n}$ Agenten mit additiv binär Bewertungen (jeder Artikelwert beträgt entweder 0 oder 1), eine "EF minus 2" -Aglokation ist ebenfalls EF1, daher lautet die Antwort Jawohl.

Selbst wenn eine zusammenhängende EF1 -Zuordnung besteht, ist die Laufzeitkomplexität des Findens unklar:

Was ist für drei oder mehr Agenten mit binären additiven Bewertungen die Komplexität, eine zusammenhängende EF1 -Zuordnung zu finden?

• Ein vernetzter Neidkuchenschnitt kann unendlich viele Fragen erfordern. Eine EF1-Zuordnung kann immer in begrenzter Zeit gefunden werden, indem alle möglichen Zuordnungen überprüft werden. Dieser Algorithmus erfordert jedoch eine exponentielle Laufzeit.

Preis der Fairness

Das Preis der Fairness ist das Verhältnis zwischen der maximalen sozialen Wohlfahrt (Summe der Versorgungsunternehmen) in jeder Zuordnung und dem maximalen sozialen Wohl in einer fairen Zuordnung.Was ist der Preis für EF1 Fairness?

• Die Obergrenze ist ${\ displayStyle o (n)}$ - von beiden Round-Robin oder maximales Nash -Wohlfahrt.
• Die untere Grenze ist ${\ displayStyle o ({\ sqrt {n}})}$.^{[22]: Sec.1.1}

Existenz der EFX -Allokation

Eine Zuteilung wird genannt EFX ("Neidfrei bis zu jedem Gut") Wenn für zwei beliebige Agenten ${\ displayStyle i}$ und ${\ displayStyle j}$und für jedes Gut im Bündel von ${\ displayStyle j}$, wenn wir das gut entfernen aus ${\ displayStyle j}$Bündel dann ${\ displayStyle i}$ Neidet sich nicht.^[23]

Gibt es für drei Agenten mit additiven Bewertungen immer eine EFX -Zuordnung?

Zum ${\ displayStyle n}$ Agenten mit allgemeinen monotonischen Bewertungen können wir beweisen, dass es keine EFX -Zuordnung gibt?

Bekannte Fälle:

• Wenn zumindest ${\ displayStyle n-1}$ Bewertungen sind identisch: Ja.
• Daher für zwei Agenten: Ja. Dies gilt auch für allgemeine monotone Bewertungen.^[24]
• Für drei Agenten: Ja, durch ein kürzlich veröffentlichtes Arbeitspapier.^[25]

Existenz einer paretoeffizienten Propx-Zuordnung von Bads

Eine Zuteilung von Bads heißt Propx (auch bekannt als FSX)^{[26]: Sec.7} Wenn, für einen Agenten ${\ displayStyle i}$und für alle schlechten Besitz ${\ displayStyle i}$, wenn wir das schlechte aus entfernen ${\ displayStyle i}$Bündel dann ${\ displayStyle i}$'S Die Unzufriedenheit ist geringer als ${\ displayStyle 1/n}$ die Gesamtnauigkeit.

Gibt es immer eine Zuteilung von Bads, die sowohl propx als auch paretoeffizient sind?

Verwandte bekannte Fälle:

• Eine Propx -Zuweisung von Waren (auch ohne paretoeffizienz) kann nicht existieren.
• Eine Propx -Zuweisung von Bads (ohne paretoeffizienz) existiert immer.
• A Prop1 und eine paretoeffiziente Zuordnung von Waren oder Bads gibt es immer.

Wettbewerbsgleichgewicht für fast alle Einkommen

Wettbewerbsgleichgewicht (CE) ist ein sehr starker Fairness-Begriff-es impliziert paretooptimal und neidfeinheit. Wenn die Einkommen gleich sind, gibt es möglicherweise nicht, selbst wenn es zwei Agenten und eines Guten gibt. Aber in allen anderen Einkommensraum existiert CE, wenn es zwei Agenten gibt und eines Gutes. Mit anderen Worten, es gibt ein wettbewerbsfähiges Gleichgewicht für fast alles Einkommensvektoren.

Gibt es für zwei Agenten mit additiven Bewertungen über eine beliebige Anzahl von Waren ein wettbewerbsfähiges Gleichgewicht für fast Einkommen?^[27]

Bekannte Fälle:

• Mit drei oder weniger Waren: Immer Jawohl.
• Mit vier Waren: Jawohl für 2 Agenten mit allgemeinen Bewertungen, nein für 3 Agenten mit allgemeinen Bewertungen, nein für 4 Agenten, auch mit additiven Bewertungen.^[28]
• Mit fünf oder mehr Waren: nein für zwei Agenten mit allgemeinen Bewertungen.

Offene Vermutungen:

• Wenn es zwei Agenten mit gibt Zusatzstoff Bewertungen, CE für fast alle Einkommen vorhanden für eine beliebige Anzahl von Waren.
• Wenn es drei Agenten gibt, gibt es auch bei additiven Bewertungen CE für fast alle Einkommen möglicherweise nicht.

Faire Aufteilung teilweise teilbarer Gegenstände

Laufzeitkomplexität der fairen Zuweisung mit begrenztem Teilen

Gegeben ${\ displayStyle N \ Geq 2}$ Agenten, ${\ displayStyle m}$ Gegenstände und eine Ganzzahl ${\ displayStyle K}$Nehmen Sie höchstens an ${\ displayStyle K}$ Artikel können unter zwei oder mehr Agenten geteilt werden. Was ist die Laufzeitkomplexität bei der Entscheidung, ob eine proportionale / neidfreie Zuordnung existiert?

Bekannte Fälle:

• Mit ${\ displayStyle k = 0}$ und identische Bewertungen für jeden ${\ displayStyle N \ Geq 2}$, Das Problem entspricht der Partitionsproblemund deshalb ist es NP-Complete.
• Mit ${\ displayStyle K \ Geq N-1}$Die Antwort lautet immer "Ja", und eine Zuordnung kann in Polynomzeit gefunden werden.^[29]
• Mit ${\ displayStyle n = 3}$ und ${\ displayStyle k = 1}$ und identische Bewertungen, eine Allokation kann in der Polynomzeit gefunden werden, wenn sie existiert.^[30]

Kleinste offene Fälle:

• ${\ displayStyle n = 3}$ und ${\ displayStyle k = 1}$ und verschiedene Bewertungen.
• ${\ displayStyle n = 4}$ und ${\ displayStyle K \ in \ {1,2 \}}$ und identische Bewertungen.

Verweise