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.
Proportional chore-cutting
The definition of proportional division in chore-cutting is the mirror-image of its definition in cake-cutting: each partner should receive a piece that is worth, according to his own personal disutility function, at most of the total value (where is the total number of partners):
Most protocols for proportional cake-cutting can be easily translated to the chore-cutting. For example: To use the last diminisher protocol: ask an agent to cut a piece worth exactly for him. If any other agent feels that this piece is too small, then he can enlarge it until it is worth exactly for him, and so on. The "last enlarger" receives the piece, which is worth exactly for him and at least for the others. To use the Even–Paz protocol: ask each agent to mark the half-value line, making sure all lines are parallel. Cut the cake in the median of the lines, divide the agents to two groups of agents, and let each half recursively divide the piece that does NOT contain its line.
Equitable and exact chore-cutting
Procedures for equitable division and exact division work equally well for cakes and for chores, since they guarantee equal values. An example is the Austin moving-knife procedure, which guarantees each partner a piece that he values as exactly 1/n of the total.
Envy-free chore-cutting
The definition of envy-freeness in chore-cutting is the mirror-image of its definition in cake-cutting: each partner should receive a piece that is worth, according to his own personal disutility function, at most as much as any other piece:
For two partners, divide and choose produces an envy-free chore-cutting. However, for three or more partners, the situation is much more complicated. The main difficulty is in the trimming – the action of trimming a piece to make it equal to another piece (as done e.g. in the Selfridge–Conway protocol). This action cannot be easily translated to the chore-cutting scenario.
Oskui's discrete procedure for three partners
Reza Oskui was the first who suggested a chore-cutting procedure for three partners. His work was never formally published; It is described in pages 73–75. It is similar to the Selfridge–Conway protocol, but more complicated: it requires 9 cuts instead of 5 cuts.
Below, the partners are called Alice, Bob and Carl.