[SatvikBeri]

In addition to other answers, one way to think about it is that the options are symmetric around the midpoint: a guess that partitions the space into (1/4 of options, 3/4 of options) is the same as one that does (3/4, 1/4). So (1/2, 1/2) is special in some way – it has to be either a local minimum or local maximum. And if the function is convex (or close enough), then (1/2, 1/2) is a global minimum/maximum.

But (1/2, 1/2) is clearly a better choice than just guessing a specific individual. So it must be the best choice.

[gregdeon]

This is all right, but it just kicks the intuition into the assumption that the function is convex. As far as I can tell from the paper, this turns out to be exactly the argument they use to prove that (1/2, 1/2) is the optimal guess. But the majority of that proof is dedicated to showing that the function is indeed convex.