Super Neidfreiheit - Super envy-freeness
Eine superneidfreie Teilung ist eine Art faire Teilung . Es ist eine Aufteilung der Ressourcen auf n Partner, bei der jeder Partner seinen Anteil strikt höher bewertet als seinen fälligen Anteil von 1/ n des Gesamtwertes und gleichzeitig den Anteil jedes anderen Partners mit einem strikt niedrigeren Wert bewertet als 1/ n . Formal erhält bei einer superneidfreien Aufteilung einer Ressource C auf n Partner jeder Partner i mit dem Wertmaß V i einen Anteil X i , so dass:
.
Dies ist ein starkes Gebot der Fairness: Es ist stärker als Neidfreiheit und Überproportionalität .
Existenz
Super Neidfreiheit von Julius Barbanel im Jahr 1996 eingeführt wurde Er bewies , dass ein super- Neid freien Kuchen Schneiden liegt vor , wenn-und-nur-wenn der Wert Maßnahmen der n Partner sind linear unabhängig . "Linear unabhängig" bedeutet, dass es keinen Vektor von n von Null verschiedenen reellen Zahlen gibt, für die ,
Berechnung
1999 stellte William Webb einen Algorithmus vor, der in diesem Fall eine superneidfreie Zuordnung findet. Sein Algorithmus basiert auf einem Zeugnis dafür, dass die Maßnahmen unabhängig sind. Ein Zeuge ist eine n- mal- n- Matrix, in der Element ( i , j ) der Wert ist, den der Agent i einem Stück j zuweist (wobei die Stücke 1,..., n eine beliebige Partition des Kuchens sein können, für B. in gleichlange Intervalle partitionieren). Die Matrix sollte invertierbar sein – dies zeugt von der linearen Unabhängigkeit der Maßnahmen.
Unter Verwendung einer solchen Matrix zerlegt der Algorithmus jedes der n Teile in eine nahezu exakte Division . Es kann gezeigt werden, dass, wenn die Matrix invertierbar ist und der Näherungsfaktor ausreichend klein ist (bezogen auf die Werte in der Inversen der Matrix), die resultierende Allokation tatsächlich super-neidfrei ist.
Die Laufzeit des Algorithmus hängt von den Eigenschaften der Matrix ab. Wenn jedoch die Wertmaße mit hoher Wahrscheinlichkeit gleichmäßig zufällig aus dem Einheitssimplex gezogen werden, ist die Laufzeit in n polynomiell .