research-article

Public Access

Surrogate Scoring Rules

Authors:

Yiling ChenAuthors Info & Claims

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

Pages 853 - 871

https://doi.org/10.1145/3391403.3399488

Published: 13 July 2020 Publication History

Abstract

Strictly proper scoring rules (SPSR) are incentive compatible for eliciting information about random variables from strategic agents when the principal can reward agents after the realization of the random variables. They also quantify the quality of elicited information, with more accurate predictions receiving higher scores in expectation. In this paper, we extend such scoring rules to settings where a principal elicits private probabilistic beliefs but only has access to agents' reports. We name our solution Surrogate Scoring Rules (SSR). SSR build on a bias correction step and an error rate estimation procedure for a reference answer defined using agents' reports. We show that, with a single bit of information about the prior distribution of the random variables, SSR in a multi-task setting recover SPSR in expectation, as if having access to the ground truth. Therefore, a salient feature of SSR is that they quantify the quality of information despite the lack of ground truth, just as SPSR do for the setting with ground truth. As a by-product, SSR induce dominant truthfulness in reporting. Our method is verified both theoretically and empirically using data collected from real human forecasters.

References

[1]

Dana Angluin and Philip Laird. 1988. Learning from noisy examples. Machine Learning, Vol. 2, 4 (1988), 343--370.

Digital Library

[2]

Pavel Atanasov, Phillip Rescober, Eric Stone, Samuel A Swift, Emile Servan-Schreiber, Philip Tetlock, Lyle Ungar, and Barbara Mellers. 2016. Distilling the wisdom of crowds: Prediction markets vs. prediction polls. Management science, Vol. 63, 3 (2016), 691--706.

[3]

Glenn W Brier. 1950. Verification of forecasts expressed in terms of probability. Monthey Weather Review, Vol. 78, 1 (1950), 1--3.

[4]

Tom Bylander. 1994. Learning linear threshold functions in the presence of classification noise. In Proceedings of the seventh annual conference on Computational learning theory. ACM, 340--347.

Digital Library

[5]

Anirban Dasgupta and Arpita Ghosh. 2013. Crowdsourced judgement elicitation with endogenous proficiency. In Proceedings of the 22nd international conference on World Wide Web. 319--330.

Digital Library

[6]

Luca De Alfaro, Michael Shavlovsky, and Vassilis Polychronopoulos. 2016. Incentives for truthful peer grading. arXiv preprint arXiv:1604.03178 (2016).

[7]

Alexander Frankel and Emir Kamenica. 2019. Quantifying information and uncertainty. American Economic Review, Vol. 109, 10 (2019), 3650--80.

[8]

Beno^it Frénay and Michel Verleysen. 2014. Classification in the presence of label noise: a survey. IEEE transactions on neural networks and learning systems, Vol. 25, 5 (2014), 845--869.

[9]

Alice Gao, James R Wright, and Kevin Leyton-Brown. 2016. Incentivizing evaluation via limited access to ground truth: Peer-prediction makes things worse. arXiv preprint arXiv:1606.07042 (2016).

[10]

Tilmann Gneiting and Adrian E. Raftery. 2007. Strictly Proper Scoring Rules, Prediction, and Estimation. J. Amer. Statist. Assoc., Vol. 102, 477 (2007), 359--378.

[11]

Naman Goel and Boi Faltings. 2018. Deep Bayesian Trust : A Dominant and Fair Incentive Mechanism for Crowd. arxiv: cs.GT/1804.05560

[12]

IARPA. 2019. Hybrid Forecasting Competition. https://www.iarpa.gov/index.php/research-programs/hfc?id=661.

[13]

Victor Richmond Jose, Robert F. Nau, and Robert L. Winkler. 2006. Scoring Rules, Generalized Entropy and utility maximization. (2006). Working Paper, Fuqua School of Business, Duke University.

[14]

Yuqing Kong. 2020. Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2398--2411.

[15]

Yuqing Kong and Grant Schoenebeck. 2016. Equilibrium selection in information elicitation without verification via information monotonicity. arXiv preprint arXiv:1603.07751 (2016).

[16]

Yuqing Kong and Grant Schoenebeck. 2018. Water from two rocks: Maximizing the mutual information. In Proceedings of the 2018 ACM Conference on Economics and Computation. 177--194.

Digital Library

[17]

Yuqing Kong and Grant Schoenebeck. 2019. An information theoretic framework for designing information elicitation mechanisms that reward truth-telling. ACM Transactions on Economics and Computation (TEAC), Vol. 7, 1 (2019), 2.

Digital Library

[18]

Yang Liu, Juntao Wang, and Yiling Chen. 2018. Surrogate scoring rules. arXiv preprint arXiv:1802.09158 (2018).

[19]

John McCarthy. 1956. Measures of the Value of Information. PNAS: Proceedings of the National Academy of Sciences of the United States of America, Vol. 42, 9 (1956), 654--655.

[20]

Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. 2015. Learning from corrupted binary labels via class-probability estimation. In International Conference on Machine Learning. 125--134.

[21]

Nolan Miller, Paul Resnick, and Richard Zeckhauser. 2005. Eliciting Informative Feedback: The Peer-Prediction Method. Management Science, Vol. 51, 9 (2005), 1359 --1373.

Digital Library

[22]

Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. 2013. Learning with noisy labels. In Advances in neural information processing systems. 1196--1204.

[23]

Matthew Parry et al. 2016. Linear scoring rules for probabilistic binary classification. Electronic Journal of Statistics, Vol. 10, 1 (2016), 1596--1607.

[24]

Dravzen Prelec. 2004. A Bayesian Truth Serum for Subjective Data. Science, Vol. 306, 5695 (2004), 462--466.

[25]

Dravz en Prelec, H Sebastian Seung, and John McCoy. 2017. A solution to the single-question crowd wisdom problem. Nature, Vol. 541, 7638 (2017), 532.

[26]

Goran Radanovic and Boi Faltings. 2013. A Robust Bayesian Truth Serum for Non-Binary Signals. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI '13).

[27]

Goran Radanovic, Boi Faltings, and Radu Jurca. 2016. Incentives for effort in crowdsourcing using the peer truth serum. ACM Transactions on Intelligent Systems and Technology (TIST), Vol. 7, 4 (2016), 48.

Digital Library

[28]

Leonard J. Savage. 1971. Elicitation of Personal Probabilities and Expectations. J. Amer. Statist. Assoc., Vol. 66, 336 (1971), 783--801.

[29]

Clayton Scott. 2015. A Rate of Convergence for Mixture Proportion Estimation, with Application to Learning from Noisy Labels. In AISTATS.

[30]

Clayton Scott, Gilles Blanchard, Gregory Handy, Sara Pozzi, and Marek Flaska. 2013. Classification with Asymmetric Label Noise: Consistency and Maximal Denoising. In COLT. 489--511.

[31]

Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C Parkes. 2016. Informed truthfulness in multi-task peer prediction. In Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 179--196.

Digital Library

[32]

Brendan van Rooyen and Robert C Williamson. 2015. Learning in the Presence of Corruption. arXiv preprint:1504.00091 (2015).

[33]

Robert L. Winkler. 1969. Scoring rules and the evaluation of probability assessors. J. Amer. Statist. Assoc., Vol. 64, 327 (1969), 1073--1078.

[34]

Jens Witkowski, Pavel Atanasov, Lyle H Ungar, and Andreas Krause. 2017. Proper proxy scoring rules. In Thirty-First AAAI Conference on Artificial Intelligence.

Digital Library

[35]

Jens Witkowski, Yoram Bachrach, Peter Key, and David C. Parkes. 2013. Dwelling on the Negative: Incentivizing Effort in Peer Prediction. In HCOMP'13.

[36]

Jens Witkowski and David C. Parkes. 2012. A Robust Bayesian Truth Serum for Small Populations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI '12).

Cited By

Keppo JSatopää V(2024)Bayesian herd detection for dynamic dataInternational Journal of Forecasting10.1016/j.ijforecast.2023.03.00140:1(285-301)Online publication date: Jan-2024
https://doi.org/10.1016/j.ijforecast.2023.03.001
Zhu ZYao YSun JLi HLiu YKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Weak proxies are sufficient and preferable for fairness with missing sensitive attributesProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620230(43258-43288)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620230
Ast FGeorge WKamalova JSharma AAouidef Y(2023)Decentralized justice: state of the art, recurring criticisms and next-generation research topicsFrontiers in Blockchain10.3389/fbloc.2023.12040906Online publication date: 9-Oct-2023
https://doi.org/10.3389/fbloc.2023.1204090
Show More Cited By

Index Terms

Surrogate Scoring Rules
1. Information systems
  1. World Wide Web
    1. Web applications
      1. Crowdsourcing
        Incentive schemes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Quality of equilibria

Recommendations

Surrogate Scoring Rules
Strictly proper scoring rules (SPSR) are incentive compatible for eliciting information about random variables from strategic agents when the principal can reward agents after the realization of the random variables. They also quantify the quality of ...
Putting Peer Prediction Under the Microeconomicscope and Making Truth-Telling Focal
WINE 2016: Proceedings of the 12th International Conference on Web and Internet Economics - Volume 10123

Peer-predictionï ź[19] is a meta-mechanism which, given any proper scoring rule, produces a mechanism to elicit prie information from self-interested agents. Formally, truth-telling is a strict Nash equilibrium of the mechanism. Unfortunately, there may ...
Two Strongly Truthful Mechanisms for Three Heterogeneous Agents Answering One Question
Peer prediction mechanisms incentivize self-interested agents to truthfully report their signals even in the absence of verification by comparing agents’ reports with their peers. We propose two new mechanisms, Source and Target Differential Peer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

July 2020

937 pages

ISBN:9781450379755

DOI:10.1145/3391403

General Chairs:
Péter Biró
Hungarian Academy of Sciences
,
Jason Hartline
Northwestern University
,
Program Chairs:
Michael Ostrovsky
Stanford University
,
Ariel Procaccia
Harvard University

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

EC '20

Sponsor:

SIGecom

EC '20: The 21st ACM Conference on Economics and Computation

July 13 - 17, 2020

Virtual Event, Hungary

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
453
Total Downloads

Downloads (Last 12 months)112
Downloads (Last 6 weeks)34

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Keppo JSatopää V(2024)Bayesian herd detection for dynamic dataInternational Journal of Forecasting10.1016/j.ijforecast.2023.03.00140:1(285-301)Online publication date: Jan-2024
https://doi.org/10.1016/j.ijforecast.2023.03.001
Zhu ZYao YSun JLi HLiu YKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Weak proxies are sufficient and preferable for fairness with missing sensitive attributesProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620230(43258-43288)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620230
Ast FGeorge WKamalova JSharma AAouidef Y(2023)Decentralized justice: state of the art, recurring criticisms and next-generation research topicsFrontiers in Blockchain10.3389/fbloc.2023.12040906Online publication date: 9-Oct-2023
https://doi.org/10.3389/fbloc.2023.1204090
Burrell NSchoenebeck GLeyton-Brown KSamuelson LHartline J(2023)Measurement Integrity in Peer Prediction: A Peer Assessment Case StudyProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597744(369-389)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597744
Cummings RElzayn HPountourakis EGkatzelis VZiani J(2023)Optimal Data Acquisition with Privacy-Aware Agents2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML54575.2023.00023(210-224)Online publication date: Feb-2023
https://doi.org/10.1109/SaTML54575.2023.00023
Himmelstein MBudescu DHan Y(2023)The Wisdom of Timely CrowdsJudgment in Predictive Analytics10.1007/978-3-031-30085-1_8(215-242)Online publication date: 3-Jun-2023
https://doi.org/10.1007/978-3-031-30085-1_8
Atanasov PHimmelstein M(2023)Talent Spotting in Crowd PredictionJudgment in Predictive Analytics10.1007/978-3-031-30085-1_6(135-184)Online publication date: 3-Jun-2023
https://doi.org/10.1007/978-3-031-30085-1_6
Kong YLi YZhang YHuang ZWu JKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Eliciting thinking hierarchy without a priorProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601239(13329-13341)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3601239
Gordon MBishop MChen YDreber AGoldfedder BHolzmeister FJohannesson MLiu YTran LTwardy CWang JPfeiffer T(2022)Forecasting the publication and citation outcomes of COVID-19 preprintsRoyal Society Open Science10.1098/rsos.2204409:9Online publication date: 28-Sep-2022
https://doi.org/10.1098/rsos.220440
Su WRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)You are the best reviewer of your own papersProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3542400(27929-27939)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3542400
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents