Symmetric fair cake-cutting

Last updated

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.

Contents

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, [1] who termed it meta-envy-free.

Several variants of symmetric fair cake-cutting have been proposed:

Definitions

There is a cakeC, 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:

Vi(F(V1,...,Vn; i)) = Vi(F(Vp(1),...,Vp(n); p−1(i)))

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

V1(F(V1,V2; 1)) = V1(F(V2,V1; 2)) and V2(F(V1,V2; 2)) = V2(F(V2,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):

V1(F(V1,V2,V3; 1)) = V1(F(V2,V3,V1; 3)) = V1(F(V3,V1,V2; 2)).

Anonymous procedure

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

F(V1,...,Vn; i) = F(Vp(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(V1,...,Vn; i)) = Vk(F(V1,...,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(V1,....Vi,...,Vk,...,Vn; i)) = Vi(F(V1,....Vk,...,Vi,...,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(V1,...,Vn; i)) ≥ Vi(F(V1,...,Vn; k)) Vk(F(V1,...,Vn; k)) ≥ Vk(F(V1,...,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 [3] 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 [1] presented symmetric and envy-free ("meta-envy-free") deterministic procedures for two and three agents.

Nicolo and Yu [2] 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. [4] Alternative symmetric fair cake-cutting procedures for two agents are rightmost mark [5] and leftmost leaves. [6]

Cheze [3] presented several procedures:

Aristotelian proportional procedure

The aristotelian procedure of Cheze [3] 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 |NG(X)|= n ≥ |X| (where NG(X) is the set of neighbors of X in Y). Hence, a non-empty envy-free matching exists. [7] 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.
  4. 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.
  5. 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.
  6. 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.

Related Research Articles

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 inheritance, partnership dissolutions, divorce settlements, electronic frequency allocation, airport traffic management, and exploitation of Earth observation satellites. It is an active research area in mathematics, economics, dispute resolution, etc. The central tenet of fair division is that such a division should be performed by the players themselves, maybe using a mediator but certainly not an arbiter as only the players really know how they value the goods.

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 share, according to their own subjective valuation.

Divide and 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 and two partners who have different preferences over parts of the cake. The protocol proceeds as follows: one person cuts the cake into two pieces; the other person selects one of the pieces; the cutter receives the remaining piece.

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.

Chore division is a fair division 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 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 in 1978.

The Selfridge–Conway procedure is a discrete procedure that produces an envy-free cake-cutting for three partners. It is named after John Selfridge and John Horton Conway. Selfridge discovered it in 1960, and told it to Richard Guy, who told many people, but Selfridge did not publish it. John Conway later discovered it independently, and also never published it. This procedure was the first envy-free discrete procedure devised for three partners, and it paved the way for more advanced procedures for n partners.

The Brams–Taylor procedure (BTP) is a procedure for envy-free cake-cutting. It explicated the first finite procedure to produce an envy-free division of a cake among any positive integer number of players.

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

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 destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

The Robertson–Webb protocol is a protocol for envy-free cake-cutting which is also near-exact. It has the following properties:

The fair pie-cutting problem is a variation of the fair cake-cutting problem, in which the resource to be divided is circular.

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/her share. Mathematically, that means that for all partners i and j:

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 any other agent. In other words, no person should feel envy.

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 the total.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

The lone divider procedure is a procedure for proportional cake-cutting. It involves a heterogenous and divisible resource, such as a birthday cake, and n partners with different preferences over different parts of the cake. It allows the n people to divide the cake among them such that each person receives a piece with a value of at least 1/n of the total value according to his own subjective valuation.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query asks an agent to specify a piece of cake with a given value.

A super-envy-free division is a kind of a fair division. It is a division of resources among n partners, in which each partner values his/her share at strictly more than his/her due share of 1/n of the total value, and simultaneously, values the share of every other partner at strictly less than 1/n. Formally, in a super-envy-free division of a resource C among n partners, each partner i, with value measure Vi, receives a share Xi such that:

.

References

  1. 1 2 Manabe, Yoshifumi; Okamoto, Tatsuaki (2010). "Meta-Envy-Free Cake-Cutting Protocols". Mathematical Foundations of Computer Science 2010. MFCS'10. Vol. 6281. Berlin, Heidelberg: Springer-Verlag. pp. 501–512. Bibcode:2010LNCS.6281..501M. doi:10.1007/978-3-642-15155-2_44. ISBN   9783642151545.
  2. 1 2 Nicolò, Antonio; Yu, Yan (2008-09-01). "Strategic divide and choose" (PDF). Games and Economic Behavior. 64 (1): 268–289. doi:10.1016/j.geb.2008.01.006. ISSN   0899-8256.
  3. 1 2 3 4 Chèze, Guillaume (2018-04-11). "Don't cry to be the first! Symmetric fair division algorithms exist". arXiv: 1804.03833 [cs.GT].
  4. ↑ Kyropoulou, Maria; Ortega, Josué; Segal-Halevi, Erel (2019). "Fair Cake-Cutting in Practice". Proceedings of the 2019 ACM Conference on Economics and Computation. EC '19. New York, NY, USA: ACM. pp. 547–548. arXiv: 1810.08243 . doi:10.1145/3328526.3329592. ISBN   9781450367929. S2CID   53041563.
  5. ↑ Segal-Halevi, Erel; Sziklai, Balázs R. (2018-09-01). "Resource-monotonicity and population-monotonicity in connected cake-cutting". Mathematical Social Sciences. 95: 19–30. arXiv: 1703.08928 . doi:10.1016/j.mathsocsci.2018.07.001. ISSN   0165-4896. S2CID   16282641.
  6. ↑ Ortega, Josue (2019-08-08). "Obvious Manipulations in Cake-Cutting". arXiv: 1908.02988 [cs.GT].
  7. ↑ Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv: 1901.09527 . doi:10.1016/j.ins.2021.11.059. S2CID   170079201.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.