Symmetric fair cake-cutting
Symmetric fair cake-cutting
- Symmetric fair cake-cutting** is a variant of the [[fair-cake-cutting]] problem, in which fairness is applied not only to the final outcome, but also to the assignment of roles in the division procedure.
As an example, consider a birthday cake that has to be divided between two children with different tastes, such that each child feels that his/her share is "fair", i.e., worth at least 1/2 of the entire cake. They can use the classic divide-and-choose procedure: Alice cuts the cake into two pieces worth exactly 1/2 in her eyes, and George chooses the piece that he considers more valuable. The outcome is always fair. However, the procedure is not symmetric: while Alice always gets a value of exactly 1/2 of her value, George may get much more than 1/2 of his value. Thus, while Alice does not envy George's share, she does envy George's role in the procedure.
In contrast, consider the alternative procedure in which Alice and George both make half-marks on the cake, i.e., each of them marks the location in which the cake should be cut such that the two pieces are equal in his/her eyes. Then, the cake is cut exactly between these cuts—if Alice's cut is a and George's cut is g, then the cake is cut at (a+g)/2. If a<g, Alice gets the leftmost piece and George the rightmost piece; otherwise Alice gets the rightmost piece and George the leftmost piece. The final outcome is still fair. And here, the roles are symmetric: the only case in which the roles make a difference in the final outcome is when a=g, but in this case, both parts have a value of exactly 1/2 to both children, so the roles do not make a difference in the final value. Hence, the alternative procedure is both fair and symmetric.
The idea was first presented by Manabe and Okamoto, who termed it meta-envy-free.
Several variants of symmetric fair cake-cutting have been proposed:
- Anonymous fair cake-cutting requires that not only the values be equal, but also the pieces themselves be equal. This implies symmeric fairness, but it is stronger . For example, it is not satisfied by the symmetric-divide-and-choose above, since in the case that a=g, the first agent always gets the leftmost piece and the second agent always gets the rightmost piece.
- Aristotelian fair cake-cutting requires only that agents with identical value measures receive the same value. This is implied by symmetric fairness, but it is weaker. For example, it is satisfied by the asymmetric version of divide-and-choose: if the agents' valuations are identical, then both of them receive a value of exactly 1/2.
Definitions There is a cake C, usually assumed to be a 1-dimensional interval. There are n people. Each person i has value function Vi which maps subsets of C to weakly-positive numbers.
A division procedure is a function F that maps n value functions to a partition of C. The piece allocated by F to agent i is denoted by F(V1,...,Vn; i).
Symmetric procedure A division procedure F is called *symmetric if, for any permutation p of (1,...,n), and for every i:<blockquote>Vi(F(V1,...,Vn; i)) = Vi(F(Vp(1),...,Vp(n); p−1(i)))</blockquote>In particular, when n=2, a procedure is symmetric if:<blockquote>V1(F(V1,V2; 1)) = V1(F(V2,V1; 2)) and V2(F(V1,V2; 2)) = V2(F(V2,V1*; 1)) </blockquote>This means that agent 1 gets the same value whether he plays first or second, and the same is true for agent 2.
As another example, when n=3, the symmetry requirement implies (among others):<blockquote>V1(F(V1,V2,V3; 1)) = V1(F(V2,V3,V1; 3)) = V1(F(V3,V1,V2; 2)).</blockquote>
Anonymous procedure A division procedure F is called *anonymous if, for any permutation p of (1,...,n), and for every i:<blockquote>F(V1,...,Vn; i) = F(Vp(1),...,Vp(n); p−1(i*))</blockquote>Any anonymous procedure is symmetric, since if the pieces are equal - their values are surely equal.
But the opposite is not true: it is possible that a permutation gives an agent different pieces with equal value.
Aristotelian procedure A division procedure F is called *aristotelian if, whenever Vi=Vk:<blockquote>Vi(F(V1,...,Vn; i)) = Vk(F(V1,...,Vn; k*))</blockquote>The criterion is named after Aristotle, who wrote in his book on ethics: "... it is when equals possess or are allotted unequal shares, or persons not equal equal shares, that quarrels and complaints arise".
Every symmetric procedure is aristotelian. Let p be the permutation that exchanges i and k. Symmetry implies that:<blockquote>Vi(F(V1,....Vi,...,Vk,...,Vn; i)) = Vi(F(V1,....Vk,...,Vi,...,Vn; k)) </blockquote>But since Vi=Vk, the two sequences of value-measures are identical, so this implies the definition of aristotelian.
Moreover, every procedure envy-free-cake-cutting is aristotelian: envy-freeness implies that:<blockquote>Vi(F(V1,...,Vn; i)) ≥ Vi(F(V1,...,Vn; k))
- Vk(F(V1,...,Vn; k)) ≥ Vk(F(V1,...,Vn; i))</blockquote>But since Vi=Vk*, the two inequalities imply that both values are equal.
However, a procedure that satisfies the weaker condition of proportional-cake-cutting is not necessarily aristotelian. Cheze Alternative symmetric fair cake-cutting procedures for two agents are rightmost mark and leftmost leaves.
Cheze Suppose w.l.o.g. that the EFM matches agents 1,...,k to pieces X1,...,Xk, and leaves unmatched the agents and pieces from k+1 to n. # For each i in 1,...,k for which Vi(Xi) = 1 - give Xi to agent i. Now, the divider and all agents whose value function is identical to the dividers' are assigned a piece and have the same value. # Consider now the agents i in 1,...,k for which Vi(Xi) > 1. Partition them into subsets with identical value-vector for the pieces X1,...,Xk. For each subset, recursively divide their pieces among them (for example, if agents 1, 3, 4 agree on the values of all the pieces 1,...,k, then divide pieces X1,X3,X4 recursively among them). Now, all agents whose value-function is identical are assigned to the same subset, and they divide a subcake whose value for them is greater than their number, so the precondition for recursion is satisfied. # Recursively divide the unmatched pieces Xk+1, ..., Xn among the unmatched agents. Note that, by envy-freeness of the matching, each unmatched agent values each matched piece at less than 1, so he values the remaining pieces at more than the number of agents, so the precondition for recursion is satisfied.