TLDR: Borgers book is \$35 and awesome for the additive case of compensation. From this you can Lagrange multipliers to solve nice variations. Add "unimodal" to your search to find articles where the marginal utility goes up for a bit and then back down.
I found cake-cutting to have some additional complications that can be solved in a manageable way by simply paying people a little to make sure things are equal. In other words, we have a cake where people have different (usually finitely additive) utility functions and those difference produce the opportunity for extra-good in the division, but we also have a pile of money where everyone's utility function agrees and is plain old "dx", the easiest of all.
Compensation problems with finitely many goods and additive utility functions are very easy to understand, and are worked out in a very nice textbook way in Borger, 2010 (\$35 print, over \$960 online form the publisher, impressive compensation scheme). The techniques used do not change too much with different utility functions if they are not too weird (for instance, unimodal, continuous function in your case, or monotone, continuous in the case I read about), since you are just optimizing differentiable functions of a single variable, and so the maximums occur either at corners or at solutions to Lagrange multiplier constraints. In the additive case, all the utility functions are linear, so the calculus disappears, and the maximums occur at (at least one of the) corners.
I did not find an easily digestible article discussing your case (which is probably very similar to the example you give: adjust compensation to encourage neither under-production nor over-production; "unimodal" should help the search). The cases I read about were "auctions" where the risk involved means utility functions are "sub-linear", so that people are less willing to risk large amounts of money, so the marginal utility of the cash decreases (but never goes negative as I think it does in your case).
- Börgers, Christoph.
Mathematics of social choice: Voting, compensation, and division.
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. xii+245 pp.
ISBN: 978-0-898716-95-5
MR2574481 DOI:10.1137/1.9780898717624
TLDR: $a_n=\log_2(1+1/n)$ works, and is the only smooth solution.
This problem hints at a deeper mathematical question, as follows. As has been observed by Pongrácz, there is a great deal of possible variation in solutions to this problem. I would like to find a "best" solution, where the sequence of pieces is somehow as evenly distributed as possible, given the constraints.
Let us fix the following strategy: at stage $n$ there are $n$ pieces, of lengths $a_n,\dots,a_{2n-1}$, ordered in decreasing length. You cut $a_n$ into two pieces, forming $a_{2n}$ and $a_{2n+1}$. We have the following constraints:
$$a_1=1\qquad a_n=a_{2n}+a_{2n+1}\qquad a_n\ge a_{n+1}\qquad a_n<2a_{2n-1}$$
I would like to find a nice function $f(x)$ that interpolates all these $a_n$s (and possibly generalizes the relation $a_n=a_{2n}+a_{2n+1}$ as well).
First, it is clear that the only degree of freedom is in the choice of cut, which is to say if we take any sequence $b_n\in (1/2,1)$ then we can define $a_{2n}=a_nb_n$ and $a_{2n+1}=a_n(1-b_n)$, and this will completely define the sequence $a_n$.
Now we should expect that $a_n$ is asymptotic to $1/n$, since it drops by a factor of $2$ every time $n$ doubles. Thus one regularity condition we can impose is that $na_n$ converges. If we consider the "baseline solution" where every cut is at $1/2$, producing the sequence
$$1,\frac12,\frac12,\frac14,\frac14,\frac14,\frac14,\frac18,\frac18,\frac18,\frac18,\frac18,\frac18,\frac18,\frac18,\dots$$
(which is not technically a solution because of the strict inequality, but is on the boundary of solutions), then we see that $na_n$ in fact does not tend to a limit - it varies between $1$ and $2$.
If we average this exponentially, by considering the function $g(x)=2^xa_{\lfloor 2^x\rfloor}$, then we get a function which gets closer and closer to being periodic with period $1$. That is, there is a function $h(x):[0,1]\to\Bbb R$ such that $g(x+n)\to h(x)$, and we need this function to be constant if we want $g(x)$ itself to have a limit.
There is a very direct relation between $h(x)$ and the $b_n$s. If we increase $b_1$ while leaving everything else the same, then $h(x)$ will be scaled up on $[0,\log_2 (3/2)]$ and scaled down on $[\log_2 (3/2),1]$. None of the other $b_i$'s control this left-right balance - they make $h(x)$ larger in some subregion of one or the other of these intervals only, but preserving $\int_0^{\log_2(3/2)}h(x)\,dx$ and $\int_{\log_2(3/2)}^1h(x)\,dx$.
Thus, to keep these balanced we should let $b_1=\log_2(3/2)$. More generally, each $b_n$ controls the balance of $h$ on the intervals $[\log_2(2n),\log_2(2n+1)]$ and $[\log_2(2n+1),\log_2(2n+2)]$ (reduced$\bmod 1$), so we must set them to
$$b_n=\frac{\log_2(2n+1)-\log_2(2n)}{\log_2(2n+2)-\log_2(2n)}=\frac{\log(1+1/2n)}{\log(1+1/n)}.$$
When we do this, a miracle occurs, and $a_n=\log_2(1+1/n)$ becomes analytically solvable:
\begin{align}
a_1&=\log_2(1+1/1)=1\\
a_{2n}+a_{2n+1}&=\log_2\Big(1+\frac1{2n}\Big)+\log_2\Big(1+\frac1{2n+1}\Big)\\
&=\log_2\left[\Big(1+\frac1{2n}\Big)\Big(1+\frac1{2n+1}\Big)\right]\\
&=\log_2\left[1+\frac{2n+(2n+1)+1}{2n(2n+1)}\right]\\
&=\log_2\left[1+\frac1n\right]=a_n.
\end{align}
As a bonus, we obviously have that the $a_n$ sequence is decreasing, and if $m<2n$, then
\begin{align}
2a_m&=2\log_2\Big(1+\frac1m\Big)=\log_2\Big(1+\frac1m\Big)^2=\log_2\Big(1+\frac2m+\frac1{m^2}\Big)\\
&\ge\log_2\Big(1+\frac2m\Big)>\log_2\Big(1+\frac2{2n}\Big)=a_n,
\end{align}
so this is indeed a proper solution, and we have also attained our smoothness goal — $na_n$ converges, to $\frac 1{\log 2}=\log_2e$. It is also worth noting that the difference between the largest and smallest piece has limit exactly $2$, which validates Henning Makholm's observation that you can't do better than $2$ in the limit.
It looks like this (rounded to the nearest hundred, so the numbers may not add to 100 exactly):
- $58:42$, ratio = $1.41$
- $42:32:26$, ratio = $1.58$
- $32:26:22:19$, ratio = $1.67$
- $26:22:19:17:15$, ratio = $1.73$
- $22:19:17:15:14:13$, ratio = $1.77$
If you are working with a sequence of points treated$\bmod 1$, where the intervals between the points are the "sausages", then this sequence of segments is generated by $p_n=\log_2(2n+1)\bmod 1$. The result is beautifully uniform but with a noticeable sweep edge:
A more concrete optimality condition that picks this solution uniquely is the following: we require that for any fraction $0\le x\le 1$, the sausage at the $x$ position (give or take a sausage) in the list, sorted in decreasing order, should be at most $c(x)$ times smaller than the largest at all times. This solution achieves $c(x)=x+1$ for all $0\le x\le 1$, and no solution can do better than that (in the limit) for any $x$.
Best Answer
After giving to (1) one of unclaimed pieces, less than 2/3 of cake can be left (in measure of (2) or (3)), so one of them will be unsatisfied.
Edit: The right solution is the following.
1. Let (1) divide cake into three equal pieces.
2. Ask (2) and (3) "What is the best one?". If their answers are different, we are done: each one of (2) and (3) gets what he (or she) wants, and (1) takes unclaimed piece. Otherwise go to step 3.
3. Ask (2) and (3) "Is there any other piece, you would satisfied with?". If at least one of the answers is "Yes" we are done similar to step 2. Otherwise go to step 4.
4. (1) takes any of two unclaimed pieces.
5. Thanks to the answer "No" at the step 3 we know, that at least 2/3 of the cake left in both measures (the one of (2) and the one of (3)). Therefore we can apply "you cut, I choose" method to the leaving 2 pieces.
Edit: This problem can be solved with arbitrary number of children using the algorithm for finding maximum matching in a bipartite graph. Suppose, number of children is n. Cutting the cake algorithm is the following.
1. Let (1) divide cake into three equal pieces.
2. Ask others the following: "Please, list all the pieces, you will be satisfied with."
3. Consider bipartite graph with 2n-1 vertices: n pieces of cake and all children except (1). Children is connected with a cake iff it will be satisfied with it. 4. Find maximum matching in this graph. Lets call vertex "free" iff it is not matched in this matching with another one.
5. If there are no free children, give pieces of the cake according to the matching (and free piece of cake is for (1)). In this case we are done. Otherwise go to step 6.
6. In the algorithm of maximum matching we are able to find its certificate, i.e. pair of sets (U,V) with U containing all free children and some non-free, and V containing some pieces of cake, such that 1) amount of elements in V is equal to amount of non-free elements in U; 2) every vertex in U has edges only to vertexes form V 3) there are no edges from chosen matching, connecting vertex from V to some vertex outside U. In our case it means that every piece of cake outside V is less than 1/n in all measures of children from U.
7. Give pieces of cake to children outside U (except (1) ) according to chosen matching.
8. Give any free piece of cake outside V to (1).
9. Note, that according to 6, all pieces of cake given at 7 and 8 are unimportant for elements of U. Therefore there is enough cake left for them. Divide it according to this algorithm between elements of U (note, that (1) is not in U, and, therefore size of U is less than n).