  A directed graph where there is exactly one edge between every pair of
vertices is called a {\em tournament}. Finding the "best" set of vertices of a
tournament is a well studied problem in social choice theory. A {\em tournament
solution} takes a tournament as input and outputs a subset of vertices of the
input tournament. However, in many applications, for example, choosing the best
set of drugs from a given set of drugs, the edges of the tournament are given
only implicitly and knowing the orientation of an edge is costly. In such
scenarios, we would like to know the best set of vertices (according to some
tournament solution) by "querying" as few edges as possible. We, in this paper,
precisely study this problem for commonly used tournament solutions: given an
oracle access to the edges of a tournament T, find $f(T)$ by querying as few
edges as possible, for a tournament solution f. We first show that the set of
Condorcet non-losers in a tournament can be found by querying $2n-\lfloor \log
n \rfloor -2$ edges only and this is tight in the sense that every algorithm
for finding the set of Condorcet non-losers needs to query at least $2n-\lfloor
\log n \rfloor -2$ edges in the worst case, where $n$ is the number of vertices
in the input tournament. We then move on to study other popular tournament
solutions and show that any algorithm for finding the Copeland set, the Slater
set, the Markov set, the bipartisan set, the uncovered set, the Banks set, and
the top cycle must query $\Omega(n^2)$ edges in the worst case. On the positive
side, we are able to circumvent our strong query complexity lower bound results
by proving that, if the size of the top cycle of the input tournament is at
most $k$, then we can find all the tournament solutions mentioned above by
querying $O(nk + \frac{n\log n}{\log(1-\frac{1}{k})})$ edges only.

Data Structures and Algorithms;Artificial Intelligence;Discrete Mathematics