Честное деление двумерного торта

Меня интересуют процедуры справедливого разделения земли (то есть разделение без зависти или, по крайней мере, пропорциональное разделение).

В отличие от хорошо изученной проблемы разделения тортов, разделение земель является двумерным, то есть предпочтения пользователей могут варьироваться как по горизонтали, так и по вертикали. Поэтому нецелесообразно ограничивать алгоритм параллельными вырезами.

Единственная ссылка, которую я нашел до сих пор, - Картик Айер и Майкл Ханс, 2007 . Они говорят, что «мы до сих пор не сталкивались с какими-либо конструктивными (алгоритмическими) решениями общей проблемы разделения земли. Во всех работах были предложены экзистенциальные решения квалифицированных версий проблемы».

Сами они доказывают алгоритм O (n ^ 2) для пропорционального разделения земель с некоторыми ограничениями (например, каждый из n агентов должен пометить n прямоугольных областей с полезностью 1 / n, и если прямоугольники не слишком сильно перекрывают друг друга, алгоритм гарантирует, что каждый агент получает один из своих прямоугольников).

Знаете ли вы какие-либо новые ссылки на эту проблему? Меня особенно интересуют практические алгоритмы, и они могут быть приблизительными.

У авторов, которых вы цитируете, есть еще одна статья на эту тему .

Будете ли вы удовлетворены моделью, которая предполагает, что свойства выделяемых поверхностей могут быть обобщены произвольно большим, но конечным набором одномерных параметров (скажем, длина, глубина, самая северная точка, самая восточная точка, ... действительно как сколько хочешь но конечно)?

Если это вас устраивает, и вы согласны с предположением, что у людей есть предпочтения над поверхностями, как описано значениями этих параметров, вы можете найти полезные сведения в теории справедливого распределения комплектов нескольких товаров. Отличное (и бесплатное) введение - «Правила справедливого распределения» Уильяма Томсона .

Конечно, когда размеры представляют параметры, описывающие формы, которые будут выделены, у вас, скорее всего, будут необычные предпочтения, с которыми трудно работать и которые не вписываются в существующие результаты. Возможно, стоит попробовать ...

Я полагаю, вы могли бы решить проблему, уменьшив размерность проблемы. Например, вы можете разделить землю на отдельные области (вручную или с помощью подходящего алгоритма). Затем вы можете использовать любой дискретный одномерный алгоритм, например, метод Sealed bid, описанный в http://www.colorado.edu/education/DMP/fair_division.html .

Я не нашел подходящего ответа, поэтому мне пришлось написать его самому . Это была первая часть моей кандидатской диссертации. Тезис. В этой области еще много открытых вопросов.