- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies data markets where there is no GT to check contributions against, so payments have to come from peer prediction. Each supplier pair only shares a finite pool of tasks and the platform has a fixed budget. A scheduler that spreads samples around to reduce uncertainty can then run out of budget without finishing any certificate. They therefore frame the goal as certifying as many pairs as possible, where a pair counts as certified once a lower confidence bound shows that truthful reporting beats every declared deviation by some margin.
They take the KFCA payment rule from earlier work as given and build this bound from a Hoeffding–Serfling style inequality for sampling without replacement, combined with a union bound over pairs, deviations, and sample counts. This makes the certificates valid even when pairs are picked adaptively (Theorem 1). The scheduler, BRCert, estimates for each pair how many more samples it would take to certify it if the current empirical margin held. It drops pairs that can’t be finished with what is left in their pool or in the budget, and it spends on the pair that looks cheapest to complete. A wrong estimate can cost coverage but can’t produce a false certificate. The authors are also explicit that the guarantee only covers unilateral deviations in the current batch, not dynamic incentives or coalitions.
For validation, they replay five crowdsourcing datasets (CIFAR-10N, Fact, RTE, and two NetEase subsets) with no model training involved. The main setting has 30 candidate pairs, a budget of 200, and pools of up to 30 tuples, with results averaged over five seeds. BRCert reaches 19.6% mean coverage, 1.6 points above the best of six baseline schedulers, and the gap grows to 1.9 points with 50 candidate pairs. Checking against the exact full-pool margins turns up no false certificates. The paper also reports sensitivity to budget and pool size, plus an ablation that separates the reachability test from the exploration strategy.
Critical strengths
The one strength I’d point to is the problem formulation. The paper makes a fair case that with finite task pools and a hard budget, the relevant question is whether a certificate can actually be completed, and that schedulers built for uncertainty reduction or asymptotic identification don’t address this. Stating the objective as budget-reachable certification is clean and could be useful beyond this specific market setting. That said, the idea itself is fairly intuitive, and the empirical benefit of the reachability test is modest (1.6 points on average, roughly half a certified pair per seed). So this strength is real but limited, and it isn’t enough on its own to outweigh the concerns below.
Critical weaknesses
The main weakness is that the empirical gain is small and not well established. With 30 candidate pairs, the average improvement of 1.6 points over the best baseline is about half a certified pair per seed, and on three of the five datasets the gap is under one point. There are only five seeds and no significance tests. The strongest baselines are essentially ablations of BRCert, and there is no oracle upper bound. Since the method’s value rests mostly on this comparison, this weighs heavily in my assessment.
The second weakness is that the technical contribution is thin and the source of the certificates is unclear. Theorem 1 is a standard concentration-plus-union-bound result, Proposition 1 follows almost directly from the definition of m_e(t), and the scheduler has no optimality guarantee. In the main binary setting, Eq. (5) only drops below 0.5a after about 28 of 30 tuples, which suggests certificates may come mostly near pool exhaustion
Questions for authors
What decision does a certificate actually support in the market? For example, does it determine whether payments are released, whether a supplier pair stays in the market, or whether the payment rule needs adjusting? And what happens to pairs left unresolved? Without this, I find it hard to judge whether certifying about half a pair more per seed matters in practice.
Why is the number of certified edges the right objective? Counting edges naturally favors pairs that are easy to certify, and Appendix D notes that concentrated allocation may leave atypical suppliers unresolved. If a platform instead wants each supplier verified at least once, or wants coverage spread across suppliers, does BRCert still make sense, and how does it compare under such an objective?
How far does the approach extend beyond the replayed annotation setting? The title emphasizes federated data markets, but KFCA relies on discrete reports on shared tasks, while federated contributions are usually continuous model updates. Conversely, the reachability idea seems to apply to budgeted auditing more generally.
When are certificates issued relative to pool size, and do BRCert’s gains hold with a tighter without-replacement bound and across individual seeds?
4 comments
Thank you for the response and the additional experiments. The revisions clarify the scope, particularly the separation of certificate validity from scheduler effectiveness.
However, I still have concerns about consistency and contribution. The client-mapping experiments use the original radius while the main results use the corrected one, so the two are hard to compare. Also, with the corrected bound, the gain over the best baseline is about 1 point (7 wins, 3 losses, 15 ties out of 25 runs), which is not enough to show a clear benefit. The revelation statistics (median n_e/M_e = 1.0, none below 90%) also show that certificates are issued almost only at pool exhaustion, so the role of the concentration bound seems limited.
Response to yMDv: Consistency and Scheduling Results [1/2]
Thank you for the follow-up. We have addressed the mixed-radius comparison and added matched evidence against stronger completion-aware controls. We also directly examine whether the concentration bound contributes beyond deterministic completion (Part 2).
1. Client results under the same corrected bound. All three client settings were recomputed using the corrected Bardenet-Maillard radius in both certification and scheduling. For the five-seed client comparison:
| Client setting | Original BRCert coverage | Margin-greedy coverage |
|---|---|---|
| Fact workers as clients | .2133 | .2000 |
| RTE workers as clients | .1467 | .1400 |
| 24 synthetic clients | .2333 | .2400 |
Methods share pools, initial histories, reveal orders and the certificate within each comparison. These client results use the original-rule implementation and tie handling of the Section 7.1 main replay. The larger confirmation below is a separate matched experiment with deterministic ties. Fact/RTE remapping preserves the reports: it checks compatibility with categorical client inputs, not independent federated-training performance. We retain the synthetic setting's slightly lower final coverage.
2. Added value beyond completion-first. The remaining-pool control is especially informative under near-exhaustion certification: the original completion-cost predictor performs essentially like remaining-pool. We do not claim an incremental gain from recomputing that full forecast. The additional question is whether allocating by the chance of a successful completion, subject to the remaining budget, improves on this strong simple control.
We evaluate a budget-aware version of the pass-rate variant already described in our response. It estimates the full-pool pass rate from observed joint gap vectors. When positive-score edges whose remaining pools fit the residual budget exist, it ranks those edges by . If none fits, it uses unrestricted ; if all scores are zero, it uses remaining-pool. Pool length is an exhaustion-cost proxy, not a proof that other edges cannot certify early. Scores are reused until that edge's observed state changes, with isolated random streams. The preference makes completion-first allocation account for the residual horizon. Payment and the corrected certificate are unchanged. Theorem 1 still applies; Proposition 1 remains restricted to the original completion-cost rule.
The variant was fixed before evaluating 100 additional tuple/reveal seeds per market: 500 matched dataset-seed cells per setting. These are repetitions on the same five markets, not new-market replications. All methods share pools, histories, reveal orders, corrected bounds and deterministic final tie breaking. At , 50 candidates, pool cap 60 and :
| Scheduler | Mean certificates | Coverage |
|---|---|---|
| Budget-aware pass-rate variant | 4.724 | .09448 |
| Previous pass-rate variant | 4.550 | .09100 |
| Remaining-pool | 4.298 | .08596 |
| Original BRCert | 4.278 | .08556 |
| ForcedEX | 3.892 | .07784 |
| Margin-greedy | 2.964 | .05928 |
Against remaining-pool, the paired gain is +0.426 edges, with 95% interval [0.366, 0.486] and 175 wins / 304 ties / 21 losses. Against the previous pass-rate variant, it is +0.174 [0.136, 0.212], with 96/393/11. Intervals resample paired seeds within each fixed market, then average markets equally; they do not establish generalization to new markets. Per-market gains over remaining-pool are CIFAR -0.02, Fact +0.07, RTE +1.10, NetEase-69 +0.43 and NetEase-126 +0.55 edges. The benefit is concentrated, not uniform.
A same-randomness control isolates the residual-budget preference from score reuse: it adds +0.182 edges [0.148, 0.216], with 89/411/0. Its benefit is principally terminal completion, not first-certificate timing. Complete purchase trajectories and per-market results are retained. No false certificates occurred. The gains over remaining-pool are also positive in the original-sized setting (+0.224 [0.164, 0.284]) and zero-target high-contention setting (+0.654 [0.588, 0.720]).
The absolute gains remain modest. The stronger evidence supports a repeatable increment beyond simple completion-first allocation, while identifying which part of the scheduler provides that increment.
Response to yMDv: The Role of the Confidence Bound [2/2]
3. Does the concentration bound contribute before exhaustion? With pool caps of 30 or 60, the observed benefit is mainly cross-edge budget allocation. At exhaustion, the finite-batch margin is known exactly. Moreover, the early certificates in these runs already satisfy a deterministic worst-case completion bound. We therefore do not use those results to claim substantial per-edge savings from concentration.
To test the bound's role directly, we examined all legal prefixes on the same five real markets with requested pool caps 120, 240, 480 and 960, seeds 0-4, and targets 0 and .05. Candidate edges follow the existing overlap-only rule; they are not selected by margin or certification outcome. Actual pool sizes, which can be below the requested cap, are recorded separately.
The per-edge deterministic control allows each unseen tuple to take its worst legal value. For observed deviation sums , it certifies using
Enumeration of legal report quadruples confirms that -2 is the exact minimum gap for each declared non-identity deviation in the evaluated two-, three- and ten-class settings. This tests whether the statistical certificate provides evidence beyond worst-case finite-pool completion, rather than merely beating an exhaustion-only check.
Fact supplies a clear real-data example. With actual and , 249 of the 250 edge instances (five seeds, 50 candidates each) have exact full-pool margins meeting the target:
| Certification rule | Mean revealed fraction at first certification |
|---|---|
| Corrected statistical bound | .8064 |
| Exact-support deterministic completion bound | .8968 |
| Exhaustion | 1.0000 |
The statistical rule saves an average of 43.4 tuples relative to the deterministic rule. For 216 of these 249 instances, the deterministic bound is still below the target when the statistical certificate is first issued. All statistical certificates pass the exact-pool audit. Thus the bound has an independent early-certification role on real reports when sufficient overlap is available.
This is an unbudgeted full-prefix diagnostic, separate from the scheduler comparison. Each Fact edge starts with 96 historical tuples and needs, on average, 291.1 additional purchases for statistical certification. These results cannot explain a coverage gain achievable under the original shared budget; they establish a different operating regime of the same certificate.
The full diagnostic also preserves the limits: on CIFAR-10N, RTE and NetEase-69, the deterministic control already passes at every first statistical crossing. NetEase-126 has occasional exceptions, but the deterministic rule is earlier on average. The statistical advantage is conditional on overlap and margin. Repeated caps and targets reuse data and are not treated as independent samples.
Together, the checks support the intended separation: the small-pool experiments assess how a hard shared budget is converted into completed assessments, while the long-pool analysis demonstrates when statistical evidence reduces revelation. The same valid certificate accommodates both regimes. The empirical contribution is a reproducible scheduling gain over completion-first controls, together with identified operating conditions for statistical early certification on real reports.
Strengthening the Evidence: Corrected Results, Market Utility, and Theoretical Scope
We thank the reviewer for recognizing our problem formulation and offering constructive suggestions. We have carefully considered the concerns and substantially revised the manuscript. We corrected the confidence bound (Section 4), clarified the objective (Section 5), reran the main experiments with timing analyses (Section 7.1, Tables 1-2), reported a high-contention contrast (Section 7.2), expanded market-decision discussion (Section 7.4), and formalized a hindsight benchmark (Appendix C).
W1/Q4 - Effect size, corrected bounds, and seed-level evidence. We agree that the original 1.6-point gain was modest. We corrected Eq. (5) using the Bardenet-Maillard radius and reran five methods with a common corrected certification/scheduling rule (B=200, M=30, ε=0):
Across 25 matched dataset-seed runs: 7 wins, 15 ties, 3 losses, averaging +0.28 certified edges (+0.93 percentage points). We report a modest descriptive gain, not proven superiority. First-certificate means condition on successful runs (13.5 fewer, about 29%). Appendix C now defines a hindsight upper bound from earliest valid prefix-crossing costs; its numerical gap remains unevaluated. Dataset-level first-certificate purchases and pool revelation:
W2 - Technical novelty, guarantees, and near-exhaustion. We strengthened Sections 4-5 to distinguish certificate validity from scheduler effectiveness. Theorem 1 combines established without-replacement concentration with simultaneous control over edges, deviations, and sample counts, preserving adaptive validity, not introducing a new inequality. Revised Eq. (7) formalizes maximizing completed valid certificates under a hard shared budget. BRCert forecasts completion costs, screens infeasible edges, and prioritizes affordable certificates without changing payments. A new three-edge example in Section 5 illustrates why margin-greedy can finish none while completion-priority finishes two. Proposition 1 is conditional on stable margins, not globally optimal; cheapest-first is optimal only with known fixed costs and equal values.
Among 143 corrected-bound BRCert certificates, mean ne/Me is 0.984, median 1.000, and none occurs below 90% revelation. The revised abstract no longer claims lower per-edge evidence requirements: the benefit is sequencing a shared budget toward completed assessments. Section 7.2 reports a corrected-bound high-contention contrast; a pass-rate variant shows a small average gain in that setting, and we do not claim universal superiority.
Q1 - What decision does a certificate support? We expanded Sections 3.2 and 7.4. A certificate qualifies a supplier pair for an incentive assessment of the declared batch and deviation family, conditional on KFCA and reference behavior. The platform may use qualified links or seek further evidence. It does not automatically authorize payment release, supplier removal, or a change of payment rules; unresolved is not a negative finding. Revised Definition 1 distinguishes ε=0 (weak payoff dominance, ties allowed) from ε>0 (strictly positive certified margin).
Q2 - Why count certified edges? Eq. (7) now explicitly states the equal-value pair-assessment objective, appropriate when completed links are the purchasable unit. For supplier breadth, revised Section 7.4 explains how priority could instead depend on newly covered endpoints per forecast completion cost. Under the corrected replay:
Q3 - Beyond crowdsourcing and toward federated clients. We revised Section 7.4 and the conclusion to clarify our evaluated setting: finite-batch, client-held categorical reports, not continuous FL model updates. We added Fact/RTE client mappings and 24-client synthetic tests (original radius):
In the synthetic replay BRCert is earlier but has slightly lower final coverage. Continuous-update transfer would require a new peer statistic and overlap model.