In proportional cake-cutting, there are $n$ agents with equal entitlements to a "cake" (an interval). Each agent $i$ has a nonatomic value measure $V_i$ over the cake, and it is required to create a partition of the cake, $X_1,\dots,X_n$, such that: $$\forall i: {V_i(X_i)\over V_i(Cake)} \geq {1 \over n}$$ It is known that a proportional partition can always be done with $n-1$ cuts, giving each agent a connected piece, e.g. using the last diminisher procedure.
In weighted-proportional cake-cutting, the agents have different entitlements. With every agent $i$ is associated an integer weight $p_i$. Let $Q = p_1+\cdots+p_n$; it is required to partition the cake such that: $$\forall i: {V_i(X_i)\over V_i(Cake)} \geq {p_i \over Q}$$
There is a simple but inefficient way to find a weighted-proportional division:
- Create, for each agent $i$, $p_i$ duplicates.
- Run a classic cake-cutting algorithm on the $Q$ duplicates.
- Give each original agent the pieces allocated to all its dopplegangers.
This is inefficient since it makes $Q-1$ cuts on the cake, giving each agent a large number of "crumbs" (when $Q$ is large).
When there are $n=2$ agents, there is a solution that requires only 2 cuts, regardless of $Q$. To simplify the presentation, assume that the entire cake is worth exactly $Q$ to both agents. Also, assume that the two endpoints of the cake are identified, so that it is topologically a circle.
- Agent #1 makes $Q$ marks on the circle, such that the piece between each two consecutive marks is worth for him exactly $1$.
- Agent #2 evaluates, for each mark, the sequence of $p_2$ consecutive pieces starting that mark and going clockwise, and selects the sequence most valuable in his eyes. By the pigeonhole principle, the value of this sequence for him is at least $p_2$ (since the sum of values of the $Q$ sequences is $p_2 Q$).
- Agent #1 receives the remaining sequence of $p_1$ pieces. The value of this sequence for him is exactly $p_1$.
How many cuts are required when there are three or more agents?
The following example shows that at least $2n-2$ cuts might be required. The valuations are:
Agent 1: 1 0 1 0 1 0 1 ... 1 0 1
Agent 2: 0 1 0 0 0 0 0 ... 0 0 0
Agent 3: 0 0 0 1 0 0 0 ... 0 0 0
Agent 4: 0 0 0 0 0 1 0 ... 0 0 0
...
Agent n: 0 0 0 0 0 0 0 ... 0 1 0
and the weights are:
- $p_1 = n^2$,
- $p_i=1$ for every agent $i\geq 2$.
Agent 1 must receive more than $(n-1)/n$ of the cake, so he must receive something from each of his $n$ desired slices. Each of the other $n-1$ agents must still receive a positive slice. Hence, we must use two cuts for each agent $i\geq 2$, and the total number of required cuts is $2(n-1)$.
We saw above that this lower bound is tight for $n=2$, since there always exists a weighted-proportional division with 2 cuts. So the following question is interesting for $n\geq 3$ agents:
Does there always exist a weighted-proportional partition with $2n-2$ cuts?