11
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Have the first $n$ players started eating? Is it fair to give a player multiple pieces, or does everyone have to get exactly one piece? $\endgroup$ – Raphael Apr 7 '13 at 12:13
  • $\begingroup$ @Raphael, I am specifically interested in fair division of land, therefore the players cannot literally start eating their share (they can build on their share, but let's ignore this problem for the moment). It is preferrable to give each player exactly one piece, however, this is apparently not possible to do fairly in case only a single new person arrives. Probably I should ask, what happens if $n$ new players arrive. In that case, it is possible (at least in theory) to divide each share of the first $n$ players into 2 new shares. In any case, any reference is welcome. $\endgroup$ – Erel Segal-Halevi Apr 10 '13 at 9:15
  • $\begingroup$ In case of unused land, why not redistribute everything? $\endgroup$ – Raphael Apr 10 '13 at 11:06
  • 2
    $\begingroup$ I think you have to clarify what your goal is. Minimise the number of updating cuts? Minimise the total length of new cuts? Can we reassign parts to old players, or can the only ever lose? $\endgroup$ – Raphael Apr 10 '13 at 20:24
  • $\begingroup$ Ah, now I see what you mean: you mean that some of the players started eating their share, and now new players arrive, and we want to divide the reminders fairly, taking into account what each player has already eaten. While this is an interesting problem by itself, my intention was different - I hope my recent edit clarifies this. $\endgroup$ – Erel Segal-Halevi Apr 12 '13 at 11:30
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure how the general problem (with non-uniform preference) is of help here; whoops? Solving the problem for unchanging players (and reasonable shapes) is easy. I guess we'll have to fix what "efficient" resp "good" means w.r.t. cuttings/allocations and changes thereof. $\endgroup$ – Raphael Apr 10 '13 at 20:23
  • 1
    $\begingroup$ @Raphael - as far as I can tell, the question asks about solving the general problem. (I agree we should use additional structure if any is specified.) $\endgroup$ – usul Apr 11 '13 at 6:06
  • $\begingroup$ Thank you, your definition precisely captured my intention. And the reference about online cake cutting is interesting and relevant. $\endgroup$ – Erel Segal-Halevi Apr 12 '13 at 13:39
6
$\begingroup$

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$:

example [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).

$\endgroup$
  • 1
    $\begingroup$ It would be interesting to compare the area which is reassigned by this method to the area which is reassigned by inserting a new piece (i.e. sector) of cake and moving (and shrinking) all the existing pieces clockwise. The number of parties affected by a move (not only a loss) differs only by a constant. Also note that rings are not more effective than sectors, but the change from one method to the other allows not to move the area assigned by the first method. $\endgroup$ – frafl Apr 10 '13 at 14:37
  • $\begingroup$ @frafl I agree. Can you present the other variant(s) in an answer? (You are right: there does not seem to be a good reason for mixing the methods. For me it was motivated by the cake problem: assume the cake has been cut already, what to do?) $\endgroup$ – Raphael Apr 10 '13 at 18:29
  • $\begingroup$ @frafl Note that one advantage of the scheme I use may be that the pieces of the first $n+1$ players only shrink but don't move. In order words, this scheme makes fewer cuts (completely) obsolete than inserting new cake-piece sectors. $\endgroup$ – Raphael Apr 11 '13 at 7:25
  • 1
    $\begingroup$ This is a beautiful gemoetrical solution, however it is relevant only for uniform cakes and uniform prererences. I refered to the general cake-cutting problem: en.wikipedia.org/wiki/Fair_division which assumes that the cake can be non-uniform, and different players may have different valuations to different parts of the cake. $\endgroup$ – Erel Segal-Halevi Apr 12 '13 at 13:37

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.