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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завистливый делёж 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. Назовём эту область . При использовании некоторой топологической леммы (которая аналогична лемме Кнастера — Куратовского — Мазуркевича[англ.]), можно доказать, что пересечение всех Ui непусто. Следовательно, существует разбиение, в котором каждый кусок является единственным, который предпочитает агент. Поскольку число кусков равно числу агентов, мы можем распределить каждый кусок агенту, который его предпочитает и получим распределение без зависти.

Процедуры

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

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

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

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

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

Разбиение без зависти со связными кусками для 3 и более агентами не может быть найдено конечным протоколом[4]. Причина этого результата не противоречит упомянутым выше алгоритмам, поскольку они не конечны в математическом смысле[5].

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

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

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

  • плотность каждой меры строго между и (так что для заданного куска оценки агентов отличаются не более чем вдвое);
  • значения кусков, определяемых числами 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 и любой константы существует чуть другая 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-мультиразбиение. Денг, Ки и Сабери[6] предложили модификацию протокола разрезания торта Симмонса, в которой находится свободное от зависти -мультиразбиение с помощью запросов. Более того, они доказали нижнюю границу в запросов. Даже когда функции полезности заданы явно алгоритмами полиномиального времени, разрезание торта без зависти является PPAD-сложной[англ.] задачей.

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

  • разбиение X называется -свободным от зависти, если существует перестановка участников, при которой для любого i значение i-го куска плюс не меньше значения любого другого куска: ;
  • мера оценки называется непрерывной по Липшицу, если существует константа K, такая что для любой пары отрезков разница их значений не превосходит K-кратной длины их симметрической разности .

Если все меры оценок непрерывны по Липшицу, то два определения аппроксимации связаны. Пусть . Тогда любое разбиение в -мультиразбиении без зависти является -свободным от зависти[6]. Следовательно, результаты Денга, Ки и Сабери доказывают, что если все участники имеют непрерывные по Липшицу оценки, -свободное от зависти разбиение можно найти с помощью запросов.

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

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

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

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

Варианты

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

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

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

Процедуры

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

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

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

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

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

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

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

Если все меры кусочно линейны, существует полиномиальный от размера представления функций оценок алгоритм [18]. Число его запросов равно , где равно числу разрывов в производных функций плотности оценок.

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

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

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

Каждый вопрос, на который ответил участник i, вводит максимум две новые конечные точки, так что число вех для участника i увеличивается не более чем на 2. Следовательно, в случае, описанном в пункте C, алгоритм должен опросить каждого из участников, задав по меньшей мере n/4 вопросов. Полное число вопросов тогда будет не меньше .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

число агентов Связные куски Куски общего вида
2 Дели-и-выбирай
3 Процедура «Движущийся нож» Стромквиста (бесконечное время); «Поспешишь — людей насмешишь» (ограниченное время, ограниченное число разрезов, возможен отбрасываемый кусок, пропорциональное) Дискретная процедура Селфриджа — Конвея (ограниченное время, не более 5 разрезов).
4 «Поспешишь — людей насмешишь» (ограниченное время, ограниченное число разрезов, возможен отбрасываемый кусок, пропорциональность 1/7). Процедура Брамса — Тейлора — Цвикера (бесконечное время, не более 11 разрезов). Дискретная процедура Сабери — Вонга[13] (ограниченное время, ограниченное число разрезов, возможен отбрасываемый кусок, пропорциональная). Дискретная процедура Азиза — Маккензи[17] (ограниченное время, ограниченное число разрезов, пропорциональная).
5 Процедуры «Движущийся нож» Сабери — Вонга[13] (бесконечное время, ограниченное число разрезов).
n протокол Симмонса (бесконечное время) Денга — Ки — Сабери (приближённо свободный от зависти, экспоненциальное время). «Поспешишь — людей насмешишь» (полностью свободен от зависти, экспоненциальное время, возможен отбрасываемый кусов, экспоненциальная пропорциональность) ConnectedPieces Азиза — Маккензи[9] (полностью свободен от зависти, экспоненциальное время, возможен отбрасываемый кусок, линейная пропорциональность) Брамс и Тейлор (1995); Робертсон и Уэбб (1998). — Оба алгоритма требуют конечного, но не ограниченного числа разрезов.

Дискретная процедура Азиза — Маккензи[9] (ограниченное время, ограниченное число разрезов, пропорциональный делёж).

Трудность Все алгоритмы для должны быть бесконечными (Stromquist, 2008). Все алгоритмы должны использовать по меньшей мере шагов (Procaccia, 2009).
Варианты Взвешенное разбиение без зависти существует для произвольных весов (Idzik, 1995), даже когда торт и куски являются симплексами (Idzik, Ichiishi, 1996), и даже с неаддитивными предпочтениями (Dall’Aglio, Maccheroni, 2009). Протокол Робертсона — Уэбба может найти взвешенное свободное от зависти разбиение для произвольных весов. Совершенный делёж существует (Dubins&Spanier, 1961). Существует свободное от зависти и эффективное разрезание торта (Теорема Веллера).

См. также

Примечания

  1. Часто переводится буквально с английского как разрезание торта без зависти (англ. Envy-free cake-cutting), хотя именно зависть и играет ключевую роль в данном дележе. В статье используется термин "завистливый делёж", но результат этого дележа должен быть распределением без зависти.
  2. Gamow, Stern, 1958.
  3. Stromquist, 1980, с. 640–644.
  4. Stromquist, 2008.
  5. Процедура «Движущийся нож» Стромквиста требует, чтобы агенты перемещали свои ножи пока рефери передвигает свой меч. Поскольку движение меча непрерывно, число требуемых шагов несчётно (а потому, естественно, бесконечно). Протоколом разрезания торта Симмонса сходится к свободному от зависти разбиению, но может потребоваться бесконечное число шагов.
  6. 1 2 Deng, Qi, Saberi, 2012, с. 1461–1476.
  7. 1 2 Brânzei, 2015, с. 93–95.
  8. 1 2 Segal-Halevi, Hassidim, Aumann, 2016, с. 1–32.
  9. 1 2 3 4 5 6 Aziz, MacKenzie, 2016.
  10. Segal-Halevi, Hassidim, Aumann, 2015, с. 1021–1028.
  11. Brams, Taylor, 1996, с. 124–125.
  12. Brams, Taylor, Zwicker, 1997, с. 547–555.
  13. 1 2 3 4 5 Saberi, Wang, 2009.
  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 Архивная копия от 30 сентября 2019 на Wayback Machine
  15. 1 2 Pikhurko, 2000, с. 736–738.
  16. Gasarch, William. "Which Unbounded Protocol for Envy Free Cake Cutting is Better?". arXiv:1507.08497 [math.LO]. {{cite arXiv}}: Неизвестный параметр |год= игнорируется (справка)
  17. 1 2 3 Aziz, MacKenzie, 2016, с. 454.
  18. 1 2 Kurokawa, Lai, Procaccia, 2013.
  19. Procaccia, 2009, с. 239–244.
  20. Zeng, 2000, с. 259–271.
  21. Idzik, 1995.
  22. Ichiishi, Idzik, 1999, с. 389–400.
  23. Dall'Aglio, MacCheroni, 2009, с. 57–77.
  24. Значение (как доля от всего торта), которая гарантирована каждому агенту при аддитивных оценках. Когда нет зависти и весь торт разделен, пропорциональность всегда равна , лучшая из возможных.

Литература

Ссылки

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

Read other articles:

Chemical compound Harmane Names Preferred IUPAC name 1-Methyl-9H-pyrido[3,4-b]indole Other names Harman, Aribine, Aribin, Locuturine, Locuturin, Loturine, Passiflorin, 1-Methylnorharman, NSC 54439 Identifiers CAS Number 486-84-0 Y 3D model (JSmol) Interactive image ChEBI CHEBI:5623 ChemSpider 4444755 ECHA InfoCard 100.006.948 EC Number 207-642-2 KEGG C09209 PubChem CID 5281404 UNII 82D6J0535P Y CompTox Dashboard (EPA) DTXSID80197568 InChI InChI=1S/C12H10N2/c1-8-12-10(6-7-13-8)9-4-2-...

 

Pour les articles homonymes, voir Duplex et Canal. Communication half-duplex. Communication full-duplex. En télécommunications, un canal de communication duplex est un canal de communication qui transporte l'information dans les deux sens (bidirectionnel). Selon que l'information peut être transportée simultanément dans les deux sens ou non, on parle respectivement de canal full-duplex ou half-duplex (également appelé à l'alternat). Un canal qui transporte l'information dans un seul ...

 

Seorang pasien yang sedang di CT scan. Tomografi terkomputasi (Inggris: computed tomography, CT), awalnya dikenal sebagai computed axial tomography (CAT), adalah sebuah metode penggambaran medis menggunakan tomografi di mana pemrosesan geometri digunakan untuk menghasilkan sebuah gambar tiga dimensi bagian dalam sebuah objek dari satu seri besar gambar sinar-X dua dimensi diambil dalam satu putaran axis. Kata tomografi berasal dari bahasa Yunani tomos (potongan) dan graphia (penggambaran)...

Voce principale: Associazione Sportiva Dilettantistica Junior Biellese Libertas. U.S. BielleseStagione 1922-1923Sport calcio Squadra Biellese Seconda DivisioneCampione italiano di Seconda Divisione. StadioCampo Sportivo Rivetti 1921-1922 1923-1924 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'Unione Sportiva Biellese nelle competizioni ufficiali della stagione 1922-1923. Indice 1 Rosa 2 Risultati 2.1 Seconda Divisione 2.1.1 Girone B 2.1.1.1 G...

 

Yang MuliaAntonius Subianto BunjaminO.S.C.Uskup BandungKetua Konferensi Waligereja IndonesiaMgr. Antonius Subianto Bunjamin, O.S.C. pada 2014GerejaKatolik RomaProvinsi gerejawiJakartaKeuskupanBandungPenunjukan3 Juni 2014 (9 tahun, 326 hari)PendahuluJohannes PujasumartaJabatan lainKetua Konferensi Waligereja IndonesiaImamatTahbisan imam26 Juni 1996 (27 tahun, 303 hari)oleh Alexander Soetandio DjajasiswajaTahbisan uskup25 Agustus 2014 (9 tahun, 243 hari)oleh&#...

 

Historic sovereign territory set aside for Native American nations, 1834–1907 Not to be confused with Indian reservation or Indian reserve. This article is about the historical territory in the United States of America. For states and union territories of India, see States and union territories of India. For other uses, see Indian country. Indian TerritoryUnorganized territory of independent Indian nations of the United States1834–1907The Oklahoma (west of the red line) and Indian Territo...

Merrillville redirects here. For the unincorporated community in Georgia, see Merrillville, Georgia. Town in Indiana, United StatesTown of Merrillville, IndianaTownMerrillville's skyline in May 2012 SealLocation of Merrillville in Lake County, Indiana.Coordinates: 41°29′08″N 87°20′07″W / 41.48556°N 87.33528°W / 41.48556; -87.33528CountryUnited StatesStateIndianaCountyLakeTownshipRossGovernment • TypeTown • Town ManagerPatrick J. Rear...

 

Branch of the Danish royal family that formerly reigned over Greece For an overview of the monarchs of Greece, see List of kings of Greece. Greek royal familyΒασιλική Οικογένεια της Ελλάδος (Greek)House of Glücksburg-GreeceHouse of Glücksburg-HellasGreater coat of arms since 1936The personal standard of the kings of GreeceParent familyHouse of GlücksburgCountry Kingdom of GreecePlace of originGlücksburg, Schleswig-HolsteinFounded30 March 1863FounderGeorge ...

 

Football leagueKTFF 1. LigFounded1955Country Northern CyprusNumber of teams16Level on pyramid2Promotion toKTFF Süper LigRelegation toBTM 1. LigDomestic cup(s)Cypriot Cup (Northern Cyprus)KTFF Super CupCurrent championsÇetinkaya Türk S.K. (1st title) (2021-22)Most championshipsYalova (5 titles)Current: 2022-23. KTFF 1. Lig KTFF 1. Lig (English: CTFA First League), officially AKSA 1. Lig for sponsorship reasons, formerly known as İkinci Lig (literally Second League) is the second-highe...

Benteng San Carlos de La Cabaña Benteng San Carlos de la Cabaña, Havana, Kuba Fortaleza de San Carlos de la Cabaña (Benteng Santo Charles), yang lebih dikenal sebagai La Cabaña, adalah sebuah kompleks benteng abad ke-18, ketiga terbesar di benua Amerika, terletak di sisi timur bagian depan pelabuhan di Havana, Kuba. Benteng tersebut berada di atas ketinggian puncak bukit 200 kaki (60 m), bersama dengan Istana Morro (benteng). Pada Januari 1959, para pemberontak komunis pimpinan Fidel Cast...

 

Pemilihan umum Gubernur Bali 20132008201815 Mei 2013Kandidat   Calon I Made Mangku Pastika A.A.G.N. Puspayoga Partai Demokrat PDI-P Pendamping I Ketut Sudikerta Dewa Nyoman Sukrawan Suara rakyat 1.063.734 1.062.738 Persentase 50,02% 49,98% Peta persebaran suara Peta lokasi Bali Gubernur dan Wakil Gubernur petahanaI Made Mangku Pastika dan Puspayoga PDI-P Gubernur dan Wakil Gubernur terpilih I Made Mangku Pastika dan Sudikerta Demokrat Pemilihan umum Gubernur Bali 2013 dilaksanakan ...

 

Journey of HopePoster filmSutradaraXavier KollerProduserPeter-Christian FueterAlfi SinnigerDitulis olehFeride ÇiçekoğluXavier KollerPemeranNur SürerNecmettin Cobanoglu Mathias GnädingerYaman OkaySinematograferElemér RagályiGalip IyitanirPenyuntingDaniel GibelDistributorMiramax (perilisan AS)Tanggal rilis Agustus 1990 (1990-08) (Locarno) Durasi110 menitNegaraSwissTurkiBahasaTurkiJerman SwissItalia Journey of Hope (Jerman: Reise der Hoffnungcode: de is deprecated ; Turki: Um...

Saltwater State ParkLocation in the state of WashingtonShow map of Washington (state)Saltwater State Park (the United States)Show map of the United StatesLocationKing, Washington, United StatesCoordinates47°22′22″N 122°19′24″W / 47.37278°N 122.32333°W / 47.37278; -122.32333Area137 acres (55 ha)OperatorWashington State Parks and Recreation CommissionWebsiteSaltwater State Park Saltwater State Park is a 137 acres (0.55 km2) plot of second-growth ti...

 

American historian of the Cold War (born 1941) John Lewis GaddisGaddis speaking to U.S. Naval War College (NWC) faculty during the Teaching Grand Strategy workshop at the NWCBorn (1941-04-02) April 2, 1941 (age 83)Cotulla, Texas, U.S.EducationUniversity of Texas, Austin (BA, MA, PhD)Occupation(s)Military historian, political scientist, writerEraContemporary philosophyRegionWestern philosophySchoolNeorealismInstitutionsOhio UniversityYale UniversityNaval War CollegeUniversity of OxfordPri...

 

1909 massacre of Armenian Christians by Ottoman Muslims This article contains too many or overly lengthy quotations. Please help summarize the quotations. Consider transferring direct quotations to Wikiquote or excerpts to Wikisource. (April 2023) Adana massacrePart of the persecution of Armenians, persecution of Assyrians and the late Ottoman genocidesA street in the Christian quarter of Adana, photographed in June 1909.LocationAdana, Ottoman EmpireDateApril 1909TargetMainly Armenian civilia...

Plants endemic to Romania Caltha palustris near the Făgăraș Mountains of Romania More than 1,000 plant species can be found in the Cheile Turzii reserve The flora of Romania comprises around 3,450 species of vascular plants, which represents around 30% of the vascular flora of Europe.[1] The three major vegetation zones in Romania are the alpine, steppe, and forest zones.[2] The latter can be subdivided (depending on soil, climate, and altitude) into regions dominated by th...

 

2022年密歇根州聯邦眾議員選舉 ← 2020 2022年11月8日 2024 → 密歇根州聯邦眾議員全部13個議席   多數黨 少數黨   政党 民主党 共和黨 上届结果 7 7 赢得席次 7 6 席次差额 ━ ▼ 1 民選得票 2185663 2087277 得票率 49.83% 47.59% 得票变动 ▲ 0.25% ▼ 0.68% 結果    民主黨奪得     共留和黨奪得    民主黨把持     �...

 

Croatian footballer (born 1984) This sports biography does not cite any sources containing significant coverage. Please help improve this article by adding citations to sources containing significant coverage. Sports biographies without significant coverage violate the requirement for such articles and may be deleted.Find sources: football – news · newspapers · books · scholar · JSTOR (January 2023) (Learn how and when to remove this message) Lovre Vul...

Questa voce sugli argomenti dirigenti sportivi statunitensi e cestisti statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Rex ChapmanNazionalità Stati Uniti Altezza193 cm Peso84 kg Pallacanestro RuoloGuardia Termine carriera2000 CarrieraGiovanili Apollo High School1986-1988 Kentucky Wildcats Squadre di club 1988-1992 Charlotte Hornets220 (3.574)1992-1995 Washington Bullet...

 

Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Pour l’article ayant un titre homophone, voir Tours. Sur les autres projets Wikimedia : tour, sur le Wiktionnaire Tour peut faire référence à : Patronyme Tour est un nom de famille notamment porté par : Yves Tour (1933-2017), joueur et dirigeant français de rugby à XV. Toponyme Tour est un nom de lieu notamment porté par : Belgique Tour, hameau de la commune de Durbuy...