Udostępnij Maksymina

Nie należy mylić z alokacją pozycji Max-min .

Udział Maximin (MMS) jest kryterium sprawiedliwego przydziału pozycji . Biorąc pod uwagę zestaw pozycji o różnych wartościach, maksymalny udział 1 z n jest maksymalną wartością, jaką można uzyskać, dzieląc pozycje na n części i biorąc część o minimalnej wartości.

Alokacja przedmiotów między n agentów o różnych wycenach nazywana jest MMS-fair , jeśli każdy agent otrzymuje pakiet, który jest co najmniej tak dobry, jak jego/jej 1-z- n- maksymalnej-udziału. Uczciwość MMS została wymyślona przez Erica Budisha jako złagodzenie kryterium proporcjonalności – każdy agent otrzymuje pakiet, który jest co najmniej tak dobry, jak równy podział (1/ n każdego zasobu). Proporcjonalność można zagwarantować, gdy pozycje są podzielne, ale nie wtedy, gdy są one niepodzielne, nawet jeśli wszyscy agenci mają identyczne wyceny. W przeciwieństwie do tego uczciwość MMS zawsze można zagwarantować identycznym agentom, więc jest to naturalna alternatywa dla proporcjonalności, nawet jeśli agenci są różni.

Motywacja i przykłady

Identyczne elementy. Załóżmy najpierw, że m identycznych przedmiotów należy sprawiedliwie rozdzielić między n osób. W idealnej sytuacji każda osoba powinna otrzymać m / n przedmiotów, ale może to być niemożliwe, jeśli m nie jest podzielne przez n , ponieważ przedmioty są niepodzielne. Naturalnym drugim najlepszym kryterium rzetelności jest zaokrąglenie m / n w dół do najbliższej liczby całkowitej i przydzielenie każdej osobie co najmniej pozycji floor ( m / n ). Odbieranie mniej niż podłoga( m / n ) przedmiotów jest „zbyt niesprawiedliwe” – jest to niesprawiedliwość nieuzasadniona niepodzielnością przedmiotów.

Różne przedmioty. Załóżmy teraz, że przedmioty są różne, a każdy element ma inną wartość. Załóżmy na przykład, że n = 3 i m = 5, a wartości pozycji to 1, 3, 5, 6, 9, sumując się do 24. Gdyby pozycje były podzielne, dalibyśmy każdej osobie wartość 24/3 = 8 (lub, gdyby były podzielne tylko do wartości całkowitych, jak w poprzednim akapicie, przynajmniej floor(24/3) = 8), ale nie jest to możliwe. Największą wartością, jaką można zagwarantować wszystkim trzem agentom, jest 7 według partycji {1,6},{3,5},{9}. Nieformalnie 7 to całkowita wartość podzielona przez n „zaokrąglona w dół do najbliższej pozycji”.

Zbiór {1,6} osiągający tę maksymalną wartość nazywa się „1-out-of-3 maximin-share” - jest to najlepszy podzbiór przedmiotów, jaki można skonstruować dzieląc oryginalny zbiór na 3 części i biorąc najmniejszą cenna część. Dlatego w tym przykładzie alokacja jest odpowiednia dla MMS-ów, jeśli daje każdemu agentowi wartość co najmniej 7.

Różne wyceny. Załóżmy teraz, że każdy agent przypisuje inną wartość do każdego elementu, na przykład:

• Alice ocenia je na 1,3,5,6,9;
• George ocenia je na 1,7,2,6,8;
• Dina wycenia je na 1,1,1,4,17.

Teraz każdy agent ma inny MMS:

• MMS Alicji to nadal {1,6} jak powyżej;
• MMS George'a to {1,7} lub {2,6} lub {8}, według partycji {1,7},{2,6},{8} (wszystkie te pakiety są dla niego równoważne);
• MMS Diny to {1,1,1}, według partycji {1,1,1},{4},{17}.

W tym przypadku przydział jest sprawiedliwy dla MMS-ów, jeśli daje Alice wartość co najmniej 7, George'owi wartość co najmniej 8, a Dinie co najmniej 3. Na przykład przyznanie George'owi dwóch pierwszych pozycji {1,7} , Alice dwie następne pozycje {5,6} i Dina ostatnia pozycja {17}, jest odpowiednia dla MMS-ów.

Interpretacja . 1-z- n MMS agenta można interpretować jako maksymalną użyteczność, jaką agent może uzyskać z alokacji, jeśli wszyscy inni agenci mają takie same preferencje , podczas gdy on zawsze otrzymuje najgorszą część. Jest to minimalna użyteczność, do której agent może czuć się uprawniony, w oparciu o następujący argument: jeśli wszyscy pozostali agenci mają takie same preferencje jak ja, istnieje co najmniej jedna alokacja, która daje mi tę użyteczność i sprawia, że ​​każdy inny agent (słabo ) lepiej; dlatego nie ma powodu, by dawać mi mniej.

Alternatywna interpretacja jest następująca: najbardziej preferowany pakiet, który agent może zagwarantować jako „dzielnik w podziale” i wybrać przeciwko wrogim przeciwnikom: agent proponuje swoją najlepszą alokację i pozostawia wszystkim pozostałym wybór jednej części przed zabraniem pozostałej.

Uczciwość MMS można również opisać jako wynik następującego procesu negocjacyjnego. Sugerowana jest pewna alokacja. Każdy agent może się temu sprzeciwić, proponując alternatywny podział przedmiotów. Jednak czyniąc to, musi pozwolić, aby wszyscy inni agenci wybrali swój udział, zanim to zrobi. W związku z tym agent sprzeciwiłby się alokacji tylko wtedy, gdyby mógł zasugerować podział, w którym wszystkie pakiety są lepsze niż jego obecny pakiet. Przydział jest sprawiedliwy dla MMS, jeśli żaden agent nie sprzeciwia się temu, tj. dla każdego agenta w każdej partycji istnieje pakiet, który jest nieznacznie gorszy niż jego aktualny udział.

Definicja formalna

Niech C będzie zbiorem reprezentującym zasób, który ma zostać przydzielony. Niech V będzie dowolną funkcją rzeczywistą na podzbiorach C , reprezentującą ich „wartość”. Udział 1-z- n maksymin V z C jest zdefiniowany jako :

${\ Displaystyle \ nazwa operatora {MMS} _ {V} ^ {1 {\ tekst {-out-of-}} n} (C): = ~ ~ ~ \ max _ {(Z_ {1}, \ ldots, Z_ {n})\in \operatorname {Partycje} (C,n)}~~~\min _{j\in [n]}~~~V(Z_{j})}$

Tutaj maksimum dotyczy wszystkich podziałów C na n rozłącznych podzbiorów, a minimum dotyczy wszystkich n podzbiorów w podziale. W powyższych przykładach C było zbiorem liczb całkowitych, a V było funkcją sumującą, to znaczy V(Z) zdefiniowano jako sumę liczb całkowitych w Z . Na przykład pokazaliśmy, że ${\ Displaystyle \ nazwa operatora {MMS} _ {V} ^ {1 {\ tekst {-out-of-}} 3} (\ {1,3,5,6,9 \}): = 7}$ , gdzie partycja maksymalizująca to ({1,6},{3,5},{9}). W typowym problemie sprawiedliwej alokacji istnieje kilka n różnych agentów o różnych funkcjach wartości V ₁ ,..., V _n względem tego samego zasobu C . Wartość 1-z- n MMS agenta i jest oznaczona jako ${\ Displaystyle \ operatorname {MMS} _ {i} ^ {1 {\ tekst {-out-of-}} n} (C): = \ operatorname {MMS } _{V_{i}}^{1{\text{-out-of-}}n}(C)}$ . Alokacja jest wektorem n rozłącznych parami podzbiorów C — po jednym podzbiorze na agenta. Alokacja Z ₁ ,..., Z _n jest nazywana MMS-fair jeśli dla każdego agenta i,

${\ Displaystyle V_ {i} (Z_ {i}) \ geq \ nazwa operatora {MMS} _ {i} ^ {1 {\ tekst {-z-}}n}(C)}$ .

Istnienie sprawiedliwych przydziałów MMS

Gdy wszystkie n agentów ma identyczne wyceny, z definicji zawsze istnieje sprawiedliwa alokacja MMS.

Nieco bardziej ogólny przypadek, w którym istnieje alokacja sprawiedliwa dla MMS, to sytuacja, w której kilku agentów n -1 ma identyczne wyceny. Alokację sprawiedliwą dla MMS można następnie znaleźć metodą dziel i wybierz : n -1 identycznych agentów dzieli elementy na n wiązek, z których każda jest co najmniej tak dobra, jak ich MMS; n ty agent wybiera paczkę o najwyższej wartości; a identyczni agenci biorą pozostałe n -1 wiązek. W szczególności w przypadku dwóch agentów zawsze istnieje sprawiedliwy przydział MMS.

Bouveret i Lemaître przeprowadzili obszerne randomizowane symulacje dla więcej niż 2 agentów i stwierdzili, że w każdej próbie istnieją przydziały zgodne z MMS. Udowodnili, że przydziały MMS istnieją w następujących przypadkach:

• Wyceny binarne - każdy agent albo lubi przedmiot (wycenia go na 1), albo go nie lubi (wycenia go na 0).
• Identyczne zbiory wielokrotne — agenci mogą wyceniać pozycje w różny sposób, ale zbiory wartości agentów są takie same.
• Kilka pozycji - m ≤ n +3.

Procaccia, Wang i Kurokawa skonstruowali instancję z n= 3 agentami i m =12 pozycji, w której żadna alokacja nie gwarantuje każdemu agentowi 1-z-3 MMS. W ich przypadku jest 12 obiektów indeksowanych przez ${\ Displaystyle i \ w [3]}$ i ${\ Displaystyle j \ w [4]}$ . Każdy agent $jot$${\ Displaystyle (i, j)}$ obiekt przez:

$\ Displaystyle v_ {k} (i, j) = 1 000 000 + 1 000 \ cdot T_ { i,j}+E_{i,j}^{(k)}}$

gdzie ${\ Displaystyle T, mi ^ {(1)}, mi ^ {(2)}, mi ^ {(3)}}$ są szczególnymi macierzami 3 na 4 z wartościami mniejszymi niż 100. Dowodzą one, że każdy agent może podzielić obiekty na 3 podzbiory po 4 obiekty w każdym, tak że suma wartości w każdym podzbiorze wynosi 4 055 000, co jest zatem MMS wszystkich agenci. Udowadniają, że każdy przydział MMS musi dać każdemu agentowi dokładnie 4 konkretne obiekty, ale taki przydział nie istnieje. Zatem każda alokacja daje co najmniej jednemu agentowi wartość co najwyżej 4 054 999. Uogólnili ten przypadek i pokazali, że dla każdego n ≥ 3 istnieje taki przypadek z 3 n +4 pozycjami.

Natomiast ci sami autorzy pokazują, że w losowym przypadku alokacja MMS istnieje z dużym prawdopodobieństwem . Dowód uwzględnia dwa przypadki:

• Istnieje $:$$,$ dla pewnej Następnie, na podstawie poprzedniego wyniku, z dużym prawdopodobieństwem istnieje alokacja pozycji wolna od zazdrości ; takim przydziałem jest zawsze MMS.
• Jest kilka elementów: $[$ że ten przypadek częściowo pokrywa się z poprzednim W tym przypadku przedstawiają algorytm zwany dopasowanym szkicem . Polega ona na zbudowaniu dwudzielnego grafu agentów vs. przedmiotów i znalezieniu w nim idealnego dopasowania . Dowodzą, że (1) prawdopodobieństwo, że dopasowany projekt się powiedzie, wynosi 1, gdy n dąży do nieskończoności. (2) Jeśli dopasowany projekt się powiedzie, wówczas wartością każdego agenta jest co najmniej jego MMS.

Amanatidis, Markakis, Nikzad i Saberi również dowodzą, że w losowo generowanych przypadkach przydziały zgodne z MMS-ami istnieją z dużym prawdopodobieństwem .

Feige, Sapir i Tauber przedstawiają ściślejszy przypadek, w którym współczynnik aproksymacji wynosi 39/40,

przybliżenia

Budish wprowadził przybliżenie do 1-of- n MMS - 1-of- ( ${\ displaystyle n + 1}$ ) MMS - każdy agent otrzymuje co najmniej tyle, ile mógłby uzyskać, dzieląc na pakiety n + 1 i dostać najgorszą. Ogólnie rzecz biorąc, dla dowolnego d > n można uznać MMS 1-of-d jako przybliżenie MMS-a 1-of -n i szukać alokacji, w której dla każdego agenta i :

${\ Displaystyle V_ {i} (Z_ {i}) \ geq \ nazwa operatora {MMS} _ {i} ^ {1 {\ tekst {-out-of-}}d}(C)}$

Zauważ, że wartość 1 z d MMS jest słabo malejącą funkcją d . Nazywa się to przybliżeniem porządkowym , ponieważ zależy tylko od uszeregowania wiązek, a nie od ich dokładnych wartości. Procaccia i Wang wprowadzili inny rodzaj przybliżenia - przybliżenie multiplikatywne do MMS: alokacja to r-frakcja MMS -fair, dla pewnego ułamka r w [0,1], jeśli wartość każdego agenta jest co najmniej ułamkiem r wartości jego/jej MMS, czyli dla każdego agenta i :

${\ Displaystyle V_ {i} (Z_ {i}) \ geq r \ cdot \ operatorname {MMS} _ {i} ^ {1{\text{-poza-}}n}(C)}$

Załóżmy, że mamy do wyboru dwa algorytmy: pierwszy gwarantuje przybliżenie multiplikatywne (np. MMS 3/4-fraction), a drugi przybliżenie porządkowe (np. 1-out-of-(3 n /2) MMS ) . Która z dwóch gwarancji jest wyższa? Odpowiedź zależy od wartości.

• Przybliżenie multiplikatywne jest większe, na przykład, gdy istnieje n identycznych towarów o wartości 1. Wtedy MMS 1-of- ${\ displaystyle d}$ wynosi 0 dla dowolnego d > n , ale 1-of- ${\ displaystyle n}$ MMS wynosi 1, więc każde pozytywne przybliżenie multiplikatywne jest lepsze.
• Przybliżenie porządkowe jest większe, np. gdy istnieje d identycznych towarów o wartości 1, dla pewnego d w { n +1,...,2 n -1}. Wtedy 1-of-d wynosi 1, a MMS 1-of- $wynosi$ 1, więc każde r -multiplikatywne przybliżenie tego z r <1 jest gorsze.

Ogólnie rzecz biorąc, dla dowolnej liczby całkowitej k , 1-z- n MMS jest co najmniej k razy większy niż 1-nk MMS : weź optymalną partycję MMS 1- nk i pogrupuj pakiety w n super-pakietów, z których każdy z czego zawiera k oryginalnych wiązek. Każdy z tych superpakietów jest wart co najmniej k -krotności najmniejszego oryginalnego pakietu. Dlatego przybliżenie 1/ k -multiplikatywne jest co najmniej tak duże jak przybliżenie porządkowe 1-of- nk , ale może być mniejsze niż 1-of-( nk- 1) przybliżenie porządkowe, jak w powyższym przykładzie. W szczególności każde r -multiplikatywne przybliżenie dla r ≥ 1/2 jest co najmniej tak samo dobre jak przybliżenie porządkowe 1-of-(2 n ), ale może być gorsze niż przybliżenie porządkowe 1-of-(2 n -1).

Uczciwa alokacja towarów MMS

Przybliżenia multiplikatywne

Procaccia i Wang przedstawili algorytm, który zawsze znajduje rn _- frakcję MMS, gdzie

${\ Displaystyle r_ {n}: = {\ Frac {2 \ cdot {\ tekst {oddfloor}} (n)} {3 \ cdot {\ tekst {oddfloor}} (n) -1}} = {\ rozpocząć { przypadkach}{\frac {2n}{3n-1}}&n~{\text{nieparzysty}}\\{\frac {2n-2}{3n-4}}&n~{\text{parzysty}}\end {sprawy}}}$

gdzie oddfloor( n ) jest największą nieparzystą liczbą całkowitą mniejszą lub równą n . W szczególności, r ₃ = r ₄ = 3/4, maleje, gdy n wzrasta, i zawsze jest większe niż 2/3. Ich algorytm działa w czasie wielomianowym w m , gdy n jest stałe, ale jego czas działania może być wykładniczy w n .

Amanatidis, Markakis, Nikzad i Saberi przedstawili kilka ulepszonych algorytmów:

• Prosty i szybki algorytm MMS 1/2 ułamka;
• Algorytm MMS o ułamkach 2/3, który działa w czasie wielomianowym zarówno w m , jak i n ;
• Algorytm MMS 7/8 frakcji dla 3 agentów;
• Algorytm MMS-fair dla przypadku wycen trójskładnikowych - każda wartość to 0 lub 1 lub 2.

Barman i Krishnamurthy zaprezentowali:

• Prosty i szybki algorytm dla 2/3-frakcyjnego MMS-a z addytywnymi wycenami . Ich algorytm opiera się na „uporządkowaniu” instancji (tj. zredukowaniu instancji do takiej, w której wszyscy agenci zgadzają się co do rankingu dóbr), a następnie przeprowadzeniu procedury grafu zazdrości, zaczynając od najcenniejszego dobra. Dowodzą, że wynikiem jest EFX i gwarantuje każdemu agentowi $jego$ .
• Prosty algorytm dla MMS-ów ułamkowych 1/10 dla bardziej wymagającego przypadku wycen submodułowych - oparty na alokacji pozycji okrężnej .

Ghodsi, Hajiaghayi, Seddighin, Seddighin i Yami przedstawili:

• W przypadku wycen addytywnych: dowód na istnienie uczciwości 3/4 frakcji MMS.
• Dla n = 4 dodatkowych środków: algorytm 4/5-frakcyjnej uczciwości MMS.
• W przypadku wycen submodularnych : algorytm czasu wielomianowego dla uczciwości MMS 1/3 ułamka i górna granica ułamka 3/4.
• Dla wycen XOS : algorytm czasu wielomianowego dla uczciwości MMS 1/8 ułamka, dowód istnienia dla ułamka 1/5 i górna granica ułamka 1/2.
• Dla wycen subaddytywnych : dowód istnienia log( m )/10-frakcji MMS-uczciwości i górna granica 1/2-ułamka.

Garg, McGlaughlin i Taki zaprezentowali prosty algorytm 2/3 frakcji uczciwości MMS, którego analiza jest również prosta.

Garg i Taki zaprezentowali:

• Prosty algorytm dla MMS-a ułamkowego 3/4, który nie musi znać wartości MMS, a więc działa w silnie wielomianowym czasie.
• Dowód na istnienie -frakcji MMS ${\ Displaystyle ({\ Frac {3} {4}} + {\ Frac {1} {12n}}}}$

Do tej pory nie wiadomo, jakie jest największe r takie, że r -frakcja MMS zawsze istnieje. Może to być dowolna liczba z przedziału od 3/4 do nieco mniejszej niż 1.

Przybliżenia porządkowe

Budish wykazał, że przybliżona równowaga konkurencyjna z równych dochodów zawsze gwarantuje 1-z- ( ${\ displaystyle n + 1}$ ) MMS, jednak ta alokacja może mieć nadwyżkę podaży i - co ważniejsze - nadwyżkę popytu: suma paczek przydzielonych wszystkim agentom może być nieco większy niż zbiór wszystkich pozycji. Taki błąd jest uzasadniony przy przydzielaniu kursów , ponieważ niewielką nadwyżkę podaży można skorygować dodając niewielką liczbę miejsc. Ale klasyczny problem sprawiedliwego podziału zakłada, że ​​elementy nie mogą być dodawane.

Bez nadwyżki podaży i popytu znane są następujące przybliżenia:

• 1 z (2 n -2) MMS i przydział obowiązków domowych 1 z (2 n / 3) MMS, przy użyciu dopasowywania bez zazdrości .
• 1-z-(3 n /2) MMS, która może być obliczona w wieloczasie, gdy n <6.
• Alokacja towarów 1-z-(3 n /2) MMS w czasie wielomianowym i wynik istnienia alokacji L -z-([ L +1/2] n ) MMS.
• 1-z-(3 n /4) MMS.

Do tej pory nie wiadomo, jaka jest najmniejsza liczba d taka, że ​​zawsze istnieje przydział wiadomości MMS 1 z d . Może to być dowolna liczba z zakresu od n +1 do 3 n/ 2. Najmniejsza otwarta sprawa to n = 4.

Dodatkowe ograniczenia

Maksymalizacja produktu : Caragiannis, Kurokawa, Moulin, Procaccia, Shah i Wang wykazali, że alokacja maksymalnego dobrobytu Nasha (alokacja maksymalizująca iloczyn użyteczności) jest zawsze ${\ displaystyle {\ frac {2 }{1+{\sqrt {4n-3}}}}}$ -fraction MMS uczciwy i ciasny.

Prawdomówność : Amanatidis, Birmpas i Markakis przedstawili zgodne z prawdą mechanizmy przybliżonej alokacji uczciwych MMS (patrz także Strategiczny podział targów ):

• Dla n agentów: frakcja 1/O( m ) MMS.
• Dla 2 agentów: MMS 1/2 frakcji i dowód, że żaden prawdomówny mechanizm nie może osiągnąć więcej niż 1/2.

Ograniczenia liczności : przedmioty są podzielone na kategorie, a każdy agent może uzyskać co najwyżej k _h elementów z każdej kategorii h . Innymi słowy, pakiety muszą być niezależnymi zestawami macierzy partycji .

• Barman i Biswas przedstawiają algorytm redukujący problem do problemu bez ograniczeń, ale z wycenami submodułowymi, a następnie używają algorytmu do osiągnięcia 1/3-frakcyjnej uczciwości MMS.
• Hummel i Hetland przedstawiają ulepszony algorytm czasu wielomianowego dla 1/2-frakcyjnej uczciwości MMS. Dostosowują standardowe techniki i redukcje z ustawienia nieograniczonego do ustawienia z ograniczeniami, a następnie stosują wariant procedury napełniania worka.

Wykres konfliktów : Hummel i Hetland badają inne ustawienie, w którym istnieje wykres konfliktów między przedmiotami (na przykład: przedmioty reprezentują zdarzenia, a agent nie może uczestniczyć w dwóch jednoczesnych wydarzeniach). Pokazują, że jeśli stopień wykresu konfliktu wynosi d i jest w (2, n ), to przydział MMS o ułamku 1/ d można znaleźć w czasie wielomianowym, a przydział MMS o ułamku 1/3 zawsze istnieje .

Łączność : elementy znajdują się na wykresie, a każda część musi być połączonym podgrafem.

• Bouveret, Cechlarova, Elkind, Igarashi i Peters dowodzą, że jeśli wykres jest acykliczny, to zawsze istnieje sprawiedliwa alokacja MMS i można ją skutecznie znaleźć. Na ogólnych wykresach alokacja odpowiednia dla MMS-ów może nie istnieć i może być NP-trudna do znalezienia.
• Lonc i Truszczyński skupiają się na przypadku, w którym graf jest cyklem, i przedstawiają algorytm dla alokacji w przybliżeniu zgodnej z MMS.

Przydział obowiązków zgodny z MMS

Aziz, Rauchecker, Schryen i Walsh rozszerzyli pojęcie MMS na prace domowe (przedmioty o negatywnej użyteczności). Należy zauważyć, że w przypadku czynności domowych multiplikatywne współczynniki przybliżenia są większe niż 1 (ponieważ mniejsza liczba czynności domowych ma wyższą użyteczność), a porządkowe współczynniki przybliżenia są mniejsze niż n . Przedstawili:

• Dowód, że przydział MMS może nie istnieć dla obowiązków domowych;
• Algorytm 2-frakcyjny MMS do zadań domowych;
• Algorytmy znajdowania optymalnej aproksymacji MMS dla danej instancji, oparte na algorytmach wielokierunkowego podziału numerów .

Barman i Krishnamurthy przedstawili algorytm osiągający MMS o ułamku 4/3 (dokładnie, ${\ Displaystyle {\ Frac {4n-1} {3n}}}$ . Algorytm można postrzegać jako uogólnienie algorytmu LPT dla planowania identycznych maszyn.

Huang i Lu dowodzą, że zawsze istnieje alokacja 11/9 ułamka MMS dla zadań domowych , a przydział MMS ułamka 5/4 można znaleźć w czasie wielomianowym. Ich algorytm można postrzegać jako uogólnienie algorytmu Multifit do szeregowania identycznych maszyn.

Kulkarni, Mehta i Taki badają sprawiedliwą alokację MMS z wycenami mieszanymi , tj. gdy występują zarówno dobra, jak i obowiązki. Dowodzą, że:

• Żadne multiplikatywne przybliżenie nie jest możliwe. Rozszerzają przykład Procaccia i Wang, dodając trzy obowiązki domowe o wartości -4 054 999,75. 1 z 3 MMS każdego agenta to 0,25 (każdy pakiet MMS zawiera cztery towary o wartości 4 055 000 i jedno zadanie). Jednak każdy przydział towarów daje co najmniej jednemu agentowi wartość najwyżej 4 054 999 z towarów. Każdemu agentowi musimy przydzielić jedno zadanie; dlatego przynajmniej jeden agent ma wartość ujemną.
• Przedstawiają również warunki, w których obliczenie α-MMS i alokacji optymalnej w sensie Pareto, dla najlepszego możliwego α w konkretnym przypadku, może być wykonane w czasie wielomianowym.

Techniki i algorytmy

Do pierwotnego problemu można zastosować różne normalizacje bez zmiany rozwiązania. Poniżej O jest zbiorem wszystkich obiektów.

skalowanie

Jeżeli dla każdego agenta i wszystkie wyceny są skalowane przez współczynnik ki _; (który może być różny dla różnych agentów), to MMS dla każdego agenta jest skalowany przez ten sam współczynnik dlatego każda alokacja wiadomości MMS w oryginalnej instancji jest alokacją wiadomości MMS w instancji skalowanej. Powszechne jest skalowanie wycen w taki sposób, że MMS każdego agenta wynosi dokładnie 1. Po tym skalowaniu problemy z aproksymacją MMS można określić jako:

• r-frakcja MMS : całkowita wartość O wynosi co najmniej n ; musimy dać każdemu z n agentów pakiet o wartości co najmniej r .
• 1-of-d MMS : całkowita wartość O wynosi co najmniej d ; musimy dać każdemu z n agentów pakiet o wartości co najmniej 1.

Powyższe skalowanie wymaga obliczenia MMS każdego agenta, co jest problemem NP-trudnym ( wielokierunkowe partycjonowanie numerów ). Alternatywnym skalowaniem, które można wykonać szybciej, jest:

• r-fraction MMS : całkowita wartość O wynosi dokładnie n ; MMS to co najwyżej 1; musimy dać każdemu z n agentów pakiet o wartości co najmniej r .
• 1-of-d MMS : całkowita wartość O wynosi dokładnie d ; MMS to co najwyżej 1; musimy dać każdemu z n agentów pakiet o wartości co najmniej 1.

Przydzielanie jednego obiektu

Jeśli usuniemy jeden obiekt o z O . Wtedy dla każdego agenta, 1-z-( n -1) MMS w pozostałym zestawie O \ o jest co najmniej jego 1-z- n MMS w stosunku do oryginalnego zestawu O . Dzieje się tak dlatego, że w oryginalnej partycji MMS n -1 części pozostaje nietkniętych. Załóżmy teraz, że chcemy nadać każdemu agentowi wartość r . Jeśli jakiś obiekt o ₁ jest wart co najmniej r dla co najmniej jednego agenta, to możemy dać o ₁ arbitralnie jednemu takiemu agentowi i przystąpić do przydzielania pozostałych obiektów pozostałym agentom. Dlatego możemy założyć wlog, że:

• r-fraction MMS : wartość każdego obiektu dla wszystkich agentów jest mniejsza niż r .
• 1-of-d MMS : wartość każdego obiektu dla wszystkich agentów jest mniejsza niż 1.

Ta normalizacja działa nawet przy szybkim skalowaniu i przy arbitralnych wycenach monotonicznych (nawet nieaddytywnych).

Wypełnienie torby

Oznacz obiekt, który jest wyceniany przez wszystkich agentów najwyżej na s jako „ s -mały obiekt”. Załóżmy, że wszystkie obiekty są s -małe. Weź pustą torbę i wypełnij ją przedmiotem po obiekcie, aż worek będzie wart co najmniej r dla co najmniej jednego agenta. Następnie daj torbę jednemu z takich agentów arbitralnie. Ponieważ wszystkie obiekty są s -małe, pozostali agenci cenią worek najwyżej r + s ; jeśli ta wartość jest wystarczająco mała, to pozostała wartość jest wystarczająco duża, abyśmy mogli postępować rekurencyjnie. W szczególności napełnianie worków daje następujące rozwiązania:

• 1/2-frakcyjny MMS : weź s = r = 1/2; zauważmy, że dzięki poprzedniej normalizacji możemy założyć, że wszystkie obiekty są 1/2 małe. Na początku jest n agentów, a ich łączna wartość wynosi co najmniej n . Po przydzieleniu worka pozostałe n -1 agentów ocenia pozostałe obiekty na co najmniej n - ( r + s ) = n -1, więc możemy postępować rekurencyjnie.
• 1-z-(2n) MMS : weź s = r = 1; zauważmy, że na podstawie poprzedniej normalizacji możemy założyć, że wszystkie obiekty są 1-małe. Na początku jest n agentów, a ich łączna wartość wynosi co najmniej 2 n . Po przydzieleniu worka pozostałe n -1 agentów ocenia pozostałe obiekty na co najmniej 2 n - ( r + s ) = 2n -2 = 2( n -1), więc możemy postępować rekurencyjnie.

Te algorytmy wypełniania worków działają nawet przy szybkim skalowaniu, więc działają w czasie wielomianowym - nie muszą znać dokładnej wartości MMS. W rzeczywistości oba algorytmy można określić bez wspominania o MMS:

• Każdy agent, dla którego każdy przedmiot jest wart najwyżej 1/(2 n ) całkowitej wartości, otrzymuje co najmniej 1/(2 n ) całkowitej wartości.

Zmodyfikowane wypełnienie worka : Warunek, że wszystkie przedmioty są małe , można złagodzić w następujący sposób. Weź trochę s < r . Oznacz obiekt, który nie jest s -mały (tj. ma wartość co najmniej s przez co najmniej jednego agenta) jako „ s -duży obiekt”. Załóżmy, że co najwyżej n obiektów jest s -dużych. Weź jeden s -duży przedmiot o ₁ , włóż go do torby i wypełnij s-małymi przedmiotami, aż jeden agent wskaże, że jest dla niego wart co najmniej r . Musi istnieć co najmniej jeden taki agent, ponieważ pewien agent i ma wartość o ₁ w pewnych x > s . Dla tego agenta pozostało co najwyżej n -1 s -dużych obiektów. Przy poprzedniej normalizacji obiekty te są nadal r -małe, więc ich łączna wartość dla i wynosi co najwyżej r(n -1) , więc wartość pozostałych s -małych obiektów wynosi co najmniej nr(n -1)- x = r ( n -1)+ rx ≥ rx.

Zamawianie

instancja jest uporządkowana , jeśli wszyscy agenci mają ten sam porządek porządkowy na obiektach, tj. obiekty mogą być ponumerowane vi _o 1 _, ..., om _tak , że dla każdego agenta i , ( o ₁ ) ≥ ... ≥ vi _ja ( o _m ). Intuicyjnie, uporządkowane instancje są najtrudniejsze, ponieważ konflikt między agentami jest największy. Rzeczywiście, negatywna instancja jest uporządkowana - kolejność obiektów jest określona przez macierz ${\ displaystyle T}$ , która jest taka sama dla wszystkich agentów. Można to również udowodnić formalnie. Załóżmy, że mamy algorytm, który znajduje dla każdej uporządkowanej instancji r -frakcyjny przydział wiadomości MMS. Teraz mamy ogólną instancję alokacji przedmiotów P . Rozwiązujemy to w następujący sposób.

1. Skonstruuj uporządkowaną instancję ord (P) w następujący sposób: dla każdego agenta i zdefiniuj v _i ( o _j ) w ord( P ) jako j -tą najwyższą wartość w zbiorze wartości agenta i w P. Wymaga to O( nm log( m )) czas.
2. Znajdź alokację r -fraction MMS ord( A) w ord( P ).
3. Skonstruuj sekwencję wybierania , w której agent, który otrzymał o ₁ w ord (A) wybiera jako pierwszy, agent, który otrzymał o ₂ w ord (A) wybiera jako drugi itd.
4. Pozwól agentom wybierać najlepsze przedmioty zgodnie z kolejnością kompletacji. Niech A będzie wynikową alokacją. W A każdy agent otrzymuje dokładnie taką samą liczbę przedmiotów jak w ord( A ). Co więcej, każdy agent, który otrzymał o _j w ord( A ), otrzymuje jedną ze swoich najwyższych pozycji j w A . Dlatego jego wartość dla każdego przedmiotu, który otrzymał w A, jest co najmniej tak duża, jak jego wartość dla odpowiadającego mu przedmiotu w ord( A ). Dlatego wartość każdego agenta w A jest co najmniej tak wysoka jak w ord( A ). Ponieważ uporządkowanie nie zmienia wartości MMS, nowy przydział A nadal jest r -ułamkiem MMS.

Więc szukając alokacji r -fraction MMS, możemy założyć wlog, że:

• Ranking porządkowy obiektów jest taki sam dla wszystkich agentów.

Alokacja dwóch obiektów

Załóżmy, że znajdujemy dwa obiekty o ₁ i o ₂ , z których jeden agent i ma wartość co najmniej r , a drugi co najwyżej 1. Wtedy te dwa obiekty można przypisać do i . Dla pozostałych agentów, 1-z-( n -1 ) MMS-ów względem pozostałego zestawu jest co najmniej jego 1-z- n MMS-ów względem oryginalnego zestawu O. Dzieje się tak dlatego, że w oryginalnej partycji MMS co najmniej n -2 części pozostają nienaruszone, podczas gdy dwie części, które nie są nienaruszone, można połączyć w jedną część o wartości co najmniej 1. Ta normalizacja działa tylko w przypadku wycen addytywnych.

Ponadto załóżmy, że instancja jest uporządkowana i załóżmy, że usuniemy z O dwa obiekty o _n , o _{n +1} (tj. n -ty i ( n +1)-ty przedmiot o najwyższej wartości). Wtedy dla każdego agenta 1-z-( n -1) MMS w stosunku do pozostałego zestawu jest co najmniej jego 1-z-n MMS w stosunku do oryginalnego zestawu O . Dzieje się tak, ponieważ zgodnie z zasadą przegródki co najmniej jedna część MMS każdego agenta musi zawierać dwa lub więcej obiektów ze zbioru { o ₁ , ..., o _{n +1} }. Tymi przedmiotami można zastąpić przedmioty oddane, _co daje n -1 części o wartości co najmniej 1. Oznacza to, że jeśli przedmioty _on , on +1 _mają wartość co najmniej MMS dla jakiegoś agenta i , możemy przekazać je i i przystąpić do przydzielania pozostałych obiektów pozostałym agentom. Dlatego możemy założyć wlog, że:

• r-fraction MMS : całkowita wartość o _n , o _{n +1} dla wszystkich agentów jest mniejsza niż r . W szczególności wartość o _{n +1} i wszystkich obiektów po niej w kolejności jest mniejsza niż r /2.
• 1-of-d MMS : całkowita wartość od , o _{d +1} dla wszystkich agentów jest mniejsza niż 1. W szczególności wartość o _{d +1} i wszystkich obiektów po niej w kolejności jest mniejsza niż 1/2.

Ta normalizacja działa nawet przy szybkim skalowaniu. Połączenie tego ze zmodyfikowanym napełnianiem worków prowadzi do następującego prostego algorytmu dla MMS o frakcji 2/3.

• Tak długo, jak pojedynczy obiekt jest wart co najmniej 2/3 dla jakiegoś agenta, przydziel go.
• Zamów instancję.
• Dopóki on _je , on ₊₁ są warte co najmniej 2/3 dla jakiegoś agenta, przydziel _.
• Wreszcie istnieje co najwyżej n obiektów o wartości co najmniej 1/3; przydziel je za pomocą zmodyfikowanego napełniania worków.

Gwarancję tego algorytmu można stwierdzić nawet nie wspominając o MMS-ach:

• Każdy agent, dla którego o ₁ jest warte co najwyżej 2/(3 n ) całkowitej wartości, a _on + o _n+1 są warte łącznie co najwyżej 2/(3 n ) całkowitej wartości, otrzymuje co najmniej 2/ (3 n ) całkowitej wartości.

Problemy algorytmiczne

Kilka podstawowych algorytmów związanych z MMS to:

• Obliczanie 1-z -n MMS danego agenta. Jest to problem optymalizacji NP-trudny, ale ma kilka algorytmów aproksymacji; zobacz Wielokierunkowe partycjonowanie numerów i Planowanie identycznych komputerów .
• Decydowanie, czy dana alokacja jest MMS-fair, jest co-NP kompletne dla agentów z wartościowaniami addytywnymi (jest w co-NP, ponieważ możliwe jest udowodnienie w czasie wielomianowym, że dana alokacja nie jest MMS -fair, biorąc pod uwagę podział MMS jednego z agentów, z czego wynika, że ​​wartość MMS agenta jest większa niż jego wartość w danej alokacji).
• Decydowanie, czy dana instancja dopuszcza jakąkolwiek alokację MMS, biorąc pod uwagę wartości MMS wszystkich agentów. Jest w NP, ponieważ można go zweryfikować w czasie wielomianowym, biorąc pod uwagę alokację; jego dokładna złożoność środowiska wykonawczego jest nieznana.
  • Dlatego podjęcie decyzji, czy dana instancja dopuszcza jakąkolwiek alokację MMS, jest w , $potrzebna$ -wielomianowym czasie przy użyciu wyroczni do problemu NP (wyrocznia jest obliczyć MMS agenta). Jednak dokładna złożoność obliczeniowa tego problemu jest nadal nieznana: może to być poziom 2 lub 1, a nawet 0 hierarchia wielomianowa .
• Problem decyzyjny sprawdzania, czy istnieje alokacja udziałów minimaksowych , jest NP-trudny. Oba problemy można przybliżyć za pomocą PTAS , zakładając, że liczba agentów jest stała. Gdy wyceny agentów są binarne lub addytywne i oparte na wyniku Borda , alokacje akcji maximin zawsze można skutecznie znaleźć. Gdy ich wyceny są nieaddytywne, istnieją przypadki, w których r -fraction MMS nie istnieje dla żadnego dodatniego r . Jednak w przypadku klasy symetrycznych narzędzi submodułowych istnieje wąska alokacja MMS wynosząca 1/2 ułamka i można ją przybliżyć z dokładnością do współczynnika 1/4.

Stosunek do innych kryteriów słuszności

Alokacja nazywana jest wolną od zazdrości z wyjątkiem c pozycji (EF c ) dla agenta i , jeśli dla każdego innego agenta j istnieje zbiór co najwyżej c pozycji, które po usunięciu z pakietu j to i reszty nie zazdrości. Alokacja EF0 jest po prostu nazywana wolną od zazdrości . Alokacje EF1 można znaleźć na przykład za pomocą alokacji pozycji okrężnej lub procedury wykresu zazdrości .

Alokacja nazywana jest proporcjonalną-oprócz-c-itemów (PROP* c ) dla agenta i , jeśli istnieje zbiór co najwyżej c pozycji poza wiązką i , który, jeśli usunie się ze zbioru wszystkich pozycji, to i wycenia jego zbierz co najmniej 1/ n reszty. Alokacja PROP*0 nazywana jest po prostu proporcjonalną .

EF0 implikuje PROP*0, a EF1 implikuje PROP*( n -1). Ponadto, dla dowolnej liczby całkowitej c 0, EF c implikuje PROP*(( n -1) c ). Odwrotna implikacja jest prawdziwa, gdy n = 2, ale nie, gdy n > 2.

n -1), a więc także z EF1 wynikają następujące przybliżenia maksymalnego udziału :

• Przybliżenie multiplikatywne: 1/ n - ułamek MMS (1/ n jest ścisłe);
• Przybliżenie porządkowe: 1-of-(2 n -1) MMS (2 n -1 jest ścisłe). Podobnie, dla każdej liczby całkowitej c , PROP* c implikuje 1-z-( c + n ) MMS.
• MMS, gdy funkcja wartości jest binarna. Zachodzi również odwrotna implikacja.

Powyższe implikacje zilustrowano poniżej:

Bez zazdrości	→	Proporcjonalny	→	Maximin-share
↓		↓		↓
			→	1/ n -frakcja MMS
EF1	→	PROP*( n -1)	↔	MMS do wyceny binarnej
↓		↓	→	1-z-(2 n -1) MMS
				↓
EF c	→	PROP*(( n -1) c )	→	1-z-(( n -1) c+n ) MMS

Alokacja nazywana jest pozbawioną zazdrości z wyjątkiem dowolnej pozycji (EF x ) dla agenta i , jeśli dla każdego innego agenta j , dla dowolnej pojedynczej pozycji usuniętej z pakietu j , i nie zazdrości reszty. EFx jest ściśle silniejszy niż EF1. Oznacza to następujące przybliżenia MMS:

• MMS 2/3 frakcji na 2 lub 3 agentów (jest ciasno);
• 4/7 frakcji MMS dla dowolnej liczby agentów (nie wiadomo, czy jest szczelna; obecna górna granica to 8/13).

MMS-y dla grup

Alokacja nazywana jest maksiminowym udziałem parami (PMMS-fair) , jeśli dla każdych dwóch agentów i i j agent i otrzymuje co najmniej swoją 1-z-2 maksimin-udział ograniczony do pozycji otrzymanych przez i oraz j . Nie wiadomo, czy alokacja PMMS zawsze istnieje, ale zawsze istnieje przybliżenie 0,618.

Alokacja nazywana jest maksymalizacją-udziału-grupy (GMMS-fair) , jeśli dla każdej podgrupy agentów wielkości k każdy członek podgrupy otrzymuje swoją 1-z-k maksymin -udziału ograniczoną do pozycji otrzymane przez tę podgrupę.

W przypadku wycen addytywnych różne pojęcia słuszności są powiązane w następujący sposób:

• Wolność od zawiści implikuje uczciwość GMMS;
• Sprawiedliwość GMMS implikuje uczciwość MMS (biorąc podgrupę wielkości n ) i uczciwość PMMS (biorąc podgrupy wielkości 2);
• Uczciwość PMMS implikuje uczciwość 2/3-MMS dla trzech agentów i ogólnie 4/7-uczciwość MMS;
• Uczciwość PMMS implikuje EFX, co implikuje EF1.
• EF1 implikuje 1/2-PMMS, a EFX implikuje 2/3-PMMS. W związku z tym alokację 1/2-PMMS można znaleźć w czasie wielomianowym.
• Uczciwość MMS i uczciwość PMMS nie implikują siebie nawzajem.

Gwarantuje się, że alokacje GMMS istnieją, gdy wyceny agentów są binarne lub identyczne. Przy ogólnych wycenach addytywnych istnieją alokacje 1/2-GMMS, które można znaleźć w czasie wielomianowym.

MMS dla agentów z różnymi uprawnieniami

Kiedy agenci mają różne uprawnienia (określane również jako: nierówne udziały lub asymetryczne prawa ), uczciwość MMS powinna zostać dostosowana w celu zagwarantowania wyższego udziału agentom o wyższych uprawnieniach. Zaproponowano różne adaptacje. Poniżej zakładamy, że uprawnienia są określone przez wektor, gdzie ${\ Displaystyle t = (t_ {1}, \ ldots, t_ {n})}$$displaystyle t_{i}}$ \ reprezentuje uprawnienia agenta ${\ displaystyle i}$ .

Ważona uczciwość MMS

Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin i Seddigin wprowadzają Weighted Maximin Share (WMMS), zdefiniowany przez:

${\ Displaystyle \ nazwa operatora {WMMS} _ {i} ^ {t} (C): = ~ ~ ~ \ max _{(Z_{1},\ldots,Z_{n})\in \operatorname {Partycje} (C,n)}~~~\min _{j\in [n]}~~~{\frac { t_{i}}{t_{j}}}V(Z_{j})=~~~t_{i}\cdot \max _{(Z_{1},\ldots,Z_{n})\in \ nazwa operatora {Partycje} (C,n)}~~~\min _{j\in [n]}~~~{\frac {V(Z_{j})}{t_{j}}}}$

Intuicyjnie optymalny WMMS uzyskuje się poprzez podział, w którym wartość części j jest proporcjonalna do uprawnienia agenta j . Załóżmy na przykład, że wszystkie funkcje wartości są sumami, a wektor uprawnień to t = (1/6, 11/24, 9/24). Wtedy ${\ Displaystyle \ nazwa operatora {WMMS} _ {1} ^ {t} (\ {1,3,5,6,9 \} )=4}$ według partycji ({1,3},{5,6},{9}); jest optymalny, ponieważ wartość każdej części $displaystyle$ równa $24t_ {i}}$ . Przez tę samą partycję ${\ Displaystyle \ nazwa operatora {WMMS} _ {2} ^ {t} = 11}$ i ${\ Displaystyle \ nazwa operatora {WMMS} _ {3} ^ {t }=9}$ . Gdy wszystkie n uprawnień są równe, ${\ Displaystyle \ nazwa operatora {WMMS} _ {i} ^ {t} \ odpowiednik \ nazwa operatora {MMS} _ {i} ^ {1 {\ tekst {-out-of-}} n} }$ .

Alokacja C nazywana jest WMMS-fair dla wektora uprawnień t , jeśli wartość każdego agenta i wynosi co najmniej ${\ Displaystyle \ nazwa operatora {WMMS} _ {i} ^ {t} (C) }$ . Gdy wszystkie n agentów ma identyczne wyceny, alokacja sprawiedliwa WMMS zawsze istnieje z definicji. Ale przy różnych wycenach najlepszym możliwym przybliżeniem multiplikatywnym jest 1/ n . Górna granica jest udowodniona przez następujący przykład z 2 n -1 towarami i n agentów, gdzie ε>0 jest bardzo małą stałą:

Agent	Uprawnienie	Wartość dla pozycji 1, ..., n -1	Wartość dla pozycji nr	Wartość dla pozycji n +1, ..., 2 n -1
1, ..., n -1	ε	ε	1-( n -1) ε	0
N	1-( n -1) ε	[1-( n -1) ε ] / rz	[1-( n -1) ε ] / rz	ε

Wszyscy agenci mają optymalną partycję WMMS: dla „małych” agentów (1, ..., n -1) jest to partycja ({1}, ..., { n -1}, { n }), a dla „duży” agent ( n ) to ({ n +1}, ..., {2 n -1}, {1,..., n }). Dlatego $,$ dla wszystkich agentów ( dla porównania $_$ _ ${\ Displaystyle \ operatorname {MMS} _ {i} ^ {1 {\ tekst {-out-of- }}n}=[1-(n-1)\epsilon ]/n=t_{i}/n}$ dla dużego agenta).

W każdym multiplikatywnym przybliżeniu WMMS wszyscy agenci muszą otrzymać wartość dodatnią. Oznacza to, że mali agenci biorą co najmniej n -1 pozycji 1,..., n , więc co najwyżej jedna taka pozycja pozostaje dla dużego agenta, a jego wartość wynosi w przybliżeniu 1/ n , a nie prawie 1.

1/ n -fraction zawsze istnieje i można ją znaleźć za pomocą alokacji elementów okrężnych . W ograniczonym przypadku, w którym każdy agent i wycenia każde dobro najwyżej o ${\ displaystyle \ operatorname {WMMS} _ {i} ^ {t}}$ , istnieje sprawiedliwa alokacja WMMS o wartości 1/2 ułamka i może można znaleźć za pomocą algorytmu podobnego do napełniania worków: wyceny każdego agenta i są mnożone przez ${\ Displaystyle t_ {i} / \ nazwa operatora {WMMS} _ {i} ^ {t}}$ ; aw każdej iteracji przedmiot $,$ agentowi (agentowi o wartości mniejszej niż który ceni bardzo. Algorytm ten przydziela każdemu agentowi co najmniej ${\ displaystyle \ operatorname {WMMS} _ {i} ^ {t}/2}$ ja co najwyżej ${\ displaystyle \ operatorname {WMMS} _ { i}^{t}}$ . W praktyce przydział zgodny z WMMS prawie zawsze istnieje.

Porządkowa uczciwość MMS

Babaioff, Nisan i Talgam-Cohen przedstawiają naturalne rozszerzenie przybliżenia porządkowego MMS na agentów o różnych uprawnieniach. Dla dowolnych dwóch liczb całkowitych $zdefiniuj$ i funkcję wartości V ,

${\ Displaystyle \ operatorname {MMS} _ {V }^{l{\text{-out-of-}}d}(C):=~~~\max _{P\in \operatorname {Partitions} (C,d)}~~~\min _{ Z\in \operatorname {Uniony} (P,l)}~~~V(Z)}$

$C$ maksimum dotyczy wszystkich podziałów na rozłączne podzbiory $,$ a minimum dotyczy wszystkich związków części Na przykład ${\ Displaystyle \ operatorname {MMS} _ {V} ^ {2 {\ tekst {-out- z-}}3}(\{1,3,5,6,9\})=15}$ według partycji ({1,6},{3,5},{9}). Teraz Ordinal Maximin Share (OMMS) jest zdefiniowany przez:

${\ Displaystyle \ operatorname {OMMS} _ {i} ^ {t} ( C):=~~~\max _{l,d:~l/d\leq t_{i}}\operatorname {MMS} _{i}^{l{\text{-out-of-}}d }(C)}$

Na przykład, jeśli uprawnienie agenta i jest dowolną liczbą rzeczywistą co najmniej tak dużą jak 2/3, to jest on uprawniony do co najmniej 2-z-3 MMS C. $spełniających$ istnieje nieskończenie wiele par $skończenie$ tylko z nich (nie sugerowane przez innych), więc możliwe jest obliczenie OMMS w skończonym czasie. Alokacja Z ₁ ,..., Z _n nazywa się OMMS-fair dla wektora uprawnień w , jeśli wartość każdego agenta i wynosi co najmniej ${\ Displaystyle \ nazwa operatora {OMMS} _ {i} ^ {t} (C)}$ .

OMMS może być wyższy lub niższy niż WMMS, w zależności od wartości:

• Jako przykład, w którym WMMS jest wyższy, załóżmy, że C = {40, 60} i t = (0,4, 0,6) . Wtedy wyraźnie WMMS ₁ = 40 i WMMS ₂ = 60, więc jedyny sprawiedliwy przydział WMMS daje 40 do 1 i 60 do 2. Jednak OMMS ₁ = 0, ponieważ ułamki spełniające ${\ displaystyle l / d \ równoważnik 0,4}$ to 1/3, 2/5, 3/7 itd. I we wszystkich przypadkach w dowolnym podziale do $co$ jest najmniej ${\ displaystyle l}$ puste podzbiory. Również OMMS _{2 = 40} $3/5$ ponieważ ułamki spełniające to 4/7 itd. I we wszystkich przypadkach , w dowolnym podziale C na $podzbiory najmniej wartościowe$ podzbiory nie zawierają 60. Dlatego alokacja sprawiedliwa OMMS może dać 40 do 2 i $1$ , lub nie dawać nic 1, co wydaje się niesprawiedliwe.
• Jako przykład, w którym OMMS jest wyższy, załóżmy, że C = {40, 60} i t = (0,2, 0,2, 0,6) . Wtedy WMMS _i = 0 dla wszystkich i , ponieważ w dowolnej 3-partycji C co najmniej jeden pakiet jest pusty. Zatem kryterium uczciwości WMMS jest bezużyteczne. Podobnie, OMMS ₁ = OMMS ₂ = 0. Jednak OMMS ₃ = 40 przez parę ${\ Displaystyle l/d = 1/2}$ i partycja ({40},{60}), więc OMMS-fairness wymaga przekazania co najmniej jednego elementu agentowi 3, co wydaje się sprawiedliwsze.

Uczciwość AnyPrice-Share

Babaioff, Ezra i Feige wprowadzili trzecie kryterium uczciwości, które nazwali AnyPrice Share (APS) . Definiują to na dwa równoważne sposoby; jednym z nich jest ewidentne umocnienie akcji maximina. Zamiast dzielić pozycje na d rozłącznych wiązek, agent może wybrać dowolną kolekcję wiązek, które mogą się nakładać. Ale agent musi następnie przypisać wagę do każdego pakietu tak, aby suma wag wynosiła co najmniej 1, a każdy przedmiot należy do pakietów, których łączna waga jest co najwyżej uprawniona do agenta. APS to wartość najmniej wartościowego pakietu o dodatniej masie. Formalnie:

${\ Displaystyle \ nazwa operatora {APS} _ {V} ^ {t} (C): = ~ ~~\max _{P\in \operatorname {AllowedBundleSets} (C,t_{i})}~~~\min _{Z\in P}~~~V(Z)}$

gdzie maksimum dotyczy wszystkich zestawów wiązek, tak że dla pewnego przypisania wag wiązkom łączna waga wszystkich wiązek wynosi co najmniej 1, a łączna waga każdej pozycji wynosi co najwyżej t _i . Istnieje algorytm czasu wielomianowego, który gwarantuje każdemu agentowi co najmniej 3/5 jego APS.

APS jest zawsze co najmniej tak wysoki jak OMMS: biorąc pod uwagę optymalny podział l -out-of- d , przy l/d ≤ t _i , można przypisać wagę 1/ d do sumy części 1, .. ., l , suma części 2,..., l +1 i tak dalej (w sposób cykliczny), tak że każda część zawiera się dokładnie w l sumach. Dlatego każdy przedmiot należy do wiązek, których łączna waga wynosi co najwyżej l / d , czyli co najwyżej t _i . Agent ma zagwarantowaną najmniej wartościową taką paczkę, czyli co najmniej l -z- d MMS-ów.

W niektórych przypadkach APS jest ściśle wyższy niż OMMS. Oto dwa przykłady:

• Prosty przykład z różnymi uprawnieniami: niech C = {2,1,1,1,0} i t _i = 2/5 . OMMS wynosi co najwyżej 1 (wystarczy sprawdzić l/d w {1/3, 2/5}). Ale APS wynosi 2 według następujących wag: 0,4*{2}, 0,2*{1,1}, 0,2*{1,1}, 0,2*{1,1}. Zauważ, że suma wag wynosi 1. 2 pojawia się w jednym zestawie o wadze 0,4, podczas gdy każda z 1 pojawia się w dwóch zestawach o wadze 0,2, 0,2.
• Bardziej złożony przykład z równymi uprawnieniami: niech C = {5, 5, 5, 7, 7, 7, 11, 17, 23, 23, 23, 31, 31, 31, 65} i t _i = 1/3 . OMMS równa się 1-z-3 MMS i wynosi co najwyżej 96; można to zweryfikować, sprawdzając wszystkie 3 partycje. APS wynosi 97, ponieważ możliwe jest skonstruowanie 6 zestawów po 5 przedmiotów każdy, o łącznej wartości 97, tak aby każdy przedmiot pojawił się w dokładnie dwóch zestawach. Następnie każdemu wiązce można przypisać wagę 1/6.
  • Ten przykład pokazuje również, że alokacja APS może nie istnieć nawet dla 3 agentów o identycznych wycenach i równych uprawnieniach. Kontrastuje to z OMMS, który zawsze istnieje z identycznymi wycenami i równymi uprawnieniami, oraz WMMS, który zawsze istnieje z identycznymi wycenami i arbitralnymi uprawnieniami.

APS może być wyższy lub niższy niż WMMS; przykłady są takie same, jak w przypadku OMMS vs WMMS:

• WMMS jest wyższy: C = {40, 60} i t = (0,4, 0,6) . Następnie WMMS ₁ = 40 i WMMS ₂ = 60. Ale APS ₁ = 0, ponieważ każdy przedmiot musi mieć wagę co najwyżej 0,4, więc pusta paczka musi mieć wagę co najmniej 0,2. Ponadto APS ₂ = 40, ponieważ każdy przedmiot musi mieć wagę co najwyżej 0,6, więc {40} i pusta paczka muszą mieć łączną wagę co najmniej 0,4.
• APS jest wyższy: C = {40, 60} i t = (0,2, 0,2, 0,6) . Wtedy WMMS _i = 0 dla wszystkich i . Podobnie APS ₁ = APS ₂ = 0 jak powyżej. Jednak APS ₃ =40 np. według wag 0,5*{40}, 0,5*{60}.

Zobacz też

• Problem zakrywania pojemników i problem pakowania pojemników - dwa dobrze zbadane problemy optymalizacyjne, które można postrzegać jako specjalne przypadki odpowiednio alokacji niepodzielnych dóbr i niepodzielnych obowiązków domowych . Wiele technik stosowanych w przypadku tych problemów jest również przydatnych w przypadku alokacji pozycji maximin share.
• Egalitarna alokacja przedmiotów - często nazywana bardzo podobną nazwą „przydział pozycji max-min”, ale jej definicja i alokacje, które daje, są bardzo różne od sprawiedliwego podziału maximin.