Two persons have 2 uniform sticks with equal length which can be cut at any point. Each person will cut the stick into $n$ parts ($n$ is an odd number). And each person's $n$ parts will be permuted randomly, and be compared with the other person's sticks one by one. When one's stick is longer than the other person's, he will get one point. The person with more points will win the game. How to maximize the probability of winning the game for one of the person. What is the best strategy to cut the stick.
Strategy for a game of breaking sticks
-
0Maximizing the probability of winning the game isn't well-defined unless you specify a distribution for the opponent's strategies. The usual question for such a game would be to find the [Nash equilibria](http://en.wikipedia.org/wiki/Nash_equilibrium) (if any). Perhaps that's what you meant? – 2012-08-09
-
0@joriki Each person will try his optimail strategy. – 2012-08-09
-
0@Fan: As I said, that's not well-defined. The optimal strategy depends on the opponent's strategy. Do you know about Nash equilibria? If not, I'd suggest to read about them and then consider updating the question. – 2012-08-09
-
1@joriki Thank you for your advice. I will read about Nash equilibria. – 2012-08-09
-
0By the way, please choose a more descriptive title. Mentioning the overall field, such as game theory, in the title isn't useful because that's what the tags are for and the tags are visible wherever the title is (e.g. on the main page), so this is redundant information. The title should be more specific to the question, e.g. "strategy for a game of breaking sticks". (Also, almost all questions are about problems, so "problem" is even more redundant.) – 2012-08-09
-
1@joriki Thank you, updated. – 2012-08-09
-
0This seems more difficult than I would have expected. Choosing the breakpoints randomly with independent uniform distributions is not a Nash equilibrium. – 2012-08-09
-
0This is sort of a [Colonel Blotto game](http://en.wikipedia.org/wiki/Colonel_Blotto), but in the standard version of that, the payoff is the number of comparisons won, whereas you have a $0$/$1$ payoff depending on who wins more comparisons. – 2012-08-09
-
0@joriki Thank you for the information. – 2012-08-09
-
0Actually, for $n=3$, there's no difference, since the difference in the number of comparisons won is always $\pm1$, so you may want to look into the standard Colonel Blotto game (apparently the Wikipedia article links to a full solution) -- the $n=3$ solution will be the same and perhaps it can give you some ideas for the solution for $n\gt3$. – 2012-08-09
-
0Simulation helps. – 2012-11-03
-
0There's another equivalent question here with sausages rather than sticks. I'm not sure how to link to it... – 2012-12-06
2 Answers
When intuition doesn't help, try brute force.
trials = Table[With[{k = RandomReal[{0, 1}, {7}]}, k/Total[k]], {50}]; Column[Sort[Transpose[{Total /@ Table[Total[Sign[trials[[a]] - trials[[b]]]], {a, 1, 50}, {b, 1, 50}], trials}]]]
Now we can look at some best/worst performers.
{-55, {0.018611, 0.0405574, 0.032157, 0.333219, 0.311017, 0.17885, 0.0855879}},
{-39, {0.313092, 0.178326, 0.0454452, 0.064321, 0.228231, 0.0907115,0.0798742}},
{29, {0.0360088, 0.220396, 0.13208, 0.145903, 0.180813, 0.240151, 0.044648}},
{29, {0.0799122, 0.0547817, 0.234127, 0.119589, 0.0290167, 0.255561,0.227013}},
{33, {0.0541814, 0.216338, 0.0619272, 0.204252, 0.0254828, 0.225743,0.212075}}
So, in the case of 7 pieces, best strategy seems to be to give 3 tiny pieces and 4 larger pieces. With some bigger trials, 2 tiny pieces and 5 larger pieces seemed best. But this is a competitive game ... so I selected the top 10% of a larger trial, and then had those guys compete. This time the winner was to have 3 values of 2/7 and one value of 1/7 {0.0263105, 0.0848388, 0.228165, 0.249932, 0.0788568, 0.215831, 0.116066}
Your iterations may behave differently.
Here's a (partial) answer to the setting where the number of sticks is 3 (i.e. $n = 3$). With some effort, one can show the following claims:
Given the strategy $(a,a,b)$ where $a \ge b$ (i.e. you break your stick into two equal parts of size $a$ and one smaller part of size $b = 1-2a$), the optimal value for $a$ is $\frac13$. That is, breaking your stick into three equal parts maximizes the number of strategies you beat.
Another similar claim: given the strategy $(a,b,0)$ (i.e. break your stick into three parts - one of length $a$, one of length $b = 1-a\le a$ and one of length 0), the optimal value of $a$ is $a = \frac12$.
Generally speaking, this is proven by drawing the space of strategies as an equilateral triangle in barycentric coordinates, dividing that triangle into spaces of strategies (triangles, trapezoids and such), and seeing what's the likelihood of your given strategy beating another strategy in that space.
For example, the strategy $(\frac13,\frac13,\frac13)$ beats any strategy that has two sticks of length $<\frac13$, and loses to all other strategies (there are some strategies with one stick of length $\frac13$, but these have measure 0 so are ignored) at all times. Two thirds of the strategies have two sticks of length $< \frac13$, so it beats strategies $2/3$ of the time.
Alternatively, for $(\frac12,\frac12,0)$, It surely beats any strategy that has two sticks of length $<\frac12$, and beats any strategy with one stick of length $>\frac12$ and two with length $< \frac12$ w.p. $\frac13$. So in total its expected winning probability is $\frac14\cdot 1 + 3\cdot\frac14\cdot \frac13 = \frac12$. (take an equilateral triangle and divide into 4 equal equilateral triangles.
I'll be happy to write a formal proof of this, but now I'm a bit busy :)
My thought is that in general it would be hard to prove anything about this setting for $n \ge 5$, but I may be wrong...