Завистливое разрезание тортаЧасто переводится буквально с английского как разрезание торта без зависти (), хотя именно зависть и играет ключевую роль в данном дележе. В статье используется термин "завистливый делёж", но результат этого дележа должен быть распределением без зависти. — вид справедливого разрезания торта. Это разрезание неоднородного ресурса («торта») с удовлетворением критерия отсутствия зависти, а именно, что любой участник обладает чувством, что выделенная ему часть (по его собственной субъективной оценке) не меньше кусков, отданных другим участникам.
Если имеется только два участника, задача проста и была решена ещё в библейские времена протоколом «Дели-и-выбирай». Если имеется три или более участников, задача становится существенно более трудной.
Изучались два главных варианта задачи: связные куски, например, в случае одномерного отрезка каждый участник должен получить отдельный подынтервал. Если имеется участников, нужно всего разрезов. куски общего вида, например, в случае одномерного отрезка каждый участник должен получить объединение непересекающихся подотрезков.
Краткая история Современные исследования по задаче справедливого разрезания торта начались в 1940-х годах. Первым критерием справедливости был пропорциональный делёж и процедура для n участников вскоре была найдена.
Более строгий критерий отсутствия зависти ввели в задачу разрезания торта Георгий Гамов и Марвин Штерн в 1950-х годах.
Процедура для трёх участников и общего вида кусков была найдена в 1960 году. Процедура для трёх участников и связных кусков была найдена лишь в 1980 году.
Завистливый делёж для четырёх и более лиц был открытой проблемой до 1990-х годов, когда были опубликованы три процедуры для общего вида кусков и процедура для связных кусков. Все эти процедуры неограниченны — они могут требовать число шагов, которое заранее не ограничено. Процедура для связных кусков может даже требовать бесконечного числа шагов.
Две нижние границы сложности по времени работы задачи завистливого дележа были опубликованы в 2000-х годах: для кусков общего вида нижняя граница равна ; для связных кусков нижняя граница равна бесконечности — возможно, нет конечного протокола для трёх и более участников.
В 2010-х годах были опубликованы некоторые аппроксимационные процедуры и процедуры для специальных случаев. Вопрос, существуют ли процедуры с ограниченным временем работы для кусков общего вида, оставался открытым долгое время. Проблема окончательно была решена в 2016 году. Харис Азиз и Саймон Макке́нзи предложили дискретный протокол завистливого дележа, который требует не более запросов. До сих пор существует огромная пропасть между нижней границей и значением, даваемым процедурой. К августу 2016 точная временная сложность задачи завистливого дележа оставалась неизвестной.
Для случая связных кусков было замечено, что результат по трудности предполагает, что весь кусок должен быть разделён. Если это требование заменяется более слабым требованием, что любой участник получает пропорциональное значение (по меньшей мере всего куска согласно его собственной оценке), то ограниченная процедура для трёх участников известна, но всё ещё остаётся открытым вопрос, существуют ли процедуры с ограниченным временем работы для четырёх и более участников.
Связные куски
Доказательство существования Завистливый делёж 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. Назовём эту область . При использовании некоторой топологической леммы (которая аналогична ), можно доказать, что пересечение всех Ui непусто. Следовательно, существует разбиение, в котором каждый кусок является единственным, который предпочитает агент. Поскольку число кусков равно числу агентов, мы можем распределить каждый кусок агенту, который его предпочитает и получим распределение без зависти.
Процедуры Для трёх агентов разбиение без зависти может быть найдено с помощью нескольких различных процедур: процедура «Движущийся нож» Стромквиста использует четыре одновременно движущихся ножа — один нож движет рефери, а остальные три — по одному на каждого агента; процедура «Движущийся нож» Барбанеля — Брамса использует два одновременно движущихся ножа; процедура «Движущийся нож» Робертсона — Уэбба может быть использована, когда торт двумерен, и используется только один движущийся нож.
Есть непрерывные процедуры — они опираются на непрерывные и одновременные движения ножей человеком. Эти процедуры нельзя выполнить за конечное число дискретных шагов.
Для n участников разбиение без зависти может быть найдено протоколом разрезания торта Симмонса — Су. Протокол использует симплекс разбиения, аналогичный используемому в доказательстве существования Стромквиста. Протокол образует последовательность разбиений, которая сходится к разбиению без зависти. Схождение может потребовать бесконечно много шагов.
Не случайно, что все эти алгоритмы требуют бесконечного числа запросов. Как мы покажем в следующей подсекции, может быть невозможно найти разрезания торта без зависти со связными кусками с конечным числом запросов.
Результаты по сложности Разбиение без зависти со связными кусками для 3 и более агентами не может быть найдено конечным протоколом. Причина этого результата не противоречит упомянутым выше алгоритмам, поскольку они не конечны в математическом смыслеПроцедура «Движущийся нож» Стромквиста требует, чтобы агенты перемещали свои ножи пока рефери передвигает свой меч. Поскольку движение меча непрерывно, число требуемых шагов несчётно (а потому, естественно, бесконечно). Протоколом разрезания торта Симмонса сходится к свободному от зависти разбиению, но может потребоваться бесконечное число шагов..
Доказательство невозможности использует систему жёсткой меры (, RMS) — система n мер оценок, для которых разбиение без зависти должно разрезать торт в очень специфичных местах. Тогда поиск разбиения без зависти сводится к поиску этих специфичных мест. При предположении, что торт из себя представляет вещественный отрезок [0;1], поиск разбиения без зависти с помощью запросов участникам эквивалентен поиску вещественных чисел на отрезке [0;1] с помощью вопросов да/нет. Это может потребовать бесконечного числа вопросов.
RMS для трёх участников может быть построен следующим образом. Пусть x, y, s и t будут параметрами, удовлетворяющими условиям
Построим множество трёх мер с двумя свойствами: плотность каждой меры строго между и (так что для заданного куска оценки агентов отличаются не более чем вдвое); значения кусков, определяемых числами x и y, приведены в таблице:
Агент [0;x] [x;y] [y;1]AttsBsttCtst
Тогда любое разбиение без зависти между Алисой, Бобом и Карлом должно иметь разрезы в x и y (имеется ровно два таких разбиения), поскольку любые другие места приведут к зависти: если разрезы сделаны слева от x и справа от y, то Алиса и Боб будут настаивать на среднем куске; если разрезы сделаны справа от x и слева от y, ни один из участников не захочет взять средний кусок; если разрезы сделаны справа от x и справа от y (скажем, в точках x*>x и y*>y), то и Алиса, и Карл будут предпочитать левые куски правым, так что Боб должен будет согласиться взять самый правый кусок. Это значит, что Боб должен оценивать кусок [x;x*] по меньшей мере вдвое больше, чем [y;y*]. Но ввиду ограничения на плотность цены это означает, что и у Алисы, и у Карла оценка [x;x*] больше, чем [y;y*], так что они будут настаивать на левых кусках; четвёртый случай (разрез слева от x и слева от y) аналогичен предыдущему.
Для любой RMS, любого агента i и любой константы существует чуть другая RMS со следующими свойствами: новая мера оценок агента i полностью идентична его старой мере оценок; новые меры оценок других двух агентов идентичны их старым мерам везде, за исключением окрестностей точек x и y.
Это означает, что если запрос отвечает как-то на вопрос вне окрестностей x и y, у агента i нет способа узнать, была ли это старая RMS, или новая RMS.
Обладая этим знанием, можно запутать любой протокол завистливого дележа, чтобы он длился бесконечно: начнём с любой RMS, например с параметров ; если протокол делает разрезы вне точек x и y, просто продолжим; когда протокол спрашивает участника i сделать разрез в x или y, переключаемся на другую RMS с и , удостоверившись, что значения будут теми же, что и для предыдущих разрезов.
Этот протокол не может никогда сделать разрез в правильных точках 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-мультиразбиение. Денг, Ки и Сабери предложили модификацию протокола разрезания торта Симмонса, в которой находится свободное от зависти -мультиразбиение с помощью запросов. Более того, они доказали нижнюю границу в запросов. Даже когда функции полезности заданы явно алгоритмами полиномиального времени, разрезание торта без зависти является задачей.
Основанная на значениях аппроксимация использует следующие обозначения: разбиение X называется -свободным от зависти, если существует перестановка участников, при которой для любого i значение i-го куска плюс не меньше значения любого другого куска: ; мера оценки называется непрерывной по Липшицу, если существует константа K, такая что для любой пары отрезков разница их значений не превосходит K-кратной длины их симметрической разности .