Efficient cake-cutting

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogenous 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 division should be Pareto-efficient.

Most often, efficiency is studied in connection with fairness, and the goal is to find a division which satisfies both efficiency and fairness criteria.

Assumptions

There is a cake $C$ . It is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane $\mathbb {R} ^{d}$ .

There are $n$ partners. Each partner $i$ has a subjective value function $V_{i}$ which maps subsets of $C$ to numbers.

$C$ has to be divided to $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}$ .

Example cake

In the following lines we consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations:

Header text	Chocolate	Vanilla
Alice	9	1
George	6	4

Efficiency

A division $Y$ Pareto-dominates a division $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})

A Pareto efficient (PE) division is a division that is not Pareto-dominated by any other division, i.e., it cannot be improved without objection. In the example cake, many PE divisions are possible. For example, every division that gives the entire cake to a single person is PE, since every change in the division will raise the objection of that single person. Of course a PE division is not necessarily fair.

A division that is both Pareto-efficient and proportional will be called PEPR and a division that is both PE and envy-free will be called PEEF for short.

Combining efficiency and fairness

PEPR division

A PE division can be achieved trivially by giving the entire cake to a single partner. But, a PE division which is also proportional cannot be found by a finite algorithm. The proof is essentially the same as for utilitarian-maximal divisions.

PEEF division

For n partners with additive value functions, when pieces may be disconnected, a PEEF division always exists. This is Weller's theorem.

If the cake is a 1-dimensional interval and each person must receive a connected interval, the following general result holds: if the value functions are strictly monotonic (i.e. each person strictly prefers a piece over all its proper subsets) then every EF division is also PE (note that this is not true if the agents may receive disconnected pieces). Hence, in this case, the Simmons–Su protocols create a PEEF division.

If the cake is a 1-dimensional circle (i.e. an interval whose two endpoints are topologically identified) and each person must receive a connected arc, then the previous result does not hold: an EF division is not necessarily PE. Additionally, there are pairs of (non-additive) value functions for which no PEEF division exists. However, if there are 2 agents and at least one of them has an additive value function, then a PEEF division exists.^[1]

References

↑ Thomson, W. (2006). "Children Crying at Birthday Parties. Why?". Economic Theory. 31 (3): 501. doi:10.1007/s00199-006-0109-3.

This article is issued from Wikipedia - version of the 8/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.