Ostatni zmniejszacz

Ostatnia procedura zmniejszania to procedura uczciwego krojenia ciasta . Obejmuje pewien heterogeniczny i podzielny zasób, taki jak tort urodzinowy, oraz n partnerów o różnych preferencjach dotyczących różnych części tortu. Pozwala n osobom na osiągnięcie proporcjonalnego podziału , tj. podzielenie tortu między siebie w taki sposób, aby każda osoba otrzymała kawałek o wartości co najmniej 1/ n całkowitej wartości według własnej subiektywnej oceny. Na przykład, jeśli Alicja wycenia cały tort na 100 USD i jest 5 partnerów, Alicja może otrzymać kawałek, który ocenia na co najmniej 20 USD, niezależnie od tego, co myślą lub robią pozostali partnerzy.

Historia

Podczas II wojny światowej polsko-żydowski matematyk Hugo Steinhaus , który ukrywał się przed nazistami, zajmował się kwestią sprawiedliwego podziału zasobów. Zainspirowany metodą dzielenia i wybierania dzielenia tortu między dwóch braci, poprosił swoich uczniów Stefana Banacha i Bronisława Knastera o znalezienie procedury, która zadziała dla dowolnej liczby osób, i opublikował swoje rozwiązanie.

Ta publikacja zapoczątkowała nowy temat badawczy, który jest obecnie przedmiotem badań wielu naukowców z różnych dyscyplin; zobacz sprawiedliwy podział .

Opis

Oto opis protokołu podziału słowami autora:

„Partnerzy ustawieni A, B, C,… N, A wycinają z tortu dowolną część. B ma teraz prawo, ale nie jest zobowiązany, do zmniejszenia odciętego kawałka. Cokolwiek zrobi, C ma prawo (bez obowiązku) zmniejszania jeszcze pomniejszonego (lub nie pomniejszonego) wycinka i tak dalej aż do N. Reguła zobowiązuje „ostatniego zmniejszającego” do wzięcia za swoją część wycinka, którego dotknął jako ostatni. usunięte, pozostałe n -1 osoby rozpoczynają tę samą grę z resztą tortu. Po zmniejszeniu liczby uczestników do dwóch, stosują klasyczną zasadę dzielenia pozostałej części na pół.

Każdy partner ma metodę, która gwarantuje, że otrzyma wycinek o wartości co najmniej 1/ n . Metoda jest następująca: zawsze wycinaj bieżący wycinek tak, aby reszta miała dla ciebie wartość 1/ n . Są dwie możliwości: albo ty otrzymujesz kawałek, który wyciąłeś, albo inna osoba otrzymuje mniejszy kawałek, którego wartość dla ciebie jest mniejsza niż 1/ n . W tym drugim przypadku pozostaje n −1 partnerów, a wartość pozostałego tortu jest większa niż ( n −1)/ n . Stąd przez indukcję można udowodnić, że otrzymana wartość wynosi co najmniej 1/ rz .

Zdegenerowany przypadek wspólnej funkcji preferencji

Algorytm upraszcza zdegenerowany przypadek, w którym wszyscy partnerzy mają tę samą funkcję preferencji, ponieważ partner, który optymalnie pierwszy przecina plasterek, będzie również jego ostatnim zmniejszającym. Równoważnie ^{[ potrzebne źródło ]} każdy partner 1, 2, ..., n −1 po kolei odcina kawałek pozostałego ciasta. Następnie w odwrotnej kolejności każdy partner n , n −1, ..., 1 z kolei wybiera wycinek, który nie został jeszcze zajęty. Pierwszy partner, który odciął plasterek inny niż o wartości 1/ n , byłby zazdrosny o innego partnera, który skończył z więcej niż oni.

Analiza

Protokół ostatniego zmniejszania jest dyskretny i można go odtwarzać na zmianę. W najgorszym przypadku potrzeba akcji $n \times (n-1) / 2 = O (n 2) : jedna akcja na gracza na turę.$

Jednak większość z tych akcji O ( n ^{2 ) nie jest faktycznymi cięciami, tj. Alicja może zaznaczyć swój żądany kawałek na papierze i poprosić innych graczy o zmniejszenie ich na tym samym papierze itp.;} tylko „ostatni zmniejszacz” musi faktycznie pokroić ciasto. Potrzebnych jest więc tylko n −1 cięć.

Procedura jest bardzo liberalna w zakresie cięć. nacięcia wykonane przez partnerów mogą mieć dowolny kształt; można je nawet rozłączyć. Z drugiej strony istnieje możliwość ograniczenia cięć w celu zagwarantowania, że elementy będą miały ładny kształt. W szczególności:

Jeśli oryginalne ciasto jest połączone, można zagwarantować, że każdy kawałek jest połączony (sąsiadujący).
Jeśli oryginalne ciasto jest zbiorem wypukłym , to można zagwarantować, że każdy kawałek jest wypukły.
Jeśli oryginalne ciasto jest prostokątem , można zagwarantować, że każdy kawałek jest prostokątem.
Jeśli oryginalne ciasto jest trójkątem , można zagwarantować, że każdy kawałek jest trójkątem.

Wersja ciągła

Wersję tego protokołu działającą w czasie ciągłym można wykonać przy użyciu procedury Dubins-Spanier Moving-knife . Był to pierwszy przykład ciągłej procedury w podziale sprawiedliwym. Nóż przesuwa się po cieście od lewej strony do prawej. Każdy gracz może powiedzieć stop, kiedy pomyśli. ${\ displaystyle 1/n}$ ciasta znajduje się na lewo od noża, ciasto jest krojone, a gracz, który mówił, otrzymuje ten kawałek. Powtórz z pozostałym ciastem i graczami, ostatni gracz otrzymuje resztę ciasta. Podobnie jak w przypadku ostatniej procedury zmniejszania, można jej użyć do pokrojenia ciasta na przylegające części dla każdego gracza.

Wersja pozbawiona zazdrości

Kiedy jest 3 lub więcej partnerów, podział uzyskany przez protokół ostatniego spadku nie zawsze jest wolny od zazdrości . Załóżmy na przykład, że pierwsza partnerka Alicja otrzymuje figurę (którą ocenia jako 1/3 całości). Następnie pozostali dwaj partnerzy Bob i Charlie dzielą resztę w sposób, który ich zdaniem jest sprawiedliwy, ale zdaniem Alicji udział Boba jest wart 2/3, a udział Charliego jest wart 0. Wtedy Alicja zazdrości Bobowi.

Prostym rozwiązaniem jest umożliwienie ponownego wejścia . Oznacza to, że partner, który wygrał figurę, będąc ostatnim zmniejszającym, nie musi opuszczać gry, ale może raczej zostać i uczestniczyć w dalszych krokach. Jeśli ponownie wygra, musi wypuścić swój obecny pionek i wraca on na tor. Aby mieć pewność, że protokół się zakończy, wybieramy pewną stałą $1$ dodajemy regułę, która pozwala każdemu partnerowi na ponowne wejście co najwyżej $\ displaystyle 1/\ epsilon}$ .

W wersji reentrant każdy partner ma metodę, która gwarantuje, że otrzyma wycinek o wartości co najmniej największej wartości minus ${\ displaystyle \ epsilon}$ . Metoda jest następująca: zawsze wycinaj bieżący wycinek tak, aby reszta miała wartość $.$ twoją bieżącą wartość Gwarantuje to, że Twoja wartość rośnie za każdym razem, gdy wygrywasz, a jeśli nie wygrywasz - wartość zwycięzcy wynosi co najwyżej $ϵ$ $epsilon}$ więcej niż twoja własna wartość. Zatem poziom zazdrości jest co najwyżej $addytywna$ ).

Czas działania wynosi najwyżej ${\ Displaystyle n ^ {2}/\ epsilon}$ $,$ ponieważ jest co najwyżej na każdym kroku wysyłamy zapytanie do każdego z ${\ displaystyle n}$ .

Wadą wariantu pozbawionego przybliżonej zazdrości jest to, że kawałki niekoniecznie są połączone, ponieważ kawałki są stale zwracane do ciasta i ponownie dzielone. Zobacz wycinanie ciasta bez zazdrości#Połączone elementy, aby poznać inne rozwiązania tego problemu.

Ulepszenia

Procedura ostatniego zmniejszacza została później ulepszona na wiele sposobów. Aby uzyskać szczegółowe informacje, zobacz podział proporcjonalny .