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: is the piece of cake allocated to partner ; is the value measure of partner . It is a real-valued function that, for every piece of cake, returns a number that represents the utility of partner from that piece. Usually these functions are normalized such that and for every . 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 , calculate and 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: It is EF, since each partner receives a value of at least 1/2. It is not EX, since the value per partner may be more than 1/2. It is Pareto efficient (PE) among all divisions that use a single cut. However, there may be more efficient divisions that use two or more cuts. If the direction of the cake is chosen at random (i.e. it can be flipped such that 0 becomes 1 and 1 becomes 0), then this procedure is also weakly truthful, in the following sense: only by submitting sincere probability measures, can a partner ensure that he receives at least half of the cake. 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 and of partner B is , with . Then, A receives and B receives . Now there is a surplus - . 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 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