Abstract
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. Designing a good IC algorithm is easy if the designer's loss function is quadratic, but for other loss functions, novel techniques are required. 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 experts and online prediction with 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.
Introduction
In the classic "prediction with expert advice" framework, an aggregator combines forecasts from multiple sources to predict a sequence of binary events. Traditionally, this framework assumes experts are passive data sources. However, in real-world scenarios—such as political polling, financial forecasting, or weather reporting—experts are agents with their own incentives. They often seek to maximize their reputation or "weight" within the prediction system.
When experts are strategic, standard algorithms like Weighted Majority (WM) can fail. If an expert knows that reporting their true belief might lead to a lower weight than a strategic lie, they will "game" the system. This paper investigates whether we can design algorithms that are incentive compatible (IC)—where experts are best served by telling the truth—and quantifies the performance cost imposed by such strategic behavior.
The Selfish Expert Model
The authors introduce a formal model where each expert $i$ has a private belief $p_i \in [0, 1]$ about the probability of an event. Instead of reporting $p_i$, the expert reports $q_i$. The algorithm then updates the expert's weight based on the outcome. The expert's utility is defined as their expected weight in the subsequent round. An algorithm is IC if, for every expert, the expected weight is maximized when $q_i = p_i$.
The Connection to Scoring Rules
A pivotal contribution of this work is the link between online learning and mechanism design. The authors prove that a weight-update rule is incentive compatible if and only if it is a strictly proper scoring rule. This allows the adaptation of classical tools from forecasting—such as the Brier score and the Spherical scoring rule—into weight-update mechanisms for online learning.
Algorithms for Absolute Loss
While designing IC algorithms for quadratic loss is straightforward, the absolute loss function presents significant challenges. Standard non-IC algorithms for absolute loss incentivize experts to report extreme values (0 or 1) even when they are uncertain. This strategic "extremism" can cause the aggregator's performance to be up to four times worse than the best expert.
To address this, the authors propose new IC algorithms:
- Spherical-Rule Algorithm: A deterministic update rule based on the Spherical scoring rule. It achieves a loss ratio of at most $2 + \sqrt{2} \approx 3.41$ compared to the best expert.
- Modified Brier Score Algorithm: A randomized approach that achieves a improved loss ratio of 2.62.
The "Selfishness Tax"
The paper establishes a formal separation between the capabilities of algorithms dealing with honest versus selfish experts. In the honest setting, it is well-known that randomized algorithms can achieve "no-regret" performance, where the average loss approaches the best expert's loss over time (a ratio of 1).
The authors prove that with selfish experts and absolute loss, no algorithm (IC or otherwise) can achieve vanishing regret. Selfishness introduces a fundamental "tax" on accuracy. Even the best possible algorithm will maintain a constant gap between its performance and that of the best expert, regardless of how much data is processed.
Empirical Validation
Though primarily theoretical, the paper validates its findings using synthetic simulations. By employing a Hidden Markov Model (HMM) to simulate experts with fluctuating accuracy, the authors compared IC algorithms against standard non-IC benchmarks. The results demonstrated that IC algorithms significantly outperformed standard rules in strategic environments, converging much closer to the best expert's performance while the standard algorithm's regret remained high due to expert manipulation.
Conclusion and Future Work
This research highlights a critical vulnerability in traditional online learning: the assumption of expert honesty. By bridging the gap with proper scoring rules, the authors provide a framework for robust aggregation in the presence of strategic agents.
Future research directions include extending these models beyond binary outcomes to multi-class or continuous predictions. Additionally, there remains a theoretical gap between the current upper bounds of the proposed IC algorithms and the proven lower bounds of the environment. Finally, exploring more complex utility functions—where experts might care about their relative rank or the final aggregate prediction—could provide deeper insights into real-world strategic forecasting.
Summary updated