A tournament graph is a complete directed graph, which can be used to model a round-robin tournament between $n$ players. In this paper, we address the problem of finding a champion of the tournament, also known as Copeland winner, which is a player that wins the highest number of matches. In detail, we aim to investigate algorithms that find the champion by playing a low number of matches. Solving this problem allows us to speed up several Information Retrieval and Recommender System applications, including question answering, conversational search, etc. Indeed, these applications often search for the champion inducing a round-robin tournament among the players by employing a machine learning model to estimate who wins each pairwise comparison. Our contribution, thus, allows finding the champion by performing a low number of model inferences. We prove that any deterministic or randomized algorithm finding a champion with constant success probability requires $\Omega(\ell n)$ comparisons, where $\ell$ is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing $\ell$, and we extend our analysis to three variants of the problem. Lastly, we conduct a comprehensive experimental assessment of the proposed algorithms on a question answering task on public data. Results show that our proposed algorithms speed up the retrieval of the champion up to $13\times$ with respect to the state-of-the-art algorithm that perform the full tournament.

翻译：锦标图是一个完整的定向图表, 可用于模拟美元球员之间的圆柱形锦标赛。 在本文中, 我们处理寻找锦标赛冠军( 也称为Copeland赢家)的问题。 我们的目标是调查通过低匹配数找到冠军的算法。 解决这个问题可以让我们加快几个信息检索和建议系统应用程序, 包括问答、 谈话搜索等。 事实上, 这些应用程序通常会通过使用机器学习模型来寻找冠军在球赛中引发圆柱形锦标赛, 以估算谁赢得了对比。 因此, 我们的贡献, 通过执行低数的模型推断可以找到冠军。 我们证明, 任何确定性或随机的算法, 找到冠军, 总是有一定的成功概率。 解决这个问题, $\\ n) 将美元作为冠军的匹配数, 包括问答、 谈话搜索等。 我们随后会展示一个完全的、 最优化的确定性平分数的计算方法, 来匹配每个赛员的比赛速度。 我们的贡献, 能够通过一个较低的模型来找到冠军的冠军, 执行这个较低的标尺形的标, 。