Super brak zazdrości

Podział wolny od superzazdrości jest rodzajem sprawiedliwego podziału . Jest to podział zasobów między n partnerów, w którym każdy partner wycenia swój udział na ściśle więcej niż jego/jej należny udział w wysokości 1/ n całkowitej wartości, a jednocześnie wycenia udział każdego innego partnera na ściśle niższą niż 1/ n . Formalnie, w super-wolnym od zazdrości podziale zasobu C między n partnerów, każdy partner i , z miarą wartości V _i , otrzymuje udział X _i takie, że:

${\ Displaystyle V_ {i} (X_ {i})> V_ { i}(C)/n~~{\text{ i }}~~\forall j\neq i:V_{i}(X_{j})<V_{i}(C)/n}$ .

Jest to silny wymóg sprawiedliwości: jest silniejszy zarówno od braku zazdrości , jak i od superproporcjonalności .

Istnienie

Wolność od superzazdrości została wprowadzona przez Juliusa Barbanela w 1996 roku. Udowodnił on, że krojenie tortu wolne od superzazdrości istnieje wtedy i tylko wtedy, gdy miary wartości n partnerów są liniowo niezależne . „Liniowo niezależny” oznacza, że ​​nie ma wektora n niezerowych liczb rzeczywistych ${\ Displaystyle c_ {1}, \ ldots, c_ {n} \ in \ mathbb {R}}$ dla co ${\ Displaystyle c_ {1} \ cdot V_ {1} + \ cdots + c_ {n} \ cdot V_ {n} = 0}$ ,

Obliczenie

W 1999 roku William Webb przedstawił algorytm, który znajduje w tym przypadku alokację wolną od superzazdrości. Jego algorytm opiera się na świadectwie , że miary są niezależne. Świadkiem jest n -na- n , w której elementem ( i , j ) jest wartość przypisana przez agenta i do jakiegoś kawałka j (gdzie kawałki 1,..., n mogą być dowolnymi częściami tortu, na przykład przykład podział na przedziały o równej długości). Macierz powinna być odwracalna - świadczy to o liniowej niezależności miar.

Wykorzystując taką macierz, algorytm dzieli każdą z n części na prawie dokładny podział . Można wykazać, że jeśli macierz jest odwracalna, a współczynnik aproksymacji jest wystarczająco mały (w stosunku do wartości w odwrotności macierzy), to wynikowa alokacja jest rzeczywiście wolna od superzazdrości.

Czas działania algorytmu zależy od właściwości macierzy. Jeśli jednak miary wartości są rysowane jednostajnie losowo z jednostki simplex, z dużym prawdopodobieństwem, czas wykonania jest wielomianowy w n .