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.