Завистливое разрезание торта

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

Если имеется только два участника, задача проста и была решена ещё в библейские времена протоколом «Дели-и-выбирай». Если имеется три или более участников, задача становится существенно более трудной.

Изучались два главных варианта задачи:

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

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

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

Более строгий критерий отсутствия зависти ввели в задачу разрезания торта Георгий Гамов и Марвин Штерн в 1950-х годах[2].

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

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

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

для кусков общего вида нижняя граница равна $\Omega (n^{2})$ ;
для связных кусков нижняя граница равна бесконечности — возможно, нет конечного протокола для трёх и более участников.

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

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

Связные куски

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

Завистливый делёж n агентов со связными кусками всегда существует при следующих допущениях[3].

никакой агент не предпочитает пустой кусок (пустое множество точек) непустому куску;
предпочтения агентов непрерывны.

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

Основной концепцией доказательства является симплекс разбиений. Предположим, что торт является отрезком [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 и более агентами не может быть найдено конечным протоколом[4]. Причина этого результата не противоречит упомянутым выше алгоритмам, поскольку они не конечны в математическом смысле[5].

Доказательство невозможности использует систему жёсткой меры (англ. rigid measure system, RMS) — система n мер оценок, для которых разбиение без зависти должно разрезать торт в очень специфичных местах. Тогда поиск разбиения без зависти сводится к поиску этих специфичных мест. При предположении, что торт из себя представляет вещественный отрезок [0;1], поиск разбиения без зависти с помощью запросов участникам эквивалентен поиску вещественных чисел на отрезке [0;1] с помощью вопросов да/нет. Это может потребовать бесконечного числа вопросов.

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

$0<x<y<1,$
$0<s<{\tfrac {1}{3}}<t<{\tfrac {1}{2}},$
$s+2t=1.$

Построим множество трёх мер с двумя свойствами:

плотность каждой меры строго между ${\tfrac {\sqrt {2}}{2}}$ и ${\sqrt {2}}$ (так что для заданного куска оценки агентов отличаются не более чем вдвое);
значения кусков, определяемых числами x и y, приведены в таблице:

Агент	[0;x]	[x;y]	[y;1]
A	t	t	s
B	s	t	t
C	t	s	t

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

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

Для любой RMS, любого агента i и любой константы $\varepsilon >0$ существует чуть другая RMS со следующими свойствами:

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

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

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

начнём с любой RMS, например с параметров $x={\tfrac {1}{3}};y={\tfrac {2}{3}};s=0,3;t=0,35$ ;
если протокол делает разрезы вне точек x и y, просто продолжим;
когда протокол спрашивает участника i сделать разрез в x или y, переключаемся на другую RMS с $x'\neq x$ и $y'\neq 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-й сегмент. $\delta$ -мультиразбиение — это мультиразбиение, в котором для каждой пары разбиений разность между их координатами не превосходит $\delta$ . Например: {(0,2+ $\delta$ ;0,5;0,3), (0,2;0,5+ $\delta$ ;0,3), (0,2;0,5;0,3+ $\delta$ )}.

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

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

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

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

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

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

для 3 агентов пропорциональность равна $1/3$ , то есть, завистливый делёж и пропорциональный делёж достижимы за ограниченное время[8];
для 4 агентов пропорциональность равна $1/7$ [8];
для n агентов пропорциональность равна $1/(3n)$ [9].

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

Варианты

Большинство процедур разрезания торта со связными кусками предполагают, что торт является одномерным отрезком, а куски являются подынтервалами. Часто желательно, чтобы куски имели определённую геометрическую форму, такую как квадрат. Имея такое ограничение может оказаться невозможным разделить весь торт (например, квадрат нельзя разделить на два квадрата), так что должны оставаться нераспределённые куски. Как объяснено выше, когда разрешены нераспределённые куски, процедуры измеряются по их уровню пропорциональности — значению, которое они гарантируют каждому участнику. В настоящее время известно следующее[10]:

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

Несвязные куски

Процедуры

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

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

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

Для четырёх и более участников существует три алгоритма, которые конечны, но не ограничены — не существует фиксированной границы числа требуемых разрезов[14]. Имеется три таких алгоритма:

процедура Брамса — Тейлора, впервые опубликованная в статье 1995 года, а затем в книге 1996 года;
протокол Робертсона — Уэбба, впервые опубликованная в статье 1997 года, а затем в книге 1998 года;
протокол Пихурко[15] опубликован в 2000.

Хотя протоколы отличаются, основная их идея остаётся похожей — делим торт на конечное, но не ограниченное число «крошек», каждая из которых настолько мала, что её значением все участники пренебрегают. Затем комбинируем крошки изощрённым способом, чтобы получить желаемый делёж. Вильям Гасар сравнил три неограниченных алгоритма с помощью порядковых чисел[16].

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

Аппроксимации и частичные решения

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

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

Результаты по сложности

Любая процедура завистливого дележа для n человек требует по меньшей мере $\Omega (n^{2})$ запросов[19]. Доказательство опирается на тщательный анализ количества информации, которое алгоритм имеет от каждого участника.

Предположим, что торт является одномерным отрезком [0;1], и что значение всего торта для каждого из участников нормализовано до 1. На каждом шаге алгоритм спрашивает определённого участника либо оценить определённый интервал, содержащийся в [0;1], Либо пометить интервал специфичным значением. В обоих случаях алгоритм собирает информацию только о интервалах, конечные точки которых были упомянуты в запросе или в ответе. Будем называть эти конечные точки вехами. Первоначально вехами для i являются только 0 и 1, поскольку алгоритм знает об участнике i только то, что $v_{i}([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, или где-то между этими значениями.

Интервал между двумя последовательными вехами для участника i называется интервалом вех участника i, Когда алгоритм решает выделить кусок торта участнику i, он должен выделить кусок, полная оценка которого для i не меньше любого интервала вех участника i. Доказательство от противного — предположим, что есть определённый интервал вех J, значение которого для i больше, чем актуальное значение, выделенное для участника i. Некоторый другой участник, скажем j, обязательно получит некоторую часть интервала вех J. Согласно пункту A есть возможность, что всё значение интервала J концентрируется внутри куска, выделенного участнику j. Тогда i будет завидовать j и разбиение будет не свободно от зависти.

Предположим, что все участники ответили на все вопросы как если бы их оценки были однородными (то есть значение интервала равно его длине). Согласно пункту B алгоритм может выделить кусок участнику i только если он длиннее всех интервалов вех для участника i. По меньшей мере ${\tfrac {n}{2}}$ участников должны получить интервал длиной, не превосходящей 2/n. Следовательно, все их интервалы вех должны иметь длины, не превосходящие 2/n. Следовательно, они должны иметь по меньшей мере ${\tfrac {n}{2}}$ интервалов вех, а следовательно и число вех у них должно быть не менее ${\tfrac {n}{2}}$ .

Каждый вопрос, на который ответил участник i, вводит максимум две новые конечные точки, так что число вех для участника i увеличивается не более чем на 2. Следовательно, в случае, описанном в пункте C, алгоритм должен опросить каждого из ${\tfrac {n}{2}}$ участников, задав по меньшей мере n/4 вопросов. Полное число вопросов тогда будет не меньше ${\tfrac {n^{2}}{8}}=\Omega (n^{2})$ .

Остаётся открытым вопрос, существует ли ограниченный алгоритм для произвольных функций оценок. Таким образом, имеется огромная пропасть между нижней границей $\Omega (n^{2})$ и лучшим известным на настоящее время алгоритмом, который конечен, но не ограничен.

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

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

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

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

Завистливый делёж с различными долями

Обобщением критерия отсутствия зависти является разрешение каждому участнику иметь различные доли. То есть, для любого участника i имеется вес $w_{i}$ , описывающий долю торта, которую ему приписывается предоставить (сумма все долей w_i равна 1). Тогда взвешенное свободное от зависти разбиение определяются следующим образом. Для любого агента i с мерой оценок $V_{i}$ и для любого другого агента k:

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

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

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

Если куски могут быть несвязными, взвешенное разбиение без зависти всегда существует и может быть найдено по протоколу Робертсона — Уэбба для любого набора весов. Зенг предложил альтернативный алгоритм для приближённого взвешенного разбиения без зависти, которое требует малого числа разрезов[20].

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

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

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

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

аддитивные функции оценок, одномерный торт (отрезок), куски должны быть связными отрезками[21];
аддитивные функции оценок, многомерный торт в виде симплекса, куски должны быть симплексами[22]. Доказательство использует теорему Шпернера, лемму Кнастера — Куратовского — Мазуркевича, лемму о покрытии Гейла и лемму Ки Фана о совпадающих точках;
неаддитивные функции оценок, многомерный торт в виде симплекса, куски должны быть многогранниками[23].

Деление «плохого» торта

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

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

Итоговые таблицы

Процедуры по результатам
Название	Тип	Торт	Куски	Число участников (n)	Число запросов	Число разрезов	зависть	Пропорциональность[24]	Комментарии
Дели-и-выбирай	Дискретная процедура	Любой	Связные	2	2	1 (оптимально)	Нет	1/2
Стромквиста	Процедура «Движущийся нож»	Отрезок	Связные	3	$\infty$	2 (оптимально)	Нет	1/3
Селфриджа — Конвея	Дискретная процедура	Любой	Несвязные	3	9	5	Нет	1/3
Брамса — Тейлора — Цвикера	Процедура «Движущийся нож»	Любой	Несвязные	4	$\infty$	11	Нет	1/4
Сабери — Вонга[13]	Дискретная процедура	Любой	Несвязные	4	Ограничено	Ограничено	Нет	1/4	возможен отбрасываемый кусок
Азиза — Маккензи[17]	Дискретная процедура	Любой	Несвязные	4	203	584	Нет	1/4
Сабери — Вонга [13]	Процедура «Движущийся нож»	Любой	Несвязные	5	$\infty$	Ограничено	Нет	1/5
Стромквиста	Существование	Отрезок	Связные	n	—	`n`−1	Нет	1/`n`
Симмонса	Дискретная процедура	Отрезок	Связные	n	$\infty$	`n`−1	Нет	1/`n`
Денга — Ки — Сабери	Дискретная процедура	Отрезок	Связные	n	$\left({\frac {1}{\varepsilon }}\right)^{n-2}$	`n`−1	$\varepsilon$	$\left({\tfrac {1}{n}}\right)-\varepsilon$	Только когда оценки непрерывны по Липшицу
Бранцей[7]	Дискретная процедура	Отрезок	Связные	n	$n^{2}d$	Неизвестно	Нет	1/`n`	Только когда плотности оценок полиномиальны с максимальной степенью d.
«Поспешишь — людей насмешишь»	Дискретная процедура	Отрезок	Связные	3	9	4	Нет	1/3	Возможен отбрасываемый кусок
«Поспешишь — людей насмешишь»	Дискретная процедура	Любой	Связные	4	16	6	Нет	1/7	Возможен отбрасываемый кусок
«Поспешишь — людей насмешишь»	Дискретная процедура	Любой	Связные	n	$2^{n}$	$2^{n-1}-1$	Нет	${\frac {1}{2^{n-1}}}$	Возможен отбрасываемый кусок
Азиза — Маккензи ConnectedPieces[9]	Дискретная процедура	Любой	Связные	n	$n^{n+1}$	$n^{n+1}$	Нет	${\frac {1}{3n}}$	Возможен отбрасываемый кусок
Брамса — Тейлора	Дискретная процедура	Любой	Несвязные	n	Не ограничено	Не ограничено	Нет	1/`n`
Робертсона — Уэбба	Дискретная процедура	Любой	Несвязные	n	Не ограничено	Не ограничено	Нет	1/`n`	Взвешенное свободное от зависти разбиение
Пихурко [15]	Дискретная процедура	Любой	Несвязные	n	Не ограничено	Не ограничено	Нет	1/`n`
Азиза — Маккензи [9]	Дискретная процедура	Любой	Несвязные	n	$n^{n^{n^{n^{n^{n}}}}}$	$n^{n^{n^{n^{n^{n}}}}}$	Нет	1/`n`
Замкнутый вариант протокола «последний уменьшивший»	Дискретная процедура	Отрезок	Несвязные	n	$n^{2}/\varepsilon$	Неизвестно	$\varepsilon$	1/`n`
Курокавы — Лея — Прокачи[18]	Дискретная процедура	Отрезок	Несвязные	n	$n^{6}k\ln k$	Неизвестно	Нет	1/`n`	Только когда значение плотностей кусочно-линейна с максимум k разрывами.
Веллер	Существование	Любой	Несвязные	n	—	$\infty$	Нет	1/`n`	эффективный по Парето.
2-D	Дискретная процедура	Квадратный	Связные и квадратные	2	2	2	Нет	1/4	Возможен отбрасываемый кусок
2-D	Процедура «Движущийся нож»	Квадратный	Связные и квадратные	3	$\infty$	6	Нет	1/10	Возможен отбрасываемый кусок

Итоговая таблица по числу участников и типу кусков:

число агентов	Связные куски	Куски общего вида
2	Дели-и-выбирай
3	Процедура «Движущийся нож» Стромквиста (бесконечное время); «Поспешишь — людей насмешишь» (ограниченное время, ограниченное число разрезов, возможен отбрасываемый кусок, пропорциональное)	Дискретная процедура Селфриджа — Конвея (ограниченное время, не более 5 разрезов).
4	«Поспешишь — людей насмешишь» (ограниченное время, ограниченное число разрезов, возможен отбрасываемый кусок, пропорциональность 1/7).	Процедура Брамса — Тейлора — Цвикера (бесконечное время, не более 11 разрезов). Дискретная процедура Сабери — Вонга[13] (ограниченное время, ограниченное число разрезов, возможен отбрасываемый кусок, пропорциональная). Дискретная процедура Азиза — Маккензи[17] (ограниченное время, ограниченное число разрезов, пропорциональная).
5		Процедуры «Движущийся нож» Сабери — Вонга[13] (бесконечное время, ограниченное число разрезов).
n	протокол Симмонса (бесконечное время) Денга — Ки — Сабери (приближённо свободный от зависти, экспоненциальное время). «Поспешишь — людей насмешишь» (полностью свободен от зависти, экспоненциальное время, возможен отбрасываемый кусов, экспоненциальная пропорциональность) ConnectedPieces Азиза — Маккензи[9] (полностью свободен от зависти, экспоненциальное время, возможен отбрасываемый кусок, линейная пропорциональность)	Брамс и Тейлор (1995); Робертсон и Уэбб (1998). — Оба алгоритма требуют конечного, но не ограниченного числа разрезов. Дискретная процедура Азиза — Маккензи[9] (ограниченное время, ограниченное число разрезов, пропорциональный делёж).
Трудность	Все алгоритмы для $n\geqslant 3$ должны быть бесконечными (Stromquist, 2008).	Все алгоритмы должны использовать по меньшей мере $\Omega (n^{2})$ шагов (Procaccia, 2009).
Варианты	Взвешенное разбиение без зависти существует для произвольных весов (Idzik, 1995), даже когда торт и куски являются симплексами (Idzik, Ichiishi, 1996), и даже с неаддитивными предпочениями (Dall’Aglio, Maccheroni, 2009).	Протокол Робертсона — Уэбба может найти взвешенное свободное от зависти разбиение для произвольных весов. Совершенный делёж существует (Dubins&Spanier, 1961). Существует свободное от зависти и эффективное разрезание торта (Теорема Веллера).

См. также

Примечания

Часто переводится буквально с английского как разрезание торта без зависти (англ. Envy-free cake-cutting), хотя именно зависть и играет ключевую роль в данном дележе. В статье используется термин "завистливый делёж", но результат этого дележа должен быть распределением без зависти.
Gamow, Stern, 1958.
Stromquist, 1980, с. 640–644.
Stromquist, 2008.
Процедура «Движущийся нож» Стромквиста требует, чтобы агенты перемещали свои ножи пока рефери передвигает свой меч. Поскольку движение меча непрерывно, число требуемых шагов несчётно (а потому, естественно, бесконечно). Протоколом разрезания торта Симмонса сходится к свободному от зависти разбиению, но может потребоваться бесконечное число шагов.
Deng, Qi, Saberi, 2012, с. 1461–1476.
Brânzei, 2015, с. 93–95.
Segal-Halevi, Hassidim, Aumann, 2016, с. 1–32.
Aziz, MacKenzie, 2016.
Segal-Halevi, Hassidim, Aumann, 2015, с. 1021–1028.
Brams, Taylor, 1996, с. 124–125.
Brams, Taylor, Zwicker, 1997, с. 547–555.
Saberi, Wang, 2009.
S. J. Brams, M. A. Jones, C. Klamler, «Better ways to cut a cake», Notices of the AMS, 2005. [Online]. Available: http://www.ams.org/notices/200611/fea-brams.pdf
Pikhurko, 2000, с. 736–738.
Gasarch, William, Which Unbounded Protocol for Envy Free Cake Cutting is Better?, arΧiv:1507.08497 [math.LO]
Aziz, MacKenzie, 2016, с. 454.
Kurokawa, Lai, Procaccia, 2013.
Procaccia, 2009, с. 239–244.
Zeng, 2000, с. 259–271.
Idzik, 1995.
Ichiishi, Idzik, 1999, с. 389–400.
Dall'Aglio, MacCheroni, 2009, с. 57–77.
Значение (как доля от всего торта), которая гарантирована каждому агенту при аддитивных оценках. Когда нет зависти и весь торт разделен, пропорциональность всегда равна ${\tfrac {1}{n}}$ , лучшая из возможных.

Литература

George Gamow, Marvin Stern. Puzzle-math. — 1958. — ISBN 978-0670583355.
Walter Stromquist. How to Cut a Cake Fairly // The American Mathematical Monthly. — 1980. — Т. 87, вып. 8. — doi:10.2307/2320951. — .
Walter Stromquist. Envy-free cake divisions cannot be found by finite protocols // Electronic Journal of Combinatorics. — 2008. Архивировано 11 марта 2016 года.
Deng X., Qi Q., Saberi A. Algorithmic Solutions for Envy-Free Cake Cutting // Operations Research. — 2012. — Т. 60, вып. 6. — doi:10.1287/opre.1120.1116.
Brânzei S. A note on envy-free cake cutting with polynomial valuations // Information Processing Letters. — 2015. — Т. 115, вып. 2. — doi:10.1016/j.ipl.2014.07.005.
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Envy-Free Cake-Cutting in Two Dimensions // The 29th AAAI Conference on Artificial Intelligence (AAAI-15). — Austin, Texas, 2015. — doi:10.13140/RG.2.1.5047.7923.
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Waste Makes Haste // ACM Transactions on Algorithms. — 2016. — Т. 13. — doi:10.1145/2988232. — arXiv:1511.02599.
Steven J. Brams, Alan D. Taylor, William S. Zwicker. A Moving-Knife Solution to the Four-Person Envy-Free Cake Division // Proceedings of the American Mathematical Society. — 1997. — Т. 125, вып. 2. — doi:10.1090/S0002-9939-97-03614-9.
Amin Saberi, Ying Wang. Cutting a Cake for Five People // Algorithmic Aspects in Information and Management. — 2009. — doi:10.1007/978-3-642-02158-9_25.
Pikhurko O. On Envy-Free Cake Division // The American Mathematical Monthly. — 2000. — Т. 107, вып. 8. — doi:10.2307/2695471. — .
Haris Aziz, Simon MacKenzie. A discrete and bounded envy-free cake cutting protocol for four agents // Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing – STOC 2016. — 2016. — ISBN 9781450341325. — doi:10.1145/2897518.2897522.
Haris Aziz, Simon MacKenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents // FOCS 2016. — 2016.
David Kurokawa, John K. Lai, Ariel D. Procaccia. How to Cut a Cake Before the Party Ends // AAAI. — 2013.
Ariel Procaccia. Thou Shalt Covet Thy Neighbor's Cake // IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence. — 2009.
Dao-Zhi Zeng. Approximate Envy-Free Procedures // Game Practice: Contributions from Applied Game Theory (англ.). — Springer, 2000. — Vol. 23. — (Theory and Decision Library). — ISBN 9781461546276. — doi:10.1007/978-1-4615-4627-6_17.
Adam Idzik. Optimal divisions of the unit interval // International Conference in Honor of Robert J. Aumann on his 65th Birthday. — Jerusalem, 1995.
Ichiishi T., Idzik A. Equitable allocation of divisible goods // Journal of Mathematical Economics. — 1999. — Т. 32, вып. 4. — doi:10.1016/s0304-4068(98)00053-6.
Dall'Aglio M., MacCheroni F. Disputed lands // Games and Economic Behavior. — 2009. — Т. 66. — doi:10.1016/j.geb.2008.04.006.
Steven J. Brams, Alan D. Taylor. Fair division: from cake-cutting to dispute resolution. — Cambridge University Press, 1996. — ISBN 0-521-55644-9.

Ссылки

Fair Division Calculator — Апплет вычисления свободного от зависти дележа для тортов, обязанностей, уборки помещений и ренты.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[EFCC-1] Часто переводится буквально с английского как разрезание торта без зависти (англ. Envy-free cake-cutting), хотя именно зависть и играет ключевую роль в данном дележе. В статье используется термин "завистливый делёж", но результат этого дележа должен быть распределением без зависти.

[_825f9cc0930c511d-2] Gamow, Stern, 1958.

[_0b177aa507be4437-3] Stromquist, 1980, с. 640–644.

[_8ae5c2d384ad03d4-4] Stromquist, 2008.

[SMK-5] Процедура «Движущийся нож» Стромквиста требует, чтобы агенты перемещали свои ножи пока рефери передвигает свой меч. Поскольку движение меча непрерывно, число требуемых шагов несчётно (а потому, естественно, бесконечно). Протоколом разрезания торта Симмонса сходится к свободному от зависти разбиению, но может потребоваться бесконечное число шагов.

[_a2c3d084817c8439-6] Deng, Qi, Saberi, 2012, с. 1461–1476.

[_9cd38ebb9e671d91-7] Brânzei, 2015, с. 93–95.

[_a2c702d1b80a2847-8] Segal-Halevi, Hassidim, Aumann, 2016, с. 1–32.

[_556ab11e28327601-9] Aziz, MacKenzie, 2016.

[_07c8efbac4d9d453-10] Segal-Halevi, Hassidim, Aumann, 2015, с. 1021–1028.

[_ffc7b489990ffb36-11] Brams, Taylor, 1996, с. 124–125.

[_56b524195eb73252-12] Brams, Taylor, Zwicker, 1997, с. 547–555.

[_4e5678b3d849f995-13] Saberi, Wang, 2009.

[BJK-14] S. J. Brams, M. A. Jones, C. Klamler, «Better ways to cut a cake», Notices of the AMS, 2005. [Online]. Available: http://www.ams.org/notices/200611/fea-brams.pdf

[_66a28cc8e31e4343-15] Pikhurko, 2000, с. 736–738.

[G15-16] Gasarch, William, Which Unbounded Protocol for Envy Free Cake Cutting is Better?, arΧiv:1507.08497 [math.LO]

[_619d28676931a1c4-17] Aziz, MacKenzie, 2016, с. 454.

[_f9e743b7ababca05-18] Kurokawa, Lai, Procaccia, 2013.

[_e40fc5619cab6c1a-19] Procaccia, 2009, с. 239–244.

[_c23bd7f5d8b28aa2-20] Zeng, 2000, с. 259–271.

[_0d8790468378668a-21] Idzik, 1995.

[_10d27c5dcca9df57-22] Ichiishi, Idzik, 1999, с. 389–400.

[_32bdd99bdd4a2aba-23] Dall'Aglio, MacCheroni, 2009, с. 57–77.

[PRO-24] Значение (как доля от всего торта), которая гарантирована каждому агенту при аддитивных оценках. Когда нет зависти и весь торт разделен, пропорциональность всегда равна ${\tfrac {1}{n}}$ , лучшая из возможных.