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

Problem Detail: 

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)?

Asked By : Erel Segal-Halevi

Answered By : usul

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11077