wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Sausage duel
        
(Message started by: Grimbal on May 31^st, 2008, 9:39am)

Title: Sausage duel
Post by Grimbal on May 31^st, 2008, 9:39am

I just heard of this excellent problem on another forum. It is about a "sausage duel".

The duel works like this:
At the beginning, the 2 participants receive one sausage each, identical in weight.
In each round, each participant cuts a piece of his sausage, unseen by the other. The pieces are compared on a 2-pan balance and the one who provided the heaviest piece earns 1 point.
The pieces are discarded after each round, the game continues with what remains from the sausages.
The first to earn 5 points wins the game.

What would a good strategy look like?

Title: Re: Sausage duel
Post by Grimbal on May 31^st, 2008, 11:14am

For a start, I see that the fate of the game depends on how many points each player needs to win and what is the length ratio between the remaining sausages. (Or the weight ratio, but I feel more comfortable reasoning in terms of length).
If a player needs only 1 point, he wins if he has the longer one. If he needs n points, he wins if he has more than n times the opponent's length.

I have tried to see what happens if A needs 1 point and has length 1 left and B needs 2 with length 1.5. It looks like it depends a lot on what happens at equality. Whether they get no point or each gets one, or each gets 1/2.

In real life it would hardly happen. And the other player's remaining length would not be known precisely. If the sausages remain hidden, the players would have to rely on an estimation of what the other has left.

Title: Re: Sausage duel
Post by jollytall on Jun 4^th, 2008, 5:09am

In general we can say that this is a 100% symmetric, zero result game. As such, if both play the optimal strategy, the expected result is a draw over many games. For the result of one game only, it is trickier. If there is a "pure" optimal strategy then the result is a draw since for the first cut they cut the same length and so the game remains the same, etc. However if the optimal strategy is a "mixed" strategy, the outcome of one game is 50-50 chance assuming both players play that.

Let's try to solve a much simpler game. Let them play up to 2 points only (instead of 5). Let the cut amount be pi and qi in the i-th step for player P and Q.
Let's see what can be the outcome after the first step.

if p1>(1+q1)/2 then the first point goes to P, but the next 2 goes to Q, so Q wins.
if p1<2*q1-1 then the first point goes to Q, but the next 2 goes to P, so P wins.
if q1<p1<(1+q1)/2 then the first point goes to P and they play on with 1-p1 and 1-q1 saucegues respectively. See in details later.
If q1>p1>2*q1-1 then the first point goes to Q and they play on again.
(The equal situations I did not look at because the extremely precise balance will always tell which one is longer/heavier. It can be interesting to look at those cases too, though.)

Continue after P-Q 1:0.

P has 1-p1 left, Q has 1-q1 left.
If p2>q2 then P wins immediately.
if p2<(p1-q1)+q2 then Q gets the next point, but P has the deciding point, so again he wins.
If (p1-q1)+q2<p2<q2 then Q gets this point as well as the deciding point.

So, it is clear that neither P, nor Q can have a “clear” strategy (because the other would have a winning counter strategy). So they both have to use a mixed strategy. Theoretically they both can have infinite options, so they should have a probability distribution function of options (length). I could not prove yet, but it seems that with the ideal mixed strategy the outcome is actually the ratio of probabilities assuming both players play a totally random strategy. This is (1-p1)/(1-q1) probability that P wins. I was thinking on various mixed strategies but it seems that some sort of triangle for Q (cutting half is the most likely, while cutting shorter and longer is less likely) and some sort of reverse triangle (cutting a short or long one is more likely than cutting half) for P is the ideal mixed strategy. In the next steps I assume this, although not sure.

Continue after P-Q 0:1. This is symmetrical to the previous case.

Now back to step 1.
Both P and Q can cut any length between 0 and 1. For every P, Q pair we know the probability of the final result, using the previous steps (see the drawing). So the question here, whether any of the players can have a “clear” winning strategy. It is clear from the drawing that for any clear strategy of P, Q has a good solution against. So I assume, here again they have to use a mixed strategy, but because the “potential” surface of the chart is already complex (see second drawing), I assume that the mixed strategy is not very simple.

Nonetheless I will try to figure out what is the ideal mixed strategy for step 2 and then many even be, what is it for step 1.

Title: Re: Sausage duel
Post by jollytall on Jun 4^th, 2008, 5:11am

And the potential 3D

Title: Re: Sausage duel
Post by Hippo on Jun 7^th, 2008, 12:24am

There is a small correction in jolytail arguments.
The strategey after first turn is following. Leading player X has x remaining, the other Y has y.

X can divide x/y into chunks of size (1-x/y). Border positions of these chunks are his choices of equal probability.
A move of Y can beat at most one choice of X so Y wins with probability 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.gifx/y / (1-x/y) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif. (There are rule dependent cases when the ratio is integer.. If Y choses the points with equal probability, X cannot gain more.

So for the 2:2 goal case: Let f(z) be the probability X choses xhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifz for the equilibrium strategy. 0<=f(z)<=1, f(z)=0 for z<=0, f(z)=1 for z>=1, f is nondecreasing,
it seems to me there are not jumps on f ... f(x₀-)=f(x₀)=f(x₀+) (otherwise x_i+1=x_i+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gifwould be counterstrategy forcing another jump ... forcing f to exceed 1)

For any pure counterstrategy y of Y it can gain at most 1/2 so for any 0<=y<=1 (after the long computation) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_N=1^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} 1/(N(N+1))(f(y-(1-y)/N)+f(y+(1-y)/(N+1))) >= 1/2+f(y)

Morever if f is increasing at point y the sum must equal 1/2.

Clearly for y=1 sums to 2 >= 3/2 so it obviously isn't the counterstrategy. For y=0 we get http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_N=1^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} 1/(N(N+1))f(1/(N+1))>=1/2. But I don't know how to continue with this functional equation.
Let y₀=sup{y|f(y)<1} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_N^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} 1/(N(N+1))f(y₀-(1-y₀)/N)>=1/2.

Title: Re: Sausage duel
Post by jollytall on Jun 8^th, 2008, 1:55am

Thnaks Hippo for the thought of a jolly tail. Very nice...

Seeing that someone else is also thinking on it, let me share some of my thought and also how they reflect to what Hippo said.

In general, I was thinking a lot on whether after the first point (I am still thinking on the "reach 2 points" game) the players have a continuous mixed strategy or a mixed of few distinct ones. In an earlier game (I will put it up on the forum soon) I had multichoice mixed strategies and it came out that most of the time you have to choose from a limited number of choices (linked to number of independent parameters) and not from all. But it is a bit different, and I was and still am not sure. This is how I came to the continuous strategy. But maybe (as Hippo also suggests) there are indeed limited choices to choose from.

Regarding what Hippo said (although I do not fully understand :-( ):
First I think there are two very different cases. In one of them X (using Hippo's namings) wins the first round narrowly (which means they have almost the same amount left, but X has a point) and in the other X won, but used a lot of sausage, so he has a little left compared to Y (I do not mean the case when he has SO LITTLE that Y can surely win). Look at the attached two drawings. Y has always left 100 px sausages left, while X has only left 60 or 90 respectively.

A totally random strategy from both players would result the same as the ratio of the green and red areas.

Look at the first one (X won but used a lot of sausages). Hippo says X should cut along the blue line. As per Hippo's formula there is only one blue line, but I think it is rather symmetrical (not fully! - see later), so he can have two blue lines. Y halving his sausage surely wins. As Hippo said, he can beat one, but if there is only one, then it is enough (actually because of the symmetry I would say that there are two, but he can beat two). So X following Hippo's strategy surely looses, what is not very promising.
Even if there are more borders (in the lower chart I drew one dark blue line and the others with two different kind of light blue), Y can achieve better chances then suggested by the area ratios.

The question whether any player can increase on his area ratio prdiceted chance and regardless whether or not, what is the best strategy, a continuous or a distinct mixed one.

Hippo suggests that Y can get to or close to 1/2. This would be a great result for him, because in any of the scenarios, the red area is less than the green. (As soon as the red is more than the green Y wins surely and not part of the current discussion).

In the upper case Y can choose the white lines with equal probability. X should not choose anything in between the blue lines, because then he surely looses. Choosing outside the blue lines, he is about 50-50%. Actually if he chooses not the max or min (i.e. a continuous mixed strategy) then Y can even increase his chances, so probably the best for X is to choose 0 or all. At the first glance it suggests that then Y reaches 50-50% because of symmetry reasons. But it is NOT the case.
X=all, Y=left white line, X wins
X=all, Y=right white line, it is a draw, but Y has sausage and X not, so Y wins.
X=0, Y=right white line, X wins.
So, for X=0, Y=left white line Y should win 100% to bring it to 50-50% overall. Symmetry would suggest that as well. But this is not the case. It is true that Y wins the second round (1:1) but they have equal amount of sausages left so they have equal chance to win overall. This also means that if Y uses his 50-50% strategy from between the two white lines, then X should have a fixed strategy of 0, winning 75% of the time what is more than his area (max 67.5%). The equilibrum is at Y choosing the left white 2/3 (right white line 1/3) and X choosing 0 2/3 (choosing all 1/3), where X wins 2/3. We approached it from the Y's prospective to maximise his chances. But because in the upper drawing the red area is more than 1/3 this does not seem the best strategy for Y, there must be a better one.
I am convinced that if we started from the X's prospective then we would get to a result of him winning 1/2, what is again not good for him, because the green area is at least 1/2.

In the lower case again, Y should prefer in between the white lines (the vertical lines are longer in the red area then outside the white lines). But X knowing it would not choose in between the blue lines. But Y knowing that X chooses outside the blue lines, cannot leave out totally the options outside the white lines. Etc. This is how I came to the triangle solution.

So, to me, still the only conclusion is, that although I do not know the best stategy, the result of it must be the area of red and green. My inner voice still says that if any of the players would try a strategy to get more than what he deserves then the opponent has a counter strategy that beats him.

All said, I still think that my guess for after the first round is correct. If so, it worth looking for the first round.

After all this my inner voice again says that for the first round there will be a very simple strategy instead of a complex probability curve based mixed strategy. Either take 0 and then it goes on for ever, or cut a random length and from thereon play on.

Title: Re: Sausage duel
Post by Grimbal on Jun 8^th, 2008, 1:03pm

Here is an optimal mixed discrete strategy for X and Y when X needs 1 point and Y needs 2 to win.

If X has more than Y, X wins. If Y has more than twice what Y has, Y wins. What happens in between?

In the first move, if X plays the larger piece, he wins. If not, they both need 1 point, so whoever has the larger piece after that wins. So the game is decided with the first move. The results are summarized below (picture a) as jollytall described. X plays the vertical coordinate and tries to be in the green, Y plays the horizontal coordinate and tries to be in the red.

If 2x > y > 1.5x then Y can play a bit over x or a bit below (y-x), (vertical lines). If Y plays either move with proability 1/2, whatever X plays, he is right at most 1/2 of the time. On the other side, if X plays all or nothing (horizontal lines), each with probability 1/2, Y can be in the red at most 1/2 of the time. This shows that both have a strategy to win with probaility 1/2. So, these strategies are optimal.

When y becomes smaller, it's a bit more complicated. If Y plays like before, X can win by playing 1/2x (picture b). To prevent this, Y must add a third move and play each with probability 1/3. Y now guarantees a win only with probability 1/3. X, by playing all, nothing or 1/2x with proability 1/3 each can guarantee to win with probability 2/3 (picture c).

Continuing like this, the narrower the red band, the more moves Y needs to have to guarantee some probabiliy of winning (picture d). The probability for Y to win is 1/n where n is the number of moves necessary to prevent a sure win for X. In the same way, X can create a set of moves that guarantees a probability (n-1)/n to win.

The number of moves necessary on both sides is given by ceil(x/(y-x)), so Y wins with probability 1/ceil(x/(y-x)) (as given by Hippo).

Title: Re: Sausage duel
Post by jollytall on Jun 9^th, 2008, 12:37am

Thanks Grimbal!

It is pretty clear now. One question remains open on the second step though. What is the strategy at the "jumps"?

I will also try to put together the new 3D (or 2D) chart for the first move.

Title: Re: Sausage duel
Post by Grimbal on Jun 9^th, 2008, 12:54am

At jumps it depends how points are awarded when both pieces have equal weight.

Title: Re: Sausage duel
Post by Hippo on Jun 9^th, 2008, 1:13am

Hi I was outside the net for a while ... actually I am not sure the equilibrium strategy has continous distribution. At least the assumption the distribution has continous derivation leads to a contradiction.

... denote g(y) the mentioned sum minus 1/2.
g(y)>=f(y) was the previous result.
Let a[x,y]=(1-a)x+ay is a metafont notation ... (non)convex combination of points x,y.

g(y)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_N=1^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} 1/(N(N+1))(f(-1/N[y,1])+f(1/(N+1)[y,1]))-1/2.

Let i(v)=inf(x|f(x)>=v) and let s(v)=sup(x|f(x)<=v).
s(v)>i(v) leads to a contradiction: as f(x) changes values in neighbourhood of both i(v) and s(v) (0<v<1), g(i(v))=f(i(v))=v=f(s(v))=g(s(v)) but f() is nondecreasing and for some N in computation of g(i(v)) are used values v while in computation of g(s(v)) values greater (and vice versa). ... Therefore we get the contradicting g(s(v))>g(i(v)).

This leads to f beenig strictly increasing until i(1) is reached. Therefore g(y)=f(y) for y< i(1). And we can compute f'(y)=g'(y)=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_N=1^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif} 1/(N(N+1))((N+1)/Nf'(-1/N[y,1])+N/(N+1)f'(1/(N+1)[y,1]))=f'(-1[y,1])+
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_N=2^{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif}1/N²(f'(-1/N[y,1])+f'(1/N[y,1])) ... this leads to nonzero f'(i(1)) ... contradiction.

Title: Re: Sausage duel
Post by jollytall on Jun 9^th, 2008, 2:56am

on 06/09/08 at 00:54:50, Grimbal wrote:

At jumps it depends how points are awarded when both pieces have equal weight.

Yes, it does. Two ways: No point to any of them or half a point.

Title: Re: Sausage duel
Post by towr on Jun 9^th, 2008, 3:16am

on 06/09/08 at 02:56:36, jollytall wrote:

Yes, it does. Two ways: No point to any of them or half a point.

Or a third way: a point to the one that's behind (each half if they're already tied). Or the converse, a point to the one that's leading (but that makes it even harder to win if you're behind)

Title: Re: Sausage duel
Post by jollytall on Jun 9^th, 2008, 3:55am

And here is the promosed probability chart for the first cut.

Title: Re: Sausage duel
Post by Eigenray on Jun 9^th, 2008, 7:04am

Ow, the artifacting hurts my eyes. Use a gif, man. :P

Title: Re: Sausage duel
Post by Hippo on Jun 9^th, 2008, 7:09am

on 06/09/08 at 07:04:32, Eigenray wrote:

Ow, the artifacting hurts my eyes. Use a gif, man. :P

Welcome in the thread ... comments are welcomed ;)

Title: Re: Sausage duel
Post by jollytall on Jun 9^th, 2008, 8:22am

on 06/09/08 at 07:04:32, Eigenray wrote:

Ow, the artifacting hurts my eyes. Use a gif, man. :P

Sorry, fixed.