Делёж обязанностей

Задача является зеркальным отражением задачи справедливого разрезания торта, в которой делимый ресурс желателен, так что участники дележа хотят получить как можно больше. Как первая, так и вторая задачи имеют неоднородные ресурсы. При дележе торта, например, торт может иметь крайние, угловые и срединные куски c различным содержанием глазировки. При дележе обязанностей работы могут иметься различные виды обязанностей и различное количество времени для выполнения каждой работы. Обе задачи предполагают, что ресурсы могут быть поделены. Виды работ можно делить бесконечно, поскольку конечный набор работ может быть разделён на различные типы, форматы и требовать разного времени на их выполнение. Например, загрузка в стиральную машину может быть разделена на число предметов одежды и на время, потраченное на загрузку машины. Задачи, однако, отличаются по желательности ресурса. Задачу дележа обязанностей предложил Мартин Гарднер в 1978[1].

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

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

Определение пропорционального дележа для дележа обязанностей является зеркальным отражением аналогичного термина для разрезания торта — каждый участник ${\displaystyle i}$ должен получить часть ${\displaystyle X_{i}}$ в худшем случае согласно его собственной функции нежелательности, не более ${\displaystyle {\tfrac {1}{n}}}$ от полного значения (где ${\displaystyle n}$ равно полному числу участников):

${\displaystyle \forall i:V_{i}(X_{i})\leqslant V_{i}(Whole)/n}$

Большинство протоколов для пропорционального разрезания торта может быть легко перенесено на делёж обязанностей. Например:

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

Процедуры беспристрастного и точного дележа работают одинаково хорошо для разрезания торта и для дележа обязанностей, поскольку они гарантируют одинаковые значения. Примером является процедура «Движущийся нож» Остина, гарантирующая, что каждому участнику достанется кусок, который оценивается ровно в ${\displaystyle {\tfrac {1}{n}}}$ полной оценки ресурса.

Определение отсутствия зависти при дележе обязанностей является зеркальным отражением определения для дележа торта — каждый участник ${\displaystyle i}$ должен получить часть ${\displaystyle X_{i}}$, которая оценивается им, согласно его собственной персональной оценке уровня неприятности, как меньшая или равная любой другой части:

${\displaystyle \forall i,j:V_{i}(X_{i})\leqslant V_{i}(X_{j})}$

Для двух участников процедура дели-и-выбирай даёт делёж обязанностей без зависти. Однако для трёх и более участников ситуация более сложная. Основной трудностью является усечение — действие на кусок торта, чтобы сделать его равным по ценности другому куску (как делается, например, в процедуре Селфриджа — Конвея). Это действие нельзя перенести простым образом на сценарий дележа обязанностей.

Гейдрих и Сти[9] вычислили цену справедливости при дележе обязанностей, если части должны быть связны.

Можно использовать процедуру дележа обязанностей для дележа работ и затрат стран на уменьшение изменений климата. Проблемы связаны с моральными аспектами и необходимостью кооперации наций. Однако использование процедуры дележа обязанностей уменьшает необходимость наднациональной власти для дележа и наблюдения за соблюдением работ этими нациями[10].

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

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