  Winner-take-all competitions in forecasting and machine-learning suffer from
distorted incentives. Witkowskiet al. identified this problem and proposed ELF,
a truthful mechanism to select a winner. We show that, from a pool of $n$
forecasters, ELF requires $\Theta(n\log n)$ events or test data points to
select a near-optimal forecaster with high probability. We then show that
standard online learning algorithms select an $\epsilon$-optimal forecaster
using only $O(\log(n) / \epsilon^2)$ events, by way of a strong
approximate-truthfulness guarantee. This bound matches the best possible even
in the nonstrategic setting. We then apply these mechanisms to obtain the first
no-regret guarantee for non-myopic strategic experts.
