Разрезание торта без зависти

Разрезание торта без зависти — это своего рода честное разрезание торта . Это разделение гетерогенного ресурса («пирога»), которое удовлетворяет критерию отсутствия зависти , а именно, что каждый партнер чувствует, что выделенная ему доля по крайней мере так же хороша, как и любая другая доля, согласно его собственной субъективной оценке.

Нерешенная задача в информатике :

Какова сложность выполнения процедуры разрезания торта без зависти?

(еще нерешенные проблемы по информатике)

Когда есть только два партнера, проблема проста и была решена в древности с помощью протокола «разделяй и выбирай» . Когда партнеров трое и более, задача становится гораздо сложнее.

Были изучены два основных варианта проблемы:

• Связные части , например, если торт представляет собой одномерный интервал, каждый партнер должен получить один подинтервал. Если есть $n$ партнеры, только $n-1$ нужны разрезы.
• Общие части , например, если торт представляет собой одномерный интервал, каждый партнер может получить объединение непересекающихся подинтервалов.

Краткая история

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

Более сильный критерий отсутствия зависти был введен в задачу о разрезании торта Георгием Гамовым и Марвином Стерном в 1950-х годах.

Процедура для трех партнеров и общих фигур была найдена в 1960 году. Процедура для трех партнеров и связных фигур была найдена только в 1980 году.

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

Две нижние оценки сложности отсутствия зависти во время выполнения были опубликованы в 2000-х годах.

• Для общих частей нижняя граница равна Ω( n ² ) .
• Для связанных частей нижняя граница равна бесконечности — доказуемо не существует конечного протокола для трех и более партнеров.

несколько процедур аппроксимации и процедур для особых случаев В 2010-х годах было опубликовано . Вопрос о том, существуют ли ограниченные по времени процедуры для общих произведений, долгое время оставался открытым. Проблема была наконец решена в 2016 году. Харис Азиз и Саймон Маккензи представили дискретный протокол без зависти, который требует не более $n^{n^{n^{n^{n^{n}}}}}$ или $n\uparrow \uparrow 6$ запросы. Между нижней границей и процедурой по-прежнему существует очень большой разрыв. По состоянию на февраль 2024 года точная сложность выполнения программы «Свобода от зависти» все еще неизвестна.

Для случая соединенных кусков было отмечено, что результат твердости предполагает, что весь пирог должен быть разделен. Если это требование заменить более слабым требованием о том, чтобы каждый партнер получал пропорциональную стоимость (не менее 1/ n от общей стоимости торта по его собственной оценке), то была известна ограниченная процедура для трех партнеров , но она осталась открытой. Проблема в том, существуют ли ограниченные по времени процедуры для четырех или более партнеров.

Соединённые части

Доказательство существования

Деление без зависти для n агентов со связными частями всегда существует при следующих мягких предположениях:

• Ни один агент не предпочитает пустую фигуру непустой.
• Предпочтения агентов непрерывны.

Обратите внимание, что не требуется , чтобы предпочтения агентов были представлены аддитивной функцией .

Основное понятие в доказательстве — симплекс разбиений . Предположим, что торт — это интервал [0,1]. Каждый раздел со связанными частями может быть однозначно представлен n -1 числами в [0,1], которые представляют места разрезов. Объединение всех разбиений является симплексом.

В каждом разделе у каждого агента есть одна или несколько частей, которые они слабо предпочитают. Например, для раздела, представленного «0.3,0.5», один агент может предпочесть кусок №1 (кусок [0,0.3]), в то время как другой агент может предпочесть кусок №2 (кусок [0.3,0.5]), а третий агент могут предпочесть и кусок №1, и кусок №2 (это означает, что они безразличны между ними, но любой из них нравится им больше, чем кусок №3).

Для каждого агента симплекс разбиения покрыт n частями, возможно, перекрывающимися на своих границах, так что для всех разбиений в части i агент предпочитает часть i . Внутри части i агент предпочитает только часть i , а на границе части i агент также предпочитает некоторые другие части. Таким образом, для каждого i существует определенная область в симплексе разбиения, в которой по крайней мере один агент предпочитает только часть i . Назовите этот регион U _i . Используя некоторую топологическую лемму (аналогичную лемме Кнастера–Куратовского–Мазуркевича ), можно доказать, что пересечение всех U _i непусто. Следовательно, существует разделение, в котором каждая часть представляет собой уникальное предпочтение агента. Поскольку количество частей равно количеству агентов, мы можем выделить каждую часть тому агенту, который ее предпочитает, и получить распределение без зависти.

Процедуры

Для трех агентов деление без зависти можно найти с помощью нескольких различных процедур:

• В процедуре движущихся ножей Стромквиста используются четыре одновременно движущихся ножа: один перемещается рефери, а другой - каждым агентом.
• В процедуре движущихся ножей Барбанеля-Брамса используются два одновременно движущихся ножа.
• Процедуру вращающегося ножа Робертсона-Уэбба можно использовать, когда пирог двумерный и используется только один движущийся нож.

Это непрерывные процедуры — они основаны на том, что люди постоянно и одновременно перемещают ножи. Они не могут быть выполнены за конечное число дискретных шагов.

Для n агентов разделение без зависти можно найти с помощью протокола разрезания торта Симмонса . Протокол использует симплекс разделов, аналогичный тому, который использовался в доказательстве существования Стромквиста. Он генерирует последовательность разделов, которая сходится к разделу без зависти. Конвергенция может занять бесконечно много шагов.

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

Результат твердости

Деление без зависти со связанными частями для 3 и более агентов не может быть найдено конечным протоколом в модели запроса Робертсона-Уэбба . Причина, по которой этот результат не противоречит ранее упомянутым алгоритмам, заключается в том, что они не являются конечными в математическом смысле.

Доказательство невозможности использует жесткую систему мер (RMS) – систему из n мер ценности, для которой разделение без зависти должно разрезать пирог в очень конкретных местах. Затем поиск подразделения, свободного от зависти, сводится к поиску этих конкретных мест. Предполагая, что торт представляет собой реальный интервал [0,1], нахождение деления без зависти с помощью запросов к агентам эквивалентно нахождению действительного числа в интервале [0,1] с помощью вопросов типа «да/нет». Для этого может потребоваться бесконечное количество вопросов.

RMS для трех агентов можно построить следующим образом. Пусть x , y , s и t будут параметрами, удовлетворяющими:

• $0<x<y<1,$
• $0<s<1/3<t<1/2,$
• $s+2t=1.$

Создайте набор из трех мер с этими двумя свойствами:

1. Плотность каждой меры всегда находится строго между √ 2/2 и √ 2 (поэтому для данного куска оценки агентов различаются менее чем в 2 раза).
2. Значения фигур, определяемые x и y, указаны в таблице:

Агент	[0, х ]	[ х , у ]	[ и ,1]
А	т	т	с
Б	с	т	т
С	т	с	т

Тогда каждое свободное от зависти деление среди Алисы Боба и Карла должно иметь разрезы в точках x и y (таких делений ровно два), поскольку все остальные варианты приводят к зависти:

• Если x* ≥ x и y* ≤ y и одно из неравенств строгое, то каждый ценит либо правую, либо левую часть больше, чем середину, поэтому тот, кто получит середину, будет завидовать.
• Если x* ≤ x и y* ≥ y и одно из неравенств строгое, то и Алиса, и Боб предпочитают средний кусок любому другому куску, поэтому тот, кто не получит его из двух, будет завидовать другому. .
• Если разрезы сделаны справа от x и справа от y (скажем, при x* > x и y* > y ), то и Алиса, и Карл предпочитают самый левый кусок самому правому, поэтому Боб должен согласиться принять самая правая часть. Это означает, что Боб должен оценить кусок [ x , x* ] как минимум в два раза больше, чем [ y , y* ]. Но из-за ограничения плотности значений это означает, что и Алиса, и Карл оценивают [ y , y* ] менее чем в два раза больше, чем [ x , x* ], поэтому они настаивают на самой левой части.
• Четвертый случай (разрез слева от x и слева от y ) аналогичен.

Для каждой RMS, каждого агента i и каждой константы ε>0 существует немного другая RMS со следующими свойствами:

• Новая мера стоимости агента i полностью идентична его старой мере ценности;
• Новые меры ценности двух других агентов идентичны их старым мерам ценности везде, кроме ε-окрестности x и y .

Это означает, что если все запросы, на которые был дан ответ, находились за пределами ε -окрестности x и y , то у агента i нет возможности узнать, находимся ли мы в старой RMS или в новой RMS.

Обладая этими знаниями, злоумышленник может обмануть любой протокол деления без зависти, чтобы он продолжал действовать вечно:

1. Начните с любого среднеквадратического значения, например, с параметров x = 1/3, y = 2/3, s = 0,3 и t = 0,35.
2. Пока протокол делает сокращения в точках, отличных от x и y , пусть он продолжается.
3. Всякий раз, когда протокол просит агента i сделать разрез в точке x или y , переключитесь на другую RMS с x'≠x и y'≠y , убедившись, что значения одинаковы для всех ранее сделанных разрезов.

Таким образом, протокол никогда не сможет сделать разрезы по правильным координатам x и y, необходимым для разделения без зависти.

Приближения

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

Одним из обходных путей является поиск подразделений, которые лишь приблизительно свободны от зависти . Существует два способа определения приближения — в единицах длины или в единицах стоимости .

Аппроксимация на основе длины использует следующие определения:

• Раздел . торта представлен n интервалами длины, которые он создает Итак, (0,2,0,5,0,3) — это разбиение единичного интервала на три подинтервала длиной 0,2, 0,5 и 0,3 (он генерируется путем разрезания единичного интервала на 0,2 и 0,7).
• Мультираздел — это набор из нескольких разных разделов.
• Многораздельное X называется свободным от зависти, если существует такая перестановка партнеров, что для каждого i существует такой элемент X, что i -й партнер предпочитает i -й сегмент.
• δ -мультиразбиение — это мультиразбиение, в котором для каждой пары разбиений разница между каждой из их координат не превышает δ . Например: {(0,2+ δ ,0,5,0,3), (0,2,0,5+ δ ,0,3), (0,2,0,5,0,3+ δ )}.

Параметр δ представляет собой допуск партнеров в единицах длины. Например, если земля разделена и партнеры согласны с тем, что разница в расположении границы в 0,01 метра для них не важна, то имеет смысл поискать 0,01-мультираздел, которому не позавидуешь. Дэн и др. представить модификацию протокола разрезания торта Симмонса без зависти, используя , которая находит δ -мультираздел $O[(1/\delta )^{n-2}]$ запросы. Более того, они доказывают нижнюю оценку $\Omega [(1/\delta )^{n-2}/2^{(n-1)(n-2)}]$ запросы. Даже когда функции полезности задаются явно с помощью алгоритмов с полиномиальным временем, задача разрезания торта без зависти является PPAD -полной.

Приближение на основе значений использует следующие определения:

• Раздел X называется ε-зависимым, если существует такая перестановка партнеров, что для каждого i стоимость i -го куска плюс ε не меньше стоимости любого другого куска: $\forall i,j:V_{i}(X_{i})+\varepsilon \geq V_{i}(X_{j})$.
• Мера ценности называется липшицевой непрерывной, если существует константа K такая, что для любой пары интервалов разница значений между ними не более чем в K раз превышает длину их симметричной разности. $\exists K:\forall j:|V_{i}(X_{i})-V_{i}(X_{j})|\leq K\cdot \mathrm {length} (X_{i}\setminus X_{j}\cup X_{j}\setminus X_{i})$.

Если все меры стоимости липшицевы, то два определения аппроксимации связаны между собой. Позволять $\epsilon =2K\delta$. без зависти Тогда каждый раздел в δ -мультиразделе является ε- свободным от зависти. Следовательно, результаты Денга и др. доказывают, что, если все партнеры имеют липшицевы непрерывные оценки, разделение ε -без зависти может быть найдено с помощью $\Theta [(1/\epsilon )^{n-2}]$ запросы с общими оценками.

При аддитивных оценках для любого ε > 0 для связного разрезания торта без ε-зависти требуется как минимум Ω(log ε ⁻¹ ) запросы. Для 3 агентов O(log ε ⁻¹ ) протокол существует. Для 4 или более агентов наиболее известный протокол требует O( n ε ⁻¹ ), что показывает экспоненциальный разрыв в сложности запроса. Более того, хотя последний протокол имеет полиномиальную сложность запроса по n , его вычислительная сложность экспоненциальна по n , даже для постоянного ε. Если требуются вычисления за полиномиальное время, наиболее известным приближением является $1/3$-зависть-свобода.

Автономный расчет — это второй обходной путь, позволяющий найти разделение, не вызывающее зависти, но только для ограниченного класса оценок. Если все меры стоимости являются полиномами степени не выше d , существует алгоритм, полиномиальный по n и d . Учитывая d , алгоритм запрашивает агентам d +1 оценочные запросы, которые дают d +1 точек на графике меры значения. Известно, что d +1 точек достаточно для интерполяции многочлена степени d . Следовательно, алгоритм может интерполировать все показатели стоимости всех агентов и найти разделение без зависти в автономном режиме. Количество необходимых запросов $O(n^{2}d)$.

Другое ограничение оценок состоит в том, что они кусочно-постоянны : для каждого агента существует не более m желаемых интервалов, а плотность значений агента в каждом интервале постоянна. При этом предположении связное распределение без зависти можно найти, решив ${\frac {n\cdot (2mn+n-1)!}{(2mn)!}}\in O(m^{n})$ линейные программы. Таким образом, когда n постоянно, проблема является полиномиальной по m .

Бесплатное распоряжение — это третий обходной путь, который сохраняет требование о том, чтобы разделение было полностью свободным от зависти и работало для всех показателей стоимости, но отменяет требование о том, что весь пирог должен быть разделен. Т.е. позволяет разделить часть торта и выбросить остаток. Без дополнительных требований задача тривиальна, поскольку всегда незавидно ничего не дать всем агентам. Таким образом, настоящая цель состоит в том, чтобы придать каждому агенту строго положительную ценность. Каждое распределение торта можно охарактеризовать уровнем пропорциональности , который представляет собой ценность наименее удачливого агента. Деление всего торта без зависти также является пропорциональным делением , и уровень его пропорциональности не ниже $1/n$, что является лучшим из возможных. Но когда разрешено свободное распоряжение, разделение без зависти может иметь более низкий уровень пропорциональности, и цель состоит в том, чтобы найти разделение без зависти с максимально возможной пропорциональностью. На данный момент известны следующие границы:

• Для трех агентов пропорциональность равна $1/3$ разделение без зависти т. е. пропорциональное достижимо за ограниченное время.
• Для 4 агентов пропорциональность равна $1/7$.
• Для n агентов пропорциональность равна $1/(3n)$.

Неизвестно, существует ли ограниченная по времени, свободная от зависти и пропорциональная процедура деления четырех и более партнеров со связанными фигурами.

Варианты

Большинство процедур разрезания торта из связанных частей предполагают, что торт представляет собой одномерный интервал, а части — одномерные подинтервалы. Зачастую желательно, чтобы детали имели определенную геометрическую форму, например квадрат. При таких ограничениях может оказаться невозможным разделить весь торт (например, квадрат нельзя разделить на два квадрата), поэтому мы должны разрешить свободное распоряжение. Как объяснялось выше , когда разрешено свободное распоряжение, процедуры измеряются уровнем их пропорциональности – ценностью, которую они гарантируют всем агентам. На данный момент известны следующие результаты:

• Для двух партнеров, делящих квадратный торт и желающих получить квадратные куски, пропорциональность равна $1/4$, и это лучшее, что можно гарантировать даже без зависти.
• Для трех партнеров, делящих квадратный торт и желающих получить квадратные кусочки, пропорциональность равна $1/10$; лучшее, что можно гарантировать без зависти, это $1/6$.

Деление без зависти существует даже при наличии неаддитивных функций значений, многомерного симплексного торта, а кусочки должны быть многогранниками .

Отключенные части

Процедуры

Для трех партнеров дискретная процедура Селфриджа-Конвея дает деление без зависти не более чем на 5 сокращений. Другие процедуры с использованием движущихся ножей требуют меньшего количества разрезов:

• Процедура движущихся ножей Левмора -Кука требует не более 4 разрезов;
• Процедура разрезания пирога с использованием вращающихся ножей Брамса-Тейлора-Цвикера требует не более 3 разрезов (в результате получается три соединенных куска, когда торт представляет собой круг, но когда торт представляет собой интервал, будет четыре куска);
• Используя процедуру «движущегося ножа» Остина для двух партнеров, можно без зависти получить деление для 3 партнеров, используя не более 3 разрезов. Эту идею приписывают Уильяму Уэббу.

Для четырех партнеров процедура Брамса-Тейлора-Цвикера обеспечивает разделение без зависти максимум с 11 сокращениями. Для пяти партнеров процедура Сабери и Ванга дает деление без зависти с ограниченным числом сокращений. Обе эти процедуры используют процедуру Остина для двух партнеров и общих дробей в качестве начального шага. Следовательно, эти процедуры следует считать бесконечными — их нельзя выполнить за конечное число шагов.

Для четырех или более партнеров существуют три алгоритма, которые конечны, но неограничены - не существует фиксированного ограничения на количество необходимых разрезов. Таких алгоритмов три:

• Протокол Брамса-Тейлора , впервые опубликованный в статье 1995 года, а затем в книге 1996 года.
• Протокол Робертсона-Уэбба , впервые опубликованный в статье 1997 года, а затем в книге 1998 года.
• Протокол Пихурко. опубликовано в 2000 году.

Хотя протоколы разные, основная идея в них схожа: разделить торт на конечное, но неограниченное количество «крошек», каждая из которых настолько мала, что ее ценность для всех партнеров незначительна. Затем сложным образом соедините крошки, чтобы получить желаемое деление. Уильям Гасарч сравнил три неограниченных алгоритма, используя порядковые числа .

Вопрос о том, можно ли разрезать торт без зависти в ограниченное время для четырех и более партнеров, оставался открытым в течение многих лет. Окончательно она была решена в 2016 году Харисом Азизом и Саймоном Маккензи. Первоначально они разработали алгоритм с ограниченным временем для четырех партнеров. Затем они расширили свой алгоритм для работы с любым количеством партнеров. Их алгоритм требует не более $n^{n^{n^{n^{n^{n}}}}}$ запросы. Хотя это число ограничено, оно очень далеко от нижней границы $\Omega (n^{2})$. Так что вопрос о том, сколько запросов необходимо для разрезания торта без зависти, остается открытым.

Приближения и частичные решения

Реентерабельный вариант последнего протокола уменьшающего числа находит аддитивную аппроксимацию деления без зависти в ограниченном времени. В частности, для каждой константы $\epsilon >0$, он возвращает деление, в котором стоимость каждого партнера равна как минимум наибольшему значению минус $\epsilon$, во времени $n^{2}/\epsilon$.

Если все меры стоимости кусочно-линейны , существует алгоритм, полиномиальный по размеру представления функций стоимости. Количество запросов $O(n^{6}k\ln {k})$, где $k$ – число разрывов в производных функций плотности значений.

Результат твердости

Любая процедура, не вызывающая зависти, для n человек требует как минимум Ω( n ² ) запросы в модели запросов Робертсона-Уэбба . Доказательство основано на тщательном анализе объема информации, которую алгоритм имеет о каждом партнере.

А. Предположим, что торт представляет собой одномерный интервал [0,1] и что значение всего торта для каждого из партнеров нормировано 1. На каждом этапе алгоритм просит определенного партнера либо оценить определенный интервал, содержащийся в [0,1], или для обозначения интервала указанным значением. В обоих случаях алгоритм собирает информацию только об интервалах, конечные точки которых были упомянуты в запросе или ответе. Назовем эти конечные точки ориентирами . Первоначально единственными ориентирами i являются 0 и 1, поскольку единственное, что алгоритм знает о партнере i, это то, что ( _vi [0,1])=1. Если алгоритм просит партнера i оценить интервал [0,2,1], то после ответа ориентирами i будут {0,0,2,1}. Алгоритм может вычислить v _i ([0,0,2]), но не значение любого интервала, конечная точка которого отличается от 0,2. Количество ориентиров увеличивается не более чем на 2 в каждом запросе. В частности, значение интервала [0,0,2] может быть сосредоточено полностью около 0, или полностью около 0,2, или где-то посередине.

B. Интервал между двумя последовательными ориентирами партнера i называется интервалом ориентиров партнера i . Когда алгоритм решает выделить кусок торта партнеру i , он должен выделить кусок, общая стоимость которого для i не менее велика. как любой ориентир-интервал i . Доказательство проводится от противного: предположим, что существует некоторый ориентир-интервал J , значение которого для i больше, чем значение, фактически присвоенное i . Какой-то другой партнер, скажем j , обязательно получит некоторую часть интервала-ориентира J. , По пункту А возможно, что вся стоимость интервала J сосредоточена внутри доли, выделенной партнеру j . Таким образом, я завидую j , и разделение не без зависти.

C. Предположим, что все партнеры отвечают на все запросы так, как будто их мера значения является однородной (т. е. значение интервала равно его длине). В соответствии с пунктом B алгоритм может назначить фигуру партнеру i только в том случае, если она длиннее всех ориентирных интервалов i . Не менее n /2 партнёров должны получить интервал длиной не более 2/ n ; следовательно, все их ориентиры-интервалы должны иметь длину не более 2/ n ; следовательно, они должны иметь по крайней мере n /2 интервалов-ориентиров; следовательно, у них должно быть не менее n /2 ориентиров.

D. Каждый запрос, на который отвечает партнер i, включает не более двух новых конечных точек, поэтому он увеличивает количество ориентиров i не более чем на 2. Следовательно, в случае, описанном в пункте C, алгоритм должен задать каждому из n /2 партнеров: не менее n /4 запросов. Таким образом, общее количество запросов составляет не менее n ² /8 = Ом( n ² ).

Доказательства существования и варианты

Помимо общих доказательств существования, подразумеваемых описанными выше алгоритмами, существуют доказательства существования разделов без зависти с дополнительными свойствами:

• Существует точное разделение , которое, в частности, не вызывает зависти; см. теоремы Дубинса–Спанье .
• Существует разделение без зависти, которое также является эффективным по Парето ; См. теорему Веллера .

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

Некоторые другие варианты:

• Сильная свобода от зависти требует, чтобы каждый агент строго предпочитал свой набор другим наборам.
• Супер-зависимость требует, чтобы каждый агент строго предпочитал свой набор 1/ n от общей стоимости и строго предпочитал 1/ n каждому из других наборов. Ясно, что сверхсвобода от зависти подразумевает сильную свободу от зависти, которая предполагает свободу от зависти.

Разделение без зависти с различными правами

Распространенное обобщение критерия отсутствия зависти состоит в том, что каждый из партнеров имеет разные права. То есть для каждого партнера i существует вес w _i, описывающий долю торта, которую он имеет право получить (сумма всех w _i равна 1). Тогда деление без взвешенной зависти определяется следующим образом. Для каждого агента i с мерой ценности Vi _и для каждого другого агента j :

$V_{i}(X_{i})/w_{i}\geq V_{i}(X_{j})/w_{j}$

То есть каждый партнер считает, что его распределение по отношению к его праву по крайней мере так же велико, как и любое другое распределение по отношению к праву другого партнера.

Когда все веса одинаковы (и равны 1/ n ), это определение сводится к стандартному определению отсутствия зависти.

Когда части могут быть разделены, всегда существует взвешенное деление без зависти, которое можно найти с помощью протокола Робертсона-Уэбба для любого набора весов. Цзэн представил альтернативный алгоритм приблизительного взвешенного деления без зависти, который требует меньшего количества сокращений.

Но когда части должны быть соединены, взвешенного разделения без зависти может не существовать. Чтобы убедиться в этом, обратите внимание, что каждое взвешенное деление без зависти также является взвешенно-пропорциональным с тем же весовым вектором; означает, что для каждого агента i с мерой ценности Vi _это :

$V_{i}(X_{i})/w_{i}\geq V_{i}(C)$

Известно, что взвешенно-пропорциональное распределение со связанными частями может не существовать: см. пропорционального разрезания пирога с различными правами пример .

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

• Аддитивные функции значений, одномерный пирог (интервал) и кусочки должны быть соединены интервалами.
• Функции аддитивных значений, многомерный симплексный пирог, а его части должны быть симплексами. В доказательстве используются теорема Спернера , лемма ККМ , лемма Гейла о накрытии и лемма Кая Фана о точках совпадения .

Разделение «плохого» торта

Основная статья: разделение обязанностей по дому без зависти

В некоторых случаях «пирог», который нужно разделить, имеет отрицательное значение. Например, это может быть участок газона, который нужно подстричь, или участок пустыря, который нужно очистить. Тогда торт — это «гетерогенное зло», а не «гетерогенное добро».

Некоторые процедуры разрезания торта без зависти можно адаптировать для плохого торта, но адаптация часто оказывается нетривиальной. см. в разделах «Работа без зависти» Более подробную информацию .

Сводные таблицы

Сводка по результату

Имя	Тип	Торт	Куски	#партнеры ( н )	#запросы	#порезы	завидовать	пропорциональность	Комментарии
Разделяй и выбирай	Дискретный процесс	Любой	Подключено	2	2	1 (оптимально)	Никто	1/2
Стромквист	Процесс движущегося ножа	Интервал	Подключено	3	∞	2 (оптимально)	Никто	1/3
Селфридж – Конвей	Дискретный процесс	Любой	Отключено	3	9	5	Никто	1/3
Брамс – Тейлор – Цвикер	Процесс движущегося ножа	Любой	Отключено	4	∞	11	Никто	1/4
Сабери-Ванг	Дискретный процесс	Любой	Отключено	4	Ограниченный	Ограниченный	Никто	1/4	Бесплатная утилизация
Азиз-Маккензи	Дискретный процесс	Любой	Отключено	4	584	203	Никто	1/4
Сабери-Ванг	Процесс движущегося ножа	Любой	Отключено	5	∞	Ограниченный	Никто	1/5
Стромквист	Существование	Интервал	Подключено	н	—	п -1	Никто	1/ н
Симмонс	Дискретный процесс	Интервал	Подключено	н	∞	п -1	Никто	1/ н
Дэн-Ци-Сабери	Дискретный процесс	Интервал	Подключено	н	$\left({\frac {1}{\epsilon }}\right)^{n-2}$	п -1	Добавка $\epsilon$	$\left({\tfrac {1}{n}}\right)-\epsilon$	Только тогда, когда оценки липшицевы.
сыр	Дискретный процесс	Интервал	Подключено	н	$n^{2}d$	?	Никто	1/ н	Только тогда, когда плотности значений полиномиальны со степенью не более d .
Отходы вызывают спешку	Дискретный процесс	Интервал	Подключено	3	9	4	Никто	1/3	Бесплатная утилизация
Отходы вызывают спешку	Дискретный процесс	Любой	Подключено	4	16	6	Никто	1/7	Бесплатная утилизация
Отходы вызывают спешку	Дискретный процесс	Любой	Подключено	н	$2^{n}$	$2^{n-1}-1$	Никто	${\frac {1}{2^{n-1}}}$	Бесплатная утилизация
Азиз-Маккензи ConnectedPieces	Дискретный процесс	Любой	Подключено	н	$n^{n+1}$	$n^{n+1}$	Никто	${\frac {1}{3n}}$	Бесплатная утилизация
Брамс-Тейлор	Дискретный процесс	Любой	Отключено	н	Неограниченный	Неограниченный	Никто	1/ н
Робертсон-Уэбб	Дискретный процесс	Любой	Отключено	н	Неограниченный	Неограниченный	Никто	1/ н	Взвешенный-без зависти.
Пихурко	Дискретный процесс	Любой	Отключено	н	Неограниченный	Неограниченный	Никто	1/ н
Азиз-Маккензи	Дискретный процесс	Любой	Отключено	н	$n^{n^{n^{n^{n^{n}}}}}$	$n^{n^{n^{n^{n^{n}}}}}$	Никто	1/ н
Реентерабельный последний уменьшитель	Дискретный процесс	Интервал	Отключено	н	$n^{2}/\epsilon$	?	Добавка $\epsilon$	1/ н
Курокава-Лай-Прокачча	Дискретный процесс	Интервал	Отключено	н	$n^{6}k\ln k$	?	Никто	1/ н	Только тогда, когда плотности значений кусочно-линейны с не более чем k разрывами.
Веллер	Существование	Любой	Отключено	н	—	∞	Никто	1/ н	Эффективен по Парето .
2-D	Дискретный процесс	Квадрат	Связанный и квадратный	2	2	2	Никто	1/4	Бесплатная утилизация
2-D	Процесс движущегося ножа	Квадрат	Связанный и квадратный	3	∞	6	Никто	1/10	Бесплатная утилизация

Сводка по количеству агентов и типам фигур:

# агентов	Соединённые части	Общие части
2	Разделяй и выбирай
3	Процедура движущихся ножей Стромквиста (бесконечное время); Отходы торопятся (ограниченное по времени, ограниченное сокращение, свободное удаление, пропорциональное)	Дискретная процедура Селфриджа – Конвея (ограниченное время, не более 5 разрезов).
4	Отходы-торопятся (ограниченность по времени, ограниченные сокращения, свободная утилизация, пропорциональность 1/7).	Процедура перемещения ножей Брамса-Тейлора-Цвикера (бесконечное время, не более 11 разрезов). Дискретная процедура Сабери – Ванга (ограниченное время, ограниченные сокращения, свободное распоряжение, пропорциональное). Дискретная процедура Азиза – Маккензи (ограниченное время, ограниченные разрезы, пропорциональные).
5		Процедура с движущимися ножами Сабери-Ванга (бесконечное время, ограниченные разрезы).
н	Протокол Симмонса (бесконечное время) Дэн-Ци-Сабери (приблизительно без зависти, экспоненциальное время). Отходы-спешка (полное отсутствие зависти, экспоненциальное время, свободное удаление, экспоненциальная пропорциональность) Азиз-Маккензи ConnectedPieces (полное отсутствие зависти, экспоненциальное время, свободное распоряжение, линейная пропорциональность)	Брэмс и Тейлор (1995) ; Робертсон и Уэбб (1998) . - Оба алгоритма требуют конечного, но неограниченного числа разрезов. Дискретная процедура Азиза-Маккензи (ограниченное время, ограниченные разрезы, пропорциональные).
Твердость	Все алгоритмы для n ≥ 3 должны быть бесконечными (Stromquist, 2008).	Все алгоритмы должны использовать как минимум Ω( n 2 ) шаги (Прокачча, 2009).
Варианты	Взвешенное деление без зависти существует для произвольных весов (Идзик, 1995), даже когда торт и кусочки представляют собой симплексы (Идзик и Ичииси, 1996). Разделение без зависти существует даже при неаддитивных предпочтениях (Dall'Aglio and Maccheroni, 2009).	Робертсон-Уэбб может найти взвешенное деление без зависти для произвольных весов. ( Существует идеальное разделение Dubins&Spanier, 1961). свободный от зависти и Существует способ разрезания торта, эффективный ( теорема Веллера ).

См. также

• Разделение домашних дел без зависти
• Назначение предметов без зависти
• Честная нарезка пирога
• Группа без зависти
• Пропорциональное разрезание торта

Внешние ссылки

• Калькулятор справедливого распределения – апплет для расчета без зависти распределения тортов, домашних дел, комнат и арендной платы.