Chore division

Chore division is a fair division problem that deals with dividing chores, known as resources, evenly among a number of people, known as players. This evenness, known as envy-freeness, is a central part of fair division, because it focuses on each person's preferences such that no one feels jealous of any other player's situation.[1]

The fair cake-cutting problem is another fair division problem that is very similar to chore division. 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. The problems differ, however, in the desirability of the resources. In chore division, the chores are undesirable to the players, and in cake division, the cake pieces are desirable to the players.[1]

Typically with chore division, it is assumed that the 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.[1]

Chore division, also called the dirty work problem,[2] was originally introduced in "Aha! Insight" by Martin Gardner in 1978.[3]


Applications

Climate Change

There exists the possibility of using chore division procedures to divide up the work and cost of reducing climate change among nations. Problems occur with morals and getting cooperation between nations. However, using chore division procedures reduces the need for a supra-national authority to partition and oversee work by those nations.[4]

Rental Harmony

Another use for chore division would be in rent partitioning. Imagine an apartment or house with multiple rooms of different sizes and features. Using chore division methods, it is possible to assign each room and the portion of the total rent to each person.[5]

Procedures

Two Players

For two players, a divide and choose approach called the Austin moving-knife procedure, commonly used in cake-cutting, works to divide the chores in half. In this method, one player continues to redefine what they believe is half of the chores until the other player agrees. Once the players are in agreement, a coin toss is used to assign the one of the separate halves to each player.[1]

Three Players

Based on the Austin's procedure, the key idea of three player chore division is to divide the chores into six pieces and then give each player (players are I, J and K) the two pieces that they feel are at least as small as the pieces the other players receive.[1]

Step One

Divide the chores into 3 parts using any envy-free cake cutting method and assign each portion to the player that finds it the largest. Name each portion the name of the player that took that portion.[1]

For example, say George, Alice, and Bobby are the three players defined as I, J and K, respectively. If George's most disliked chore was mowing the lawn, Alice's most disliked chore was doing the dishes, and Bobby's most disliked chore was vacuuming, and the players agreed the work load of each chore was even, then the players would be assigned their most disliked chores and those chores would be labeled by their respective player's names.

Step Two

Have player I divide their portion of the chores into two equal parts, and assign those parts to players J and K so that they feel they haven't received more than half.[1]

This can also be done using Austin's method by having players I and J decide on a 50/50 split. Then player K is assigned the portion that they believe is the smaller half while player J gets the other half.[1]

For example, George may indefinitely redefine the size of the lawn needed mowing into two halves until Alice also feels as if it is half, then Bobby gets to decide which half he has to mow and which half Alice needs to mow.

Step Three

Repeat Step Two except for the portions labeled J and K.[1]

For example, Alice and Bobby may divide the dishes by drying and cleaning, and George would assign half to himself and the other half to Bobby. Also, Bobby and George may divide the vacuuming by time, and Alice would assign half the time vacuuming to herself and the other half to George.

Explanation

Player I is envy-free, because they believes that their half of player K's chores is no larger than player J's half, and player J's other piece is no larger than half of the portion it came from. Player I also feels that the largest chore was divided in half and they don't have to do either half. This applies to all permutations of the players, so all players feel envy-free.[1]

For example, since all three chores are defined to be even in their workload, George feels like he would be doing a third of the workload by doing half of the dish washing and half of the vacuuming. He would also be envy-free of Alice and Bobby, because the two of them have been assigned half of the lawn mowing, which is George's most disliked chore. Both Alice and Bobby feel the same way as George, because they also feel like they are performing a third of the total workload and they are envy-free of the other two players.

N-Players

While there does exist finite n-player envy-free chore division procedures, they are not bounded by time or cuts. Bounded procedures are still yet to be solved.[1]

References

  1. 1 2 3 4 5 6 7 8 9 10 11 Peterson, Elisha; Su, Francis Edward (2002-04-01). "Four-Person Envy-Free Chore Division". Mathematics Magazine 75 (2): 117–122. doi:10.2307/3219145.
  2. ↑ Jack Robertson and William Webb (1998). Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, . ISBN 1-56881-076-8
  3. ↑ Gardner, Martin (1978). aha! Insight. New York: W. F. Freeman and Co. ISBN 978-0716710172.
  4. ↑ Traxler, Martino (2002-01-01). "Fair Chore Division for Climate Change". Social Theory and Practice 28 (1): 101–134.
  5. ↑ Su, Francis Edward (1999-12-01). "Rental Harmony: Sperner's Lemma in Fair Division". The American Mathematical Monthly 106 (10): 930–942. doi:10.2307/2589747.

See also


This article is issued from Wikipedia - version of the Tuesday, November 10, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.