Optimal Spot-Checking for Improving the Evaluation Quality of Crowdsourcing: Application to Peer Grading Systems

Peer grading is a natural crowdsourcing application, where dispersed students/peers resources are collected to evaluate others' assignments. Peer grading also offers a promising solution for scaling evaluation and learning to large-scale educational systems. A key challenge in peer grading is motivating peers to grade diligently and provide a high-quality evaluation. Spot-checking (SC) mechanisms, allowing instructors to check evaluations, can prevent peer collusion where peers grade arbitrarily and coordinate to report the uninformative grade. However, existing SC mechanisms unrealistically assume that peers have the same grading reliability and cost. This is limiting in practice, where we would expect peers to differ in reliability and cost. This article proposes the general Optimal SC (OptSC) model of determining the probability that each assignment needs to be checked to maximize assignments' evaluation accuracy aggregated from peers and takes into consideration: 1) peers' heterogeneous characteristics and 2) peers' strategic grading behaviors to maximize their own utility. We prove that the bilevel OptSC is NP-hard to solve. By exploiting peers' grading behaviors, we first formulate a single-level relaxation to approximate OptSC. By further exploiting structural properties of the relaxed problem, we propose an efficient algorithm to that relaxation, which also gives a good approximation of the original OptSC. Extensive experiments on both synthetic and real data sets show significant advantages of the proposed algorithm over existing approaches.