Sprawiedliwy podział dwuwymiarowego ciasta

10

Interesują mnie procedury sprawiedliwego podziału gruntów (tj. Podział wolny od zazdrości lub podział przynajmniej proporcjonalny).

W przeciwieństwie do dobrze zbadanego problemu podziału ciasta, podział gruntu jest dwuwymiarowy, tzn. Preferencje użytkowników mogą się różnić zarówno w poziomie, jak i w pionie. Dlatego nie jest praktyczne ograniczenie algorytmu do równoległych cięć.

Jedyne odniesienie, które do tej pory znalazłem, to Karthik Iyer i Michael Huhns, 2007 . Mówią, że „do tej pory nie natrafiliśmy na żadne konstruktywne (algorytmiczne) rozwiązania ogólnego problemu podziału gruntów. Wszystkie artykuły oferowały rozwiązania egzystencjalne dla kwalifikowanych wersji problemu”.

Sami dowodzą, że algorytm O (n ^ 2) dla proporcjonalnego podziału gruntu, z pewnymi ograniczeniami (np. Każdy z n czynników musi oznaczyć n prostokątnych regionów za pomocą użyteczności 1 / n, a jeśli prostokąty nie nakładają się zbytnio, algorytm gwarantuje, że każdy agent otrzyma jeden ze swoich prostokątów).

Czy znasz jakieś nowsze referencje dotyczące tego problemu? Interesują mnie w szczególności algorytmy praktyczne, które mogą być przybliżone.

Erel Segal-Halevi
źródło
Czy czytałeś artykuł z Wikipedii na temat sprawiedliwego podziału ?
Pål GD
2
Tak, wszystkie odniesienia dotyczą preferencji 1-wymiarowych.
Erel Segal-Halevi

Odpowiedzi:

3

Przytoczeni autorzy mają kolejny artykuł na ten temat .

Czy byłbyś zadowolony z modelu, który zakłada, że ​​właściwości powierzchni, które mają być przydzielone, można podsumować za pomocą dowolnego dużego, ale skończonego zestawu parametrów jednowymiarowych (powiedzmy długość, głębokość, punkt najbardziej na północ, punkt na wschód ... naprawdę tak ile chcesz, ale skończone)?

Jeśli jest to dla Ciebie satysfakcjonujące i zgadzasz się z założeniem, że ludzie mają preferencje względem powierzchni zgodnie z wartościami tych parametrów, możesz znaleźć przydatne spostrzeżenia w teorii sprawiedliwego przydziału pakietów wielu towarów. Świetnym (i bezpłatnym) wstępem są „Zasady uczciwej alokacji” Williama Thomsona .

Oczywiście, gdy wymiary reprezentują parametry opisujące kształty, które mają zostać przydzielone, prawdopodobnie będziesz mieć nietypowe preferencje, z którymi trudno jest pracować i nie pasują do istniejących wyników. Może warto spróbować ...

Martin Van der Linden
źródło
2

Przypuszczam, że można rozwiązać ten problem, zmniejszając wymiar problemu. Na przykład możesz podzielić ziemię na odrębne obszary (ręcznie lub przy użyciu odpowiedniego algorytmu). Następnie możesz użyć dowolnego dyskretnego jednowymiarowego algorytmu, takiego jak metoda Sealed bid opisana w http://www.colorado.edu/education/DMP/fair_division.html .

Sami Sieranoja
źródło
2

Nie znalazłem odpowiedniej odpowiedzi, więc sam musiałem ją napisać . To była pierwsza część mojego doktoratu. Praca dyplomowa. W tej dziedzinie wciąż jest wiele otwartych pytań.

Erel Segal-Halevi
źródło