Finding a Mediocre Player
share
Consider a totally ordered set S of n elements; as an example, a set of tennis players and their rankings. Further assume that their ranking is a total order and thus satisfies transitivity and anti-symmetry.Following Frances Yao (1974), an element (player) is said to be (i,j)-mediocre if it is neither among the top i nor among the bottom j elements of S. More than 40 years ago, Yao suggested a stunningly simple algorithm for finding an (i,j)-mediocre element: Pick i+j+1 elements arbitrarily and select the (i+1)-th largest among them. She also asked: "Is this the best algorithm?" No one seems to have found such an algorithm ever since. We first provide a deterministic algorithm that beats the worst-case comparison bound in Yao's algorithm for a large range of values of i (and corresponding suitable j=j(i)). We then repeat the exercise for randomized algorithms; the average number of comparisons of our algorithm beats the average comparison bound in Yao's algorithm for another large range of values of i (and corresponding suitable j=j(i)); the improvement is most notable in the symmetric case i=j. Moreover, the tight bound obtained in the analysis of Yao's algorithm allows us to give a definite answer for this class of algorithms. In summary, we answer Yao's question as follows: (i) "Presently not" for deterministic algorithms and (ii) "Definitely not" for randomized algorithms. (In fairness, it should be said however that Yao posed the question in the context of deterministic algorithms.)
READ FULL TEXT