Online Prediction with Selfish Experts
We consider the problem of binary prediction with expert advice in settings where experts have agency and seek to maximize their credibility. This paper makes three main contributions. First, it defines a model to reason formally about settings with selfish experts, and demonstrates that "incentive compatible" (IC) algorithms are closely related to the design of proper scoring rules. Second, we design IC algorithms with good performance guarantees for the absolute loss function. Third, we give a formal separation between the power of online prediction with selfish versus honest experts by proving lower bounds for both IC and non-IC algorithms. In particular, with selfish experts and the absolute loss function, there is no (randomized) algorithm for online prediction-IC or otherwise-with asymptotically vanishing regret.
In this paper, the standard (binary outcome) "prediction with expert advice" setting is altered by treating the experts themselves as players in the game.  Specifically, restricting to the class of weight-update algorithms, the experts seek to maximize the weight assigned to them by the algorithm, as a notion of "rating" for their predictions.  It is shown that learning algorithms are IC, meaning that experts reveal their true beliefs to the algorithm, if and only if the weight-update function is a strictly proper scoring rule.  Because the weighted-majority algorithm (WM) has a weight update which is basically the negative of the loss function, WN is thus IC if and only if the (negative) loss is strictly proper.  As the (negative) absolute loss function is not strictly proper, WM is not IC for absolute loss.  The remainder of the paper investigates the absolute loss case in detail, showing that WM with the spherical scoring rule performs well, and moreover performs better than WM with absolute loss; no other deterministic IC (or even non-IC) algorithm for absolute loss can beat the performance in the non-strategic case; analogous results for the randomized case.
I like the results, but find the motivation to be on loose footing.  First, it is somewhat odd that experts would want to maximize the algorithm's weight assigned to them, as after all the algorithm's weights may not correspond to "performance" (a modified WM which publishes bogus weights intermittently can still achieve no regret), and even worse, the algorithm need not operate by calculating weights at all.  I did find the 538 example compelling however.
My biggest concern is the motivation behind scoring the algorithm or the experts with non-proper scoring rules.  A major thrust of elicitation (see Making and Evaluating Point Forecasts, Gneiting 2011) is that one should always measure performance in an incentive-compatible way, which would rule out absolute loss.  The authors do provide an example in 538's pollster ratings, but herein lies a subtlety: 538 is using absolute loss to score *poll* outcomes, based on the true election tallies.  Poll results are not probabilistic forecasts, and in fact, that is a major criticism of polls from e.g. the prediction market community.  Indeed, the "outcome" for 538's scoring is itself a real number between 0 and 1, and not just the binary 0,1 of e.g. whether the candidate won or lost.
I would be much more positive about the paper if the authors could find a natural setting where non-proper losses would be used.
Minor comment:  Using "r" as the outcome may be confusing as it often denotes a report.  It seems that "y" is more common, in both the scoring rules and prediction with expert advice literature.