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

Процесс справедливого распределения ресурсов

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

Нерешенная проблема в информатике :

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

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

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

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

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

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

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

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

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

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

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

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

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

Для случая связанных частей было отмечено, что результат твердости предполагает, что весь торт должен быть разделен. Если это требование заменить более слабым требованием, чтобы каждый партнер получал пропорциональную стоимость (по крайней мере 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]

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

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

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

Постройте набор из трех мер со следующими двумя свойствами:

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

Тогда каждое разделение без зависти между Алисой, Бобом и Карлом должно иметь разрезы в точках 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.

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

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-мульти-раздел, который свободен от зависти. Дэн и др. ^[6] представляют модификацию протокола разрезания торта Симмонса , которая находит свободный от зависти δ -мульти-раздел с помощью запросов. Более того, они доказывают нижнюю границу запросов. Даже когда функции полезности заданы явно с помощью алгоритмов с полиномиальным временем, задача разрезания торта без зависти является PPAD -полной. ${\displaystyle O[(1/\delta )^{n-2}]}$ ${\displaystyle \Omega [(1/\delta )^{n-2}/2^{(n-1)(n-2)}]}$

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

• Разбиение X называется ε-свободным от зависти , если существует перестановка участников, такая, что для каждого i стоимость i -го куска плюс ε по крайней мере равна стоимости любого другого куска: . ${\displaystyle \forall i,j:V_{i}(X_{i})+\varepsilon \geq V_{i}(X_{j})}$
• Мера значения называется липшицево-непрерывной, если существует константа K такая, что для любой пары интервалов разность значений между ними не превышает K , умноженных на длину их симметричной разности . ${\displaystyle \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})}$

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

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

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

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

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

• Для 3 агентов пропорциональность равна , т.е. пропорциональное и свободное от зависти разделение достижимо за ограниченное время. ^[11] ${\displaystyle 1/3}$
• Для 4 агентов пропорциональность равна . ^[11] ${\displaystyle 1/7}$
• Для n агентов пропорциональность равна . ^[2] ${\displaystyle 1/(3n)}$

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

Варианты

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

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

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

Разъединенные части

Процедуры

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

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

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

Для четырех или более партнеров существует три алгоритма, которые являются конечными, но неограниченными — нет фиксированного предела на количество требуемых разрезов. ^[17] Существует три таких алгоритма:

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

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

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

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

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

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

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

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

A. Предположим, что торт представляет собой одномерный интервал [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, или где-то между ними.

B. Интервал между двумя последовательными ориентирами партнера i называется ориентир-интервалом партнера i . Когда алгоритм решает выделить кусок торта партнеру i , он должен выделить кусок, общая стоимость которого для i по крайней мере такая же большая, как любой ориентир-интервал i . Доказательство от противного: предположим, что существует определенный ориентир-интервал J , стоимость которого для i больше стоимости, фактически выделенной для i . Какой-то другой партнер, скажем, j , обязательно получит некоторую часть ориентир-интервала J . Согласно пункту A, возможно, что вся стоимость интервала J сосредоточена внутри доли, выделенной партнеру j . Таким образом, i завидует 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 ² ).

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

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

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

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

Вот еще несколько вариантов:

• Сильная свобода от зависти требует, чтобы каждый агент строго предпочитал свой набор другим наборам. ^[23]
• Супер-свобода от зависти требует, чтобы каждый агент строго предпочитал свой набор 1/ n от общей стоимости и строго предпочитал 1/ n каждому из других наборов. ^{[23] [24]} Очевидно, что супер-свобода от зависти подразумевает сильную свободу от зависти, которая подразумевает свободу от зависти.

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

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

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

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

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

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

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

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

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

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

• Функции аддитивного значения, одномерный торт (интервал), и части должны быть соединены интервалами. ^[26]
• Аддитивные функции значений, многомерный симплексный торт, и части должны быть симплексами. ^[27] Доказательство использует теорему Шпернера , лемму ККМ , лемму Гейла о покрытии и лемму Ки Фана о точках совпадения .

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

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

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

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

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

Смотрите также

• Разделение обязанностей без зависти
• Назначение предметов без зависти
• Справедливое разделение пирогов
• Групповая-зависть-свободная
• Пропорциональное разрезание торта

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

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

Ссылки

1. Гамов, Джордж; Стерн, Марвин (1958). Головоломка-математика. Viking Press. ISBN 978-0670583355.
2. Азиз, Харис; Маккензи, Саймон (2016). «Дискретный и ограниченный протокол разрезания торта без зависти для любого числа агентов». 57-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS) 2016 года . Нью-Брансуик, Нью-Джерси, США: IEEE. стр. 416–427. arXiv : 1604.03655 . Bibcode :2016arXiv160403655A. doi :10.1109/FOCS.2016.52.
3. Стромквист, Уолтер (1980). «Как честно разрезать торт». The American Mathematical Monthly . 87 (8): 640–644. doi :10.2307/2320951. JSTOR  2320951.
4. Стромквист, Уолтер (2008). «Беззавистные дележи торта не могут быть найдены с помощью конечных протоколов» (PDF) . Электронный журнал комбинаторики . 15 . doi :10.37236/735.
5. Процедура перемещения ножей Стромквиста требует, чтобы три агента корректировали свои ножи всякий раз, когда меч судьи движется. Поскольку меч движется непрерывно, количество требуемых шагов — несчетная бесконечность. Протокол разрезания торта Симмонса сходится к разделению без зависти, но для сходимости может потребоваться бесконечное количество шагов.
6. Deng, X.; Qi, Q.; Saberi, A. (2012). «Алгоритмические решения для разрезания торта без зависти». Исследование операций . 60 (6): 1461–1476. doi :10.1287/opre.1120.1116. S2CID  4430655.
7. Бранзеи, Симина; Нисан, Ноам (2022-12-06). «Сложность запроса при разрезании торта». Достижения в области нейронных систем обработки информации . 35 : 37905–37919., arXiv :1705.02946.
8. Голдберг, Пол В.; Холлендер, Александрос; Суксомпонг, Варут (2020). «Непрерывное разрезание торта: результаты по твердости и алгоритмы аппроксимации». Журнал исследований искусственного интеллекта . 69 : 109–141. arXiv : 1911.05416 . doi : 10.1613/jair.1.12222. S2CID  221865778.
9. Brânzei, S. (2015). «Заметка о разделке торта без зависти с полиномиальными оценками». Information Processing Letters . 115 (2): 93–95. doi :10.1016/j.ipl.2014.07.005.
10. Алиджани, Реза; Фархади, Маджид; Годси, Мохаммед; Седдигин, Масуд; Таджик, Ахмад С. (10 февраля 2017 г.). «Механизмы без зависти с минимальным количеством сокращений». Тридцать первая конференция AAAI по искусственному интеллекту . 31 . дои : 10.1609/aaai.v31i1.10584 . S2CID  789550.
11. Сегал-Халеви, Эрель; хасидим, Авинатан; Ауманн, Йонатан (2016). «Отходы торопят». Транзакции ACM на алгоритмах . 13 : 1–32. arXiv : 1511.02599 . дои : 10.1145/2988232. S2CID  11358086.
12. Эрель Сегал-Халеви и Авинатан Хассидим и Йонатан Ауманн (январь 2015 г.). Разрезание торта без зависти в двух измерениях . 29-я конференция AAAI по искусственному интеллекту (AAAI-15). Остин, Техас. стр. 1021–1028. doi :10.13140/RG.2.1.5047.7923.
13. Далл'Альо, М.; Макчерони, Ф. (2009). «Спорные земли» (PDF) . Игры и экономическое поведение . 66 : 57–77. дои : 10.1016/j.geb.2008.04.006.
14. Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Cambridge University Press. ISBN 0-521-55644-9.
15. Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). "Решение с помощью движущегося ножа для деления торта без зависти четырьмя лицами" (PDF) . Труды Американского математического общества . 125 (2): 547–555. doi :10.1090/S0002-9939-97-03614-9. S2CID  17233874 . Получено 2 сентября 2014 г. .
16. Амин Сабери и Ин Ван (2009). Разрезание торта на пять человек . Алгоритмические аспекты в информации и управлении. doi :10.1007/978-3-642-02158-9_25.
17. SJ Brams, MA Jones и C. Klamler, «Лучшие способы нарезать торт», Notices of the AMS, 2005. [Онлайн]. Доступно: http://www.ams.org/notices/200611/fea-brams.pdf
18. Pikhurko, O. (2000). «О разделении торта без зависти». The American Mathematical Monthly . 107 (8): 736–738. doi :10.2307/2695471. JSTOR  2695471.
19. Гасарч, Уильям (2015). «Какой неограниченный протокол для разрезания торта без зависти лучше?». arXiv : 1507.08497 [math.LO].
20. Азиз, Харис; Маккензи, Саймон (2016). «Дискретный и ограниченный протокол разрезания торта без зависти для четырех агентов». Труды 48-го ежегодного симпозиума ACM SIGACT по теории вычислений – STOC 2016. стр. 454. arXiv : 1508.05143 . doi : 10.1145/2897518.2897522. ISBN 9781450341325.
21. Курокава, Дэвид; Лай, Джон К.; Прокачча, Ариэль Д. (2013). «Как разрезать торт до окончания вечеринки». AAAI . 27 : 555–561. doi : 10.1609/aaai.v27i1.8629 . S2CID  12638556 . Получено 2 сентября 2014 г. .
22. Прокачча, Ариэль (2009). «Возжелай пирога ближнего твоего». Труды IJCAI'09 21-й Международной объединенной конференции по искусственному интеллекту : 239–244.
23. Barbanel, Julius B. (1996-01-01). "Суперсвободное от зависти разделение тортов и независимость мер". Журнал математического анализа и приложений . 197 (1): 54–60. doi : 10.1006/S0022-247X(96)90006-2 . ISSN  0022-247X.
24. Вебб, Уильям А. (1 ноября 1999 г.). «Алгоритм для суперсвободного от зависти деления торта». Журнал математического анализа и приложений . 239 (1): 175–179. doi : 10.1006/jmaa.1999.6581 . ISSN  0022-247X.
25. Цзэн, Дао-Чжи (2000). «Приблизительные процедуры без зависти». Игровая практика: вклад из прикладной теории игр . Библиотека теории и принятия решений. Том 23. Springer. С. 259–271. doi :10.1007/978-1-4615-4627-6_17. ISBN 9781461546276.
26. Идзик, Адам (1995). Оптимальные деления единичного интервала . Международная конференция в честь Роберта Дж. Ауманна в день его 65-летия. Иерусалим.
27. Ичииси, Т.; Идзик, А. (1999). «Справедливое распределение делимых благ». Журнал математической экономики . 32 (4): 389–400. doi :10.1016/s0304-4068(98)00053-6.
28. Пропорциональность = ценность (как доля всего пирога), которая гарантирована каждому агенту с аддитивными оценками. Когда нет зависти и весь пирог разделен, пропорциональность всегда равна 1/ n , что является наилучшим возможным.