Social:Symmetric fair cake-cutting

Short description: 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:

• 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 V_i 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₁,...,V_n; i).

Symmetric procedure

A division procedure F is called symmetric if, for any permutation p of (1,...,n), and for every i:

V_i(F(V₁,...,V_n; i)) = V_i(F(V_p(1),...,V_p(n); p⁻¹(i)))

In particular, when n=2, a procedure is symmetric if:

V₁(F(V₁,V₂; 1)) = V₁(F(V₂,V₁; 2)) and V₂(F(V₁,V₂; 2)) = V₂(F(V₂,V₁; 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₁(F(V₁,V₂,V₃; 1)) = V₁(F(V₂,V₃,V₁; 3)) = V₁(F(V₃,V₁,V₂; 2)).

Anonymous procedure

A division procedure F is called anonymous if, for any permutation p of (1,...,n), and for every i:

F(V₁,...,V_n; i) = F(V_p(1),...,V_p(n); p⁻¹(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 V_i=V_k:

V_i(F(V₁,...,V_n; i)) = V_k(F(V₁,...,V_n; 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:

V_i(F(V₁,....V_i,...,V_k,...,V_n; i)) = V_i(F(V₁,....V_k,...,V_i,...,V_n; k))

But since V_i=V_k, 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:

V_i(F(V₁,...,V_n; i)) ≥ V_i(F(V₁,...,V_n; k)) V_k(F(V₁,...,V_n; k)) ≥ V_k(F(V₁,...,V_n; i))

But since V_i=V_k, 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:

• Anonymous → Symmetric → Aristotelian
• Envy-free → Aristotelian
• Envy-free → Proportional

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:

• A general scheme for convering any envy-free procedure into a symmetric deterministic procedure: run the original procedure n! times, once for each permutation of the agents, and choose one of the outcomes according to some topological criterion (e.g. minimizing the number of cuts). This procedure is not practical when n is large.
• An aristotelian proportional procedure for n agents, which requires O(n³) queries and a polynomial number of arithmetic operations by the referee.
• A symmetric proportional procedure for n agents, which requires O(n³) queries, but may require an exponential number of arithmetic operations by the referee.

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.

1. One player chosen arbitrarily, called the divider, cuts the cake into n pieces whose value in his/her eyes is exactly 1.
2. Construct a bipartite graph G = (X+Y, E) in which each vertex in X is an agent, each vertex in Y is a piece, and there is an edge between an agent x and a piece y iff x values y at least 1.
3. Find a maximum-cardinality envy-free matching in G (a matching in which no unmatched agent is adjacent to a matched piece). Note that the divider is adjacent to all n pieces, so |N_G(X)|= n ≥ |X| (where N_G(X) is the set of neighbors of X in Y). Hence, a non-empty envy-free matching exists. Suppose w.l.o.g. that the EFM matches agents 1,...,k to pieces X₁,...,X_k, and leaves unmatched the agents and pieces from k+1 to n.
4. For each i in 1,...,k for which V_i(X_i) = 1 - give X_i 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.
5. Consider now the agents i in 1,...,k for which V_i(X_i) > 1. Partition them into subsets with identical value-vector for the pieces X₁,...,X_k. 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 X₁,X_3,X₄ 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.
6. Recursively divide the unmatched pieces X_k+1, ..., X_n 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.