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.

本文研究在仅查询尽可能少的边的情况下找到锦标赛的最佳顶点集合的问题，并给出了 Condorcet 非输家集合的计算方法，并证明了任何找到 Copeland 集合，Slater 集合，Markov 集合，双方集合，未覆盖集合，Banks 集合和顶点集合的算法在最坏情况下必须查询 Ω(n²) 条边，但如果输入的锦标赛的顶部循环的大小不超过 k，则可以只查询 O (nk + n log (n)/(log (1-1/k))) 条边即可找到所有锦标赛解。