[Solved]: Fair cake-cutting when players join late

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.