Neidfreiheit - Envy-freeness

Neidfreiheit , auch Neidfreiheit genannt , ist ein Kriterium für eine gerechte Aufteilung . Darin heißt es, dass bei der Verteilung der Ressourcen auf gleichberechtigte Personen jeder einen Anteil erhalten soll, der in seinen Augen mindestens so gut ist wie der Anteil jedes anderen Akteurs. Mit anderen Worten, niemand sollte Neid empfinden .

Allgemeine Definitionen

Angenommen, eine bestimmte Ressource wird auf mehrere Agenten aufgeteilt, sodass jeder Agent einen Anteil erhält . Jeder Agent hat eine persönliche Präferenzbeziehung gegenüber verschiedenen möglichen Aktien. Die Teilung heißt neidfrei ( EF ) wenn für alle und :

Ein anderer Begriff für Neidfreiheit ist No-Neid ( NE ).

Wenn die Präferenzen der Agenten durch eine Wertfunktion repräsentiert werden , dann ist diese Definition äquivalent zu:

Anders ausgedrückt: Wir sagen, dass der Agent den Agenten beneidet , wenn er das Stück von seinem eigenen Stück bevorzugt , dh:

Eine Division wird als neidfrei bezeichnet, wenn kein Agent einen anderen Agenten beneidet.

Sonderfälle

Der Begriff der Neidfreiheit wurde 1958 von George Gamow und Marvin Stern eingeführt . Sie fragten, ob es immer möglich ist, einen Kuchen (eine heterogene Ressource) auf n Kinder mit unterschiedlichem Geschmack aufzuteilen , sodass kein Kind ein anderes beneidet. Für n = 2 Kinder kann dies mit dem Divide-and-select- Algorithmus erfolgen, aber für n > 2 ist das Problem viel schwieriger. Siehe neidfreies Kuchenschneiden .

Beim Kuchenschneiden bedeutet EF, dass jedes Kind glaubt, dass sein Anteil mindestens so groß ist wie jeder andere Anteil; in der Hausarbeit bedeutet EF, dass jeder Agent glaubt, dass sein Anteil mindestens so klein ist wie jeder andere Anteil (der entscheidende Punkt in beiden Fällen ist, dass kein Agent seinen Anteil mit einem anderen Agenten tauschen möchte). Siehe Aufgabenteilung .

Die Neidfreiheit wurde 1967 von Duncan Foley in das wirtschaftliche Problem der Ressourcenallokation eingeführt . Bei diesem Problem gibt es statt einer einzelnen heterogenen Ressource mehrere homogene Ressourcen. Neidfreiheit allein ist leicht zu erreichen, indem jeder Person 1/ n jeder Ressource gegeben wird. Die Herausforderung aus wirtschaftlicher Sicht besteht darin, sie mit Pareto-Effizienz zu kombinieren. Die Herausforderung wurde zuerst von David Schmeidler und Menahem Yaari definiert . Siehe Effiziente neidfreie Teilung .

Wenn die aufzuteilenden Ressourcen diskret (unteilbar) sind, kann Neidfreiheit selbst dann unerreichbar sein, wenn eine Ressource und zwei Personen vorhanden sind. Es gibt verschiedene Möglichkeiten, dieses Problem zu lösen:

Varianten

Starke Neidfreiheit erfordert, dass jeder Agent sein Bündel den anderen Bündeln strikt vorzieht.

Superneidfreiheit erfordert, dass jeder Agent sein Bündel strikt 1/ n des Gesamtwerts vorzieht und 1/ n jedem der anderen Bündelstrikt vorzieht. Offensichtlich impliziert Superneidfreiheit eine starke Neidfreiheit, die Neidfreiheit impliziert.

Gruppenneidfreiheit (auch Koalitionsneidfreiheit genannt ) ist eine Stärkung der Neidfreiheit, die verlangt, dass jede Teilnehmergruppe das Gefühl hat, dass ihr zugewiesener Anteil mindestens so gut ist wie der Anteil jeder anderen Gruppe mit derselben Größe. Eine schwächere Anforderung ist, dass jeder einzelne Agent keine Koalition anderer Agenten beneidet; es wird manchmal strenge Neidfreiheit genannt .

Stochastische Dominanz-Neidfreiheit (SD-Neidfreiheit, auch notwendige Neidfreiheit genannt ) ist eine Verstärkung der Neidfreiheit für ein Setting, in dem Agenten ordinale Rankings über Items melden. Sie erfordert Neidfreiheit gegenüber allen additiven Bewertungen, die mit der ordinalen Rangfolge vereinbar sind. Mit anderen Worten, jeder Agent sollte glauben, dass sein Bündel mindestens so gut ist wie das Bündel jedes anderen Agenten, entsprechend der responsiven Mengenerweiterung seiner ordinalen Rangfolge der Items. Eine ungefähre Variante von SD-EF, genannt SD-EF1 (SD-EF bis zu einem Artikel), kann durch das Round-Robin-Artikelzuweisungsverfahren erreicht werden.

Kein berechtigter Neid ist eine Abschwächung des Nicht-Neids für zweiseitige Märkte, in denen sowohl die Agenten als auch die "Items" Präferenzen gegenüber der Gegenseite haben, zB dem Markt der Schüler/Schulen. Schüler A empfindet berechtigten Neid gegenüber Schüler B, wenn A die B zugewiesene Schule bevorzugt und gleichzeitig die B zugewiesene Schule A bevorzugt.

Ex-ante-Neidfreiheit ist eine Schwächung der Neidfreiheit, die im Rahmen einer fairen Zufallszuweisung verwendet wird . In dieser Einstellung erhält jeder Agent eine Verlosung über die Artikel; eine Zuteilung von Lotterien heißt ex-ante neidfrei, wenn kein Vermittler die Lotterie eines anderen Vermittlers bevorzugt, dh kein Vermittler der Lotterie eines anderen Vermittlers einen höheren erwarteten Nutzen zuweist. Eine Zuordnung heißt ex-post neidfrei, wenn jedes Ergebnis neidfrei ist. Offensichtlich impliziert ex-post-Neidfreiheit ex-ante-Neidfreiheit, aber das Gegenteil ist möglicherweise nicht der Fall.

Lokale Neidfreiheit (auch: vernetzte Neidfreiheit oder soziale Neidfreiheit genannt ) ist eine Schwächung der Neidfreiheit auf Basis eines sozialen Netzwerkes . Es geht davon aus, dass die Menschen nur die Zuweisungen ihrer Nachbarn im Netz kennen und ihre Nachbarn daher nur beneiden können. Die Standard-Neidfreiheit ist ein Sonderfall der sozialen Neidfreiheit, bei der das Netzwerk der vollständige Graph ist .

Die Meta-Neidfreiheit erfordert, dass sich Agenten nicht gegenseitig beneiden, nicht nur in Bezug auf die endgültige Zuteilung, sondern auch in Bezug auf ihre Ziele im Protokoll. Siehe Symmetrisches faires Kuchenschneiden .

Neidminimierung ist ein Optimierungsproblem, bei dem es darum geht, die Neidmenge (die auf verschiedene Weise definiert werden kann) zu minimieren, auch in Fällen, in denen Neidfreiheit nicht möglich ist. Ungefähre Varianten der Neidfreiheit, die bei der Zuordnung von unteilbaren Objekten verwendet werden, finden Sie unter neidfreie Artikelzuordnung .

Beziehungen zu anderen Fairnesskriterien

Implikationen zwischen Verhältnismäßigkeit und Neidfreiheit

Verhältnismäßigkeit (PR) und Neidfreiheit (EF) sind zwei unabhängige Eigenschaften, aber in einigen Fällen kann das eine das andere implizieren.

Wenn alle Bewertungen additive Mengenfunktionen sind und der gesamte Kuchen geteilt wird, gelten folgende Implikationen:

  • Bei zwei Partnern sind PR und EF gleichwertig;
  • Bei drei oder mehr Partnern bedeutet EF PR, aber nicht umgekehrt. So ist es beispielsweise möglich, dass jeder von drei Partnern nach seiner subjektiven Meinung 1/3 erhält, aber nach Alices Meinung ist Bobs Anteil 2/3 wert.

Wenn die Bewertungen nur subadditive sind , impliziert EF immer noch PR, aber PR impliziert auch mit zwei Partnern nicht mehr EF: Es ist möglich, dass Alices Anteil in ihren Augen 1/2 wert ist, aber Bobs Anteil ist noch mehr wert. Im Gegenteil, wenn die Bewertungen nur superadditive sind , impliziert PR immer noch EF mit zwei Partnern, aber EF impliziert auch nicht mehr PR mit zwei Partnern: Es ist möglich, dass Alices Anteil in ihren Augen 1/4 wert ist, aber Bobs ist sogar wert weniger. In ähnlicher Weise impliziert EF keine PR mehr, wenn nicht alle Kuchen geteilt werden. Die Auswirkungen sind in der folgenden Tabelle zusammengefasst:

Bewertungen 2 Partner 3+ Partner
Zusatzstoff
Subadditiv
Superadditiv -
Allgemein - -

Siehe auch

Verweise