Egalitarny przydział przedmiotów

Egalitarna alokacja pozycji , zwana także alokacją pozycji max-min, jest problemem sprawiedliwej alokacji pozycji , w której kryterium sprawiedliwości jest zgodne z zasadą egalitarności . Celem jest maksymalizacja minimalnej wartości agenta. Oznacza to, że spośród wszystkich możliwych alokacji celem jest znalezienie alokacji, w której najmniejsza wartość agenta jest jak największa. W przypadku dwóch lub więcej alokacji o tej samej najmniejszej wartości, celem jest wybranie spośród tych alokacji tej, w której druga najmniejsza wartość jest jak największa i tak dalej (zgodnie z porządkiem leksyminowym ) . Dlatego egalitarna alokacja pozycji jest czasami nazywana alokacją pozycji leksyminowych .

Szczególny przypadek, w którym wartość każdej pozycji j dla każdego agenta wynosi 0 lub pewną stałą v _{j ,} nazywa się problemem Świętego Mikołaja : Święty Mikołaj ma ustalony zestaw prezentów i chce je rozdzielić między dzieci w taki sposób, aby najmniej- szczęśliwe dziecko jest tak szczęśliwe, jak to tylko możliwe.

Niektóre powiązane problemy to:

Wielokierunkowe partycjonowanie liczb z celem max-min odpowiada szczególnemu przypadkowi, w którym wszyscy agenci mają takie same wyceny. Jeszcze bardziej szczególnym przypadkiem jest problem partycji , który odpowiada przypadkowi dwóch agentów. Nawet ten szczególny przypadek jest ogólnie NP-trudny .
Szeregowanie niepowiązanych maszyn to podwójny problem, w którym celem jest zminimalizowanie maksymalnej wartości.
Alokacja pozycji akcji Maximin to inny problem, w którym celem nie jest osiągnięcie optymalnego rozwiązania, ale raczej znalezienie dowolnego rozwiązania, w którym każdy agent otrzyma wartość powyżej pewnego progu.

Normalizacja

Istnieją dwa warianty rządów egalitarnych:

absolutny egalitaryzm (lub absolutna leksymina ), gdzie maksymalizacja wykorzystuje wartości nominalne agentów;
względny egalitaryzm (lub względna leksymina ), gdzie maksymalizacja wykorzystuje ich znormalizowane wartości - wartość pakietu podzielona przez wartość wszystkich pozycji.

Te dwie reguły są równoważne, gdy wyceny agentów są już znormalizowane, to znaczy wszyscy agenci przypisują tę samą wartość do zbioru wszystkich pozycji. Mogą się one jednak różnić w przypadku wycen nieznormalizowanych. Na przykład, jeśli są cztery pozycje, Alicja ocenia je na 1,1,1,1, a George na 3,3,3,3, to reguła leksymin bezwzględnych dałaby Alicji trzy pozycje i jedną pozycję George'owi , ponieważ profil użyteczności w tym przypadku to (3,3), co jest optymalne. W przeciwieństwie do tego, reguła względnej leksyminy dałaby dwa elementy każdemu agentowi, ponieważ znormalizowany profil użyteczności w tym przypadku, gdy całkowita wartość obu agentów jest znormalizowana do 1, wynosi (0,5, 0,5), co jest optymalne.

Dokładne algorytmy

Chociaż ogólny problem jest NP-trudny, małe przypadki można dokładnie rozwiązać za pomocą technik programowania z ograniczeniami . Bouveret i Lemaître przedstawiają pięć różnych algorytmów znajdowania optymalnych rozwiązań leksyminy dla dyskretnych problemów spełniania ograniczeń. Przedstawiają alokację pozycji max-min jako przypadek szczególny.

Algorytmy aproksymacyjne

Poniżej n to liczba agentów, a m to liczba pozycji.

Dla szczególnego przypadku problemu Świętego Mikołaja:

O $}}) }$ } /\ log {\ log {\ log {n -algorytm aproksymacyjny, oparty na zaokrąglaniu programu liniowego .
Feige udowodnił, że istnieje algorytm aproksymacji wielomianu ze stałym współczynnikiem czasu, ale dowód wykorzystywał lokalny lemat Lovásza i był niekonstruktywny.
Asadpour, Feige i Saberi podali rzeczywisty algorytm aproksymacji ze stałym współczynnikiem, używając dopasowywania hipergrafów . Nie mogli udowodnić, że zbiega się w skończonej liczbie kroków.
Annamalai, Kalaitzis i Svensson podali algorytm 13-aproksymacji w czasie wielomianowym.

W przypadku ogólnym, dla agentów z wycenami addytywnymi :

Bezakova i Dani przedstawili dwa algorytmy. Pierwszy $przybliżenie$ _ Drugi znajduje alokację, która jest egalitarna do jednego dobra, to znaczy każdy agent otrzymuje swoją wartość w optymalnej egalitarnej alokacji pomniejszonej co najwyżej o jedną pozycję. Ich algorytm opiera się na poprzednim algorytmie autorstwa Lenstry, Shmoysa i Tardosa, który zasadniczo znajduje egalitarny przydział do jednego zadania . Oba algorytmy opierają się na podobnym pomyśle. Znajdują podstawowe wykonalne rozwiązanie liniowego programu znajdowania ułamkowej egalitarnej alokacji i zaokrąglają je w taki sposób, że każdy agent traci co najwyżej jedno dobro lub zyskuje co najwyżej jedno zadanie.
$_$ i podali _ Ich algorytm wykorzystuje iteracyjną metodę zaokrąglania dopasowania ułamkowego na drzewie . Zapewniają również lepsze granice, gdy pozwala się wykluczyć niewielką część osób z problemu.

$/ \ varepsilon})}$ Chuzoy i Khanna algorytm o czasie wykonywania $) {\$ $O (m ^$ , dla dowolnego ${\ Displaystyle \ varepsilon \ in \ Omega \ lewo ({\ Frac {\ log \ log m} {\ log m}} \prawo)}$ . Dla szczególnego przypadku, w którym każdy element ma niezerową użyteczność dla co najwyżej dwóch agentów, podali dwuczynnikowy algorytm aproksymacji i udowodnili, że trudno jest przybliżyć jakikolwiek lepszy czynnik.
Golovin podał algorytm, dzięki któremu dla każdej liczby całkowitej $} \displaystyle OPT/k}$ $($ co najmniej użyteczność za $\ Displaystyle (1-1$ . Wynik ten uzyskuje się z zaokrąglenia odpowiedniej relaksacji problemu w programowaniu liniowym i jest to najlepszy możliwy wynik dla tego programu liniowego. Podał również $aproksymacyjny$ dla szczególnego przypadku z dwiema
Dall'Aglio i Mosca podali dokładny, rozgałęziony algorytm dla dwóch agentów, oparty na adaptacji procedury Dostosowanego zwycięzcy .

Dla agentów z submodułowymi funkcjami użytkowymi :

Golovin podał $nieaproksymacji$ i pewne wyniki
Goemans, Harvey, Iwata i Mirrkoni podają za $} \ cdot n ^ {1/4} \cdot \log n\cdot \log ^{3/2}m)}$ -algorytm aproksymacji
Nguyen, Roos i Rothe przedstawiają nieco lepsze wyniki twardości.

Zwykle egalitarne przydziały

Standardowa reguła egalitaryzmu wymaga, aby każdy agent przypisał każdemu obiektowi wartość liczbową. Często agenci mają tylko narzędzia porządkowe . Istnieją dwa uogólnienia reguły egalitarnej na ustawienia porządkowe.

1. Załóżmy, że agenci mają uporządkowany ranking nad zbiorem wiązek . Biorąc pod uwagę dowolną dyskretną alokację, dla dowolnego agenta i zdefiniuj r ( i ) jako rangę pakietu agenta i, tak że r(i)=1, jeśli mam jego najlepszy pakiet, r(i)=2, jeśli mam jego drugi- najlepszy pakiet itd. To r jest wektorem o rozmiarze n (liczba agentów). Porządkowo egalitarna alokacja to taka, która minimalizuje największy element w r. Procedura Malejącego Popytu znajduje uporządkowaną egalitarną alokację dla dowolnej liczby agentów z dowolnym uporządkowaniem wiązek.

2. Załóżmy, że agenci mają porządek porządkowy w zbiorze przedmiotów . Biorąc pod uwagę dowolną alokację dyskretną lub ułamkową, dla dowolnego agenta i i dodatniej liczby całkowitej k , zdefiniuj t ( i , k ) jako całkowity ułamek, który agent i otrzymuje z jego k najwyższych klas obojętności. To t jest wektorem o rozmiarze co najwyżej n * m , gdzie n to liczba agentów, a m to liczba elementów. Porządkowo egalitarna alokacja to taka, która maksymalizuje wektor t w porządku leksymin. Algorytm jednoczesnego jedzenia z równymi prędkościami jedzenia jest unikalną regułą, która zwraca typowo egalitarny przydział.

Porównanie z innymi kryteriami słuszności

Proporcjonalność

Ilekroć istnieje alokacja proporcjonalna, alokacja względna leksymin jest proporcjonalna. Dzieje się tak dlatego, że w alokacji proporcjonalnej najmniejsza względna wartość agenta wynosi co najmniej 1/ n , więc to samo musi obowiązywać, gdy maksymalizujemy najmniejszą względną wartość. Jednak absolutna alokacja leksymin może nie być proporcjonalna, jak pokazano w powyższym przykładzie.

Wolność od zazdrości

1. Gdy wszyscy agenci mają identyczne wyceny z niezerowymi użytecznościami krańcowymi, każda alokacja względna leksymin to PO i EFX .

Ulepszenie leksyminy zwane leximin++ gwarantuje EFX (ale nie PO) z generalnie identycznymi wartościami.

2. Dla dwóch agentów z wartościowaniem addytywnym, jakakolwiek alokacja względna leksyminowa to EF1. Jednakże:

Absolutna alokacja leksymin może nie być EF1 nawet dla dwóch agentów z wartościami addytywnymi. Załóżmy na przykład, że istnieją cztery towary i dwóch agentów, którzy wyceniają je na {0,1,1,1} i {3,3,3,3}. Unikalna alokacja leksymin bezwzględnych daje {1,1,1} pierwszemu agentowi i {3} drugiemu agentowi, ale wtedy drugi agent zazdrości.
Względna alokacja leksymin może nie być EF1 dla trzech lub więcej agentów. Załóżmy na przykład, że są cztery towary i trzech agentów, którzy wyceniają je na {30,0,0,0} {20,5,5,0} i {0,12,12,6}. Należy zauważyć, że wyceny są znormalizowane (łączna wartość to 30). W alokacji leksyminowej pierwsze dobro musi zostać przydzielone agentowi 1. Następnie drugie i trzecie dobro musi zostać przydzielone agentowi 2, a dobro pozostaje dla agenta 3. Ale wtedy agent 3 zazdrości agentowi 2 nawet po usunięciu pozycji.

3. Kiedy wszyscy agenci mają wartościowania, które są matroidowymi funkcjami rang (tj. submodularnymi z binarnymi marginesami), zbiór absolutnych alokacji leksyminowych jest równoważny zbiorowi alokacji maksymalnych produktów; wszystkie takie alokacje to max-sum i EF1.

4. W kontekście niepodzielnej alokacji prac domowych (przedmioty o użyteczności ujemnej), z 3 lub 4 agentami z wartościowaniami addytywnymi, każda optymalna alokacja leksyminowa to PROP1 i PO; z n agentami o generalnie identycznych wartościowaniach, każda optymalna alokacja leksyminy to EFX.

Udostępnij Maksymina

Gdy wszyscy agenci mają identyczne wyceny, egalitarna alokacja z definicji daje każdemu agentowi co najmniej jego maksiminowy udział.

Jednak gdy agenci mają różne wyceny, problemy są inne. Alokacja maximin-share jest problemem satysfakcji: celem jest zagwarantowanie, że każdy agent otrzyma wartość powyżej progu identycznych wycen. Natomiast egalitarna alokacja jest problemem optymalizacyjnym: celem jest nadanie każdemu agentowi jak największej wartości. W niektórych przypadkach wynikowe przydziały mogą być bardzo różne. Załóżmy na przykład, że są cztery towary i trzech agentów, którzy wyceniają je na {3,0,0,0}, {3-2 ε,ε,ε ,0} i {1-2 ε ,1,1,2 ε } (gdzie ε jest małą dodatnią stałą). Należy zauważyć, że wyceny są znormalizowane (całkowita wartość wynosi 3), więc leksymina bezwzględna i leksymina względna są równoważne.

Alokacja leksymin daje profil użyteczności (3, 2ε, 2ε ): pierwsza pozycja musi trafić do agenta 1 - w przeciwnym razie najmniejsza użyteczność wynosi 0. Następnie druga i trzecia pozycja muszą trafić do agenta 2 - w przeciwnym razie kolejna najmniejsza użyteczność wynosi ε lub mniej; więc agent 3 otrzymuje tylko ostatni przedmiot.
Wartości maksymalnego udziału agentów wynoszą 0, ε , 1. Dlatego przydział maksymalnego udziału agenta musi dać agentowi 3 jedną z pierwszych trzech pozycji; niektóre możliwe profile użyteczności w tym przypadku to (0, 2ε , 1) lub (3, ε , 1+ 2ε ).

Przykład można rozszerzyć do 1-z- k MMS-ów dla dowolnego k >3. Jest k +1 towarów i trzech agentów, którzy wyceniają je na { k , 0, ..., 0}, { k - ( k -1) ε , ε, ..., ε , 0} i {1- kε , 1, 1, ..., k ε }. Profil użyteczności leksyminy musi wynosić ( k , kε, kε ), podczas gdy 1-z- k MMS agenta 3 wynosi 1.

Aplikacja w świecie rzeczywistym

Reguła leksymin została wykorzystana do sprawiedliwego przydzielania nieużywanych sal lekcyjnych w szkołach publicznych do szkół społecznych.