Equitable cake-cutting
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 and : Where: See the page on equitability for examples and comparison to other fairness criteria. Finding an equitable cake-cutting for two partners. One cut - full revelation. When there are 2 partners, it is possible to get an EQ division with a single cut , but it requires full knowledge of the partners' valuations. Assume that the cake is the interval [0,1]. For each formula_6, calculate formula_7 and formula_8 and plot them on the same graph. Note that the first graph is increasing from 0 to 1 and the second graph is decreasing from 1 to 0, so they have an intersection point. Cutting the cake at that point yields an equitable division. This division has several additional properties: The same procedure can be used for dividing chores (with negative utility). Proportional-equitability variant. The full revelation procedure has a variant which satisfies a weaker  kind of equitability and a stronger kind of truthfulness. The procedure first finds the median points of each partner. Suppose the median point of partner A is formula_9 and of partner B is formula_10, with formula_11 and B receives formula_12. Now there is a surplus - formula_13. The surplus is divided between the partners in "equal proportions". So, for example, if A values the surplus as 0.4 and B values the surplus as 0.2, then A will receive twice more value from formula_13 than B. So this protocol is not equitable, but it is still EF. It is weakly-truthful in  the following sense: a risk-averse player has an incentive to report his true valuation, because reporting an untrue valuation might leave him with a smaller value. Two cuts - moving knife. Austin moving-knife procedure gives each of the two partners a piece with a subjective value of "exactly" 1/2. Thus the division is EQ, EX and EF. It requires 2 cuts, and gives one of the partners two disconnected pieces. Many cuts - full revelation. When more than two cuts are allowed, it is possible to achieve a division which is not only EQ but also EF and PE. Some  authors call such a division "perfect". The minimum number of cuts required for a PE-EF-EQ division depends on the valuations of the partners. In most practical cases (including all cases when the valuations are piecewise-linear) the number of required cuts is finite. In these cases, it is possible to both find the optimal number of cuts and their exact locations. The algorithm requires full knowledge of the partners' valuations. Run-time. All the above procedures are continuous: the second requires a knife that moves continuously, the others requires a continuous plot of the two value measures. Therefore , they cannot be carried out in a finite number of discrete steps. This infinity property is characteristic of division problems which require an exact result. See Exact division#Impossibility. One cut - near-equitable division. A "near-equitable division" is a division in which the partners' values differ by at most formula_15, for any given formula_16. A near-equitable division for two partners can be found in finite time and with a single cut. Finding an equitable division for three or more partners. Moving knife procedure. Austin's procedure can be extended to "n" partners. It gives each partner a piece  with a subjective value of exactly formula_17. This division is EQ, but not necessarily EX or EF or PE (since some partners may value the share given to other partners as more than formula_17). Connected pieces - full revelation. Jones' full revelation procedure can be extended to formula_19 partners in the following way: Note that the maximal equitable value must be at least formula_17, because we already know that a proportional division (giving each partner at least formula_17) is possible. If the value measures of the partners are absolutely continuous with respect to each other (this means that they have the  same support), then any attempt to increase the value of a partner must decrease the value of another partner. This means that the solution is PE among the solutions which give connected pieces. Impossibility results. Brams, Jones and Klamler study a division which is EQ, PE and EF (they call such a division "perfect"). They first prove that, for 3 partners that must get connected pieces, an EQ+EF division may not exist. They do this by describing 3 specific value measures on a 1-dimensional cake, in which every EQ allocation with 2 cuts is not EF. Then they prove  that, for 3 or more partners, a PE+EF+EQ division may not exist even with disconnected pieces. They do this by describing 3 specific value measures on a 1-dimensional cake, with the following properties: Pie cutting. A "pie" is a cake in the shape of a 1-dimensional circle (see fair pie-cutting). Barbanel, Brams and Stromquist study the existence of divisions of a pie, which are both EQ and EF. The following existence results are proved without providing a specific division algorithm: Divisible goods. The adjusted winner procedure calculates an equitable, envy-free and efficient division of a set  of divisible goods between two partners. Query complexity. An equitable cake allocation cannot be found using a finite protocol in the Robertson–Webb query model, even for 2 agents. Moreover, for any ε > 0: Properties of max-equitable allocation rules. The "max-equitable" division rule is a rule that selects, from among all equitable cake allocations, the one in which the common value of the agents is maximum. It has two variants: There always exists a connected max-equitable alloation (both absolute and relative), and it can be found using a generalized moving-knives procedure. Equitable cake-cutting