patternMinor
Fair cake-cutting when players join late
Viewed 0 times
fairlatecuttingplayersjoinwhencake
Problem
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)?
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)?
Solution
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).
$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).
Context
StackExchange Computer Science Q#11077, answer score: 6
Revisions (0)
No revisions yet.