CoChat
Sign Up
PreprintCited by 1Game Theory and ApplicationsAuction Theory and ApplicationsGame Theory and Voting Systems

Optimization of Scoring Rules

Open access
Hartline, Jason D., Li, Yingkai, Shan, Liren, Wu, Yifan·2020·arXiv
DOI 10.48550/arxiv.2007.02905arXiv 2007.02905
Open this paper in CoChat — free accountOpen PDF

Abstract

We characterize the optimal reward functions (scoring rules) that incentivize an agent to acquire information and report it truthfully to the principal. The optimal scoring rules let the agent make a simple binary bet in single-dimensional problems, and choose the dimension with the most surprising signal to be scored on in symmetric multi-dimensional problems. This scoring rule format remains approximately optimal for asymmetric distributions. These results demonstrate the importance of linking incentives to obtain high-quality information in multi-dimensional problems. In contrast, standard scoring rules like the quadratic scoring rule, or averages of single-dimensional scoring rules can be far from optimal.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2007.02905

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Hartline et al. (2020) showed that the most robust 'low effort' strategy is to report the class average, because it minimizes the expected distance to an effortful report.

    “Hartline et al. (2020)showed that the most robust”

    From Better Peer Grading through Bayesian Inference (2023) · cites this paper as Hartline et al. (2020)

    Section 6, “Application to Peer Grading” (page unavailable), says that when a peer does not read a submission, her optimal strategy is to report her prior belief—the class average mark for each criterion. It does not say this is the “most robust” strategy or explain its optimality as minimizing expected distance to an effortful report. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 32

  1. Jacob D Abernethy and Rafael M Frongillo. A characterization of scoring rules for linear properties. In Conference on Learning Theory, pages 27-1, 2012.
  2. Saeed Alaei, Hu Fu, Nima Haghpanah, Jason D Hartline, and Azarakhsh Malekian. Efficient computation of optimal auctions via reduced forms. Mathematics of Operations Research, 44(3): 1058-1086, 2019.
  3. Mark Armstrong. Multiproduct nonlinear pricing. Econometrica: Journal of the Econometric Society, pages 51-75, 1996.
  4. Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S Matthew Weinberg. A simple and approximately optimal mechanism for an additive buyer. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 21-30. IEEE, 2014.
  5. Shai Ben-David and Allan Borodin. A new measure for the study of on-line algorithms. Algorith- mica, 11(1):73-91, 1994.
  6. Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S Matthew Weinberg. Pricing lotteries. Journal of Economic Theory, 156:144-174, 2015.
  7. Jeremy Bulow and Paul Klemperer. Auctions versus negotiations. The American Economic Review, 86(1):180-194, 1996.
  8. Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. An algorithmic characterization of multi-dimensional mechanisms. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 459-478. ACM, 2012a.
  9. Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Optimal multi-dimensional mech- anism design: Reducing revenue to welfare maximization. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 130-139. IEEE, 2012b.
  10. Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. In Conference on Learning Theory, pages 280-296, 2015.
  11. Yiling Chen and Fang-Yi Yu. Optimal scoring rule design. arXiv preprint arXiv:2107.07420, 2021. · arXiv
  12. Yiling Chen and Shuran Zheng. Prior-free data acquisition for accurate statistical estimation. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 659-677, 2019.
  13. Yiling Chen, Nicole Immorlica, Brendan Lucier, Vasilis Syrgkanis, and Juba Ziani. Optimal data acquisition for statistical estimation. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 27-44, 2018.
  14. Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceed- ings of the forty-sixth annual ACM symposium on Theory of computing, pages 243-252, 2014.
  15. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Strong duality for a multiple- good monopolist. Econometrica, 85(3):735-767, 2017.
  16. Luca de Alfaro and Michael Shavlovsky. Crowdgrader: Crowdsourcing the evaluation of homework assignments. arXiv preprint arXiv:1308.5273, 2013. · arXiv
  17. Rafael Frongillo and Jens Witkowski. A geometric perspective on minimal peer prediction. ACM Transactions on Economics and Computation, 5(3):1-27, 2017.
  18. Sarah Gielen, Elien Peeters, Filip Dochy, Patrick Onghena, and Katrien Struyven. Improving the effectiveness of peer feedback for learning. Learning and instruction, 20(4):304-315, 2010.
  19. Nima Haghpanah and Jason Hartline. Reverse mechanism design. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 757-758, 2015.
  20. J. Hartline and T. Roughgarden. Simple versus optimal mechanisms. In Proc. 10th ACM Conf. on Electronic Commerce, 2009.
  21. Matthew O Jackson and Hugo F Sonnenschein. Overcoming incentive constraints by linking deci- sions. Econometrica, 75(1):241-257, 2007.
  22. David R Karger, Sewoong Oh, and Devavrat Shah. Budget-optimal task allocation for reliable crowdsourcing systems. Operations Research, 62(1):1-24, 2014.
  23. Yuqing Kong. Optimizing multi-task peer prediction. arXiv preprint arXiv:2103.02214, 2021. · arXiv
  24. John McCarthy. Measures of the value of information. Proceedings of the National Academy of Sciences of the United States of America, 42(9):654, 1956.
  25. Eric Neyman, Georgy Noarov, and S Matthew Weinberg. Binary scoring rules that incentivize precision. Proceedings of the 22nd ACM Conference on Economics and Computation, 2021.
  26. Kent Osband. Optimal forecasting incentives. Journal of Political Economy, 97(5):1091-1112, 1989.
  27. Kent Osband and Stefan Reichelstein. Information-eliciting compensation schemes. Journal of Public Economics, 27(1):107-115, 1985.
  28. Jean-Charles Rochet. The taxation principle and multi-time hamilton-jacobi equations. Journal of Mathematical Economics, 14(2):113-128, 1985.
  29. Philip M Sadler and Eddie Good. The impact of self-and peer-grading on student learning. Edu- cational assessment, 11(1):1-31, 2006.
  30. Kristin Stephens-Martinez, An Ju, Krishna Parashar, Regina Ongowarsito, Nikunj Jain, Sreesha Venkat, and Armando Fox. Taking advantage of scale by analyzing frequent constructed-response, code tracing wrong answers. In Proceedings of the 2017 ACM Conference on International Com- puting Education Research, pages 56-64, 2017.
  31. James R Wright, Chris Thornton, and Kevin Leyton-Brown. Mechanical ta: Partially automated high-stakes peer grading. In Proceedings of the 46th ACM Technical Symposium on Computer Science Education, pages 96-101, 2015.
  32. Yuchen Zhang, Xi Chen, Dengyong Zhou, and Michael I Jordan. Spectral methods meet em: A provably optimal algorithm for crowdsourcing. The Journal of Machine Learning Research, 17 (1):3537-3580, 2016.

Cited by

Sorted by citations

Authors
Hartline, J. D., Li, Y., Shan, L., & Wu, Y.
Affiliations
Northwestern University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2007.02905
arXiv
2007.02905
OpenAlex
W4299804667
Cited by
1
References
0
Citations by year
2023: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (1733860, 1947021, 1955351, 1934931)
Topics
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Auction Theory and Applications
  • Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
Keywords
scoring rules, incentive compatibility, information acquisition, truthful reporting, principal-agent problem, multidimensional problems, quadratic scoring rule, skewed distributions, information quality

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review