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 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.

• Publication year

  2017

• Venue

  Neural Information Processing Systems

• Publication date

  2017-02-13

• Fields of study

  Computer Science, Economics

• Identifiers
  arXiv 1702.03615
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Bayesian Exploration: Incentivizing Exploration in Bayesian Games

  2016cited by this paper
• A Bandit Framework for Strategic Regression

  2016cited by this paper
• Strategic Classification

  2015cited by this paper
• Incentivizing exploration

  2014cited by this paper
• Prediction Markets: A literature review 2014

  2014cited by this paper
• Optimum Statistical Estimation with Strategic Data Sources

  2014cited by this paper
• Double or Nothing: Multiplicative Incentive Mechanisms for Crowdsourcing

  2014cited by this paper
• Efficient Market Making via Convex Optimization, and a Connection to Online Learning

  2013cited by this paper
• Choosing a Strictly Proper Scoring Rule

  2013cited by this paper
• Eliciting forecasts from self-interested experts: scoring rules for decision makers

  2011cited by this paper
• Stackelberg games for adversarial prediction problems

  2011cited by this paper
• Designing Markets for Prediction

  2010cited by this paper
• Truthful mechanisms with implicit payment computation

  2010cited by this paper
• Scoring Rules, Generalized Entropy, and Utility Maximization

  2008cited by this paper
• Verification of The Weather Channel Probability of Precipitation Forecasts

  2008cited by this paper
• Incentive compatible regression learning

  2008cited by this paper
• Algorithmic Game Theory: Cost Sharing

  2007cited by this paper
• Strictly Proper Scoring Rules, Prediction, and Estimation

  2007influential reference
• Playing games with approximation algorithms

  2007cited by this paper
• Introduction to the Inefficiency of Equilibria

  2007cited by this paper
• Algorithmic Game Theory

  2007cited by this paper
• Eliciting Informative Feedback: The Peer-Prediction Method

  2005cited by this paper
• Improved second-order bounds for prediction with expert advice

  2005cited by this paper
• Loss Functions for Binary Class Probability Estimation and Classification: Structure and Applications

  2005cited by this paper
• Collusion-resistant mechanisms for single-parameter agents

  2005cited by this paper
• Incremental cost sharing: Characterization by coalition strategy-proofness

  1999cited by this paper
• A decision-theoretic generalization of on-line learning and an application to boosting

  1997influential reference
• The weighted majority algorithm

  1989influential reference
• Optimal Reporting of Predictions

  1989cited by this paper
• A General Method for Comparing Probability Assessors

  1989cited by this paper
• Eliciting production possibilities from a well-informed manager

  1979cited by this paper
• On the Design of Managerial Incentive Structures in a Decentralized Planning Environment

  1976cited by this paper
• Elicitation of Personal Probabilities and Expectations

  1971cited by this paper
• MEASURES OF THE VALUE OF INFORMATION.

  1956cited by this paper
• VERIFICATION OF FORECASTS EXPRESSED IN TERMS OF PROBABILITY

  1950cited by this paper

• No-Regret Incentive-Compatible Online Learning under Exact Truthfulness with Non-Myopic Experts

  2025cites this paper
• The Battling Influencers Game: Nash Equilibria Structure of a Potential Game and Implications to Value Alignment

  2025cites this paper
• Online Learning from Strategic Human Feedback in LLM Fine-Tuning

  2024cites this paper
• Recent Trends in Information Elicitation

  2024cites this paper
• On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: a regret lower bound for WSU-UX

  2024influential citation
• Learning With Incremental Instances and Features

  2023cites this paper
• No-Regret Online Prediction with Strategic Experts

  2023cites this paper
• Steering No-Regret Learners to a Desired Equilibrium

  2023cites this paper
• Online Nonconvex Optimization with Limited Instantaneous Oracle Feedback

  2023cites this paper
• Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts

  2023cites this paper
• Steering No-Regret Learners to Optimal Equilibria

  2023cites this paper
• Scoring Rules for Performative Binary Prediction

  2022cites this paper
• Data-driven personal thermal comfort prediction: A literature review

  2022cites this paper
• Reflexive Measurement

  2022cites this paper
• Information Discrepancy in Strategic Learning

  2021cites this paper
• Efficient Competitions and Online Learning with Strategic Forecasters

  2021influential citation
• Incentive-Aware PAC Learning

  2021cites this paper
• Classification with Few Tests through Self-Selection

  2021cites this paper
• No-Regret and Incentive-Compatible Online Learning

  2020influential citation
• Binary Scoring Rules that Incentivize Precision

  2020cites this paper
• Lie on the Fly: Strategic Voting in an Iterative Preference Elicitation Process

  2019cites this paper
• No-Regret and Incentive-Compatible Prediction with Expert Advice

  2019influential citation
• New Potential-Based Bounds for Prediction with Expert Advice

  2019cites this paper
• Online Learning from Data Streams with Varying Feature Spaces

  2019cites this paper
• A Perspective on Incentive Design: Challenges and Opportunities

  2019cites this paper
• Online Learning: A Comprehensive Survey

  2018cites this paper