Fair cake-cutting
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 that he or  she believes to be a fair share. 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 prototypical procedure for fair cake-cutting is divide and choose, which is mentioned already in the book of Genesis. It solves the fair division problem for two people. The modern study of fair cake-cutting was initiated during World War II, when Hugo Steinhaus asked his students Stefan Banach and Bronisław Knaster to find a generalization of divide-and-choose to three or  more people. They developed the last diminisher procedure. Today, fair cake-cutting is the subject of intense research in mathematics, computer science, economics and political science. 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 R. There are "n" people with subjective value functions over "C". Each person "i" has a value function "V" 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. 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. In many 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). "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 formula_1, and formula_2. The "n" people have equal rights to "C". I.e., there is  no dispute over the rights of the people – everyone agrees that everyone else is entitled to a fair share. The only problem is how to divide the cake such that each person receives a fair share. In the following examples the following cake will be used as an illustration. Justice requirements. Proportionality. 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: For "n" people with additive valuations, a proportional division always exists. The most common protocols are: See proportional cake-cutting for more details and complete references. 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): Where the "w" are weights that sum up to 1. Envy-freeness. 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: In some cases, there are implication relations between proportionality and envy-freeness, as summarized in the following table: The divide and choose protocol finds an allocation that is always EF. If the value functions are additive then this division is also PR; otherwise, proportionality is  not guaranteed. 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: 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: 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 Ω(n") 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. Other criteria. 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: A fourth criterion is "exactness". If the entitlement of each partner "i" is "w", then an exact division is a division in which: If the weights are all equal (to 1/"n") then the division is called "perfect" and: Geometric requirements. In some cases, the pieces allocated to the partners must satisfy some geometric constraints, in addition to being fair. Procedural requirements. 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. Another property is symmetry: there should not be a difference between different roles in the procedure. Several variants of this property have been studied: See symmetric fair cake-cutting for details and references. A third family of procedural requirements is monotonicity: when a division procedure is re-applied with a smaller/larger cake and a smaller/larger set of agents, the utility of all agents should change in the same direction. See resource monotonicity for more details. Efficiency requirements. In addition to justice , it is also common to consider the economic efficiency of the division; see efficient cake-cutting. There are several levels of efficiency: Efficient fair division. For "n" people with additive value functions, a PEEF division always exists. 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. 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. 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. 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". An EF division is not necessarily UM. 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. Models of computation. Reasoning about the run-time complexity of algorithms requires a model of computation. Several such models are common in the literature: Dividing multiple cakes. There is a generalization of the cake-cutting problem in which there are several cakes, and each agent needs to get a piece in each cake. Two related problems are: