Egalitarian cake-cutting

Last updated April 15, 2024

Egalitarian cake-cutting is a kind of fair cake-cutting in which the fairness criterion is the egalitarian rule. The cake represents a continuous resource (such as land or time), that has to be allocated among people with different valuations over parts of the resource. The goal in egalitarian cake-cutting is to maximize the smallest value of an agent; subject to this, maximize the next-smallest value; and so on. It is also called leximin cake-cutting, since the optimization is done using the leximin order on the vectors of utilities.

Existence

Leximin-optimal allocations exist whenever the set of allocations is a compact space. This is always the case when allocating discrete objects, and easy to prove when allocating a finite number of continuous homogeneous resources. Dubins and Spanier proved that, with a continuous heterogeneous resource ("cake"), the set of allocations is compact.^[1] Therefore, leximin-optimal cake allocations always exist. For this reason, the leximin cake-allocation rule is sometimes called the Dubins–Spanier rule.^[2]

Variants

When the agents' valuations are not normalized (i.e., different agents may assign a different value to the entire cake), there is a difference between the absolute utility profile of an allocation (where element i is just the utility of agent i), and its relative utility profile (where element i is the utility of agent i divided by the total value for agent i). The absolute leximin rule chooses an allocation in which the absolute utility profile is leximin-maximal, and the relative leximin rule chooses an allocation in which the relative utility profile is leximin-maximal.

Properties

Both variants of the leximin rule are Pareto-optimal and population monotonic. However, they differ in other properties:^[3]

The absolute-leximin rule is resource monotonic but not proportional;
The relative-leximin rule is proportional but not resource-monotonic.

Relation to envy-freeness

Both variants of the leximin rule may yield allocations that are not envy-free. For example, suppose there are 5 agents, the cake is piecewise-homogeneous with 3 regions, and the agents' valuations are (missing values are zeros):

Agent	Left	Middle	Right
A	6	9
B		5	10
C			15
D			15
E			15

All agents value the entire cake at 15, so absolute-leximin and relative-leximin are equivalent. The largest possible minimum value is 5, so a leximin allocation must give all agents at least 5. This means that the Right must be divided equally among agents C, D, E, and the Middle must be given entirely to agent B. But then A envies B.^[3]

Dubins and Spanier^[1] proved that, when all value-measures are strictly positive, every relative-leximin allocation is envy-free.^[4]^: Sec.4

Weller^[4]^: Sec.4 showed an envy-free and efficient cake allocation that is not relative-leximin. The cake is [0,1], there are three agents, and their value measures are trianglular distributions centered at 1/4, 1/2 and 3/4 respectively. The allocation ([0,3/8],[3/8,5/8],[5/8,1]) has utility profile (3/8,7/16,7/16). It is envy-free and utilitarian-optimal, hence Pareto-efficient. However, there is another allocation ([0,5/16],[5/16,11/16],[11/16,1]) with a leximin-better utility profile.

Computation

Dall'aglio^[2] presents an algorithm for computing a leximin-optimal resource allocation.

Aumann, Dombb and Hassidim^[5] present an algorithm that, for every e>0, computes an allocation with egalitarian welfare at least (1-e) of the optimum using $2^{n}\cdot n\cdot \log _{2}(n/\epsilon )$ queries. This is exponential in n, but polynomial in the number of accuracy digits.

On the other hand, they prove that, unless P=NP, it is impossible to approximate the optimal egalitarian value to a factor better than 2, in time polynomial in n. The proof is by reduction from 3-dimensional matching (3DM). For every instance of 3DM matching with m hyperedges, they construct a cake-cutting instance with n agents, where 4m ≤ n ≤ 5m. They prove that, if the 3DM instance admits a perfect matching, then there exists a cake allocation with egalitarian value at least 1/m; otherwise, there is no cake-allocation with egalitarian value larger than 1/(2m).

Related Research Articles

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. In many fair division settings, all agents have equal entitlements, which means that each agent is entitled to 1/n of the resource. But there are practical settings in which agents have different entitlements. Some examples are:

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

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$ :

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

The Dubins–Spanier theorems are several theorems in the theory of fair cake-cutting. They were published by Lester Dubins and Edwin Spanier in 1961. Although the original motivation for these theorems is fair division, they are in fact general theorems in measure theory.

A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/n of the total.

Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

Resource monotonicity is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems.

Fair division of a single homogeneous resource is one of the simplest settings in fair division problems. There is a single resource that should be divided between several people. The challenge is that each person derives a different utility from each amount of the resource. Hence, there are several conflicting principles for deciding how the resource should be divided. A primary conflict is between efficiency and equality. Efficiency is represented by the utilitarian rule, which maximizes the sum of utilities; equality is represented by the egalitarian rule, which maximizes the minimum utility.

Egalitarian equivalence (EE) is a criterion of fair division. In an egalitarian-equivalent division, there exists a certain "reference bundle" $such that each agent feels that his/her share is equivalent to .$

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

In social choice and operations research, the egalitarian rule is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the minimum utility of all individuals in society. It is a formal mathematical representation of the egalitarian philosophy. It also corresponds to John Rawls' principle of maximizing the welfare of the worst-off individual.

Population monotonicity (PM) is a principle of consistency in allocation problems. It says that, when the set of agents participating in the allocation changes, the utility of all agents should change in the same direction. For example, if the resource is good, and an agent leaves, then all remaining agents should receive at least as much utility as in the original allocation.

References

1 2 3 Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68 (1): 1–17. doi:10.2307/2311357. JSTOR 2311357.
1 2 Dall'Aglio, Marco (2001-05-01). "The Dubins–Spanier optimization problem in fair division theory". Journal of Computational and Applied Mathematics. 130 (1–2): 17–40. Bibcode:2001JCoAM.130...17D. doi: 10.1016/S0377-0427(99)00393-3 . ISSN 0377-0427.
1 2 Segal-Halevi, Erel; Sziklai, Balázs R. (2019-09-01). "Monotonicity and competitive equilibrium in cake-cutting". Economic Theory. 68 (2): 363–401. arXiv: 1510.05229 . doi:10.1007/s00199-018-1128-6. ISSN 1432-0479. S2CID 179618.
1 2 Weller, Dietrich (1985-01-01). "Fair division of a measurable space". Journal of Mathematical Economics. 14 (1): 5–17. doi:10.1016/0304-4068(85)90023-0. ISSN 0304-4068.
↑ Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013-05-06). "Computing socially-efficient cake divisions". Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems. AAMAS '13. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 343–350. ISBN 978-1-4503-1993-5.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[DS2-1] 1 2 3 Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly. 68 (1): 1–17. doi:10.2307/2311357. JSTOR 2311357.

[:3-2] 1 2 Dall'Aglio, Marco (2001-05-01). "The Dubins–Spanier optimization problem in fair division theory". Journal of Computational and Applied Mathematics. 130 (1–2): 17–40. Bibcode:2001JCoAM.130...17D. doi: 10.1016/S0377-0427(99)00393-3 . ISSN 0377-0427.

[:0-3] 1 2 Segal-Halevi, Erel; Sziklai, Balázs R. (2019-09-01). "Monotonicity and competitive equilibrium in cake-cutting". Economic Theory. 68 (2): 363–401. arXiv: 1510.05229 . doi:10.1007/s00199-018-1128-6. ISSN 1432-0479. S2CID 179618.

[:1-4] 1 2 Weller, Dietrich (1985-01-01). "Fair division of a measurable space". Journal of Mathematical Economics. 14 (1): 5–17. doi:10.1016/0304-4068(85)90023-0. ISSN 0304-4068.

[5] Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013-05-06). "Computing socially-efficient cake divisions". Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems. AAMAS '13. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 343–350. ISBN 978-1-4503-1993-5.

[1]

[2]

[3]

[4]

[5]