Fair cake-cutting when players join late

Question

The usual statement of the fair cake-cutting problem assumes that all $n$ players get their share at the same time. However, in many cases the players arrive incrementally. For example, we may divide a cake over $n$ players, but then a new player arrives and wants a share.

Usually, fair cake division requires a lot of effort (for example, requires the players to answer many queries), especially when the number of players is large.

Is it possible to use the existing division of the cake over $n$ players, in order to create a new division of the cake to $n+1$ players, with minimal additional effort (i.e. substantially less effort than re-distributing the cake from scratch)?

Answer 1

I will say up front that I can't provide a good answer to your question (I think you could maybe get a research paper out of it if you could), but I think I can help by defining the problem formally and stating where some of the difficulties lie.

Background. Let me clearly state the model for cake-cutting. We wish to divide the interval $[0,1]$ between $n$ players. Each player $i$ has a valuation function $v_i(S)$ over subsets $S$ of the cake. We will assume that this function is a probability measure; it is nonnegative and additive (for disjoint $A,B \subseteq [0,1]$, $v_i(A \cup B) = v_i(A) + v_i(B)$) and $v_i([0,1]) = 1$. A solution to this problem is a protocol or algorithm that queries the players and assigns portions of the interval. Note that players may misreport/lie in answering queries.

Some papers will have more specific restrictions; e.g., valuation functions are continuous, or piecewise-linear, or piecewise-constant.

Let the pieces assigned to the players be $\{S_1,\dots,S_n\}$. We often want the following properties of a protocol:

• proportionality: Every player $i$ has a strategy that guarantees s/he receives a value of at least $(1/n)v_i([0,1])$. (From $i$'s perspective, s/he gets $1/n$ of the total value of the cake.)
• envy-freeness: Every player has a strategy that guarantees that $v_i(S_i) \geq v_i(S_j)$ for every other player $j$. (Every player prefers his/her own piece to any other player's piece.)

Note that envy-freeness implies proportionality.

There are also "operational" properties we might want, such as cutting into few pieces, polynomial running time (or indeed computability/constructability at all -- we don't want to use the Axiom of Choice to select a subset of the cake!), and so on.

---

Specific questions to ask. Two notes. First, any answer to your question will solve the general problem: Start by giving the whole cake to player $1$, then let the other players arrive online and iteratively apply this protocol. So we should expect this problem to be harder than the standard cake-cutting setting that we apply it to.

Second, we can always solve your problem by taking the entire cake back from everyone and using a known algorithm to redistribute it from scratch. So the question is just if there's a somewhat more elegant way to do this. I think a good way to quantify this is "when does the redistribution require less time or fewer cuts than starting from scratch; and/or when do players get to keep a significant portion of their current slice?"

1. Suppose we have a envy-free allocation for $n$ players. How do we redistribute to produce an envy-free allocation among the $n+1$ players?

I suspect this is very difficult. The reason is that finding an envy-free, efficient allocation is already a difficult problem. As far as I know, known protocols could require an unbounded number of cuts to the cake and are very complex. (See Brams and Taylor, An Envy-Free Cake Division Protocol, 1995.) So there may be nothing better than to take the entire cake back from everyone and redistribute it to the $n+1$ agents using Brams-Taylor.

1. Suppose we have a proportional allocation for $n$; how do we redistribute to get a proportional allocation for $n+1$?

I think this is still difficult (although more doable). Consider the case where every player values the cake uniformly and every player has a $1/n$-sized slice. Then whatever the new player does will require reshuffling among everyone. Here's another bad case: Suppose player $1$ has a valuation of exactly $1/n$ for her slice, but values player $2$'s slice at $(n-1)/n$. Suppose player $2$ values her own slice at exactly $1/n$, but values player $3$'s slice at $(n-1)/n$, and so on, with player $n$ valuing her own slice at $1/n$ and player $1$'s slice at $(n-1)/n$. Now the new player arrives. No matter what the new player wants, your protocol will end up having to reshuffle something from player $2$ to player $1$, from player $3$ to player $2$, etc.

---

One reference might be Walsh, Online Cake Cutting, in Algorithmic Decision Theory 2011 (pdf link). But I think that paper assumes we know in advance the number of agents arriving, and assumes players must be allocated a piece precisely when they leave (which is before the end of protocol), so it is really not that applicable to your problem.

---

One way to redistribute a proportional allocation that maintains proportionality is as follows. Let each of the present $n$ players cut his allocated piece of cake into $n+1$ pieces that he himself equally values. Player $n+1$ will now choose the best piece, according to him, from each of the $n$ player's cuts. It is easy to show that the resulting allocation is also proportional.

Answer 2

Assume the cake/area is a circle $C$ with radius $r$. Then, we can create $n$ fair pieces by the canonical cake cutting and thus assign each player an area of $\frac{\pi r^2}{n}$. We can then assign the $(n+1)$th a small circle around the center, and subsequent new players rings around that one (swallowing part of the inner circle), and so on. In this way, every player gets one contiguous piece/plot which shrinks in a monotone way for the first $n+1$ players, and moves towards the center for those joining later.

Working out the numbers is simple; for the first new player, simply solve

$\qquad \pi r_1^2 = \frac{\pi r^2}{n+1}$

to get the radius for his plot. For the second, solve

$\qquad\begin{align} \pi r_1^2 &= \frac{\pi r^2}{n+2} \\ \pi r_2^2 - \pi r_1^2 &= \frac{\pi r^2}{n+2} \end{align}$

to get (outer) radii for both new players, and so on. It seems that player $n + i$ gets outer radius $r_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$ after $k$ additional players have joined, but I did not prove this.

This is what you get for $n=6$ and $k=0,1,2,3$:

^[source]

The same idea works for regular polygons with $n$ sides. If you assume a rectangle as basic form, you can do a similar thing by assigning the first $n$ equally sized columns and the following players rows (starting at one side).