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))) 条边即可找到所有锦标赛解。

竞赛方案的查询复杂度

Query Complexity of Tournament Solutions

In this paper we study noisy sorting without re-sampling. In this problem
there is an unknown order $a_{\pi(1)} < ... < a_{\pi(n)}$ where $\pi$ is a
permutation on $n$ elements. The input is the status of $n \choose 2$ queries
of the form $q(a_i,x_j)$, where $q(a_i,a_j) = +$ with probability at least
$1/2+\ga$ if $\pi(i) > \pi(j)$ for all pairs $i \neq j$, where $\ga > 0$ is a
constant and $q(a_i,a_j) = -q(a_j,a_i)$ for all $i$ and $j$. It is assumed that
the errors are independent. Given the status of the queries the goal is to find
the maximum likelihood order. In other words, the goal is find a permutation
$\sigma$ that minimizes the number of pairs $\sigma(i) > \sigma(j)$ where
$q(\sigma(i),\sigma(j)) = -$. The problem so defined is the feedback arc set
problem on distributions of inputs, each of which is a tournament obtained as a
noisy perturbations of a linear order. Note that when $\ga < 1/2$ and $n$ is
large, it is impossible to recover the original order $\pi$.
It is known that the weighted feedback are set problem on tournaments is
NP-hard in general. Here we present an algorithm of running time
$n^{O(\gamma^{-4})}$ and sampling complexity $O_{\gamma}(n \log n)$ that with
high probability solves the noisy sorting without re-sampling problem. We also
show that if $a_{\sigma(1)},a_{\sigma(2)},...,a_{\sigma(n)}$ is an optimal
solution of the problem then it is ``close'' to the original order. More
formally, with high probability it holds that $\sum_i |\sigma(i) - \pi(i)| =
\Theta(n)$ and $\max_i |\sigma(i) - \pi(i)| = \Theta(\log n)$.
Our results are of interest in applications to ranking, such as ranking in
sports, or ranking of search items based on comparisons by experts.

研究了反馈弧集问题的算法，使用 n 个元素上的顺序形成的锦标赛作为输入，并考虑到噪声干扰，以最大似然的方式找到排名。