Efficient cake-cutting

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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: * The most common notion is Pareto-efficiency. It means that no other allocation is better for at least one participant and at least as good for everyone. * A weaker notion is non-wastefulness. An allocation is non-wasteful if no agent receives a piece of cake that is worth 0 for him/her, and worth more than 0 for another agent. Most often, efficiency is studied in connection with fairness, and the goal is to find a division which satisfies both efficiency and fairness criteria.

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: The most common notion is Pareto-efficiency. It means that no other allocation is better for at least one participant and at least as good for everyone. A weaker notion is non-wastefulness. An allocation is non-wasteful if no agent receives a piece of cake that is worth 0 for him/her, and worth more than 0 for another agent. Most often, efficiency is studied in connection with fairness, and the goal is to find a division which satisfies both efficiency and fairness criteria. C has to be divided into n disjoint subsets, such that each person receives a disjoint subset. The piece allocated to person i is called X_i , so that C = X_1 \sqcup ... \sqcup X_n . In the following lines we consider a cake with four parts: chocolate, vanilla, lemon and sugar, and two agents: Alice and George, with the following valuations: An allocation X is called wasteful if it allocates to some agent a piece that is worth 0 to that agent but worth more than 0 to another agent. In symbols: \exists{i,j}: \exists Z\subseteq X_i: V_i(Z)=0 ~~\text{and}~~ V_j(Z)>0 and \exists{i}: V_i(Y_i)>V_i(X_i) . Otherwise it is called non-wasteful (NW). In the example cake, an allocation giving all the cake to Alice is NW, but an allocation giving all the cake to George is wasteful since the lemon part is "wasted". There are many other NW allocations, for example, giving the chocolate to George and the remaining cake to Alice is NW. An allocation Y Pareto-dominates an allocation X , if at least one person feels that Y is better than X , and no person feels that Y is worse than X . In symbols: \forall{i}:\ V_i(Y_i)\geq V_i(X_i) and \exists{i}: V_i(Y_i)>V_i(X_i) An allocation X is called Pareto optimal (PO) if it is not Pareto-dominated by any other division, i.e., it cannot be improved without objection. In the example cake, giving the entire cake to Alice is PO, but giving the entire cake to Bob is Pareto-dominated by the allocation where the lemon part is given to Alice. In general (when there are no connectivity requirements on the pieces), every wasteful allocation is Pareto-dominated, therefore every PO allocation is NW. However, the opposite is not true. For example, the allocation giving the chocolate to George and the remaining cake to Alice is NW but it is not PO - it is Pareto-dominated by the allocation giving to George the vanilla and half the chocolate. This is because, in the original allocation the utilities of (Alice, George) are (3, 6), while in the alternative allocation the utilities are (5.5, 7).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1345718756 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001345718756 · captured 1774634557.0 · version history

Cite this page as: encyclopegia.org, “Efficient cake-cutting”, snapshot enwiki-001345718756. https://encyclopegia.org/a/efficient-cake-cutting

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.