Хозяйственное подразделение

Разделение обязанностей — это задача справедливого деления, в которой разделение ресурсов нежелательно, так что каждый участник хочет получить как можно меньше. Это зеркальное отражение справедливой задачи о разрезании торта , в которой желательно разделить ресурсы, чтобы каждый участник хотел получить как можно больше. Обе задачи имеют неоднородные ресурсы, а это означает, что ресурсы неоднородны. При разделении тортов торты могут иметь края, углы и середину, а также разное количество глазури. В то время как при разделении работы существуют разные типы работы и разное количество времени, необходимое для завершения каждой работы. Аналогично, обе задачи предполагают, что ресурсы являются делимыми. Работа по дому может быть бесконечно делимой, поскольку конечное множество дел можно разделить по задачам или по времени. Например, загрузка белья может быть разделена по количеству предметов одежды и/или по времени, потраченному на загрузку машины. Однако проблемы различаются по желательности ресурсов. Проблема разделения обязанностей была предложена Мартин Гарднер в 1978 году. ^[1]

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

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

Пропорциональное сокращение обязанностей

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

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

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

Чтобы использовать протокол последнего уменьшителя : попросите агента отрезать кусок ровно на сумму $1/n$ для него. Если какой-либо другой агент почувствует, что этот кусок слишком мал, то он может увеличить его до тех пор, пока он не будет стоить ровно $1/n$ для него и так далее. «Последний увеличитель» получает кусок, который стоит ровно $1/n$ для него и по крайней мере $1/n$ для остальных.
Чтобы использовать протокол Эвен-Паз : попросите каждого агента отметить линию половинного значения, убедившись, что все линии параллельны. Разрежьте пирог посередине линий, разделите агентов на две группы. $n/2$ агентов, и пусть каждая половина рекурсивно делит часть, НЕ содержащую ее строку.

Справедливое и точное распределение работы по дому

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

Работа по дому без зависти

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

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

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

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

Реза Оскуи был первым, кто предложил процедуру разделения обязанностей для трех партнеров. Его работы никогда официально не публиковались; Это описано в ^[2] страницы 73–75. Он похож на протокол Селфриджа-Конвея , но более сложен: требует 9 разрезов вместо 5.

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

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

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

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

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

Теперь нам нужно разделить обрезки Е2 и Е3. Для каждой обрезки делается следующее:

Боб разрезает его на три равные части.
Агенты выбирают фигуры в следующем порядке: Карл, Алиса, Боб.

Карл не завидует, поскольку сделал выбор первым; Боб не завидует, потому что он порезался;Алиса не завидует, поскольку у нее было (отрицательное) преимущество перед Карлом:на первом этапе Карл взял X1, а Алиса взяла кусок, который меньше X1 на max(E2,E3), а на последнем шаге Алиса взяла два куска стоимостью не более (E2+E3)/2.

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

Случай 3. Подстройка Боба слабее в X2, а обрезка Карла слабее в X3. То есть, если Боб сокращает X2 до X2', что для него равно X1, а Карл сокращает X3 до X3', что для него равно X1, тогда:

Для Карла: X2' >= X1 = X3'
Для Боба: X3' >= X1 = X2'

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

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

Обрезки E2 и E3 делятся аналогично случаю 1.

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

Процедура перемещения ножей Стромквиста
Процедура с вращающимся ножом. ^[2]^: 77–78

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

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

Шаг первый. Разделите работу на 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. Поэтому разделение не вызывает зависти.

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

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

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

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

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

Процедуры для связанных частей

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

Процедура Робертсона-Уэбба с вращающимся ножом ^[2]^{: упражнение 5.10}
Процедура перемещения ножей Стромквиста ^[2]^{: упражнение 5.11}
Протоколы Симмонса-Су . Симмонс первоначально разработал протокол для приблизительного разрезания торта без зависти с соединенными кусочками, основанный на лемме Спернера . Су показал, используя двойную лемму, что аналогичный протокол можно использовать для приблизительного разделения обязанностей без зависти. В частности, это показывает, что всегда существует свободное от зависти разделение обязанностей со связанными между собой частями.

Справедливая цена

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

Приложения

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

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

Ссылки

^ Гарднер, Мартин (1978). Ага! Понимание . WF Freeman and Co. Нью-Йорк: ISBN 978-0-7167-1017-2 .
^ Jump up to: ^а ^б ^с ^д Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .
^ Jump up to: ^а ^б Петерсон, Элиша; Су, Фрэнсис Эдвард (1 апреля 2002 г.). «Отдел по работе без зависти из четырех человек». Журнал «Математика» . 75 (2): 117–122. CiteSeerX 10.1.1.16.8992 . дои : 10.2307/3219145 . JSTOR 3219145 .
^ Петерсон, Элиша; Фрэнсис Эдвард Су (2009). «Деление работы по дому без зависти на N человек». arXiv : 0909.0303 [ math.CO ].
^ Дегани, Сина; Алиреза Фархади; Мохаммад Таги Хаджиагайи; Хади Ями (2018). «Отделение рутинной работы без зависти для произвольного количества агентов». Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. стр. 2564–2583. дои : 10.1137/1.9781611975031.164 . ISBN 978-1-61197-503-1 .
^ Гейдрих, Сэнди; Ван Сти, Роб (2015). «Справедливое разделение связанных обязанностей» . Теоретическая информатика . 593 : 51–61. дои : 10.1016/j.tcs.2015.05.041 . hdl : 2381/37387 .
^ Тракслер, Мартино (1 января 2002 г.). «Подразделение по борьбе с изменением климата». Социальная теория и практика . 28 (1): 101–134. дои : 10.5840/soctheorpract20022814 . JSTOR 23559205 . S2CID 143631012 .

См. также

[1] Гарднер, Мартин (1978). Ага! Понимание . WF Freeman and Co. Нью-Йорк: ISBN 978-0-7167-1017-2 .

[rw98-2] Jump up to: ^а ^б ^с ^д Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .

[ps02-3] Jump up to: ^а ^б Петерсон, Элиша; Су, Фрэнсис Эдвард (1 апреля 2002 г.). «Отдел по работе без зависти из четырех человек». Журнал «Математика» . 75 (2): 117–122. CiteSeerX 10.1.1.16.8992 . дои : 10.2307/3219145 . JSTOR 3219145 .

[4] Петерсон, Элиша; Фрэнсис Эдвард Су (2009). «Деление работы по дому без зависти на N человек». arXiv : 0909.0303 [ math.CO ].

[5] Дегани, Сина; Алиреза Фархади; Мохаммад Таги Хаджиагайи; Хади Ями (2018). «Отделение рутинной работы без зависти для произвольного количества агентов». Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. стр. 2564–2583. дои : 10.1137/1.9781611975031.164 . ISBN 978-1-61197-503-1 .

[6] Гейдрих, Сэнди; Ван Сти, Роб (2015). «Справедливое разделение связанных обязанностей» . Теоретическая информатика . 593 : 51–61. дои : 10.1016/j.tcs.2015.05.041 . hdl : 2381/37387 .

[7] Тракслер, Мартино (1 января 2002 г.). «Подразделение по борьбе с изменением климата». Социальная теория и практика . 28 (1): 101–134. дои : 10.5840/soctheorpract20022814 . JSTOR 23559205 . S2CID 143631012 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]