3
$\begingroup$

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?


$\endgroup$
1
$\begingroup$

We can do an inductive construction for $n(n-1)$ cuts. For two agents, you gave the construction. For $n>2$, divide the cake proportionally among the first $n-1$ (into ratios of $\frac{p_i}{p_1+\cdots+p_{n-1}}$). Then the $n$th agent comes along and wants to take a fraction of $\frac{p_n}{Q}$ from each of the others (then he'll have $\frac{p_n}{Q}$ of the cake). Each of the other agents wants to make sure that he retains a fraction of $1-\frac{p_n}{Q}$, since then he'll have a total of $\left(1-\frac{p_n}{Q}\right)\left(\frac{p_i}{p_1+\cdots+p_{n-1}}\right)=\frac{p_i}{Q}$. They can achieve this using 2-agent division, at the cost of 2 cuts (even though the piece they're dividing may be disconnected; just pretend it's a circle and ignore the rest of the cake).

That means that the $n$th agent coming in makes $2(n-1)$ cuts, so the total number of cuts is $$ \sum_{k=1}^n 2(k-1)=n(n-1) $$

$\endgroup$
  • $\begingroup$ This makes sense. I think I can even improve this to $O( n \log n)$. But, the lower bound is only $2n - 2$. So it is still interesting, whether this lower bound can be attained. $\endgroup$ – Erel Segal-Halevi Jun 21 '16 at 9:42
  • $\begingroup$ Here is the explanation on why $O(n \log n)$ is sufficient: arxiv.org/abs/1803.05470 $\endgroup$ – Erel Segal-Halevi Mar 17 '18 at 17:40
0
$\begingroup$

Two sub-problems in which the lower bound can be attained

In both sub-problems, assume that the cake is a circle and all agents value it as $Q = \sum_{i=1}^n p_i$.

Sub-problem A: three agents, two equal weights

there are $n=3$ agents, two of whom have the same entitlement, e.g. $p_1=p_2$. The lower bound is $2n-2=4$ cuts. The following protocol matches this bound:

  • Agent #1 makes $Q$ marks on the circle, such that the piece between each two consecutive marks is worth for him exactly $1$.
  • Agent #3 evaluates the $Q$ arcs of length $p_1$. By the pigeonhole principle, there is at least one such arc that agent #3 values as at most $p_1$. Ask agent #2 to evaluate this arc too:
    • If agent #2 also thinks that this arc is worth at most $p_1$, then this arc is given to agent #1, who values it as exactly $p_1$. So far we used two cuts. The remaining cake is worth to agents #2 and #3 at least $p_2+p_3$, so they can divide it among them using two additional cuts.
    • Otherwise, agent #2 receives the arc, which is worth for him more than $p_2$. So far we used two cuts. The remaining cake is worth for agents #1 and #3 at least $p_1+p_3$, so they can divide it among them using two additional cuts.

Sub-problem B: $n$ agents, $n-1$ equal weights

there are $n$ agents, $n-1$ of them have an entitlement of 1, and the $n$-th agent has an entitlement of $Q-(n-1)$, for some integer $Q$. The following protocol matches the lower bound of $2n-2$ cuts:

  • Create $Q-(n-1)$ doppelgangers of agent $n$. Now there are $Q$ agents.
  • Divide the cake among the $Q$ agents using a standard cake-cutting procedure which uses $Q$ cuts.
  • Each agent $1,\dots,n-1$ has a single connected interval worth for him at least 1. We need at most two cuts to extract each interval, so the total number of cuts used is $2n-2$.
  • The remaining cake is given to agent $n$. It is worth for him at least $Q-(n-1)$.

Three agents, failed directions

Again the goal is to use at most 4 cuts (the lower bound).

Let agent #3 make $Q$ marks on the circle, such that the piece between each two consecutive marks is worth for him exactly $1$. We would like to give one of the three agents a fair piece, while making sure that the remaining cake is sufficiently valuable for the remaining two agents. This can be done in three ways:

Way 1. Give agent #1 an arc of length at most $p_1$, whose value for agent #1 is at least $p_1$ and for agent #2 at most $p_1$.

Way 2. Give agent #2 an arc of length at most $p_2$, whose value for agent #2 is at least $p_2$ and for agent #1 at most $p_2$.

Way 3. Give agent #3 an arc of length $p_3$, whose value for agents #1 and #2 is at most $p_3$.

Unfortunately, there are cases in which none of this ways is possible. For example, suppose the weights are $p_1=3,p_2=2,p_3=1$. Agent 3 cuts six pieces equal in his eyes, and the valuations of 1 and 2 for these pieces are:

 Agent 2:   1.4   0.3   1.2   0.3   1.4   1.4
 Agent 1:   1.1   1.1   0.5   1.1   1.1   1.1

There is no arc of length 3 that is worth at least 3 for Agent 1 and at most 3 for Agent 2; no arc that is worth 2 for Agent 2 and at most 2 for Agent 1; and no arc of length 1 that is worth at most 1 for both Agent 2 and Agent 1;

But all is not lost. It is possible to relax the requirement of Way 3. For each arc of length $p_3$, let $x\cdot p_3$ be its value to Agent 1 and $y\cdot p_3$ its value to Agent 2. So the value of the remaining cake to Agent 1 is $Q-x\cdot p_3$ and to Agent 2 is $Q-y\cdot p_3$. If we want to divide the remaining cake fairly between Agent 1 and Agent 2, we must give the former at least ${p_1 \over Q-x\cdot p_3}$ of the remaining value and the latter at least ${p_2 \over Q-y\cdot p_3}$ of the remaining value. Motivated by this observation, let's call a piece "good" if: $$ {p_1 \over Q-x\cdot p_3} + {p_2 \over Q-y\cdot p_3} < 1$$ otherwise call it "bad". In the linked graph, the purple region represents the good pieces and the white region to its top-right represents the bad pieces.

If there exists a good piece (in the purple region), then we can cut this piece (using 2 cuts) and give it to Agent 3. The remaining cake can be divided between Agent 1 and Agent 2 using the procedure for two agents, with modified weights. The new weights are determined such that:

  • ${p_1' \over p_1'+p_2'} \geq {p_1 \over Q-x}$
  • ${p_2' \over p_1'+p_2'} \geq {p_2 \over Q-y}$

We already know that the procedure for 2 agents uses 2 additional cuts, so all in all we need 4 cuts.

In the above cake, there is indeed a good piece, for example, the second slice. It is worth 1.1 for Agent #2 and 0.3 for Agent #1, which is well within the purple region (the sum of adjusted weights is 0.97). Indeed, if this slice is given to Agent #3, then the remainder can be easily divided between Agents #1 and #2 using two cuts.

MY CONJECTURE IS that, if Way 1 and Way 2 are impossible, then there must be a good piece. Moreover, I conjecture it may be possible to simplify the definition of a "good piece" as follows: \begin{align*} (p_1+p_3)\cdot x + p_2\cdot y \leq Q \\ \text{ and } \\ p_1\cdot x + (p_2+p_3)\cdot y \leq Q \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.