Разделение по дому - это проблема справедливого разделения, в которой разделение ресурсов нежелательно, так что каждый участник хочет получить как можно меньше. Это зеркальное отражение задачи по резке торта , в которой желательно разделение ресурсов, чтобы каждый участник хотел получить как можно больше. Обе проблемы имеют разнородныересурсы, что означает, что ресурсы неоднородны. При разделении торта у торта могут быть крайние, угловые и средние части, а также разное количество глазури. В то время как в разделении по рутинной работе есть разные типы работы и разное количество времени, необходимое для завершения каждой работы. Точно так же обе проблемы предполагают, что ресурсы делимы. Работа по дому может быть бесконечно делимой, потому что конечный набор обязанностей может быть разделен по рутинной работе или по времени. Например, загрузка белья может быть разделена по количеству предметов одежды и / или по времени, затраченному на загрузку машины. Однако проблемы различаются желательностью ресурсов. Проблема разделения рутинной работы была введена Мартином Гарднером в 1978 г. [1]
Разделение по хозяйству часто называют справедливым разделением плохих товаров , в отличие от более распространенной проблемы, называемой «справедливое разделение товаров». Другое название - проблема грязной работы . Один и тот же ресурс может быть как хорошим, так и плохим, в зависимости от ситуации. Например, предположим, что разделяемым ресурсом является задний двор дома. В ситуации раздела наследства этот двор будет считаться хорошим, так как каждый наследник хотел бы иметь как можно больше земли, поэтому это проблема разрезания торта. Но в ситуации разделения домашних обязанностей, таких как стрижка газона , этот двор будет считаться плохим, поскольку каждый ребенок, вероятно, хотел бы, чтобы у него было как можно меньше земли, поэтому это серьезная проблема.
Некоторые результаты справедливой разрезки торта можно легко перенести на сценарий разделки по дому. Например, процедура « разделяй и выбирай» одинаково хорошо работает в обеих задачах: один из партнеров делит ресурс на две равные в его глазах части, а другой партнер выбирает ту часть, которая «лучше» в его глазах. Единственная разница в том, что «лучше» означает «больше» при резке торта, а «меньше» - при резке по дому. Однако не все результаты так легко перевести. Более подробная информация представлена ниже.
Пропорциональная работа по дому
Определение пропорционального деления в разделке по дому является зеркальным отражением его определения в разрезании торта: каждый партнер должен получить кусок которая стоит, согласно его личной функции бесполезности , не более от общей стоимости (где - общее количество партнеров):
Большинство протоколов пропорциональной нарезки торта можно легко перевести на рутинную резку. Например:
- Чтобы использовать последний протокол уменьшителя : попросите агента отрезать кусок, который стоит точнодля него. Если какой-либо другой агент считает, что этот кусок слишком мал, он может увеличить его до тех пор, пока он не будет стоить точно.для него и так далее. "Последний увеличитель" получает кусок, который стоит ровно для него и по крайней мере для остальных.
- Чтобы использовать протокол Even – Paz : попросите каждого агента отметить линию половинного значения, убедившись, что все линии параллельны. Разрезать торт посередине линий, разделить агентов на две группы. агентов, и пусть каждая половина рекурсивно делит кусок, НЕ содержащий ее строки.
Справедливое и точное выполнение работ по дому
Процедуры справедливого и точного разделения одинаково хорошо подходят для тортов и для работы по дому, поскольку они гарантируют одинаковую ценность. Примером может служить процедура с движущимся ножом Остина , которая гарантирует каждому партнеру кусок, который он оценивает как ровно 1 / n от общей суммы.
Рутинная работа без зависти
Свобода от зависти в разделке по дому является зеркальным отражением ее определения в разрезании торта: каждый партнер должен получить кусок это стоит, в соответствии с его собственной личной функцией бесполезности, не больше, чем любая другая часть:
Для двух партнеров принцип «разделяй и выбирай» производит рутинную работу без зависти. Однако для трех и более партнеров ситуация намного сложнее. Основная трудность заключается в обрезке - действии обрезки части, чтобы сделать ее равной другой части (как это сделано, например, в протоколе Селфриджа – Конвея ). Это действие не может быть легко переведено на сценарий рутинной работы.
Дискретная процедура Оскуи для трех партнеров
Реза Оскуи был первым, кто предложил трём партнёрам рутинную процедуру. Его работа никогда официально не публиковалась; Он описан на [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);
- Боб получает фишку, которую не взяла Алиса (обе для него равны X1).
Теперь нам нужно разделить обрезки E2 и E3. Для каждой обрезки выполняется следующее:
- Боб разрезает его на три равные части.
- Агент выбирает фигуры в порядке: Карл, Алиса, Боб.
Карл не завидует, так как он сделал выбор первым; Боб не завидует, так как резал; Алиса не завидует, поскольку у нее было (отрицательное) преимущество перед Карлом: на первом этапе Карл взял 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). Следовательно, партнер 1 считает, что его доля (слабо) меньше, чем каждая из двух других долей. Те же соображения применимы к партнерам 2 и 3. Таким образом, разделение не вызывает зависти.
Петерсон и Су расширяют свою непрерывную процедуру до четырех партнеров. [3]
Дискретная процедура Петерсона и Су для любого количества партнеров
Существование дискретной процедуры для пяти или более партнеров оставалось открытым до тех пор, пока в 2009 году Петерсон и Су не опубликовали процедуру для n партнеров. [4] Она аналогична процедуре Брамса – Тейлора и использует ту же идею безвозвратного преимущества . Вместо обрезки они прибавляют из резерва .
Дискретная и ограниченная процедура Дехгани и др. Для любого количества партнеров
Петерсон и Су провели процедуру с движущимся ножом для разделения работы на 4 человека. Dehghani et al. [5] предоставил первый дискретный и ограниченный протокол без зависти для разделения рутинной работы между любым количеством агентов.
Процедуры для соединенных частей
Следующие процедуры могут быть адаптированы для разделения торта на отсоединенные куски:
- Процедура вращающегося ножа Робертсона – Уэбба [2] : упражнение 5.10.
- Методика движущихся ножей Стромквиста [2] : упражнение 5.11.
- Протоколы Симмонса – Су . Первоначально Симмонс разработал протокол для приблизительного вырезания торта без зависти со связанными кусочками, основанный на лемме Спернера . Су показал, используя двойственную лемму, что подобный протокол можно использовать для приблизительного разделения рутинной работы без зависти. В частности, это показывает, что всегда существует свободное от зависти разделение работы на соединенные части.
Цена справедливости
Гейдрих и ван Сти [6] вычисляют цену справедливости при разделении рутинной работы, когда части должны быть соединены.
Приложения
Возможно, можно будет использовать процедуры разделения рутинной работы, чтобы разделить работу и затраты на уменьшение изменения климата между странами. Проблемы возникают с моралью и налаживанием сотрудничества между народами. Однако использование процедур разделения рутинной работы снижает необходимость в наднациональном органе для разделения и надзора за работой этих стран. [7]
Другое использование разделения рутинной работы может быть связано с проблемой арендной гармонии .
Рекомендации
- ^ Гарднер, Мартин (1978). Ага! Проницательность . Нью-Йорк: ISBN WF Freeman and Co. 978-0-7167-1017-2.
- ^ а б в г Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы резки торта: будьте честны, если можете . Натик, Массачусетс: А. К. Питерс. ISBN 978-1-56881-076-8. LCCN 97041258 . OL 2730675W .
- ^ а б Петерсон, Елисей; Су, Фрэнсис Эдвард (01.04.2002). «Подразделение по дому без зависти из четырех человек». Математический журнал . 75 (2): 117–122. CiteSeerX 10.1.1.16.8992 . DOI : 10.2307 / 3219145 . JSTOR 3219145 .
- ^ Петерсон, Елисей; Фрэнсис Эдвард Су (2009). «Подразделение по дому без зависти из N человек». arXiv : 0909.0303 [ math.CO ].
- ^ Дехгани, Сина; Алиреза Фархади; Мохаммад Таги Хаджиагайи; Хади Ями (2018). Свободное от зависти рутинное подразделение для произвольного количества агентов . Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. С. 2564–2583. DOI : 10.1137 / 1.9781611975031.164 .
- ^ Гейдрих, Сэнди; Ван Сти, Роб (2015). «Честное разделение связанных дел» . Теоретическая информатика . 593 : 51–61. DOI : 10.1016 / j.tcs.2015.05.041 . hdl : 2381/37387 .
- ^ Трэкслер, Мартино (01.01.2002). «Подразделение справедливой работы по изменению климата». Социальная теория и практика . 28 (1): 101–134. DOI : 10.5840 / soctheorpract20022814 . JSTOR 23559205 .
Смотрите также
- Нарезка торта без зависти
- Плохо (экономика)
- Гармония аренды