HOME

TheInfoList



OR:

Chore division is a
fair division Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inh ...
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 Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
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 Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of Lew ...
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 A lawn is an area of soil-covered land planted with grasses and other durable plants such as clover which are maintained at a short height with a lawnmower (or sometimes grazing animals) and used for aesthetic and recreational purposes. ...
-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 Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
can be easily translated to the chore-cutting scenario. For example, the
divide and choose Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
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 A proportional division is a kind of fair division in which a resource is divided among ''n'' partners with subjective valuations, giving each partner at least 1/''n'' of the resource by his/her own subjective valuation. Proportionality was the f ...
in chore-cutting is the mirror-image of its definition in cake-cutting: each partner i should receive a piece X_i that is worth, according to his own personal ''dis''utility function, at most 1/n of the total value (where n is the total number of partners): :\forall i: V_i(X_i) \leq V_i(Whole)/n Most protocols for
proportional cake-cutting A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/''n'' of t ...
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 1/n for him. If any other agent feels that this piece is too small, then he can enlarge it until it is worth exactly 1/n for him, and so on. The "last enlarger" receives the piece, which is worth exactly 1/n for him and at least 1/n 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 n/2 agents, and let each half recursively divide the piece that does NOT contain its line.


Equitable and exact chore-cutting

Procedures for
equitable division Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/h ...
and
exact division Exact division, also called consensus division, is a partition of a continuous resource ("fair cake-cutting, cake") into some ''k'' pieces, such that each of ''n'' people with different tastes agree on the value of each of the pieces. For example, c ...
work equally well for cakes and for chores, since they guarantee equal values. An example is the
Austin moving-knife procedure The Austin moving-knife procedures are procedures for equitable division of a cake. They allocate each of ''n'' partners, a piece of the cake which this partner values as ''exactly'' 1/n of the cake. This is in contrast to proportional division p ...
, 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 Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by a ...
in chore-cutting is the mirror-image of its definition in cake-cutting: each partner i should receive a piece X_i that is worth, according to his own personal disutility function, at most as much as any other piece: :\forall i,j: V_i(X_i) \leq V_i(X_j) For two partners,
divide and choose Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have diffe ...
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. Step one. Alice cuts the chore to three pieces equal in her eyes (this is also the first step in the Selfidge-conway protocol). Bob and Carl specify their smallest piece. The easy case is that they disagree, since then we can give each partner a smallest piece and we are done. The hard case is that they agree. Let's call the piece, that both Bob and Carl view as smallest, X1, and the other two pieces, X2 and X3. Step two. Ask Bob and Carl to mark, on each of the pieces X2 and X3, where the piece has to be cut in order to make it equal to X1. We consider several cases. ''Case 1.'' Bob's trims are weaker. I.e, if Bob trims X2 to X2' and X3 to X3', such that both X2' and X3' are for him as small as X1, then Carl thinks X1 is still a smallest piece – weakly smaller than X2' and X3'. Then, the following partial division is envy-free: * Carl gets X1; * Alice gets the smaller of X2' and X3' (both are smaller than X1 for her); * Bob gets the piece not taken by Alice (both are equal to X1 for him). Now we have to divide the trimmings E2 and E3. For each trimming, the following is done: * Bob cuts it to three equal pieces. * The agents choose pieces in the order: Carl, Alice, Bob. Carl is not envious since he chose first; Bob is not envious since he cut; Alice is not envious since she had a (negative) advantage over Carl: in the first step, Carl took X1, while Alice took a piece that is smaller than X1 by max(E2,E3), while in the last step, Alice took two pieces that are worth at most (E2+E3)/2. ''Case 2.'' Carl's trims are weaker. I.e, if Carl trims X2 to X2' and X3 to X3', such that both X2' and X3' are for him as small as X1, then Bob thinks X1 is still a smallest piece – weakly smaller than X2' and X3'. Then, we proceed as in Case 1, with the roles of Bob and Carl switched. ''Case 3.'' Bob's trim is weaker in X2, and Carl's trim is weaker in X3. I.e, if Bob trims X2 to X2' which is equal to X1 for him, and Carl trims X3 to X3' which is equal to X1 for him, then: * For Carl: X2' >= X1 = X3' * For Bob: X3' >= X1 = X2' Then, the following partial division is envy-free: * Alice gets the smaller of X2' and X3' (both are smaller than X1 for her); * Bob gets either X2' (if it was not taken by Alice) or X1 (otherwise); * Carl gets either X3' (if it was not taken by Alice) or X1 (otherwise). The trimmings, E2 and E3, are divided in a similar way to Case 1. Oskui also showed how to convert the following moving-knife procedures from cake-cutting to chore-cutting: *
Stromquist moving-knives procedure The Stromquist moving-knives procedure is a procedure for envy-free cake-cutting among three players. It is named after Walter Stromquist who presented it in 1980. This procedure was the first envy-free moving knife procedure devised for three pla ...
* The rotating-knife procedure.


Peterson and Su's continuous procedures for three and four partners

Peterson and Su suggested a different procedure for three partners. It is simpler and more symmetric than Oskui's procedure, but it is not discrete, since it relies on a moving-knife procedure. Their key idea is to divide the chores into six pieces and then give each partner the two pieces that they feel are at least as small as the pieces the other players receive. Step One. Divide the chores into 3 pieces using any envy-free cake cutting method and assign each piece to the player that finds it the largest. Step Two. * Using
Austin moving-knife procedure The Austin moving-knife procedures are procedures for equitable division of a cake. They allocate each of ''n'' partners, a piece of the cake which this partner values as ''exactly'' 1/n of the cake. This is in contrast to proportional division p ...
, divide piece 1 to two slices that partners 1 and 2 consider equal. Let partner 3 choose the slice that is smaller in his eyes, and give the other slice to partner 2. * Similarly, divide piece 2 to two slices that partners 2 and 3 consider equal, let partner 1 choose the smallest slice and give the other slice to partner 3. * Similarly, divide piece 3 to two slices that partners 3 and 1 consider equal, let partner 2 choose the smallest slice and give the other slice to partner 1. Analysis. Partner 1 holds two slices: one from piece 2 and one from piece 3. In the eyes of partner 1, the slice from piece 2 is smaller than its slice given to partner 3, and the slice from piece 3 is smaller than its slice given to partner 2. Moreover, both these slices are smaller than the slices of piece 1, since piece 1 is larger than both piece 2 and piece 3 (by Step One). Therefore, partner 1 believes that his share is (weakly) smaller than each of the other two shares. The same considerations apply to partners 2 and 3. Therefore, the division is envy-free. Peterson and Su extend their continuous procedure to four partners.


Peterson and Su's discrete procedure for any number of partners

The existence of a discrete procedure for five or more partners remained an open question, until in 2009 Peterson and Su published a procedure for ''n'' partners. It is analogous to the Brams–Taylor procedure and uses the same idea of ''irrevocable advantage''. Instead of trimming, they use ''adding from reserve''.


Dehghani et al.'s discrete and bounded procedure for any number of partners

Peterson and Su gave a moving knife procedure for 4-person chore division. Dehghani et al. provided the first discrete and bounded envy-free protocol for chore division among any number of agents.


Procedures for connected pieces

The following procedures can be adapted to divide a bad cake with disconnected pieces: * Robertson–Webb rotating-knife procedure *
Stromquist moving-knives procedure The Stromquist moving-knives procedure is a procedure for envy-free cake-cutting among three players. It is named after Walter Stromquist who presented it in 1980. This procedure was the first envy-free moving knife procedure devised for three pla ...
* Simmons–Su protocols. Simmons originally developed a protocol for approximate envy-free cake-cutting with connected pieces, based on Sperner's lemma. Su showed, using a dual lemma, that a similar protocol can be used for approximate envy-free chore division. In particular, it shows that there always exists an envy-free chore division with connected pieces.


Price-of-fairness

Heydrich and van Stee calculate the
price of fairness In the theory of fair division, the price of fairness (POF) is the ratio of the largest economic welfare attainable by a division to the economic welfare attained by a ''fair'' division. The POF is a quantitative measure of the loss of welfare that ...
in chore division when the pieces have to be connected.


Applications

It may be possible to use 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. Another use for chore division would be in the
rental harmony Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem. In the t ...
problem.


References

{{reflist


See also

*
Envy-free cake-cutting An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other sha ...
* Bad (economics) *
Rental harmony Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem. In the t ...
Cake-cutting Fair division protocols