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 $i$ and $j$ :

V_{i}(X_{i})=V_{j}(X_{j})

Where:

$X_{i}$ is the piece of cake allocated to partner $i$ ;
$V_{i}$ is the value measure of partner $i$ . It is a real-valued function that, for every piece of cake, returns a number that represents the utility of partner $i$ from that piece. Usually these functions are normalized such that $V_{i}(\emptyset )=0$ and $V_{i}(EntireCake)=1$ for every $i$ .

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.[1] Assume that the cake is the interval [0,1]. For each $x\in [0,1]$ , calculate $u_{1}([0,x])$ and $u_{2}([x,1])$ 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.[2]
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.[1]

The same procedure can be used for dividing chores (with negative utility).

Proportional-equitability variant

The full revelation procedure has a variant[3] 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 $a$ and of partner B is $b$ , with $0<a<b<1$ . Then, A receives $[0,a]$ and B receives $[b,1]$ . Now there is a surplus - $[a,b]$ . 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 $[a,b]$ 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".[4]

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.[4]

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 $\epsilon$ , for any given $\epsilon >0$ . A near-equitable division for two partners can be found in finite time and with a single cut.[5]

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 $1/n$ . 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 $1/n$ ).

Connected pieces - full revelation

Jones' full revelation procedure can be extended to $n$ partners in the following way:[3]

For each of the $n!$ possible orderings of the partners, write a set of $n-1$ equations in $n-1$ variables: the variables are the $n-1$ cut-points, and the equations determine the equitability for adjacent partners. For example, of there are 3 partners and the order is A:B:C, then the two variables are $x_{AB}$ (the cut-point between A and B) and $x_{BC}$ , and the two equations are $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ and $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$ . These equations have at least one solution in which all partners have the same value.
Out of all $n!$ orderings, pick the ordering in which the (equal) value of all partners is the largest.

Note that the maximal equitable value must be at least $1/n$ , because we already know that a proportional division (giving each partner at least $1/n$ ) 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.[3] 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.[2] They do this by describing 3 specific value measures on a 1-dimensional cake, with the following properties:

With 2 cuts, every EQ allocation is not EF nor PE (but there are allocations which are EF and 2-PE, or EQ and 2-PE).
With 3 cuts, every EQ allocation is not PE (but there is an EQ+EF allocation).
With 4 cuts, every EQ allocation is not EF (but there is an EQ+PE allocation).

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:[6]

For 2 partners, there always exists a partition of a pie which is both envy-free and equitable. 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 undominated.
For 3 or more partners, it may be impossible to find an allocation that is both envy-free and equitable. But there always exists a division that is both equitable and undominated.

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.[7] Moreover, for any ε > 0:

A connected ε-equitable cake-cutting requires at least Ω(log ε⁻¹) queries.[8] For 2 agents, an O(log ε⁻¹) protocol exists.[5] For 3 or more agents, the best known protocol requires O(n (log n + log ε⁻¹)) queries.[9]
Even without connectivity, ε-equitable cake-cutting requires at least Ω(log ε⁻¹ / log log ε⁻¹ ) queries.[7]

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:

The absolute-equitable rule equalizes the absolute (not normalized) values;
The relative-equitable rule equalizes the relative (normalized) values.

There always exists a connected max-equitable alloation (both absolute and relative), and it can be found using a generalized moving-knives procedure.

The absolute-equitable rule is weakly Pareto-optimal and resource-monotonic, but not proportional.
The relative-equitable rule is weakly Pareto-optimal and proportional, but not resource-monotonic.[10]

Summary table

Name	Type	# partners	# cuts	Properties
Jones[1]	Full-revelation proc	2	1 (optimal)	EQ, EF, 1-PE
Brams-Jones-Klamler[3]	Full-revelation proc	n	n−1 (optimal)	EQ, (n−1)-PE
Austin	Moving-knife proc	2	2	EQ, EF, EX
Austin	Moving-knife proc	n	many	EQ
Barbanel-Brams[4]	Full-revelation proc	2	many	EQ, EF, PE
Cechlárová-Pillárová[5]	Discrete approximation proc	2	1 (optimal)	near-EQ

References

Jones, M. A. (2002). "Equitable, Envy-Free, and Efficient Cake Cutting for Two People and Its Application to Divisible Goods". Mathematics Magazine. 75 (4): 275–283. doi:10.2307/3219163. JSTOR 3219163.
Steven j. Brams; Michael a. Jones; Christian Klamler (2013). "N-Person Cake-Cutting: There May Be No Perfect Division". The American Mathematical Monthly. 120: 35. doi:10.4169/amer.math.monthly.120.01.035. S2CID 7929917.
Steven J. Brams; Michael A. Jones; Christian Klamler (2007). "Better Ways to Cut a Cake - Revisited" (PDF). Notices of the AMS.
Barbanel, Julius B.; Brams, Steven J. (2014). "Two-Person Cake Cutting: The Optimal Number of Cuts". The Mathematical Intelligencer. 36 (3): 23. CiteSeerX 10.1.1.361.366. doi:10.1007/s00283-013-9442-0. S2CID 189867346.
Cechlárová, Katarína; Pillárová, Eva (2012). "A near equitable 2-person cake cutting algorithm". Optimization. 61 (11): 1321. doi:10.1080/02331934.2011.563306. S2CID 120300612.
Barbanel, J. B.; Brams, S. J.; Stromquist, W. (2009). "Cutting a Pie is Not a Piece of Cake". American Mathematical Monthly. 116 (6): 496. CiteSeerX 10.1.1.579.5005. doi:10.4169/193009709X470407.
Procaccia, Ariel D.; Wang, Junxing (2017-06-20). "A Lower Bound for Equitable Cake Cutting". Proceedings of the 2017 ACM Conference on Economics and Computation. EC '17. Cambridge, Massachusetts, USA: Association for Computing Machinery. pp. 479–495. doi:10.1145/3033274.3085107. ISBN 978-1-4503-4527-9. S2CID 9834718.
Brânzei, Simina; Nisan, Noam (2018-07-13). "The Query Complexity of Cake Cutting". arXiv:1705.02946 [cs.GT].
Cechlárová, Katarína; Pillárová, Eva (2012-11-01). "On the computability of equitable divisions". Discrete Optimization. 9 (4): 249–257. doi:10.1016/j.disopt.2012.08.001. ISSN 1572-5286.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Segal-Halevi, Erel; Sziklai, Balázs R. (2018-09-01). "Resource-monotonicity and population-monotonicity in connected cake-cutting". Mathematical Social Sciences. 95: 19–30. arXiv:1703.08928. doi:10.1016/j.mathsocsci.2018.07.001. ISSN 0165-4896. S2CID 16282641.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[jones2002-1] Jones, M. A. (2002). "Equitable, Envy-Free, and Efficient Cake Cutting for Two People and Its Application to Divisible Goods". Mathematics Magazine. 75 (4): 275–283. doi:10.2307/3219163. JSTOR 3219163.

[bjk2011-2] Steven j. Brams; Michael a. Jones; Christian Klamler (2013). "N-Person Cake-Cutting: There May Be No Perfect Division". The American Mathematical Monthly. 120: 35. doi:10.4169/amer.math.monthly.120.01.035. S2CID 7929917.

[bjk07-3] Steven J. Brams; Michael A. Jones; Christian Klamler (2007). "Better Ways to Cut a Cake - Revisited" (PDF). Notices of the AMS.

[bb2014-4] Barbanel, Julius B.; Brams, Steven J. (2014). "Two-Person Cake Cutting: The Optimal Number of Cuts". The Mathematical Intelligencer. 36 (3): 23. CiteSeerX 10.1.1.361.366. doi:10.1007/s00283-013-9442-0. S2CID 189867346.

[cp11-5] Cechlárová, Katarína; Pillárová, Eva (2012). "A near equitable 2-person cake cutting algorithm". Optimization. 61 (11): 1321. doi:10.1080/02331934.2011.563306. S2CID 120300612.

[bbs09-6] Barbanel, J. B.; Brams, S. J.; Stromquist, W. (2009). "Cutting a Pie is Not a Piece of Cake". American Mathematical Monthly. 116 (6): 496. CiteSeerX 10.1.1.579.5005. doi:10.4169/193009709X470407.

[:2-7] Procaccia, Ariel D.; Wang, Junxing (2017-06-20). "A Lower Bound for Equitable Cake Cutting". Proceedings of the 2017 ACM Conference on Economics and Computation. EC '17. Cambridge, Massachusetts, USA: Association for Computing Machinery. pp. 479–495. doi:10.1145/3033274.3085107. ISBN 978-1-4503-4527-9. S2CID 9834718.

[:0-8] Brânzei, Simina; Nisan, Noam (2018-07-13). "The Query Complexity of Cake Cutting". arXiv:1705.02946 [cs.GT].

[:1-9] Cechlárová, Katarína; Pillárová, Eva (2012-11-01). "On the computability of equitable divisions". Discrete Optimization. 9 (4): 249–257. doi:10.1016/j.disopt.2012.08.001. ISSN 1572-5286.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[10] Segal-Halevi, Erel; Sziklai, Balázs R. (2018-09-01). "Resource-monotonicity and population-monotonicity in connected cake-cutting". Mathematical Social Sciences. 95: 19–30. arXiv:1703.08928. doi:10.1016/j.mathsocsci.2018.07.001. ISSN 0165-4896. S2CID 16282641.