Английская Википедия:Fair pie-cutting
The fair pie-cutting problem is a variation of the fair cake-cutting problem, in which the resource to be divided is circular.
As an example, consider a birthday cake shaped as a disk. The cake should be divided among several children such that no child envies another child (as in a standard cake-cutting problem), with the additional constraint that the cuts must be radial, so that each child receives a circular sector.
A possible application of the pie model might be for dividing an island’s shoreline into connected lots.
Another possible application is in division of periodic time, such as dividing a daily cycle into "on-call" periods.
Model
A pie is usually modeled as the 1-dimensional interval [0,2π] (or [0,1]), in which the two endpoints are identified.
This model was introduced in 1985 and later in 1993.[1][2]
Every procedure for fair cake-cutting can also be applied to cutting a pie by just ignoring the fact that the two endpoints are identified. For example, if the cake-cutting procedure yielded a division in which Alice receives [0,1/3] and the George receives [1/3,1], then we would give Alice a circular sector of 120 degrees and George the remaining sector with 240 degrees.
Pie cutting becomes more interesting when we consider questions of efficiency, since in pie-cutting more divisions are possible.
Two partners
Envy-free division
A division is called envy-free (EF) if each partner thinks that his piece is at least as valuable as the other piece.
An EF division of a pie can always be found using divide and choose: one partner cuts the pie into two sectors he considers equal, and the other partner chooses the sector that he considers better. But for a pie, better divisions may be possible.
Envy-free and Pareto-efficient division
A division is called Pareto efficient (PE) if no other division is better for one partner and not worse for the other. Often, Pareto efficiency is evaluated only with relation to a subset of all possible divisions. I.e, only divisions to two contiguous sectors (divisions with the minimal number of cuts).
A division is called PEEF if it is both PE and EF.
When the valuations of the partners are (additive) measures, the following moving-knife procedure guarantees a division which is EF, and PE relative to divisions to two contiguous sectors.[3]
One partner (the Rotator) holds two radial knives above the pie in such a way that, in her view, the two sectors of pie determined by these knives each have the same value. She then rotates these knives continuously, all the way around the pie, maintaining this equal value of the sectors until the knives return to their original positions.
The other partner (the Chooser) observes this process during an entire cycle. Then, in the next cycle, he identifies the position that, in his view, gives the maximum value to one of the two sectors so determined. The Chooser receives this sector and the Rotator receives the other sector.
This partition is obviously EF, since the Rotator is indifferent between the two sectors the Chooser receives the better sector. It is PE because there is no partition that would give the Chooser a larger value and leave a value of 1/2 to the Rotator.
Additivity constraints
The above procedure works only if the value function of the Rotator is additive, so that the equal shares always have the same value of 1/2. If her value is not additive, then the division would still be envy-free but not necessarily Pareto-efficient.
Moreover, when the valuations of both partners are not additive (so none of them can play as the Rotator), a PEEF division does not always exist.[4]
Consensus division and weighted proportional division
A division is called an exact division (aka consensus division) if the value of piece <math>i</math> is exactly <math>w_i</math> according to all partners, where the <math>w_i</math>are pre-specified weights.
Suppose the sum of all weights is 1, and the value of the pie for all agents is normalized to 1 too. By the Stromquist-Woodall theorem, for every weight <math>w \in [0,1]</math>, there is a subset <math>C_w</math>, which is a union of at most <math>n-1</math> sectors, which all partners value at exactly <math>w</math>. For <math>n=2</math> agents this implies that there always exists a consensus division of a pie with connected sectors: give agent 1 a sector that is worth exactly <math>w_1</math>for both agents, and give agent 2 the remaining sector, which is worth <math>1-w_1 = w_2</math>for both agents (see [5] for an alternative proof).
This can be generalized to any number of agents: each piece except the last one requires at most <math>2(n-1)</math>cuts, so the total number of cuts required is <math>2(n-1)^2</math>.
A division is called proportional if each of two partners receives a value of at least 1/2. It is called weighted proportional (WPR) if partner <math>i</math> receives a value of at least <math>w_i</math>, where <math>w_i</math>are pre-specified weights representing the different entitlements of the partners to the cake. The above procedure shows that in a pie, a WPR division with connected pieces always exists. This is in contrast to a non-circular cake (an interval), in which a WPR with connected pieces might not exist.
Weighted envy-free division
If the valuations of the partners are absolutely continuous with respect to each other, then there exists a WPR division which is also weighted-envy-free (WEF) and Pareto efficient (PE), and the ratio between the values of the partners is exactly w1/w2.[5]
Proof. For every angle t, let Шаблон:Tmath be the angle in which the ratio Шаблон:Tmath
The function Шаблон:Tmath is a continuous function of t that achieves a maximum for some Шаблон:Tmath. Cut the pie with radial cuts at Шаблон:Tmath and Шаблон:Tmath, giving the piece Шаблон:Tmath to partner #1 and the complement to partner #2. The partition is WEF because the value of each partner is exactly his due share. It is PE because the share of partner #1 is maximized, so it is not possible to give more to partner #2 without harming partner #1.
Equitable division
An equitable division is a division in which the subjective value of both partners is the same (i.e. each partner is equally happy).
There always exists a partition of a pie to two partners, which is both envy-free and equitable. However, currently no procedure is known for finding such a partition.[3]
When the value measures of the partners are absolutely continuous with respect to each other (i.e. every piece which has a positive value for one partner also has a positive value for the other partner), then there exists a partition which is envy-free, equitable and Pareto efficient. Again, no procedure is known.[3]
Truthful division
A division rule is called truthful if reporting the true value functions is a weakly dominant strategy in that rule. I.e., it is not possible to gain any value by mis-representing the valuations.
A division rule is called dictatorial if it allocates the entire cake to a single, pre-specified partner.
A PE division rule is truthful if and only if it is dictatorial.[4]
Three or more partners
1-out-of-(n+1) procedure for n partners
Iyer and Huhns[6] were the first to present a specialised protocol for dividing a pie. In their protocol, each agent marks (n+1) disjoint pieces on the pie. The algorithm gives each agent one of his/her pieces.
Envy-free division for 3 partners
Stromquist moving-knives procedure can be used to cut a cake in 1 dimension, so obviously it can also be used to cut a pie.
But there is a simpler algorithm, that takes advantage of the circularity of the pie.[7][3]
Partner A rotates three radial knives continuously around the pie, maintaining what s/he believes to be 1/3-1/3-1/3 sectors.
Partner B measures the value of these 3 sectors. Typically they will all have different values, but at one point, two sectors will have the same value. Why? Because after a rotation of 120 degrees, the sector that was previously the most valuable is now less valuable, and another sector is now the most valuable. Hence, by the intermediate value theorem, there must be a position in the rotation when partner B views two sectors as tied for largest. At this point, partner B calls "stop".
The partners then choose sectors in the order: C - B - A. Partner C of course feels no envy because he is the first to choose; partner B has at least one larger sector to choose from; and partner A thinks that all pieces have the same value anyway.
Envy-free and Pareto-efficient division
For 3 partners, there exist a pie and corresponding measures for which no allocation is PEEF.[8]
This is also true for more than 3 partners. This is true even if all value functions are additive and strictly positive (i.e. every partner values every single bit of the pie).[3]
Both examples use measures that are nearly uniform, but with very fine adjustments. Since the measures are nearly uniform, it is easy to find allocations of the pie that are almost envy-free and almost undominated. It is not known whether it is possible to find examples in which the discrepancies are much larger.
Proportional division with different entitlements
When there are 3 or more partners with different entitlements, a weighted-proportional (WPR) division is needed. A WPR division with connected pieces does not always exist.[5]
This is analogous to an impossibility result for 1-dimensional interval cake and 2 partners (see proportional cake-cutting with different entitlements).
External links
References
