Source-linked AI summary
Whom to Ask? Jury Selection for Decision Making Tasks on Micro-blog Services
Caleb Chen Cao, Jieying She, Yongxin Tong, Lei Chen
TL;DR
The paper studies selecting a budget-limited jury of micro-blog users whose majority vote minimizes the probability of a wrong decision. It develops efficient JER calculations and model-specific selection algorithms for altruistic and incentive-requiring users, validating them on synthetic and real datasets.
Problem
The Jury Selection Problem seeks a budget-limited subset of micro-blog users whose aggregated majority vote has the lowest Jury Error Rate despite differing individual error rates.
Method
The paper formalizes AltrM and PayM models, develops efficient JER algorithms, proves an exact AltrM solution and PayM NP-hardness, and proposes a greedy PayM heuristic.
Results
The proposed algorithms were validated for efficiency and effectiveness through extensive experiments on synthetic and real datasets.
Takeaways & Limitations
The study provides computational approaches for jury selection in micro-blog decision-making tasks under limited budgets.
Takeaways & Limitations
Estimating each user's individual requirement is domain-specific, requires task-dependent design, and is outside the work's scope.
Abstract
from arXiv · showhide
It is universal to see people obtain knowledge on micro-blog services by asking others decision making questions. In this paper, we study the Jury Selection Problem(JSP) by utilizing crowdsourcing for decision making tasks on micro-blog services. Specifically, the problem is to enroll a subset of crowd under a limited budget, whose aggregated wisdom via Majority Voting scheme has the lowest probability of drawing a wrong answer(Jury Error Rate-JER). Due to various individual error-rates of the crowd, the calculation of JER is non-trivial. Firstly, we explicitly state that JER is the probability when the number of wrong jurors is larger than half of the size of a jury. To avoid the exponentially increasing calculation of JER, we propose two efficient algorithms and an effective bounding technique. Furthermore, we study the Jury Selection Problem on two crowdsourcing models, one is for altruistic users(AltrM) and the other is for incentive-requiring users(PayM) who require extra payment when enrolled into a task. For the AltrM model, we prove the monotonicity of JER on individual error rate and propose an efficient exact algorithm for JSP. For the PayM model, we prove the NP-hardness of JSP on PayM and propose an efficient greedy-based heuristic algorithm. Finally, we conduct a series of experiments to investigate the traits of JSP, and validate the efficiency and effectiveness of our proposed algorithms on both synthetic and real micro-blog data.
1. INTRODUCTION
The paper frames decision making on micro-blog services as a crowdsourcing task and studies how to select reliable jurors under error-rate and budget constraints. It introduces models and algorithms for minimizing jury error while addressing computational complexity and user incentives.
- Motivation: Micro-blog services support crowdsourcing for decision questions, including rumor identification, by letting question holders actively select potential workers.Users can solicit answers through mentions and replies, extending crowdsourcing beyond specially designed platforms.
- Problem Formulation: Jury selection seeks a subset of jurors whose majority vote has the lowest error rate despite individual mistake probabilities and participation requirements.The paper denotes workers as jurors, crowds as a jury, and each juror’s mistake probability as ϵ_i.
- Motivation: Majority voting can improve on individual jurors, but adding members does not necessarily lower the jury error rate.The motivating example reports error rates of 0.072, 0.0704, and 0.085 for different jury compositions.
- Problem Formulation: Limited budgets create a trade-off between selecting reliable but costly jurors and selecting cheaper users with potentially higher error rates.Users D and E together require $1.05, exceeding the $1 budget in the example.
- Contributions: The paper proposes AltrM and PayM models, efficient JER-calculation algorithms, an exact AltrM algorithm, and a polynomial heuristic for NP-hard PayM JSP.It also proposes retrieving individual error rates from message-forwarding graphs and user rankings.
2. MODELS AND PROBLEM DEFINITION
This section defines juries, voting, error rates, Jury Error Rate, and the Jury Selection Problem under altruistic and payment-constrained crowdsourcing models.
- Voting Scheme: Majority Voting chooses the decision supported by more than half of the jurors, with odd jury sizes assumed for a clear outcome.A voting is a set of binary values, and a voting scheme maps it to a decision.
- Error Rate: A juror’s individual error rate is the probability of voting incorrectly when the ground truth is unknown to the jury.The ground truth may be false or true, while the jury does not know it before aggregation.
- Error Rate: Jury Error Rate is the probability that more than half of a jury’s jurors are mistaken during voting.Carelessness counts mistaken jurors, and enumerating all possible mistaken subsets creates exponentially many probability terms.
- Crowdsourcing Models: AltrM permits any candidate subset as a jury, whereas PayM permits a jury only when total payments do not exceed budget B.PayM associates each juror with a nonnegative payment requirement r_i.
- Problem Definition: JSP selects an allowed jury J_n from candidate jurors to minimize JER under a budget and crowdsourcing model.The model may be AltrM or PayM, and jury size can range from 1 to N.
3. JURY SELECTION ALGORITHM
The jury-selection algorithm section frames the challenge as choosing jury size and members when JER varies across jurors and is difficult to compute.
- Algorithm Overview: Selecting jurors solely by sorting individual error rates does not directly identify the best jury in terms of JER.The difficulty arises from variation among jurors’ error rates and the interaction among selected jurors.
- Algorithm Overview: Jury selection must determine both which jurors to choose and how large the jury should be, because larger groups do not always perform better.The cited example reports that a 5-juror group outperforms a 3-juror group, while a 7-juror group offers no superiority.
- Algorithm Overview: The paper next calculates JER, develops algorithms for AltrM, and presents a PayM solution with a complexity analysis.The section outline covers JER calculation, two AltrM algorithms, and the PayM problem.
3.1 Calculation of JER
The paper defines JER as the probability that more than half of a jury votes incorrectly, then develops faster ways to compute and prune JER calculations.
- Dynamic Programming: Dynamic programming computes JER in O(n^2) time and O(n) space by recursively combining juror error probabilities.The recurrence uses the previous jury's probabilities for one fewer or the same number of wrong votes.
- Convolution-based Algorithm: The convolution-based algorithm uses divide and conquer with FFT polynomial multiplication to reduce JER computation to O(n log n).Each juror contributes a one-order polynomial, and convolutions merge smaller jury distributions.
- Lower Bound-based Pruning: A Paley-Zygmund lower bound can prune candidate juries before full JER computation, with bound calculation taking O(n) time.The bound is cheaper than either exact JER algorithm and is intended to improve overall efficiency.
- JER is the probability that more than half of the jurors give wrong votes.The number of wrong votes follows a Poisson-Binomial distribution.
3.2 JSP on AltrM
For altruistic users, JER increases with individual error rate, so the optimal jury of each size uses the lowest-error jurors; the resulting algorithm evaluates these sizes efficiently.
- Monotonicity: Among candidate jurors, the lowest JER comes from the individuals with the lowest error rates.This follows from JER being monotone increasing in each individual error rate for a fixed jury size.
- Algorithm for AltrM: AltrALG sorts jurors by ascending error rate, evaluates odd jury sizes, and returns the candidate with minimum JER.Lower-bound pruning can terminate some JER evaluations early.
- Algorithm for AltrM: AltrALG has time complexity O(N^2 · log N).The cost combines sorting with repeated JER evaluation across candidate jury sizes.
3.3 JSP on PayM
Under PayM, jury selection must minimize JER subject to payment requirements and a budget, making the problem NP-complete; the paper therefore proposes a greedy heuristic.
- NP-hardness: Unlike traditional 0/1 knapsack, PayM selection compares both payment weight and JER benefit rather than additive item value.The paper identifies this objective structure as a source of additional difficulty.
- NP-hardness: JSP on PayM is NP-complete because its JER objective creates a nonlinear budget-constrained selection problem.The proof reduces a knapsack variant to the decision version of JSP.
- Approximate Algorithm: PayALG ranks jurors by the product of error rate and payment requirement, then enlarges feasible odd-sized juries when JER improves.Candidate pairs are considered as one enlargement under the budget constraint.
4. PARAMETER ESTIMATION
The paper estimates juror reliability from retweet-based user graphs and estimates payment requirements using account age, while presenting an integrated system for jury formation and voting.
- Error-rate Estimation: Individual error rates are estimated from user authority in a retweet graph, using HITS authority or PageRank scores as quality scores.The graph links users according to retweet actions rather than follower relationships.
- Error-rate Estimation: The real dataset shows that most top-ranked users identified by PageRank overlap with those identified by HITS.The paper uses normalized ranking scores as user quality measures.
- Requirement Estimation: The paper treats payment-requirement estimation as domain-specific and proposes account age only as an optional indicator.It assumes more experienced users are less interested in a task.
- System Overview: The system estimates candidate characteristics, selects a jury, and aggregates its opinions into a Yes/No decision by Majority Voting.Different parameter-estimation methods may be used for different situations.
5. EVALUATION
Experiments examine JSP traits and evaluate AltrALG and PayALG on synthetic and real micro-blog data. Results show that jury quality, optimal size, efficiency, and approximation fidelity depend on error-rate distributions and available budget.
- JSP Traits on AltrM: When most candidates have error-rates above 0.5, AltrALG reduces the jury size; when most are reliable, the best jury size is more variable.The reliable-candidate setting produces a relatively flat optimization landscape.
- Efficiency on AltrM: As the candidate set grows, lower-bound enhancement increases more slowly in running time than the non-enhanced algorithm, with a ratio of O(1/log N).For sizes from 2,000 to 3,000, checking the bound can initially cost more because of its pruning overhead.
- JSP Traits on PayM: A higher budget reduces JER, while candidates with lower individual error-rates form better juries within the same budget.For jurors with error-rates above 0.5, the method selects fewer jurors but pays more per selected juror.
- Effectiveness on PayM: PayALG reaches the optimal JER 4 times out of 11, and its JER approaches ground truth as the budget increases.The largest discrepancy occurs at the lowest budget, B = 0.5.
- Efficiency on AltrM: PageRank data benefits substantially from lower-bound enhancement, whereas HITS data becomes slower because checking the bound adds overhead.The distribution of error-rates near 0 or 1 in PageRank creates more opportunities for bounding-based pruning.
- Evaluation on PayM: On HITS data, PayALG has precision and recall of 1, while PageRank has lower resemblance to ground truth but still achieves JER 0.00075.The selected jury size on HITS is always identical to ground truth; PageRank jury sizes remain close to ground truth.
6. RELATED WORK
Related work spans crowdsourcing systems, worker-quality estimation, and expert team formation. This paper differs by studying voting reliability with actively selectable workers on micro-blog services.
- Crowdsourcing: Prior crowdsourcing research includes database systems, graph search, multimedia annotation, document searching, and methods for reconciling worker disagreement.These works provide related uses of collective intelligence and worker-quality estimation.
- Worker Quality: This paper focuses on the relationship between individual worker quality and the reliability of majority voting.Its setting concerns a specialized collective product rather than general task completion.
- Worker Quality: Unlike AMT, where requesters cannot actively choose workers, micro-blog services allow worker selection through the “@” markup.The paper applies this capability to selecting jurors for decision-making tasks.
- Expert Team Formation: Expert Team Formation selects users with required skills while considering selection costs such as communication or relationship costs.Related work also identifies expertise through communication activities such as email.
7. CONCLUSION
The paper formulates jury selection for micro-blog decision-making tasks around computing JER and finding a budget-feasible subset. It proposes efficient computation, two user models, selection algorithms, and experimental validation.
- Conclusion: The JSP challenges are calculating JER and finding the optimal subset under a limited budget.The paper proposes algorithms for JER computation with time costs O(n^2) and O(n · log n).
- Conclusion: AltrM and PayM model altruistic and incentive-requiring users, with JER monotonicity on AltrM and NP-hard JSP on PayM.The paper proposes efficient algorithms for JSP under both models.
- Conclusion: Extensive experiments on synthetic and real datasets verify the proposed algorithms.