Problem podziału gruntów Hilla-Becka

Następujący wariant problemu krojenia tortu został wprowadzony przez Teda Hilla w 1983 roku.

Do n krajów przylega terytorium D. Każdy kraj inaczej ocenia różne podzbiory D. Kraje chciałyby sprawiedliwie podzielić między siebie D , gdzie „sprawiedliwy” oznacza podział proporcjonalny . Dodatkowo udział przydzielony każdemu krajowi musi być połączony i sąsiadować z tym krajem . To ograniczenie geograficzne odróżnia ten problem od klasycznego krojenia tortu .

Formalnie Ci ∪ D i każdy kraj Ci Ci musi otrzymać rozłączny kawałek D , oznaczony D i , tak aby część granicy między i D zawierała się we wnętrzu .

Niemożliwość i możliwość

Istnieją przypadki, w których problemu nie można rozwiązać:

  1. Jeśli istnieje jeden punkt, któremu dwa kraje przypisują całą swoją wartość (np. święte miejsce), to oczywiście terytorium nie może być podzielone proporcjonalnie. Aby zapobiec takim sytuacjom, zakładamy, że wszystkie kraje przypisują wszystkim punktom osobliwym wartość 0.
  2. Jeśli D jest kwadratem, do 4 boków kwadratu przylegają 4 kraje, a każdy kraj przypisuje całą swoją wartość granicy po przeciwnej stronie, to każdy przydział, który łączy, powiedzmy, kraj północny z jego pożądaną granicą południową uniemożliwi połączenie wschodniego kraju z jego pożądaną zachodnią granicą (o ile będziemy w płaszczyźnie dwuwymiarowej). Aby zapobiec takim sytuacjom, zakładamy, że wszystkie kraje przypisują granicy D wartość 0 .

W 1983 roku Hill udowodnił, że jeśli każdy pojedynczy punkt w D ma wartość 0 dla wszystkich krajów, a granica D ma wartość 0 dla wszystkich krajów, to istnieje podział proporcjonalny z ograniczeniem sąsiedztwa. Jego dowód był tylko egzystencjalny – nie opisano żadnego algorytmu.

Algorytm

4 lata później Anatole Beck opisał protokół osiągnięcia takiego podziału. Zasadniczo protokół jest rozwinięciem ostatniego zmniejszania . Pozwala krajom licytować części D , daje najniższą ofertę oferentowi i dzieli pozostałą część między pozostałe n − 1 kraje. Potrzebne są pewne odmiany, aby zagwarantować, że ograniczenie sąsiedztwa jest spełnione.

Po prostu połączone terytorium

Gdy D jest po prostu spójny , używany jest następujący algorytm.

1. Znajdź odwzorowanie Riemanna h , które odwzorowuje D na dysk jednostkowy , tak że dla wszystkich krajów wartość każdego okręgu o środku w początku wynosi 0, a wartość każdego promienia od początku wynosi 0 (istnienie takiego h jest udowodnione argumentem liczącym).

2. Poproś każdy kraj o narysowanie na mapie dysku jednostek h ( D ) dysku o wartości 1/ n , którego środek znajduje się na początku układu współrzędnych . Jest to możliwe dzięki warunkowi, że wartość wszystkich okręgów wyśrodkowanych w początku układu współrzędnych wynosi 0.

3. Znajdź dysk D 1 o najmniejszym promieniu, r 1 .

Istnieją dwa przypadki.

Pojedynczy zwycięzca

4. Jeśli D 1 wylosował tylko jeden kraj, powiedzmy Ci , to daj ten krążek Ci . Jego wartość dla innych krajów jest ściśle mniejsza niż 1/ n , więc możemy dać C i mały dodatkowy element łączący go z przydzielonym mu dyskiem.

narysuj sektor łączący D 1 z obrazem granicy między Ci i D . Niech każdy kraj (inny niż C i ) obetnie ten sektor tak, aby wszystkie kraje oceniły połączenie dysku i sektora najwyżej na 1/ n . Jest to możliwe dzięki warunkowi, że wartość wszystkich promieni od początku układu współrzędnych wynosi 0. Przydziel C i sumę D 1 i przyciętego sektora.

Reszta jest po prostu połączona i ma wartość co najmniej ( n - 1)/ n dla pozostałych n - 1 krajów, więc podział może przebiegać rekurencyjnie w kroku 1.

Wielu zwycięzców

Jeśli D 1 zostało wylosowane przez k > 1 krajów, to potrzebne są bardziej wyrafinowane aukcje, aby znaleźć kraj, któremu możemy dać dysk i łączący go sektor.

5. wybierz dowolny zwycięski kraj i nazwij go rozgrywającym , C 1 . Niech doda sektor łączący D 1 z jego obecnym terytorium i niech inne kraje obetną ten sektor tak, aby:

  • Dla każdego kraju, który nie wygrywa, wartość D 1 plus przycięty sektor wynosi co najwyżej 1/ n (jest to możliwe, ponieważ wartość D 1 jest dla nich mniejsza niż 1/ n ).
  • Dla każdego zwycięskiego kraju wartość samego przyciętego sektora jest mniejsza niż 1/ n .

6. Niech każdy ze zwycięskich krajów zalicytuje nowy promień r (mniejszy niż jego pierwsza oferta), tak aby wartość przyciętego sektora plus dysk o promieniu r wynosiła dokładnie 1/ n . Wybierz najmniejszy taki krążek, D 2 . Znowu mamy dwa przypadki:

Jeśli C 1 jest jednym z krajów licytujących D 2 , po prostu podaj mu D 2 (który jest nieco mniejszy niż pierwotny D 1 ) i sektor łączący. C 1 zgodziło się, że wartość wynosi 1/ n , a inne kraje zgodziły się, że jest to co najwyżej 1/ n , więc możemy przejść rekurencyjnie do kroku 1.

W przeciwnym razie C1 zgadza się, że całkowita wartość D2 plus sektor łączący jest mniejsza niż 1 / n . Wszyscy, którzy nie wygrali, również muszą się na to zgodzić, ponieważ D 2 jest mniejsze niż D 1 . Tak więc C 1 i wszystkie inne kraje, które się na to zgodzą, są usuwane z zestawu zwycięzców.

7. Spośród pozostałych zwycięzców wybierz nowego rozgrywającego C 2 . Niech doda kolejny sektor łączący D 2 z jego obecnym terytorium i niech inne kraje przycinają ten sektor, jak w kroku 5.

Zauważ, że teraz D 2 jest połączone z dwoma różnymi terytoriami – C 1 i C 2 . Jest to problem, ponieważ sprawia, że ​​pozostałe terytorium jest odłączone. Aby rozwiązać ten problem, C 2 może zająć inny sektor, tym razem o długości mniejszej niż 1, aby nie zaszkodzić łączności. Ten trzeci sektor jest ponownie przycinany przez wszystkie kraje, tak jak w kroku 5. W zamian C 2 musi zrezygnować z części sektora łączącego D 2 z C 1 , którego wartość jest równa wartości otrzymanego trzeciego sektora.

Alokacja kandydująca C2 zawiera teraz następujące części : D2 , pojedynczy sektor o długości 1 łączący D2 z C2 oraz dwa krótkie sektory , które nie sięgają granicy D. Wartość tej konstrukcji dla C 2 wynosi 1/ n , jej wartość dla przegranych jest mniejsza niż 1/ n , a jej wartość dla pozostałych zwycięzców wynosi co najwyżej 1/ n .

Proces ten jest kontynuowany z pozostałymi zwycięzcami, aż pozostanie tylko jeden zwycięzca.

Skończenie połączone terytorium

Jeśli terytorium D jest k -połączone ze skończonym k , to dzielenie może przebiegać przez indukcję względem k .

Gdy k = 1, D jest prosto spójny i można go podzielić za pomocą protokołu z poprzedniej sekcji.

W przeciwnym razie ( k > 1 ) zaznaczmy zewnętrzną granicę D przez B 1 , a wewnętrzne przez B 2 , ..., B k .

Znajdź linię L łączącą zewnętrzną granicę B 1 z wewnętrzną granicą B k , tak aby wszystkie kraje miały wartość L jako 0. Jest to możliwe dzięki następującemu argumentowi liczącemu. Istnieje niepoliczalna nieskończoność parami rozłącznych prostych łączących B 1 i B k i zawartych w D . Ale miara D jest skończona, więc liczba prostych o dodatniej mierze musi być skończona.

Zbiór D \ L jest ( k − 1) -spójny. Podziel go rekurencyjnie, a następnie przypisz L arbitralnie do dowolnego sąsiadującego z nim kraju. Nie wpływa to na sprawiedliwość alokacji, ponieważ wartość L wynosi 0 dla wszystkich krajów.

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Hill–Beck_land_division_problem&oldid=1033881845 ”