2021/02/16 by Frongillo, Rafael, Gomez, Robert, Thilagar, Anish +1 · 2 citations
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2102.08358
Winner-take-all competitions in forecasting and machine-learning suffer from distorted incentives. Witkowski et al. 2018 identified this problem and proposed ELF, a truthful mechanism to select a winner. We show that, from a pool of n forecasters, ELF requires Θ(nlog 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 ε-optimal forecaster using only O(log(n) / ε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.