Кіріспе
Оптимизациялау мәселесінің түрі Жұмысты бөлу - әділ бөлу мәселесі, онда бөлінген ресурс қолайсыз, сондықтан әрбір қатысушы мүмкіндігінше аз алуға тырысады. Бұл әділ торт кесу проблемасының айналымы, онда әр қатысушы мүмкіндігінше көп нәрсе алғысы келетін ресурстың бөлінуі қажет. Екі проблеманың да хетерогенді ресурстары бар, яғни ресурстар біркелкі емес. Тортты бөлу кезінде торттың әртүрлі мөлшердегі балқымамен бірге шеткі, бұрышты және ортаңғы бөліктері болуы мүмкін. Ал үй шаруаларын бөлуде әр түрлі жұмыс түрлері бар және әр жұмысты аяқтауға әр түрлі уақыт қажет. Сол сияқты, екі проблемада да ресурстар бөлінуі мүмкін деп болжанады. Үй шаруалары шексіз бөлінуі мүмкін, өйткені үй шаруаларының шекті жиынтығы үй шаруасымен немесе уақытпен бөлінеді. Мысалы, кір жуу машинасын киім-кешектің санымен және/немесе машинаны жүктеуге жұмсалған уақытпен бөлуге болады. Алайда, бұл проблемалар ресурстардың қалауы бойынша ерекшеленеді. Жұмысты бөлу проблемасын 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 адамнан тұратын үй шаруасы бөліміне пышақпен жұмыс істеуге мүмкіндік берді. Дехгани және басқалар. Бұл кез келген агенттердің арасында жұмыс бөлу үшін бірінші дискретті және шектелген қызғанышсыз протоколды ұсынды.
Қолданбалар
Климаттың өзгеруін азайту үшін жұмыс пен шығындарды елдердің арасында бөлу үшін үй шаруаларын бөлу әдістерін қолдану мүмкін. Адамгершілік пен ұлттар арасындағы ынтымақтастық мәселесі туындап жатады. Алайда, үй шаруаларын бөлу процедураларын қолдану осы халықтардың жұмысын бөлу және қадағалау үшін ұлттық билік органы қажеттілігін азайтады. Жұмысты бөлудің тағы бір пайдасы - жалға беру үйлесімділігі проблемасы.