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

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

Общее обсуждение задачиПравить

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

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

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

Пропорциональный делёж обязанностейПравить

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

\text{[math]}

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

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

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

Беспристрастный и точный делёж обязанностейПравить

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

Завистливое распределение обязанностейПравить

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

\text{[math]}

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

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

Дискретная процедура Оскуи для трёх участниковПравить

Реза Оскуи первым предложил процедуру дележа обязанностей для трёх участников. Его работа формально никогда не была опубликована и упомянута лишь в работе Робертсона и Уэбба^[2]. Протокол подобен протоколу Селфриджа — Конвея, но более сложен — он требует 9 разрезов вместо 5 разрезов.

Ниже в дележе принимают участие Алиса, Боб и Карл.

Первый шаг. Алиса делит работы на три части, равные в её глазах (это также первый шаг в протоколе Селфриджа — Конвея). Боб и Карл указывают на наименьшие куски (по их мнению). Простым случаем будет случай, когда они указывают на разные доли, поскольку тогда мы можем дать каждому участнику наименьшую (по его мнению) долю, и мы совершили делёж. Сложным является случай, когда они указывают на одну и ту же долю. Обозначим часть работ, которую и Боб, и Карл считают наименьшей, как X1, а другие два куска как X2 и X3.

Второй шаг. Просим Боба и Карла отметить на каждой из частей X2 и X3, где нужно отрезать от них, чтобы сделать их равными X1. Рассмотрим несколько случаев.

Случай 1. Объем, который отрезает Боб, меньше. То есть, Боб отрезает от X2 до X2', а от X3 до X3', так что и X2', и X3', по его мнению, одинаковы с X1, а Карл думает, что X1 остаётся наименьшей частью, не больше X2' и X3'. Тогда следующий делёж свободен от зависти:

Карл получает X1;
Алиса получает меньший из X2' и X3' (обе части в её глазах меньше X1);
Боб получает кусок, который не взяла Алиса (обе части для него равны X1).

Теперь мы должны разделить отрезанные от X2 и X3 части. Для каждой отрезанной части делаем следующее:

Боб делит их на три равные части;
Участники выбирают части в таком порядке: Карл, Алиса, Боб.

Карл теперь не завидует, поскольку он выбирает первым. Боб не завидует, поскольку он разрезал. Алиса не завидует, поскольку она имеет (отрицательное) преимущество над Карлом — на первом шаге Карл выбрал X1, в то время как Алиса взяла часть, которая меньше, чем X1, в то время как на последнем шаге Алиса забрала кусок, который не хуже (X2+X3)/2.

Случай 2. Объем, который отрезает Карл, меньше. То есть, если Карл отрезает от X2 до X2', а от X3 до X3' таким образом, что и X2', и X3' для него так же малы, как и X1, то Боб по-прежнему думает, что X1 является самым маленьким, не больше, чем X2' и X3'. Тогда мы действуем так же, как и в случае 1, поменяв роли Боба и Карла.

Случай 3. Объем, который отрезает Боб, меньше для X2, а объем, который отрезает Карл, меньше для X3. То есть, если после того, как Боб отрезал от куска X2, получается X2', который в его глазах равен куску X1, а Карл получает после того, как отрезал от куска X3, кусок X3', который в его глазах равен X1, то:

для Карла: $\text{[math]}$ $\text{[math]}$ $X2'\geqslant X1=X3'$
для Боба: $\text{[math]}$ $\text{[math]}$ $X3'\geqslant X1=X2'$

Тогда следующий частичный делёж не имеет зависти:

Алиса получает меньший из X2' и X3' (для неё обе части меньше, чем X1);
Боб получает либо X2' (если эту часть не забрала Алиса), либо X1 (в противном случае);
Карл получает либо часть X3' (если её не забрала Алиса), или X1 (в противном случае).

Отрезанные части X2 и X3 делятся аналогично случаю 1.

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

процедура «Движущийся нож» Стромквиста;
процедура вращающегося ножа^[3].

Непрерывная процедура Петерсона и Су для трёх и четырёх участниковПравить

Петерсон и Су^[4] предложили другую процедуру для трёх участников. Она проще и более симметрична, чем процедура Оскуи, но она не дискретна, поскольку опирается на процедуру движущегося ножа. Основной идеей этой процедуры является делёж обязанностей на шесть частей и передача каждому участнику двух кусков, которые они считают меньше частей, полученных другими участниками.

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

Второй шаг.

С помощью процедуры «Движущийся нож» Остина делим кусок 1 на две части, которые участники 1 и 2 считают одинаковыми. Пусть участник 3 выбирает часть, которая в его глазах меньше, а оставшуюся часть отдаём участнику 2.
Аналогично делим кусок 2 на две части, которые участники 2 и 3 считают равными, и позволим участнику 1 выбрать меньшую из двух частей, а оставшуюся часть отдадим участнику 3.
Аналогично делим кусок 3 на две части, которые участники 3 и 1 считают равными, и позволим участнику 2 выбрать меньшую из двух частей, а оставшуюся часть отдадим участнику 1.

Анализ. Участник 1 имеет две разрезанные части — одна часть от куска 2 и одна от куска 3. В глазах участника 1, часть куска 2 меньше, чем часть, отданная участнику 3, а часть куска 3 меньше, чем часть, переданная участнику 2. Более того, обе этих отрезанные части меньше, чем части куска 1, поскольку кусок 1 больше как куска 2, так и куска 3 (согласно первому шагу). Поэтому участник 1 считает, что его доля не больше каждой из двух других долей. То же самое рассуждение применимо к участникам 2 и 3. Следовательно, при таком дележе будет отсутствовать зависть.

Петерсон и Су расширили их непрерывную процедуру до четырёх участников^[4].

Дискретная процедура Петерсона и Су для любого числа участниковПравить

Существование дискретной процедуры для пяти и более участников оставалось открытым вопросом до 2009, когда Петерсон и Су опубликовал процедуру для n участников^[5]. Процедура аналогична процедуре Брамса — Тейлора и использует ту же идею неотъемлемого преимущества. Вместо отрезания они использовали добавление из резерва.

Дискретная и ограниченная процедура Дехгани с соавторами для любого числа участниковПравить

Петерсон и Су привели процедуру «движущегося ножа» для дележа обязанностей для 4-х лиц. Дехгани с соавторами^[6] дал первый дискретный ограниченный протокол для дележа обязанностей без зависти среди любого числа агентов.

Процедуры для связных кусковПравить

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

процедура «Движущийся нож» Робертсона — Уэбба^[7];
процедура «Движущийся нож» Стромквиста^[8];
протоколы Симмонса — Су. Симмонс первоначально разработал протокол для приближённого дележа торта без зависти со связными кусками, основываясь на лемме Шпернера. Су показал, используя двойственную лемму, что аналогичный протокол может быть использован для приближённого дележа обязанностей без зависти. В частности, он показал, что всегда существует делёж обязанностей без зависти со связными кусками.

Цена справедливостиПравить

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

ПриложенияПравить

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

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

См. такжеПравить

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

ПримечанияПравить

↑ Gardner, 1978.
↑ Robertson, Webb, 1998, с. 73–75.
↑ Robertson, Webb, 1998, с. 77–78.
↑ ¹ ² Peterson, Su, 2002, с. 117–122.
↑ Peterson, Su, 2009.
↑ Dehghani, Farhadi, Hajiaghayi, Yami, 2018, с. 2564–2583.
↑ Robertson, Webb, 1998, с. exercise 5.10.
↑ Robertson, Webb, 1998, с. exercise 5.11.
↑ Heydrich, Van Stee, 2015, с. 51–61.
↑ Traxler, 2002, с. 101–134.

ЛитератураПравить

Martin Gardner. aha! Insight. — New York: W. F. Freeman and Co., 1978. — ISBN 978-0-7167-1017-2.
Jack Robertson, William Webb. Cake-Cutting Algorithms: Be Fair If You Can. — Natick, Massachusetts: A. K. Peters, 1998. — ISBN 978-1-56881-076-8.
Elisha Peterson, Francis Edward Su. Four-Person Envy-Free Chore Division // Mathematics Magazine. — 2002. — Т. 75, вып. 2. — doi:10.2307/3219145. — JSTOR 3219145.
Elisha Peterson, Francis Edward Su. N-person envy-free chore division. — 2009.
Sina Dehghani, Alireza Farhadi, MohammadTaghi Hajiaghayi, Hadi Yami. Envy-free Chore Division for An Arbitrary Number of Agents. — Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018. — doi:10.1137/1.9781611975031.164.
Sandy Heydrich, Rob Van Stee. Dividing connected chores fairly (англ.) // Theoretical Computer Science (англ.) (рус.. — 2015. — Vol. 593. — doi:10.1016/j.tcs.2015.05.041.
Martino Traxler. Fair Chore Division for Climate Change // Social Theory and Practice. — 2002. — Т. 28, вып. 1. — doi:10.5840/soctheorpract20022814. — JSTOR 23559205.

[_ddf58af73af6dda7-1] Gardner, 1978.

[_071da91d53cd7f19-2] Robertson, Webb, 1998, с. 73–75.

[_41d72145f8704198-3] Robertson, Webb, 1998, с. 77–78.

[_125e753d22dabeaa-4] ¹ ² Peterson, Su, 2002, с. 117–122.

[_d47d4989bee73ab4-5] Peterson, Su, 2009.

[_9fb46f4137339592-6] Dehghani, Farhadi, Hajiaghayi, Yami, 2018, с. 2564–2583.

[_7c29bc3b04ec10fa-7] Robertson, Webb, 1998, с. exercise 5.10.

[_7c29bc3b04ec10fb-8] Robertson, Webb, 1998, с. exercise 5.11.

[_4806f9c5446180c5-9] Heydrich, Van Stee, 2015, с. 51–61.

[_432fbdeb02bf3070-10] Traxler, 2002, с. 101–134.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]