Truthful cake-cutting – Wikipedia

Truthful division drawback

Truthful cake-cutting is a type of fair division drawback. The issue entails a heterogeneous useful resource, comparable to a cake with totally different toppings, that’s assumed to be divisible – it’s potential to chop arbitrarily small items of it with out destroying their worth. The useful resource must be divided amongst a number of companions who’ve totally different preferences over totally different components of the cake, i.e., some folks choose the chocolate toppings, some choose the cherries, some simply need as giant a bit as potential. The division must be unanimously truthful – every individual ought to obtain a bit believed to be a fair proportion.

The “cake” is just a metaphor; procedures for truthful cake-cutting can be utilized to divide numerous sorts of assets, comparable to land estates, commercial house or broadcast time.

The prototypical process for truthful cake-cutting is divide and choose, which is talked about within the ebook of Genesis. It solves the truthful division drawback for 2 folks. The trendy examine of truthful cake-cutting was initiated throughout World War II, when Hugo Steinhaus requested his college students Stefan Banach and Bronisław Knaster to discover a generalization of divide-and-choose to 3 or extra folks. They developed the last diminisher process.^[1] As we speak, truthful cake-cutting is the topic of intense analysis in mathematics, computer science, economics and political science.^[2]

Assumptions[edit]

There’s a cake C, which is often assumed to be both a finite 1-dimensional section, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean airplane R^d.

There are n folks with subjective value functions over C. Every individual i has a worth operate V_i which maps subsets of C to numbers. All worth capabilities are assumed to be absolutely continuous with respect to the size, space or (basically) Lebesgue measure.^[3] Because of this there are not any “atoms” – there are not any singular factors to which a number of brokers assign a constructive worth, so all components of the cake are divisible. In lots of instances, the worth capabilities are assumed to be sigma additive (the worth of a complete is the same as the sum of the values of its components).

C must be divided to n disjoint subsets, such that every individual receives a disjoint subset. The piece allotted to individual i known as ${displaystyle X_{i}}$, and ${displaystyle C=X_{1}sqcup cdots sqcup X_{n}}$.

The n folks have equal rights to C. I.e., there isn’t a dispute over the rights of the folks – everybody agrees that everybody else is entitled to a fair proportion. The one drawback is how one can divide the cake such that every individual receives a fair proportion.

Within the following examples the next cake will probably be used as an illustration.

• The cake has two components: chocolate and vanilla.
• There are two folks: Alice and George.
• Alice values the chocolate as 9 and the vanilla as 1.
• George values the chocolate as 6 and the vanilla as 4.

Justice necessities[edit]

Proportionality[edit]

The unique and most typical criterion for justice is proportionality (PR). In a proportional cake-cutting, every individual receives a bit that he values as at the least 1/n of the worth of the complete cake. Within the instance cake, a proportional division may be achieved by giving all of the vanilla and 4/9 of the chocolate to George (for a worth of 6.66), and the opposite 5/9 of the chocolate to Alice (for a worth of 5). In symbols:

${displaystyle forall {i}: V_{i}(X_{i})geq 1/n}$

For n folks with additive valuations, a proportional division all the time exists. The most typical protocols are:

• Last diminisher, a protocol that may assure that the n items are linked (i.e. no individual will get a set of two or extra disconnected items). Particularly, if the cake is a 1-dimensional interval then every individual receives an interval. This protocol is discrete and may be performed in turns. It requires O(n²) actions.
• The Dubins–Spanier Moving-knife procedure is a continuous-time model of Final diminisher.^[4]
• Fink protocol (also called successive pairs or lone chooser) is a discrete protocol that can be utilized for on-line division: given a proportional division for n − 1 companions, when a brand new companion enters the social gathering, the protocol modifies the prevailing division in order that each the brand new companion and the prevailing companions stay with 1/n. The drawback is that every companion receives numerous disconnected items.
• The Even–Paz protocol, primarily based on recursively halving the cake and the group of brokers, requires solely O(n log n) actions. That is quickest potential deterministic protocol for proportional division, and the quickest potential protocol for proportional division which might assure that the items are linked.
• Edmonds–Pruhs protocol is a randomized protocol that requires solely O(n) actions, however ensures solely {a partially} proportional division (every companion receives at the least 1/an, the place a is a few fixed), and it would give every companion a set of “crumbs” as an alternative of a single linked piece.
• Beck land division protocol can produce a proportional division of a disputed territory amongst a number of neighbouring nations, such that every nation receives a share that’s each linked and adjoining to its at the moment held territory.
• Woodall’s super-proportional division protocol produces a division which supplies every companion strictly greater than 1/n, on condition that at the least two companions have totally different opinions concerning the worth of at the least a single piece.

See proportional cake-cutting for extra particulars and full references.

The proportionality criterion may be generalized to conditions during which the rights of the individuals are not equal. For instance, in proportional cake-cutting with different entitlements, the cake belongs to shareholders such that considered one of them holds 20% and the opposite holds 80% of the cake. This results in the criterion of weighted proportionality (WPR):

${displaystyle forall i:V_{i}(X_{i})geq w_{i}}$

The place the w_i are weights that sum as much as 1.

Envy-freeness[edit]

One other widespread criterion is envy-freeness (EF). In an envy-free cake-cutting, every individual receives a bit that he values at the least as a lot as each different piece. In symbols:

${displaystyle forall i,j: V_{i}(X_{i})geq V_{i}(X_{j})}$

In some instances, there are implication relations between proportionality and envy-freeness, as summarized within the following desk:

The divide and choose protocol finds an allocation that’s all the time EF. If the worth capabilities are additive then this division can be PR; in any other case, proportionality will not be assured.

An EF division for n folks exists even when the valuations should not additive, so long as they are often represented as constant choice units. EF division has been studied individually for the case during which the items have to be linked, and for the better case during which the items could also be disconnected.

For linked items the key outcomes are:

• Stromquist moving-knives procedure produces an envy-free division for 3 folks, by giving every considered one of them a knife and instructing them to maneuver their knives repeatedly over the cake in a pre-specified method.
• Simmons’ protocol can produce an approximation of an envy-free division for n folks with an arbitrary precision. If the worth capabilities are additive, the division may also be proportional. In any other case, the division will nonetheless be envy-free however not essentially proportional. The algorithm offers a quick and sensible manner of fixing some truthful division issues.^[5][6]

Each these algorithms are infinite: the primary is steady and the second may take an infinite time to converge. In actual fact, envy-free divisions of linked intervals to three or extra folks can’t be discovered by any finite protocol.

For possibly-disconnected items the key outcomes are:

• Selfridge–Conway discrete procedure produces an envy-free division for 3 folks utilizing at most 5 cuts.
• Brams–Taylor–Zwicker moving knives procedure produces an envy-free division for 4 folks utilizing at most 11 cuts.
• A reentrant variant of the Last Diminisher protocol finds an additive approximation to an envy-free division in bounded time. Particularly, for each fixed ${displaystyle epsilon >0}$, it returns a division during which the worth of every companion is at the least the most important worth minus ${displaystyle epsilon }$, in time ${displaystyle O(n^{2}/epsilon )}$.
• Three totally different procedures, one by Brams and Taylor (1995) and one by Robertson and Webb (1998) and one by Pikhurko (2000), produce an envy-free division for n folks. Each algorithms require a finite however unbounded variety of cuts.
• A process by Aziz and Mackenzie (2016)^[7] finds an envy-free division for n folks in a bounded variety of queries.

The unfavourable consequence within the normal case is way weaker than within the linked case. All we all know is that each algorithm for envy-free division should use at the least Ω(n²) queries. There’s a giant hole between this consequence and the runtime complexity of one of the best identified process.

See envy-free cake-cutting for extra particulars and full references.

Different standards[edit]

A 3rd, much less widespread criterion is equitability (EQ). In an equitable division, every individual enjoys precisely the identical worth. Within the instance cake, an equitable division may be achieved by giving every individual half the chocolate and half the vanilla, such that every individual enjoys a worth of 5. In symbols:

${displaystyle forall i,j: V_{i}(X_{i})=V_{j}(X_{j})}$

A fourth criterion is exactness. If the entitlement of every companion i is w_i, then an exact division is a division during which:

${displaystyle forall {i,j}: V_{i}(X_{j})=w_{j}}$

If the weights are all equal (to 1/n) then the division known as good and:

${displaystyle forall i,j: V_{i}(X_{j})=1/n}$

Geometric necessities[edit]

In some instances, the items allotted to the companions should fulfill some geometric constraints, along with being truthful.

• The most typical constraint is connectivity. In case the “cake” is a 1-dimensional interval, this interprets to the requirement that every piece can be an interval. In case the cake is a 1-dimensional circle (“pie”), this interprets to the requirement that every piece be an arc; see fair pie-cutting.
• One other constraint is adjacency. This constraint applies to the case when the “cake” is a disputed territory that must be divided amongst neighboring nations. On this case, it could required that the piece allotted to every nation is adjoining to its present territory; this constraint is dealt with by Hill’s land division problem.
• In land division there are sometimes two-dimensional geometric constraints, e.g., every bit must be a sq. or (extra usually) a fat object.^[8]

Procedural necessities[edit]

Along with the specified properties of the ultimate partitions, there are additionally desired properties of the division course of. One in every of these properties is truthfulness (aka incentive compatibility), which is available in two ranges.

• Weak truthfulness signifies that if the companion reveals his true worth measure to the algorithm, he’s assured to obtain his fair proportion (e.g. 1/n of the worth of the complete cake, in case of proportional division), no matter what different companions do. Even when all different companions make a coalition with the one intent to hurt him, he’ll nonetheless obtain his assured proportion. Most cake-cutting algorithms are truthful on this sense.^[1]
• Sturdy truthfulness signifies that no companion can acquire from mendacity. I.e., telling the reality is a dominant strategy. Most cake-cutting protocols should not strongly truthful, however some truthful protocols have been developed; see truthful cake-cutting.

One other property is symmetry: there shouldn’t be a distinction between totally different roles within the process. A number of variants of this property have been studied:

See Also

Fringe of Emulation: Glucoboy

• Anonymity requires that, if the brokers are permuted and the process is re-executed, then every agent receives precisely the identical piece as within the unique execution. This can be a robust situation; at the moment, an nameless process is thought just for 2 brokers.
• Symmetry requires that, if the brokers are permuted and the process is re-executed, then every agent receives the identical worth as within the unique execution. That is weaker than anonymity; at the moment, a symmetric and proportional process is thought for any variety of brokers, and it takes O(n³) queries. A symmetric and envy-free process is thought for any variety of brokers, but it surely takes for much longer – it requires n! executions of an present envy-free process.
• Aristotelianity requires that, if two brokers have an similar value-measure, then they obtain the identical worth. That is weaker than symmetry; it’s glad by any envy-free process. Furthermore, an aristotelian and proportional process is thought for any variety of brokers, and it takes O(n³) queries.

See symmetric fair cake-cutting for particulars and references.

A 3rd household of procedural necessities is monotonicity: when a division process is re-applied with a smaller/bigger cake and a smaller/bigger set of brokers, the utility of all brokers ought to change in the identical path. See resource monotonicity for extra particulars.

Effectivity necessities[edit]

Along with justice, it’s also widespread to think about the financial effectivity of the division; see efficient cake-cutting. There are a number of ranges of effectivity:

• The weaker notion is Pareto efficiency. It may be simply glad by simply giving the complete cake to a single individual; the problem is to fulfill it together with equity. See Efficient envy-free division.
• A stronger notion is utilitarian-maximality – maximizing the sum of utilities. (UM). When the worth capabilities are additive, UM divisions exist. Intuitively, to create a UM division, we should always give every bit of cake to the person who values it probably the most. Within the example cake, a UM division would give the complete chocolate to Alice and the complete vanilla to George, attaining a utilitarian worth of 9 + 4 = 13. This course of is simple to hold out when the worth capabilities are piecewise-constant, i.e. the cake may be divided to items such that the worth density of every piece is fixed for all folks. When the worth capabilities should not piecewise-constant, the existence of UM allocations follows from basic measure-theoretic theorems. See Utilitarian cake-cutting.

Environment friendly truthful division[edit]

For n folks with additive worth capabilities, a PEEF division all the time exists. That is Weller’s theorem.^[9]

If the cake is a 1-dimensional interval and every individual should obtain a linked interval, the next normal consequence holds: if the worth capabilities are strictly monotonic (i.e. every individual strictly prefers a bit over all its correct subsets) then each EF division can be PE.^[10] Therefore, Simmons’ protocol produces a PEEF division on this case.

If the cake is a 1-dimensional circle (i.e. an interval whose two endpoints are topologically recognized) and every individual should obtain a linked arc, then the earlier consequence doesn’t maintain: an EF division will not be essentially PE. Moreover, there are pairs of (non-additive) worth capabilities for which no PEEF division exists. Nevertheless, if there are 2 brokers and at the least considered one of them has an additive worth operate, then a PEEF division exists.^[11]

If the cake is 1-dimensional however every individual might obtain a disconnected subset of it, then an EF division will not be essentially PE. On this case, extra sophisticated algorithms are required for locating a PEEF division.

If the worth capabilities are additive and piecewise-constant, then there may be an algorithm that finds a PEEF division.^[12] If the worth density capabilities are additive and Lipschitz continuous, then they are often approximated as piecewise-constant capabilities “as shut as we like”, due to this fact that algorithm approximates a PEEF division “as shut as we like”.^[12]

An EF division will not be essentially UM.^[13][14] One strategy to deal with this problem is to seek out, amongst all potential EF divisions, the EF division with the best utilitarian worth. This drawback has been studied for a cake which is a 1-dimensional interval, every individual might obtain disconnected items, and the worth capabilities are additive.^[15]

Fashions of computation[edit]

Reasoning concerning the run-time complexity of algorithms requires a model of computation. A number of such fashions are widespread within the literature:

• The Robertson–Webb query model – during which the algorithm might ask every agent a question of considered one of two sorts: “consider a given piece of cake” or “mark a bit of cake with a given worth”.
• The Moving-knives model – during which the algorithm repeatedly strikes a number of knives above the cake till some brokers shout “cease”.
• The direct revelation mannequin – during which all brokers reveal their whole valuation to the mechanism. This mannequin is smart solely when the valuations may be represented succinctly, for instance, when they’re piecewise-uniform, piecewise-constant or piecewise-linear.
• The simultaneous studies mannequin – during which brokers concurrently ship discretizations of their value-measures. A discretization is a sequence of cut-points, and the values of items between these cut-points (for instance: a protocol for 2 brokers may require every agent to report a sequence of three cut-points (0,x,1) the place the values of (0,x) and (x,1) are 1/2).^[16]

Dividing a number of desserts[edit]

There’s a generalization of the cake-cutting drawback during which there are a number of desserts, and every agent must get a bit in every cake.

• Cloutier, Nyman and Su^[17] examine two-player envy-free multi-cake division. For 2 desserts, they show that an EF allocation might not exist when there are 2 brokers and every cake is reduce into 2 items. Nevertheless, an EF allocation exists when there are 2 brokers and one cake is reduce into 3 items (the least-wanted piece is discarded), or when there are 3 brokers and every cake is reduce into 2 items (one agent is ignored; the allocation is EF for the remaining two).
• Lebert, Meunier and Carbonneaux^[18] show, for 2 desserts, that an EF allocation all the time exists when there are 3 brokers and every cake is reduce into 5 items (the 2 least-wanted items in every cake are discarded).
• Nyman, Su and Zerbib^[19] show, for ok desserts, that an EF allocation all the time exists when there are ok(n-1)+1 brokers and every cake is reduce into n items (the allocation is EF for some set of n brokers).

Two associated issues are:

• Multi-layered cake-cutting,^[20] the place the desserts are organized in “layers” and items of the identical agent should not overlap (for instance, every cake represents the time during which a sure facility is accessible throughout the day; an agent can not use two services concurrently).
• Truthful multi-cake chopping,^[21] the place the brokers don’t wish to get a bit on each cake, quite the opposite, they wish to get items on as few desserts as potential.

Cake sharing[edit]

Bei, Lu and Suksompong^[22] current a mannequin during which, somewhat than dividing a person piece of cake to every agent, the brokers ought to select collectively a bit of cake that they are going to all share. This may be seen as a variant of committee election, the place the candidates are divisible. There’s a continuum of candidates, represented by an actual interval [0,c], and the aim is to pick a subset of this interval, with complete size at most ok, the place ok and c may be any actual numbers with 0<ok<c. They generalize the justified illustration notion to this setting. Lu, Peters, Aziz, Bei and Suksompong^[23] lengthen these definitions to settings with combined divisible and indivisible candidates (see justified representation).

See additionally[edit]

References[edit]

Additional studying[edit]