  We consider the problem of inferring an unknown ranking of $n$ items from a
random tournament on $n$ vertices whose edge directions are correlated with the
ranking. We establish, in terms of the strength of these correlations, the
computational and statistical thresholds for detection (deciding whether an
observed tournament is purely random or drawn correlated with a hidden ranking)
and recovery (estimating the hidden ranking with small error in Spearman's
footrule or Kendall's tau metric on permutations). Notably, we find that this
problem provides a new instance of a detection-recovery gap: solving the
detection problem requires much weaker correlations than solving the recovery
problem. In establishing these thresholds, we also identify simple algorithms
for detection (thresholding a degree 2 polynomial) and recovery (outputting a
ranking by the number of "wins" of a tournament vertex, i.e., the out-degree)
that achieve optimal performance up to constants in the correlation strength.
For detection, we find that the above low-degree polynomial algorithm is
superior to a natural spectral algorithm. We also find that, whenever it is
possible to achieve strong recovery (i.e., to estimate with vanishing error in
the above metrics) of the hidden ranking, then the above "Ranking By Wins"
algorithm not only does so, but also outputs a close approximation of the
maximum likelihood estimator, a task that is NP-hard in the worst case.
