The definition of
envy-freeness 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 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 rotating-knife procedure. 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, 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. 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 •
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 ==