An Optimal Algorithm for Finding Champions in Tournament Graphs

A tournament graph is a complete directed graph, which can be used to model a round-robin tournament between <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\Omega (\ell n)$</tex-math></inline-formula> comparisons, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell$</tex-math></inline-formula> is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell$</tex-math></inline-formula> , 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$13\times$</tex-math></inline-formula> with respect to the state-of-the-art algorithm that perform the full tournament. The identification of the most relevant result from a set of candidates is a crucial task in many Information Retrieval and Recommender System applications including ad-hoc search, conversational search, machine translation, question answering, etc. State-of-the-art solutions solving the task leverage ad-hoc machine learning techniques—developed in a field known as Learning-to-Rank—to estimate the relevance of the set of candidate results and to select the most relevant one. These solutions address the problem in two different ways. From one side, several techniques work by estimating one candidate at a time so to select the candidate achieving the highest score. On the other side, some techniques compare a pair of candidate results at a time so to select the candidate achieving the highest sum of pairwise scores of an all-vs-all tournament between results. In this paper, we focus on the second class of techniques. In detail, we propose to model the task of identifying the most relevant result from a set of candidates as the problem of finding the champion of a tournament, which is the player that wins the highest number of matches in the tournament. Our goal is to find the champion, also known as the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Copeland winner</i> , of the tournament by minimizing the number of matches played in the tournament, i.e., the number of pairwise comparisons. We prove that any deterministic or randomized algorithm finding a champion with constant success probability requires <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\Omega (\ell n)$</tex-math></inline-formula> comparisons, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell$</tex-math></inline-formula> is the number of matches lost by the champion. We then present an asymptotically-optimal deterministic algorithm matching this lower bound without knowing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell$</tex-math></inline-formula> . Moreover, we extend the result by providing a parallel version of our algorithm, as well as a version that retrieve all the best <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> players of the tournament. Lastly, we conduct a comprehensive experimental assessment of the proposed algorithms on a public dataset (MS-MARCO) with the aim of speeding up a well-known state-of-the-art solution for ranking textual passages for question answering. Results show that our proposed solutions allow to speed up the identification of the champion up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$13\times$</tex-math></inline-formula> .