17

Too long for a comment. Here is a way to use around $8n/3$ pieces.
Cut out as many pieces of length $1/(n+1)+1/n+1/(n-1)$ as you can; there are $k\approx n/3$ of them. Imagine each such piece as a segment; this segment can be cut into pieces $1/(n+1),1/n,1/(n-1)$ (in this order) and $1/(n-1),1/(n+1),1/n$ (in this order). Mark cutting points for both cuttings,...

13

Here are the fairest sequences with $v_0\ge v_1$ for small $n = $ $1,$ $2,$ $\dots,$ $14$, according to an exhaustive search, where $v_b$ denotes the expected score for the player who can choose when the binary digit is $b$.
The reverse Thue-Morse sequence do look better than the Thue-Morse sequence but its score is far from the fairest. The Thue-Morse ...

11

Writing down the details of the argument of Ilya Bogdanov, we can obtain the following upper bound:
Theorem. $f(n)\le\frac83n-1$ for every $n\ge 2$.
Proof. If $n=3k+1$ or $n=3k+2$, then following the idea of Ilya Bogdanov, divide the cake into $k$ pieces of length $\frac1{n-1}+\frac1n+\frac1{n-1}$. This is possible since
$k(\tfrac1n+\tfrac1{n-1}+\tfrac1{n+...

11

Just a remark : with your weights (0,...,n) you have an simple formula to calculate the expectation.
$$v_1(1b_1b_2\cdots b_n)=1+v_1(b_1\cdots b_n) $$
$$v_1(0b_1b_2\cdots b_n)=\frac{1}{n+2}+\frac{n+3}{n+2}v_1(b_1 \cdots b_n) $$
Proof :
Let us call $Y$ the value obtained by the first player with a sequence $b_1 \cdots b_n$. Now consider the same sequence ...

8

Edit: The below does rely on the assumption that knives move continuously, see the comments.
I think the procedure is "safe": Each player can guarantee not to envy either of the others by following the suggested protocol. I am assuming that the rules are that players must keep their knives to the right of the sword. Intuitively, the straightforward proof of ...

8

Here is a counter-intuitive result that gets us as far as possible from the Thue-Morse sequence. Infinitely many sequences which are alternating only once are among the fairest sequences of all. Their score differences are 0.
Let's use free-monoid notations and write $1^40^2$ for $111100$. Then
$v_0(1^40^2) = v_1(1^40^2) = 5$
$v_0(1^{12}0^4) = v_1(1^{12}0^...

7

$f(7)=15$.
$f(7)\ge15$ follows from a comment of Fedor Petrov on the original question, so it suffices to find a way to cut the cake into $15$ pieces so as to serve $6$, $7$, or $8$ guests.
Let the size of the cake be $168$ (so that all the following computations involve only whole numbers). Let the $15$ pieces be of sizes $1,2,4,5,7,8,10,11,13,14,16,17,...

answered May 6 '19 at 5:25

Gerry Myerson

34.2k77 gold badges158158 silver badges202202 bronze badges

5

Since it is possible that there are citizens in different states with the exact same valuation of land, we might as well solve the stronger version where each citizen in each state believes that her state received exactly $\frac{1}{2}$ the land value.
In this case, I think a suitable version of the Ham Sandwich Theorem for measures should imply the ...

4

I take the freedom to interprete the question in the following way:
the value-measures of the citizens are not secret and the two nations are befriended, so they want to partition the land in a way that the citizens of state $A$ receive a piece of land that is worth at least 50% of the total land's value according to their value-measure and, the citizens ...

4

The following paper apparently addresses exactly the question that you are interested in:
A General Elicitation-free Protocol for Allocating Indivisible Goods, by: Sylvain Bouveret and Jérôme Lang, International Joint Conference on Artificial Intelligence (2011).

3

Encouraged by the existence result in Tony Huynh's answer, the next interesting question is: what is the smallest number of connected pieces with which a unanimously-fair division can be achieved?
The following simple example shows that the number of pieces must be at least $N$ - the total number of citizens in all states. In the example there are 3 states ...

2

$f(6) = 13$ with a cake of size $210$ and piece sizes:
$$\{3, 5, 8, 10, 12, 13, 17, 18, 20, 22, 25, 27, 30\},$$
where
$$17+25 = 5+10+27 = 20 + 22 = 3+8+13+18 = 12+30,$$
$$10+25 = 5+30 = 3+12+20 = 17+18 = 13 + 22 = 8+27,$$
$$5+25 = 3+27 = 10+20 = 12+18 = 13+17 = 30 = 8+22.$$
It was computed with via solving MILP as explained in my other answer.

2

As far as I know, this is an open question. Some information can be found in:
Branzei and Nisan (2017), The Query Complexity of Cake Cutting.

1

We can do an inductive construction for $n(n-1)$ cuts. For two agents, you gave the construction. For $n>2$, divide the cake proportionally among the first $n-1$ (into ratios of $\frac{p_i}{p_1+\cdots+p_{n-1}}$). Then the $n$th agent comes along and wants to take a fraction of $\frac{p_n}{Q}$ from each of the others (then he'll have $\frac{p_n}{Q}$ of the ...

1

Two sub-problems in which the lower bound can be attained
In both sub-problems, assume that the cake is a circle and all agents value it as $Q = \sum_{i=1}^n p_i$.
Sub-problem A: three agents, two equal weights
there are $n=3$ agents, two of whom have the same entitlement, e.g. $p_1=p_2$. The lower bound is $2n-2=4$ cuts. The following protocol matches ...

1

In "Consensus-halving via theorems of Borsuk-Ulam and Tucker", Su and Simmons describe a way to divide a cake to two parts such that each of $n-1$ people believe the parts have the same value. This can be done with $n-1$ cuts ($n$ pieces), which is optimal.
Once we have such a division, we can let the $n$-th person choose which half is better. Now, ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

fair-division × 11game-theory × 6

co.combinatorics × 3

oc.optimization-and-control × 3

reference-request × 2

measure-theory × 2

economics × 2

social-choice × 2

voting-theory × 2

nt.number-theory × 1

gn.general-topology × 1

partitions × 1

recreational-mathematics × 1

extremal-combinatorics × 1

continuity × 1

combinatorics-on-words × 1