Online Prediction with Selfish Experts

Tim Roughgarden, Okke Schrijvers

Introduction

Standard online learning algorithms operate under a critical, yet often overlooked, assumption: the "experts" providing data to the model are entirely honest. However, in real-world scenarios involving pollsters, financial analysts, or weather forecasters, experts are strategic agents who care deeply about their own reputation and credibility. This paper explores the intersection of machine learning and game theory, proving that expert selfishness makes online prediction strictly harder. While we can design "incentive compatible" algorithms, the holy grail of "vanishing regret" is mathematically impossible when experts have agency.

The Problem: Agency in Expert Advice

In the classical "prediction with expert advice" framework, an algorithm aggregates predictions from multiple sources to make a decision. After the true outcome is revealed, the algorithm updates the "weights" (or perceived credibility) of each expert based on their accuracy.

The authors highlight a major flaw in applying this to human experts: agency. If a pollster knows that an aggregator will reward them more for being "bold" and correct rather than being honest and uncertain, they will strategically misreport their beliefs. For instance, weather forecasters often exhibit a "wet bias," overestimating the probability of rain because consumers are far more upset by an unexpected downpour than an unnecessary umbrella.

This raises a fundamental question: Can we design algorithms that incentivize experts to be truthful? And if so, how much predictive performance is sacrificed compared to a utopian world where everyone is honest?

Methodology: Mechanism Design Meets Online Learning

To address this, the authors bridge the gap between Online Learning and Mechanism Design. They modify standard aggregation algorithms, such as Weighted Majority (WM) and Randomized Weighted Majority (RWM), by fundamentally changing how expert weights are updated.

  • Incentive Compatibility (IC): An algorithm is defined as IC if an expert’s optimal strategy to maximize their future weight is to report their true, unvarnished belief.
  • Proper Scoring Rules: The key technical mechanism used to enforce IC is the "Proper Scoring Rule" (e.g., the Brier score or Spherical score). By utilizing these rules to calculate weight updates instead of standard absolute loss, the algorithm mathematically ensures that honesty is the best policy.
  • Evaluation via Simulation: As a primarily theoretical paper, the authors evaluate their algorithms using synthetic simulations rather than real-world datasets. They employ a two-state Hidden Markov Model (HMM) to simulate "good" and "bad" experts receiving signals about a binary event, tracking performance as experts act strategically.

Key Insights and Theoretical Results

The paper's theoretical contributions formally separate the power of online prediction with selfish experts from that of honest experts.

  • Absolute Loss Incentivizes Extremism: The authors demonstrate that the commonly used "absolute loss" function is disastrous for incentives. It encourages experts to report absolute certainty (0 or 1) even when their true belief is uncertain (e.g., 0.6), effectively gambling for a higher weight increase.
  • The "Free Lunch" of Collusion: A surprising finding is that if an algorithm is incentive compatible for a single expert, it is inherently "Group Incentive Compatible." This means experts cannot gain an advantage by forming a cartel to jointly misreport their beliefs.
  • The Cost of Selfishness (Impossibility Theorem): In a standard model with honest experts, randomized algorithms can achieve "vanishing regret"—meaning they eventually perform exactly as well as the best expert. The authors prove this is impossible with selfish experts under the absolute loss function. Regret will always remain bounded away from zero.
  • Performance Bounds:
    • Deterministic: The authors designed an IC algorithm using a Spherical weight-update rule that achieves a regret bound of $2 + \sqrt{2} \approx 3.41$ (compared to the best possible bound of 2 with honest experts).
  • Randomized: They developed a randomized IC algorithm using the Brier score that achieves a 2.62 regret bound.
  • Lower Bound: They prove that no "natural" algorithm (IC or otherwise) can achieve a regret better than 2 when experts are selfish.

Limitations and Future Directions

While foundational, the paper's model is currently restricted to binary events (0 or 1). Real-world predictions frequently involve multi-class or continuous variables, which require expanded theoretical frameworks. Furthermore, the paper assumes experts only care about their absolute weight in the algorithm. In reality, experts often care about their relative weight compared to peers, which would significantly alter the game-theoretic dynamics. Finally, there remains a numerical gap between the proven lower bound (2) and the best-designed IC algorithm (2.62), leaving the discovery of the strictly "optimal" IC algorithm as an open challenge for future research.

Summary updated

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. 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.
BibTeX
@inproceedings{roughgarden2017online,
  author = {Tim Roughgarden and Okke Schrijvers},
  title = {{Online Prediction with Selfish Experts}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=r1Zw3v-uZH},
}
Figure