8
$\begingroup$

Inspired by a question about bisection I wondered about the following: The are two players X and Y and a moderator Z who knows two (random,independent, uniformly chosen) hidden reals $x$ and $y$ from (0,1). The game has $t$ turns. At the beginning of each turn player X knows an open interval containing $x$, she names an internal point and learns which sub-interval contains $x$. Simultaneously, Y does the same for $y$. The player with the shorter interval wins one dollar from the other player (in case of a tie, no one wins).

What is the optimal strategy?

For $t=1$ turn it is obviously to choose the midpoint $0.5$. But for $t=2$ the following strategy beats a player who has decided on bisection: on turn 1 choose $0.45$ and on turn 2 choose either $0.225$ or $0.675$.

Then the probabilities of winning are $0.45,0.225$ and $0.325 $ for $+1,0$ and $-1$ respectively.

Also: Consider the variation where X wins only if her interval is $90 \%$ or less that of player $Y$.

What are the (respective) optimal strategies in this case?

It is still not optimal for $Y$ to use bisection. The exact same strategy as above has the exact same payoff odds for X.

Improve this question
$\endgroup$
2
  • $\begingroup$ There is certainly not a pure strategy equilibrium, owing to the discrete jumps in payoffs for small changes in interval size. Do X and Y know the length of the other one's interval? If not, then you could just have both players choose a partition into 2^k. If so, then one would want to define an optimal strategy dependent on the time left and the ratio between the partitions. Doing so would handily answer your second question. However, it sounds quite difficult. $\endgroup$
    – Will Sawin
    Oct 8, 2011 at 6:11
  • $\begingroup$ I suppose one could discretize and say that the selected x and y are irrational but the guesses must be $\frac{n}{2^{100}}$ or something like that. $\endgroup$
    – Aaron Meyerowitz
    Oct 8, 2011 at 7:39

2 Answers 2

Reset to default
2
$\begingroup$

This is not a complete answer, but I lack the reputation to post as a comment.

The strategy must account for the winning/losing streak because the advantage of a smaller interval compounds. If both players choose 0.5 for the first turn, by the rules neither one wins. This highlights an ambiguity in the rules as stated. In the case of a tie, do the players know that they tied?

Suppose after some number of moves, player X has a losing streak of N moves and first lost with an interval of length I. Then player X knows that player Y will have an interval no larger than $I^{-2(N-1)}$ if player Y is following a bisection strategy. Player X must make a guess with an interval smaller than this number to have any chance of winning, unless player Y is following some other strategy.

Suppose instead that player X has a winning streak of N moves and first won with an interval of length I. Then player X knows that player Y must be guessing smaller and smaller intervals with each loss. As a result, player X can attempt to safeguard the streak by choosing non-bisecting moves. This requires also knowing how much time is left (as Will Sawin says) because the more turns left the more important it is not to start losing.

Fascinating question. Have you tried any Monte Carlo simulations on it?

Improve this answer
$\endgroup$
2
  • $\begingroup$ I assume that at the start of each turn one knows the length of both intervals. $\endgroup$
    – Aaron Meyerowitz
    Oct 9, 2011 at 5:19
  • $\begingroup$ That makes it a much different problem than I was considering. I'll give it some more thought. $\endgroup$
    – Chad Musick
    Oct 9, 2011 at 5:24
0
$\begingroup$

Possibly nothing simple, even when there is only one turn left. Suppose that there is just one turn left, the intervals are of length 4 and 6 (just to scale up) and the moves must create intervals of length $\frac{j}{4}.$ Then by my calculations, the player with the shorter interval should guess $$\frac54, \frac64 \text{ or }\frac74 \text{ with probabilities } \frac{4462\ }{6005\ }, \frac{53}{6005}, \frac{1490}{6005}$$ while the other player should choose $$\frac54, \frac74 \text{ or } \frac84 \text{ with probabilities } \frac{392}{1201} ,\frac{200}{1201}, \frac{609}{1201}.$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.