ROB selects A and B. First suppose A < B. Suppose A is revealed. Further Suppose that some deterministic Algorithm R exists which takes in A, and produces the probability that A is smaller.
In round one the only input to the algorithm can be A alone. Furthermore since we have supposed that R is “better than 50%”, we must see have R yield us that P( A smaller ) > 0.5. We can then easily extrapolate P( A bigger ) < 0.5.
Now suppose we have the opposite case, that A > B. Again the only input to our algorithm can be A for the first round. However we must receive as output: P( A smaller ) < 0.5 and thus P( A bigger ) > 0 5
But consider that in both cases our only input was A, then it follows that R must not be deterministic since it produces two different results on the same input. This is a contradiction, hence there is no such deterministic algorithm R.
It is possible that there is a nondeterministic algorithm R’, however I’m almost certain that no such algorithm can outperform a deterministic one in a case like this.
Other posters have suggested using a function which increases montonically over the reals. My instinct is that for any such function, for any choice of epsilon, there is some delta such that n+delta does not provided a benefit of epsilon.
In my example i spoke of selecting n and n+1 as A and B. Instead let B be n+delta.
Recall that any monotnic increasing bounded function over the reals is continuous. Suppose we want to achieve a success rate with our guesses of 0.5+epsilon. ROB can select delta such that our performance is less than that. Then it follows that our success rate s will satisfy
0.5 < s < 0.5 + epsilon
Since we can produce a delta for any epsilon (because the montonic function is continuous), it follows that we can define a sequence of success rates which have the infinum 0.5
Essentially ROB can select two real nunbers sufficiently close together that no strategum produces a benefit of any substance. He can enact a strategy which pushes us arbitraily close to a 50⁄50 shot.
You made a comment regarding restricting the problem to integers. A solution may exist in that case, I’m not sure.
P.S. Thanks for making this post, it’s been an interesting problem to think about.
I think you’re right that there is no epsilon such that you can guarantee 50% + epsilon performance. You can however guarantee that your performance is greater than 50%. (Since ROB isn’t allowed to use the full limit strategy of giving two identical reals, there will always be some nonzero delta.)
Monotonicity is insufficient. Your function does need to be strictly increasing. Otherwise ROB can always pick numbers in a non-increasing interval.
I do not believe that “any monotonically increasing bounded function over the reals is continuous”. For instance, choose some montonically increasing function bounded to (0,0.4) for x<-1, another function bounded to (0.45,0.55) for −1<x<1, and a third function bounded to (0.6,1) for x>1.
You’re right. I Misremembered, but i checked and it is true that a bounded montonic function of the reals can have only a countable number of discontinuities. So if ROB knows our algorithm, he can select one continuous interval for all of his values to come from.
Proof of the countable nature of discontinutes given here:
ROB selects A and B. First suppose A < B. Suppose A is revealed. Further Suppose that some deterministic Algorithm R exists which takes in A, and produces the probability that A is smaller.
In round one the only input to the algorithm can be A alone. Furthermore since we have supposed that R is “better than 50%”, we must see have R yield us that P( A smaller ) > 0.5. We can then easily extrapolate P( A bigger ) < 0.5.
Now suppose we have the opposite case, that A > B. Again the only input to our algorithm can be A for the first round. However we must receive as output: P( A smaller ) < 0.5 and thus P( A bigger ) > 0 5
But consider that in both cases our only input was A, then it follows that R must not be deterministic since it produces two different results on the same input. This is a contradiction, hence there is no such deterministic algorithm R.
It is possible that there is a nondeterministic algorithm R’, however I’m almost certain that no such algorithm can outperform a deterministic one in a case like this.
Could you explain why you are almost certain?
Other posters have suggested using a function which increases montonically over the reals. My instinct is that for any such function, for any choice of epsilon, there is some delta such that n+delta does not provided a benefit of epsilon.
In my example i spoke of selecting n and n+1 as A and B. Instead let B be n+delta.
Recall that any monotnic increasing bounded function over the reals is continuous. Suppose we want to achieve a success rate with our guesses of 0.5+epsilon. ROB can select delta such that our performance is less than that. Then it follows that our success rate s will satisfy
0.5 < s < 0.5 + epsilon
Since we can produce a delta for any epsilon (because the montonic function is continuous), it follows that we can define a sequence of success rates which have the infinum 0.5
Essentially ROB can select two real nunbers sufficiently close together that no strategum produces a benefit of any substance. He can enact a strategy which pushes us arbitraily close to a 50⁄50 shot.
You made a comment regarding restricting the problem to integers. A solution may exist in that case, I’m not sure.
P.S. Thanks for making this post, it’s been an interesting problem to think about.
I think you’re right that there is no epsilon such that you can guarantee 50% + epsilon performance. You can however guarantee that your performance is greater than 50%. (Since ROB isn’t allowed to use the full limit strategy of giving two identical reals, there will always be some nonzero delta.)
Monotonicity is insufficient. Your function does need to be strictly increasing. Otherwise ROB can always pick numbers in a non-increasing interval.
Thanks!
I do not believe that “any monotonically increasing bounded function over the reals is continuous”. For instance, choose some montonically increasing function bounded to (0,0.4) for x<-1, another function bounded to (0.45,0.55) for −1<x<1, and a third function bounded to (0.6,1) for x>1.
I did not check the rest of the argument, sorry
You’re right. I Misremembered, but i checked and it is true that a bounded montonic function of the reals can have only a countable number of discontinuities. So if ROB knows our algorithm, he can select one continuous interval for all of his values to come from.
Proof of the countable nature of discontinutes given here:
https://math.stackexchange.com/questions/2793202/set-of-discontinuity-of-monotone-function-is-countable