Breadstick Puzzle

This one from a good friend of mine.

You and some others have a long breadstick to divide on basis that everyone, in turn, puts one finger on it, and every gets all parts of the bread that are closest to his finger. Everyone follows the same strategy:
First rule: maximize how much bread you get.
Second rule: if your choice doesn't change how much bread you get, go for even split among the others.
Third rule: there is no deal making, diplomacy, barter etc.

The question is, where to touch the bread?

n = 1 is pretty obvious.. touch anywhere, and claim the whole bread.
n = 2 is simple too. Touch at the middle, your buddy touches the bread right next to your fingertip, and each one gets half the bread.

things get interesting at n = 3 and even more so at n = 4 or more.


(Variants.. rather than breadstick, use a bagel, or to get the largest area of a pizza, or the most volume from a watermelon; or allow negotiation, or have limited information, etc.)

Eliminating the equations:

if there are three players: put your fingertip at some point, dividing the breadstick into two segments. If you choose too far from one end, the second player's best strategy is to claim the shorter of the two halves, and the third player's to claim the larger, and you get nothing, so don't be too greedy. The second player then faces the same dilemma, too far from the other end and the third player take the long end, with the second getting one half of the middle section. Optimally, that translates into saying that the best bet for the first player is to put his finger one quarter of the way along the bread from one end, and the second player to the same, starting from the other end. The third player then gets 1/4 of the bread by placing right next to either finger near the end, of anywhere between the two fingers. The two rules - maximize how much you get (1/4 or less, so 1/4) and given that condition be impartial to the others means that the third player puts his finger right in the middle, so the fingertips are at 1/4, 3/4, and 1/2, making the shares of the breadstick 3/8, 3/8, and 1/4.

With four players, a similar reasoning would put the fingertips at points 1/6, 5/6, 7/18 and 11/18. Whether that is still optimal for everyone.. and how to expand to n = 5+..?

I got stuck on "fairness" whilst considering this.
with four players:

A puts finger at 1/6
B puts finger at 5/6
C puts finger in middle

Now D can go in several places:
Next to A on either side, scoring 1/6 and disadvantaging A
Next to B on either side, scoring 1/6 and disadvantaging B
Exactly Between A and C, scoring 1/6 and disadvantaging A and C
Next to C, scoring 1/6 and disadvantaging C
Between B and C, scoring 1/6th and disadvantaging B and C

So where will he go most "fairly"? Was C's move unfair to D because it stopped him playing fairly?

C's move may have been fair or not, that is irrelevant as long choosing the middle point is the best strategy for C.

As for D, I suppose it's simplest to replace the fairness rule with a random choice and expected value. That is, if there are multiple places that all give an equal share of the breadstick, the player tosses a coin and just picks one of those.. but random is not that obvious either, as some of those are simply points with zero width, and some are lengths with non-zero length.

Changing it to "if there are multiple points that all give a player the biggest possible portion of the breadstick, he'll choose the one closest to the left end of the breadstick" should avoid randomness.

I think if it is fairness then he should choose "The position that minimises the variance of the other scores from their mean."?

If there is a tie he should choose randomly, treating each contiguous block of breadstick that he could play in as one choice. (i.e if there is one zero with point and 1 quarter stick length that each get the same variance he should choose one of them randomly.

If, he has chosen a non-zero length piece of stick, and all points in it get the same score then he should go in the middle.

This may apply to a player before the last if there are several points he could play in that give the same expected score.

What do you think? If we have some solid rules like this I could write a simulation...

I like your definition of fairness. It is both unambiguous and has the spirit of what I and my friend had in mind.

Hmm, do you think that, if a player is evaluating putting his finger between two other players' fingers then, he only needs to initially evaluate going in the middle, and only re-evaluate whether this is the best choice if players go on either side of him?

The logic is:
If nobody plays on either side of player A, then as he gets the same breadstick amount wherever he goes (in the gap), so going in the middle is the joint best he can do (making gap * 3/6) profit.

If somebody later plays on one side of player A, then that must happen because that is the play (or one of several equal plays) with the most profit that person can make. If player A edges either side of the middle, the intruding player will see the longer gap as the most profit and go there so player A's profit is reduced. Therefore going in the middle is the best option. (Making gap *3/8 profit)

If two people play on each side of Player A the two straddling players made gap/4 profit and Player A made gap/4 profit too. If Player A goes anywhere else than the middle, to change his profit significantly he must make them both play on one side of him. To do this Player A can go at gap/5 from the end, the next player goes in the middle of the large chunk at gap*3/5 and the second player has a choice of 3 places each giving him gap/5: In the best case the third player might go at gap*4/5 which leaves player A with gap 3/10 profit which is better than the middle play.

Therefore Player A only needs to evaluate positions (between two fingers) other than the middle play if he is double straddled, but if he IS doubly straddled he must evaluate other positions as they may increase his bread.

Does that logic hold? The other interesting thing, is that it looks as if, if a player plays in the middle of a gap then possibly he always makes an optimal profit of gap * 3/(6+2n) where n is the number of later players that also go in that gap.

Ok, let us say that player A goes in a gap (between two other players) in the optimal position Gap*P from the edge. Player A scores Gap * K and the worst off remaining player scores Gap*W.

Consider what happens if one more player goes in the gap. Player A plays at Gap*X from the nearest edge and he wants no other players to go between him and the edge.

The gap A wants everyone to go in has size Gap*(1-X), the worst off player (if they all play on that side) will therefore score Gap*(1-X)*W

If the worst player plays on the unwanted side of A he scores Gap*X/2 and at the balance point therefore
Gap*X/2 = Gap*(1-X)*W

X/2 = W - WX
X(W + 1/2) = W
X = W/(W+1/2)

So, with N players, Player A plays at position Gap*W/(W+1/2) where Gap*W is the score of the worst remaining player whether there were N-1 players. As this must be the balance point, we can also predict that with N players, the worst player scores Gap*W(W+1/2)/2, essentially half of the Gap that player A left.

Is this right?

With 1 player, playing in between two others, the player goes at Gap/2 and he is also the worst off player, scoring Gap/2/ So W = 1/2

With two players, we would predict that the player would go at Gap*(1/2)/(1/2*1/2) = Gap/2, This is right. In this case the worst (second) player should score Gap/4 which we can see is also right.

With three players, the first player must play at Gap*(1/4)/(3/4) = Gap*1/3

which we can also see is right with some thought.

To be continued!

Ok carrying on, I have shown that, when N people are playing in a gap between two fingers:

P is (as yet) an unknown

player 1 plays at a proportion P (of the gap) from the edge.
The last (worst off) player scores a proportion P/2 bread.

With N+1 players

The first player plays at (P/2)/((P/2)+1/2)

= (P/2)/((P+1)/2)
= (P/(P+1))

= 1/(1+1/p)

i.e if the first player plays at 1/x then the next player will play at 1/(x+1)

With 1 player playing in the gap he plays at 1/2 which implies that with two players he should play at 1/3 and with N players, the first player plays at 1/(1+N) with the worst off (last player) making a profit of 1/(2+2N)

So we now have a good equation for how much money the worst off player will make in a set of N players who play into the gap between two fingers.

Let us now consider what a person playing on a half open gap should do, where a half open gap is a section of bread with a finger at one end and the end of the bread at the other.

It makes most sense for this person to play in a position where nobody gains from cutting inside him i.e. somebody plays just a fraction closer to the edge. To just do this he has to play W from the edge, where W is what the worst of player in the N remaining will get.

If he plays at W
Then the remaining proportion is (1-W)
and the worst player gets (1-W)/(2N-2)

(where N is the number of players including this player who is playing in a half open gap)

So, at the balance point
W = (1-W)/(2N-2)
2NW-2W = 1-W
W(2N - 1) = 1

W = 1/(2N-1)

With the worst player getting 1/(2N-1) of the remaining stick

Now, considering the first player, who is playing on a completely unclaimed breadstick

HE doesn't want to be undercut.

Assuming he goes at a position X
Then the stick left for the remaining players is (1-X)

Converting their equation to n where n is the total number of players, the last player will get:

(1-W)/(2n-3)

so at the balance point

W = (1-W)/(2n-3)

2Wn-3W + W = 1
W = 1/(2n-2)

This implies that:

With 2 players the first player plays at 1/2
With 3 players the first player plays at 1/4
With 4 players the player plays at 1/6
With 5 players the player plays at 1/8
etc.

So the answer to the question is:
The first player plays at a proportion of 1/(2n-2) from the edge of the bread stick, where n is the number of players

The second player plays at this proportion from the OTHER edge.

The worst-off player is the last and he gets 1/(2n-2) of the stick.

Bagels and Pizza (touch the edge) follow similarly. I have no idea at all about watermelons.

Aha, watermelons are actually the easiest! Just touch anywhere! (all points are the same).

N players.

Each player touches 1/n from the end.

Everyone gets equal amounts of bread.

Originally posted by AThousandYoung
N players.

Each player touches 1/n from the end.

Everyone gets equal amounts of bread.

We can see that is wrong with 3 players

Stick length is 12

if player A goes at 1/3rd of 12 (4) then
Player B selects 8.1

If C plays between A and B he gets 4.1/2 = 2.05
If C plays next to B (nearer end) say at 8.2, then he gets 3.85
If C plays next to A (nearer end), say at 3.9, then he wins 3.95

So, C cuts inside A leaving A with 2.1, B with 5.95, and C with 3.95
A has clearly lost, B has clearly won.

My algorithm predicts A should go at 12/4 = 3
If B tries the same trick, and goes at 9.1 then:
If C goes outside B at 9.2 then he gets 2.85
If C goes in between A and B he gets 6.1/3 = 3.05
and if C cuts inside A, say at 2.9 then he gets 2.95

So C plays in between A and B, and due to the rules plays exactly in between them at 6.05
Now B gets 4.425
A gets 4.525
and C gets 3.05

A has won

So my algorithm is best for A

Originally posted by talzamir
This one from a good friend of mine.

You and some others have a long breadstick to divide on basis that everyone, in turn, puts one finger on it, and every gets all parts of the bread that are closest to his finger. Everyone follows the same strategy:
First rule: maximize how much bread you get.
Second rule: if your choice doesn't change how much bread ...[text shortened]... , or the most volume from a watermelon; or allow negotiation, or have limited information, etc.)

In n=2 if I put my finger in exactly in the middle and you put yours right next to mine wouldn't i get a slightly larger piece? This can be remedied by both parties putting their finger on the ends. The problem is, should everyone play fair? If I put my finger on the end then you can put yours right next to me in such a way that you get almost the whole bread.

I think my preffered strategy would just be to grab the dang bread and start eating it.

Does anyone want me to work out the ideal strategy if the fingers are some none zero width?