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 i is exactly wi according to all partners, where wi are pre-specified weights.
For every pie, there is always a consensus division to 2 partners with connected sectors.[5]
Proof. Normalize the angles and the values to the range [0,1]. For every value v, let x(v) be the first angle in which partner #1 values the sector from 0 to that angle as v, i.e.: v1(0,x(v)) = v. Let g(v) be the value of this sector according to partner #2, i.e.: v2(0,x(v)) = g(v).
Define f(v)=g(v)-v. Then f(0)=f(1)=0. By the intermediate value theorem, for every weight w1 there is an angle c in [0,1] such that f(c+w1)=f(c).
Now consider the sector from angle x(c) to angle x(c+w1). By definition of c, this sector satisfies:
- g(c+w1)-c-w1=g(c)-c
By definitions of g:
- v2(0,x(c+w1))-v2(0,x(c))=w1
By additivity:
- v2(x(c),x(c+w1))=w1
- v2(x(c+w1),x(c))=1-w1=w2
This means that we can give the sector (x(c),x(c+w1)) to partner #1 and the complementary sector to partner #2; each of them receives exactly his due share.
Note: 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 i receives a value of at least wi, where wi 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 y(t) be the angle in which the ratio v1(t,y(t)) / v2(t,y(t)) = w1 / w2.
The function v1([t,y(t)]) is a continuous function of t that achieves a maximum for some t*. Cut the pie with radial cuts at t* and y(t∗), giving the piece [t∗,y(t∗)] 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
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.[6][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.[7]
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 fair cake-cutting#Weighted proportional division).
References
- ↑ Stromquist, W.; Woodall, D. R. (1985). "Sets on which several measures agree". Journal of Mathematical Analysis and Applications. 108: 241. doi:10.1016/0022-247x(85)90021-6.
- ↑ Gale, D. (2009). "Mathematical entertainments". The Mathematical Intelligencer. 15: 48. doi:10.1007/BF03025257.
- 1 2 3 4 5 Barbanel, J. B.; Brams, S. J.; Stromquist, W. (2009). "Cutting a Pie is Not a Piece of Cake". American Mathematical Monthly. 116 (6): 496. doi:10.4169/193009709X470407.
- 1 2 Thomson, W. (2006). "Children Crying at Birthday Parties. Why?". Economic Theory. 31 (3): 501. doi:10.1007/s00199-006-0109-3.
- 1 2 3 Brams, S. J.; Jones, M. A.; Klamler, C. (2007). "Proportional pie-cutting". International Journal of Game Theory. 36 (3–4): 353. doi:10.1007/s00182-007-0108-z.
- ↑ "A Moving-Knife Solution to the Four-Person Envy-Free Cake Division". Proceedings of the American Mathematical Society. 125 (2): 547–554. 1997.
- ↑ Stromquist, Walter (June 2007). A pie that can't be cut fairly. Retrieved 15 December 2014.