Timezone: »
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.
Author Information
Tim Roughgarden (Stanford University)
Okke Schrijvers (Facebook Inc.)
More from the Same Authors
-
2018 Poster: Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization »
Rad Niazadeh · Tim Roughgarden · Joshua Wang -
2018 Oral: Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization »
Rad Niazadeh · Tim Roughgarden · Joshua Wang -
2017 Workshop: Learning in the Presence of Strategic Behavior »
Nika Haghtalab · Yishay Mansour · Tim Roughgarden · Vasilis Syrgkanis · Jennifer Wortman Vaughan -
2016 : Online Prediction with Selfish Experts »
Okke Schrijvers -
2015 Poster: On the Pseudo-Dimension of Nearly Optimal Auctions »
Jamie Morgenstern · Tim Roughgarden -
2015 Spotlight: On the Pseudo-Dimension of Nearly Optimal Auctions »
Jamie Morgenstern · Tim Roughgarden -
2013 Poster: Marginals-to-Models Reducibility »
Tim Roughgarden · Michael Kearns