Введение
Тип задачи оптимизации Разделение задач - это задача справедливого деления, в которой разделенный ресурс нежелателен, так что каждый участник хочет получить как можно меньше. Это зеркальное отражение проблемы справедливого разрезания торта, в котором разделенный ресурс желателен, так что каждый участник хочет получить как можно больше. Обе проблемы имеют гетерогенные ресурсы, что означает, что ресурсы не однородны. В разделе тортов, торты могут иметь край, угол, и средние части вместе с различным количеством глазури. В то время как в разделе домашних дел есть разные типы домашних дел и разное количество времени, необходимое для завершения каждой работы. Аналогично, обе проблемы предполагают, что ресурсы делятся. Задачи могут быть бесконечно делящимися, потому что конечный набор задач может быть разделен на задачи или время. Например, груз стирки может быть разделен на количество предметов одежды и/или на количество времени, затрачиваемого на загрузку машины. Однако проблемы различаются по желательности ресурсов. Проблема разделения обязанностей была введена Мартином Гарднером в 1978 году. Разделение работы часто называют справедливым разделением плохих, в отличие от более распространенной проблемы, называемой "справедливым разделением товаров" (экономическое плохое - противоположность экономическому хорошему). Еще одно название - "проблема грязной работы". Один и тот же ресурс может быть хорошим или плохим, в зависимости от ситуации. Например, предположим, что ресурс, который нужно разделить, - это задний двор дома. В ситуации разделения наследства, эта площадь будет считаться хорошей, так как каждый наследник хотел бы иметь как можно больше земли, так что это проблема разрезания торта. Но в ситуации разделения домашних дел, таких как стрижка газона, этот двор будет считаться плохим, так как каждый ребенок, вероятно, хотел бы иметь как можно меньше земли для стрижки, поэтому это проблема срезки домашних дел. Некоторые результаты от честного резания торта могут быть легко переведены в сценарий резания домашней работы. Например, процедура "разделяй и выбирай" работает одинаково хорошо в обеих задачах: один из партнеров делит ресурс на две части, которые равны в его глазах, а другой партнер выбирает часть, которая "лучше" в его глазах. Единственное отличие в том, что "лучше" означает "больший" в резке тортов и "меньший" в резке домашних дел. Однако не все результаты так легко перевести. Более подробная информация приведена ниже.
Chore division is a fair division problem in which the divided resource is undesirable, so that each participant wants to get as little as possible. It is the mirror image of the fair cake cutting problem, in which the divided resource is desirable so that each participant wants to get as much as possible. Both problems have heterogeneous resources, meaning that the resources are nonuniform. In cake division, cakes can have edge, corner, and middle pieces along with different amounts of frosting. Whereas in chore division, there are different chore types and different amounts of time needed to finish each chore. Similarly, both problems assume that the resources are divisible. Chores can be infinitely divisible, because the finite set of chores can be partitioned by chore or by time. For example, a load of laundry could be partitioned by the number of articles of clothing and/or by the amount of time spent loading the machine. The problems differ, however, in the desirability of the resources. The chore division problem was introduced by Martin Gardner in 1978. Chore division is often called fair division of bads, in contrast to the more common problem called "fair division of goods" (an economic bad is the opposite of an economic good). Another name is dirty work problem. The same resource can be either good or bad, depending on the situation. For example, suppose the resource to be divided is the back yard of a house. In a situation of dividing inheritance, this yard would be considered good, since each heir would like to have as much land as possible, so it is a cake cutting problem. But in a situation of dividing house chores such as lawn mowing, this yard would be considered bad, since each child would probably like to have as little land as possible to mow, so it is a chore cutting problem. Some results from fair cake cutting can be easily translated to the chore cutting scenario. For example, the divide and choose procedure works equally well in both problems: one of the partners divides the resource to two parts that are equal in his eyes, and the other partner chooses the part that is "better" in his eyes. The only difference is that "better" means "larger" in cake cutting and "smaller" in chore cutting. However, not all results are so easy to translate. More details are given below.
Равномерное и точное распределение обязанностей
Процедуры равномерного и точного деления одинаково хорошо работают как для пирожных, так и для домашних дел, поскольку они гарантируют равные ценности. Примером является процедура движущегося ножа Остина, которая гарантирует каждому партнеру кусочек, который он оценивает как точно 1/n от общего количества.
Дискретная и ограниченная процедура Дехгани и др. для любого количества партнеров
Питерсон и Су провели процедуру с ножом для 4 человек в отделе домашних дел. Деггани и др. обеспечил первый дискретный и ограниченный протокол без зависти для разделения работы между любым количеством агентов.
Приложения
Возможно, можно использовать процедуры разделения обязанностей для распределения работы и затрат на сокращение изменения климата между странами. Проблемы возникают с моралью и получением сотрудничества между странами. Однако использование процедур разделения работы уменьшает необходимость в супрациональном органе для разделения и надзора за работой этих стран. Еще одно применение для разделения домашних дел будет в проблеме арендной гармонии.