Cake-cutting problem
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:
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"("V"1...,"Vn"; "i").
Symmetric procedure.
A division procedure "F" is called symmetric if, for any permutation "p" of (1...,"n"), and for every "i":"Vi"("F"("V"1...,"Vn"; "i")) = "Vi"("F"("V"p(1)...,"Vp(n)"; "p"−1("i")))In particular, when "n"=2, a procedure is symmetric if:"V"1("F"("V"1,"V2"; 1)) = "V"1("F"("V"2,"V1"; 2)) and "V"2("F"("V"1,"V2"; 2)) = "V"2("F"("V"2,"V1"; 1)) 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):"V"1("F"("V"1,"V2","V3"; 1)) = "V"1("F"("V"2,"V3,V1"; 3)) = "V"1("F"("V3,V1","V"2; 2)).
Anonymous procedure.
A division procedure "F" is called anonymous if, for any permutation "p" of (1...,"n"), and for every "i":"F"("V"1...,"Vn"; "i") = "F"("V"p(1)...,"Vp(n)"; "p"−1("i"))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":"Vi(F"("V"1...,"Vn"; "i")) = "Vk"("F"("V"1...,"Vn"; "k"))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:"Vi(F"("V"1..."Vi"...,"Vk"...,"Vn"; "i")) = "Vi(F"("V"1..."Vk"...,"V"i...,"Vn"; "k")) 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:"Vi(F"("V"1...,"Vn"; "i")) ≥ "Vi"("F"("V"1...,"Vn"; "k"))
"Vk(F"("V"1...,"Vn"; "k")) ≥ "Vk"("F"("V"1...,"Vn"; "i"))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 shows an example with 4 agents in which the Even-Paz procedure for proportional cake-cutting may give different values to agents with identical value-measures.
The following chart summarizes the relations between the criteria:
Procedures.
Every procedure can be made "symmetric ex-ante" by randomization. For example, in the asymmetric divide-and-choose, the divider can be selected by tossing a coin. However, such a procedure is not symmetric ex-post. Therefore, the research regarding symmetric fair cake-cutting focuses on deterministic algorithms.
Manabe and Okamoto presented symmetric and envy-free ("meta-envy-free") deterministic procedures for two and three agents.
Nicolo and Yu presented an anonymous, envy-free and Pareto-efficient division protocol for two agents. The protocol implements the allocation in subgame perfect equilibrium, assuming each agent has complete information on the valuation of the other agent.
The symmetric cut and choose procedure for two agents was studied empirically in a lab experiment. Alternative symmetric fair cake-cutting procedures for two agents are "rightmost mark" and "leftmost leaves".
Cheze presented several procedures:
Aristotelian proportional procedure.
The aristotelian procedure of Cheze for proportional cake-cutting extends the lone divider procedure. For convenience, we normalize the valuations such that the value of the entire cake is "n" for all agents. The goal is to give each agent a piece with a value of at least 1.
References.
 ;templatestyles src="Reflist/styles.css" / ;