# Fair cake-cutting

Last updated

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 subjectively fair, in that each person should receive a piece that he or she believes to be a fair share.

## Contents

The "cake" is only a metaphor; procedures for fair cake-cutting can be used to divide various kinds of resources, such as land estates, advertisement space or broadcast time.

The cake-cutting problem was introduced by Hugo Steinhaus after World War II [1] and is still the subject of intense research in mathematics, computer science, economics and political science. [2]

## Assumptions

There is a cake C, which is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane Rd.

There are n people with equal rights to C. [3]

C has to be divided to n disjoint subsets, such that each person receives a disjoint subset. The piece allocated to person i is called ${\displaystyle X_{i}}$, and ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{n}}$.

Each person should get a piece with a "fair" value. Fairness is defined based on subjective value functions. Each person i has a subjective value function Vi which maps subsets of C to numbers.

All value functions are assumed to be absolutely continuous with respect to the length, area or (in general) Lebesgue measure. [4] This means that there are no "atoms" – there are no singular points to which one or more agents assign a positive value, so all parts of the cake are divisible.

Additionally, in some cases, the value functions are assumed to be sigma additive (the value of a whole is equal to the sum of the values of its parts).

## Example cake

In the following lines we will use the following cake as an illustration.

• The cake has two parts: chocolate and vanilla.
• There are two people: Alice and George.
• Alice values the chocolate as 9 and the vanilla as 1.
• George values the chocolate as 6 and the vanilla as 4.

## Justice requirements

The original and most common criterion for justice is proportionality (PR). In a proportional cake-cutting, each person receives a piece that he values as at least 1/n of the value of the entire cake. In the example cake, a proportional division can be achieved by giving all the vanilla and 4/9 of the chocolate to George (for a value of 6.66), and the other 5/9 of the chocolate to Alice (for a value of 5). In symbols:

${\displaystyle \forall {i}:\ V_{i}(X_{i})\geq 1/n}$

The proportionality criterion can be generalized to situations in which the rights of the people are not equal. For example, in proportional cake-cutting with different entitlements, the cake belongs to shareholders such that one of them holds 20% and the other holds 80% of the cake. This leads to the criterion of weighted proportionality (WPR):

${\displaystyle \forall i:V_{i}(X_{i})\geq w_{i}}$

Where the wi are weights that sum up to 1.

Another common criterion is envy-freeness (EF). In an envy-free cake-cutting, each person receives a piece that he values at least as much as every other piece. In symbols:

${\displaystyle \forall i,j:\ V_{i}(X_{i})\geq V_{i}(X_{j})}$

In some cases, there are implication relations between proportionality and envy-freeness, as summarized in the following table:

AgentsValuationsEF implies PR?PR implies EF?
2generalNoYes
3+generalNoNo

A third, less common criterion is equitability (EQ). In an equitable division, each person enjoys exactly the same value. In the example cake, an equitable division can be achieved by giving each person half the chocolate and half the vanilla, such that each person enjoys a value of 5. In symbols:

${\displaystyle \forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})}$

A fourth criterion is exactness. If the entitlement of each partner i is wi, then an exact division is a division in which:

${\displaystyle \forall {i,j}:\ V_{i}(X_{j})=w_{j}}$

If the weights are all equal (to 1/n) then the division is called perfect and:

${\displaystyle \forall i,j:\ V_{i}(X_{j})=1/n}$

## Geometric requirements

In some cases, the pieces allocated to the partners must satisfy some geometric constraints, in addition to being fair.

• The most common constraint is connectivity . In case the "cake" is a 1-dimensional interval, this translates to the requirement that each piece is also an interval. In case the cake is a 1-dimensional circle ("pie"), this translates to the requirement that each piece be an arc; see fair pie-cutting.
• Another constraint is adjacency. This constraint applies to the case when the "cake" is a disputed territory that has to be divided among neighboring countries. In this case, it may required that the piece allocated to each country is adjacent to its current territory; this constraint is handled by Hill's land division problem.
• In land division there are often two-dimensional geometric constraints, e.g., each piece should be a square or (more generally) a fat object. [5]

## Efficiency and truthfulness

In addition to justice, it is also common to consider the economic efficiency of the division; see Efficient cake-cutting.

In addition to the desired properties of the final partitions, there are also desired properties of the division process. One of these properties is truthfulness (aka incentive compatibility), which comes in two levels.

• Weak truthfulness means that if the partner reveals his true value measure to the algorithm, he is guaranteed to receive his fair share (e.g. 1/n of the value of the entire cake, in case of proportional division), regardless of what other partners do. Even if all other partners make a coalition with the only intent to harm him, he will still receive his guaranteed proportion. Most cake-cutting algorithms are truthful in this sense. [1]
• Strong truthfulness means that no partner can gain from lying. I.e., telling the truth is a dominant strategy. Most cake-cutting protocols are not strongly truthful, but some truthful protocols have been developed; see truthful cake-cutting.

## Results

### 2 people – proportional and envy-free division

For ${\displaystyle n=2}$ people, an EF division always exists and can be found by the divide and choose protocol. If the value functions are additive then this division is also PR; otherwise, proportionality is not guaranteed.

### Proportional division

For n people with additive valuations, a proportional division always exists. The most common protocols are:

• Last diminisher, a protocol that can guarantee that the n pieces are connected (i.e. no person gets a set of two or more disconnected pieces). In particular, if the cake is a 1-dimensional interval then each person receives an interval. This protocol is discrete and can be played in turns. It requires O(n2) actions.
• The Dubins–Spanier Moving-knife procedure is a continuous-time version of Last diminisher. [6]
• Fink protocol (also known as successive pairs or lone chooser) is a discrete protocol that can be used for online division: given a proportional division for n  1 partners, when a new partner enters the party, the protocol modifies the existing division so that both the new partner and the existing partners remain with 1/n. The disadvantage is that each partner receives a large number of disconnected pieces.
• The Even–Paz protocol, based on recursively halving the cake and the group of agents, requires only O(n log n) actions. This is fastest possible deterministic protocol for proportional division, and the fastest possible protocol for proportional division which can guarantee that the pieces are connected.
• Edmonds–Pruhs protocol is a randomized protocol that requires only O(n) actions, but guarantees only a partially proportional division (each partner receives at least 1/an, where a is some constant), and it might give each partner a collection of "crumbs" instead of a single connected piece.
• Beck land division protocol can produce a proportional division of a disputed territory among several neighbouring countries, such that each country receives a share that is both connected and adjacent to its currently held territory.
• Woodall's super-proportional division protocol produces a division which gives each partner strictly more than 1/n, given that at least two partners have different opinions about the value of at least a single piece.

See proportional cake-cutting for more details and complete references.

The above algorithms focus mainly on agents with equal entitlements to the resource; however, it is possible to generalize them and get a proportional cake-cutting among agents with different entitlements.

### Envy-free division

An EF division for n people exists even when the valuations are not additive, as long as they can be represented as consistent preference sets. EF division has been studied separately for the case in which the pieces must be connected, and for the easier case in which the pieces may be disconnected.

For connected pieces the major results are:

• Stromquist moving-knives procedure produces an envy-free division for 3 people, by giving each one of them a knife and instructing them to move their knives continuously over the cake in a pre-specified manner.
• Simmons' protocol can produce an approximation of an envy-free division for n people with an arbitrary precision. If the value functions are additive, the division will also be proportional. Otherwise, the division will still be envy-free but not necessarily proportional. The algorithm gives a fast and practical way of solving some fair division problems. [7] [8]

Both these algorithms are infinite: the first is continuous and the second might take an infinite time to converge. In fact, envy-free divisions of connected intervals to 3 or more people cannot be found by any finite protocol.

For possibly-disconnected pieces the major results are:

• Selfridge–Conway discrete procedure produces an envy-free division for 3 people using at most 5 cuts.
• Brams–Taylor–Zwicker moving knives procedure produces an envy-free division for 4 people using at most 11 cuts.
• A reentrant variant of the Last Diminisher protocol finds an additive approximation to an envy-free division in bounded time. Specifically, for every constant ${\displaystyle \epsilon >0}$, it returns a division in which the value of each partner is at least the largest value minus ${\displaystyle \epsilon }$, in time ${\displaystyle O(n^{2}/\epsilon )}$.
• Three different procedures, one by Brams and Taylor (1995) and one by Robertson and Webb (1998) and one by Pikhurko (2000), produce an envy-free division for n people. Both algorithms require a finite but unbounded number of cuts.
• A procedure by Aziz and Mackenzie (2016) finds an envy-free division for n people in a bounded number of queries.

The negative result in the general case is much weaker than in the connected case. All we know is that every algorithm for envy-free division must use at least Ω(n2) queries. There is a large gap between this result and the runtime complexity of the best known procedure.

See envy-free cake-cutting for more details and complete references.

### Efficient division

When the value functions are additive, utilitarian-maximal (UM) divisions exist. Intuitively, to create a UM division, we should give each piece of cake to the person that values it the most. In the example cake, a UM division would give the entire chocolate to Alice and the entire vanilla to George, achieving a utilitarian value of 9 + 4 = 13.

This process is easy to carry out when the value functions are piecewise-constant, i.e. the cake can be divided to pieces such that the value density of each piece is constant for all people. When the value functions are not piecewise-constant, the existence of UM divisions is based on a generalization of this procedure using the Radon–Nikodym derivatives of the value functions; see Theorem 2 of. [6]

When the cake is 1-dimensional and the pieces must be connected, the simple algorithm of assigning each piece to the agent that values it the most no longer works. In this case, the problem of finding a UM division is NP-hard, and furthermore no FPTAS is possible unless P = NP. There is an 8-factor approximation algorithm, and a fixed-parameter tractable algorithm which is exponential in the number of players. [9]

For every set of positive weights, a WUM division can be found in a similar way. Hence, PE divisions always exist.

### Procedural fairness

Recently there is interest not only in the fairness of the final allocation but also in the fairness of the allocation procedures: there should not be a difference between different roles in the procedure. Several definitions of procedural fairness have been studied:

• Anonymity requires that, if the agents are permuted and the procedure is re-executed, then each agent receives exactly the same piece as in the original execution. This is a strong condition; currently, an anonymous procedure is known only for 2 agents.
• Symmetry requires that, if the agents are permuted and the procedure is re-executed, then each agent receives the same value as in the original execeution. This is weaker than anonymity; currently, a symmetric and proportional procedure is known for any number of agents, and it takes O(n3) queries. A symmetric and envy-free procedure is known for any number of agents, but it takes much longer - it requires n! executions of an existing envy-free procedure.
• Aristotelianity requires that, if two agents have an identical value-measure, then they receive the same value. This is weaker than symmetry; it is satisfied by any envy-free procedure. Moreover, an aristotelian and proportional procedure is known for any number of agents, and it takes O(n3) queries.

See symmetric fair cake-cutting for details and references.

### Efficient fair division

For n people with additive value functions, a PEEF division always exists. [10]

If the cake is a 1-dimensional interval and each person must receive a connected interval, the following general result holds: if the value functions are strictly monotonic (i.e. each person strictly prefers a piece over all its proper subsets) then every EF division is also PE. [11] Hence, Simmons' protocol produces a PEEF division in this case.

If the cake is a 1-dimensional circle (i.e. an interval whose two endpoints are topologically identified) and each person must receive a connected arc, then the previous result does not hold: an EF division is not necessarily PE. Additionally, there are pairs of (non-additive) value functions for which no PEEF division exists. However, if there are 2 agents and at least one of them has an additive value function, then a PEEF division exists. [12]

If the cake is 1-dimensional but each person may receive a disconnected subset of it, then an EF division is not necessarily PE. In this case, more complicated algorithms are required for finding a PEEF division.

If the value functions are additive and piecewise-constant, then there is an algorithm that finds a PEEF division. [13] If the value density functions are additive and Lipschitz continuous, then they can be approximated as piecewise-constant functions "as close as we like", therefore that algorithm approximates a PEEF division "as close as we like". [13]

An EF division is not necessarily UM. [14] [15] One approach to handle this difficulty is to find, among all possible EF divisions, the EF division with the highest utilitarian value. This problem has been studied for a cake which is a 1-dimensional interval, each person may receive disconnected pieces, and the value functions are additive. [16]

## Related Research Articles

Fair division is the problem of dividing a set of resources among several people who have an entitlement to them, such that each person receives their due share. This 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. This is an active research area in mathematics, economics, game theory, dispute resolution, and more. 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 envy-free cake-cutting between two partners. 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 chooses 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.

An exact division, also called even division or consensus division, is a division of a heterogeneous resource ("cake") to several subsets such that each of n people with different tastes agree about the valuations of the pieces.

The last diminisher procedure is a procedure for fair cake-cutting. It involves a certain 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 achieve a proportional division, i.e., 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. For example, if Alice values the entire cake as $100 and there are 5 partners then Alice can receive a piece that she values as at least$20, regardless of what the other partners think or do.

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, 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, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

The Simmons–Su protocols are several protocols for envy-free division. They are based on Sperner's lemma. The merits of these protocols is that they put few restrictions on the preferences of the partners, and ask the partners only simple queries such as "which piece do you prefer?".

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

An equitable division (EQ) is a division of a heterogeneous object, 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:

Fair item allocation is a kind of a fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Envy-freeness (EF) is a criterion of fair division. In an envy-free division, every agent feels that their share is at least as good as the share of any other agent, and thus no agent feels 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 inspired by the utilitarian philosophy. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is in conflict with fair cake-cutting.

Envy-free item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that he believes to be at least as good as the bundle of any other agent.

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.

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.

## References

1. Steinhaus, Hugo (1949). "The problem of fair division". Econometrica. 17: 315–9. JSTOR   1907319.
2. Ariel Procaccia, "Cake Cutting Algorithms". Chapter 13 in: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN   9781107060432.
3. I.e. there is no dispute over the rights of the people – the only problem is how to divide the cake such that each person receives a fair share.
4. Hill, T. P.; Morrison, K. E. (2010). "Cutting Cakes Carefully". The College Mathematics Journal. 41 (4): 281. CiteSeerX  . doi:10.4169/074683410x510272.
5. Segal-Halevi, Erel; Nitzan, Shmuel; Hassidim, Avinatan; Aumann, Yonatan (2017). "Fair and square: Cake-cutting in two dimensions". Journal of Mathematical Economics. 70: 1–28. arXiv:. doi:10.1016/j.jmateco.2017.01.007.
6. Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68 (1): 1–17. doi:10.2307/2311357. JSTOR   2311357.
7. "The Fair Division Calculator". Archived from the original on 2010-02-28. Retrieved 2014-07-10.
8. Ivars Peterson (March 13, 2000). "A Fair Deal for Housemates". MathTrek.
9. Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013). Computing Socially-Efficient Cake Divisions. AAMAS.
10. Weller, D. (1985). "Fair division of a measurable space". Journal of Mathematical Economics. 14: 5–17. doi:10.1016/0304-4068(85)90023-0.
11. Berliant, M.; Thomson, W.; Dunz, K. (1992). "On the fair division of a heterogeneous commodity". Journal of Mathematical Economics. 21 (3): 201. doi:10.1016/0304-4068(92)90001-n.
12. Thomson, W. (2006). "Children Crying at Birthday Parties. Why?". Economic Theory. 31 (3): 501–521. doi:10.1007/s00199-006-0109-3.
13. Reijnierse, J. H.; Potters, J. A. M. (1998). "On finding an envy-free Pareto-optimal division". Mathematical Programming. 83 (1–3): 291–311. doi:10.1007/bf02680564.
14. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M. (2011). "The Efficiency of Fair Division". Theory of Computing Systems. 50 (4): 589. CiteSeerX  . doi:10.1007/s00224-011-9359-y.
15. Aumann, Y.; Dombb, Y. (2010). . Internet and Network Economics. Lecture Notes in Computer Science. 6484. pp.  26. CiteSeerX  . doi:10.1007/978-3-642-17572-5_3. ISBN   978-3-642-17571-8.
16. Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Optimal Envy-Free Cake Cutting. AAAI.