acceptodds
Under review as a conference paper at ICLR 2027

Certify What the Budget Can Reach: Peer Assessment in Federated Data Markets

Abstract

In federated data markets, evaluating decentralized client contributions without central ground truth or public validation sets is a core challenge. Peer prediction addresses this by rewarding informative reports via peer cross-validation, yet its theoretical guarantees often become operationally unusable in practice. Because distributed supplier pairs share only scarce task overlap, the platform must ration a limited assessment budget across many candidate pairs. Existing mechanisms assume fixed task assignments, while sequential allocation methods merely reduce generic uncertainty; neither assesses whether the remaining budget and local overlap can actually complete statistically defensible incentive evidence. Consequently, cautious schedulers often exhaust the entire budget without certifying any supplier, even when multiple certificates were affordable. We formalize this missing objective as budget-reachable certification under adaptive sampling and heterogeneous finite pools. We propose BRCert, which pairs simultaneous finite-population confidence bounds with a lookahead estimator of each edge’s remaining certification cost. BRCert prunes unreachable pairs and concentrates purchases on the most affordable reachable certificates without modifying the underlying payment rule. Across five real-world markets, BRCert achieves the highest mean certified coverage with zero false certificates under exact audits, outperforming the strongest baseline by 1.6% on average in the main setting. The gain increases to 1.9% with 50 candidate edges, demonstrating that finite-batch incentive design must prioritize completed evidence over diffuse exploration.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
data markets, federated learning, peer prediction, incentive certification, adaptive sampling

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_yMDvOpenReview ↗
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
AuthorsOpenReview ↗

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=200B=200, M=30M=30, ε=0\varepsilon=0):

MetricBRCertMarginForcedEXCA-greedyUnc.
Coverage.191.181.168.156.000
First-cert.32.746.234.458.4--

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:

DatasetFirst (BR/Mg)Certsn_e/M_eExh.
CIFAR-10N21.2/42.641.948.171
Fact24.8/47.432.999.969
NetEase-6935.6/51.0231.0001.000
RTE34.2/39.822.995.909
NetEase-12647.6/50.4251.0001.000

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/Men_e/M_e 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\varepsilon=0 (weak payoff dominance, ties allowed) from ε>0\varepsilon>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:

SchedulerCoverageEdgesSuppliers
BRCert.1915.727.60
Margin-greedy.1815.447.40

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):

SettingCoverage (BR / Mg)First-cert. (BR / Mg)
Fact workers as clients.220 / .20025.0 / 47.4
RTE workers as clients.147 / .14029.2 / 39.8
24 synthetic clients.233 / .24023.6 / 32.4

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.

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.

AuthorsOpenReview ↗

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 settingOriginal BRCert coverageMargin-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 pep_e from observed joint gap vectors. When positive-score edges whose remaining pools fit the residual budget exist, it ranks those edges by pe/Rep_e/R_e. If none fits, it uses unrestricted pe/Rep_e/R_e; 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 B=200B=200, 50 candidates, pool cap 60 and ε=.05\varepsilon=.05:

SchedulerMean certificatesCoverage
Budget-aware pass-rate variant4.724.09448
Previous pass-rate variant4.550.09100
Remaining-pool4.298.08596
Original BRCert4.278.08556
ForcedEX3.892.07784
Margin-greedy2.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.

AuthorsOpenReview ↗

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 Sf(n)S_f(n), it certifies using

De(n)=min⁡fSf(n)−2(Me−n)Me.D_e(n)=\min_f\frac{S_f(n)-2(M_e-n)}{M_e}.

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 M=480M=480 and ε=.05\varepsilon=.05, 249 of the 250 edge instances (five seeds, 50 candidates each) have exact full-pool margins meeting the target:

Certification ruleMean revealed fraction at first certification
Corrected statistical bound.8064
Exact-support deterministic completion bound.8968
Exhaustion1.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 B=200B=200 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.

Reviewer_vEYJOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper considers a data market where a platform pays suppliers through a peer-prediction rule and has a limited budget for revealing shared tasks on supplier pairs (edges). An edge is certified when a lower confidence bound on its truthful payoff advantage exceeds ε, and Theorem 1 shows the bounds stay valid under adaptive selection. BRCert spends the budget on edges that can still reach certification, preferring the ones cheapest to finish. On five crowdsourcing datasets, it has the best mean coverage, 1.6 pp above margin-greedy on average, with no false certificates.

Critical strengths
  1. Validity and scheduling are cleanly separated. Every scheduler uses the same certificate test, which stays valid under adaptive selection, so the comparison is fair and a poor reachability estimate can only cost coverage. The objective is stated precisely.
Critical weaknesses
  1. The empirical gain is small. Gains over margin-greedy are 0.6–4.0 pp, comparable to the reported standard errors (0.8–3.2 pp), and with 30 edges one certified edge is already 3.3 pp. In the sensitivity studies BRCert ties or loses in several settings.
  2. The experiments are incomplete and hard to reproduce. The paper claims nine schedulers but Table 1 shows seven, and the ablation doesn't remove any part of BRCert. The supplementary code contains only BRCert, although the Reproducibility Statement says the baselines and table scripts are included.
  3. The tested regime makes the problem and the guarantee close to trivial. With pools of 30 tuples and a union bound, the confidence radius stays above any realistic margin until nearly the whole pool is revealed (about 28 of 30 tuples by my calculation from Eq. (5)). Scheduling then reduces to finishing the edges closest to exhaustion, and zero false certificates is expected, since the remaining tuples can't flip the sign of the margin.
  4. The theory is thin and the framing doesn't match the experiments. Theorem 1 is a standard concentration bound plus a union bound, and Proposition 1 restates the definition of the required sample count. The title refers to federated data markets, but the experiments replay crowdsourcing annotation logs without any federated learning.
Questions for authors
  1. Please release the baselines and the scripts for Tables 1–4 and Figures 2–3.
  2. What fraction of the pool had been revealed when each certificate was issued? Results with larger pools and ε > 0 would help.
  3. The formulation includes heterogeneous costs and degree limits, but the released code uses unit costs. How do they enter the experiments?
  4. Which nine schedulers were evaluated, and where are the Uncertainty Sampling results?
  5. If the federated framing stays, at least one experiment with federated clients is needed. Otherwise the title should match the crowdsourcing setting that is actually evaluated.
2 comments
AuthorsOpenReview ↗

Response to Reviewer vEYJ [1/2]

We sincerely thank the reviewer for the careful and constructive assessment. We have already revised the manuscript to address the concerns about effect size, near-exhaustion, theoretical novelty, and the claimed scope. In particular, we corrected the confidence radius (Section 4, Eq. (5)), reformulated the objective (Section 5, Eq. (7)), reran the main experiments (Section 7.1, Tables 1-2), added a high-contention contrast and sensitivity analyses (Sections 7.2-7.3), and tempered the abstract and conclusion.

W1 - Effect size and practical value. We agree that the originally reported coverage gains alone were too small to justify a strong superiority claim. The revised Section 7.1 and Tables 1-2 use the corrected Bardenet-Maillard radius for both certification and scheduling across matched methods (B=200B=200, M=30M=30, ε=0\varepsilon=0):

MetricBRCertMarginForcedEXCA-greedyUnc.
Coverage.191.181.168.156.000
First-cert.32.746.234.458.4--

Across 25 paired dataset-seed runs versus Margin-greedy the outcome is 7 wins/15 ties/3 losses, an average gain of 0.28 edges (0.93 percentage points). This is a modest descriptive gain, not a statistically established superiority; BRCert ties on NetEase-69 and trails on NetEase-126. First-certificate means condition on runs that issue a certificate; we do not claim per-run dominance. BRCert requires 13.5 fewer purchases (about 29%). The revised abstract and conclusion highlight budget sequencing and early completion, rather than overstating the small terminal-coverage gain.

W3/Q2 - Near-exhaustion and nontrivial scheduling. We have directly verified the reviewer's calculation in revised Table 2. Among 143 BRCert certificates under the corrected bound, ne/Men_e/M_e has mean 0.984, median 1.000, and IQR [0.967,1.000]; none is issued below 90% of its edge pool.

DatasetFirst (BR/Mg)Certsn_e/M_eExh.
CIFAR-10N21.2/42.641.948.171
Fact24.8/47.432.999.969
NetEase-6935.6/51.0231.0001.000
RTE34.2/39.822.995.909
NetEase-12647.6/50.4251.0001.000

We now explicitly acknowledge that BRCert does not materially reduce per-edge sample requirements. The relevant optimization is instead across competing edges: directing the finite global budget to assessments that can be completed can produce valid certificates, whereas spreading purchases across unfinished candidates may produce none.

We have further added Section 7.2 under the corrected radius. Remaining pool length approximates completion cost when certificates nearly exhaust the pool; at a positive target we also consider the chance of passing if exhausted and rank by pe/Rep_e/R_e (256-draw bootstrap; ReR_e=remaining samples). Certificates still use the corrected Bardenet bound (B=200B=200, M=60M=60, 50 candidates):

SchedulerCov. (eps=0.05)First (eps=0.05)Cov. (eps=0)First (eps=0)
Pass-rate.08846.5.10141.8
Original BRCert.08548.0.09042.2
Remaining-pool.08548.9.09142.3
Margin-greedy.05888.2.06287.7

Paired W/T/L versus remaining-pool: 7/15/3 (mean +0.16) at ε=0.05\varepsilon=0.05 and 8/17/0 (mean +0.48) at ε=0\varepsilon=0; 0 false certificates. Original BRCert ties remaining-pool at ε=0.05\varepsilon=0.05 (0/25/0). This is a small average coverage gain in this high-contention setting, not a general advantage. First-certificate purchases are auxiliary. Section 7.3 remains original-radius.

W4 - Theory and contribution. We have revised Sections 4-5 to separate statistical validity from scheduling. We do not claim a new concentration inequality: Theorem 1 applies a simultaneous finite-pool bound across edges, deviations, and sample counts to preserve certification validity under adaptive selection. The newly explicit objective in Eq. (7) values completed incentive certificates before a hard budget, not generic uncertainty reduction. BRCert's distinctive design estimates the remaining cost to cross a fixed valid threshold, screens unreachable edges, and prioritizes affordable completions without changing peer payments. Proposition 1 is a conditional completion statement under stable empirical margins, not a global optimality theorem. We have added a concrete scheduling example in Section 5.

Finally, we revised Definition 1 and the scope discussion to clarify that ε=0\varepsilon=0 permits zero-margin ties (weak payoff dominance), whereas ε>0\varepsilon>0 requires a strictly positive certified margin; our claims concern finite-batch reporting deviations, not semantic correctness, collusion-proofness, or dynamic incentive compatibility.

AuthorsOpenReview ↗

Response to Reviewer vEYJ [2/2]

We thank the reviewer for pinpointing omissions and mismatches between the description, experiments, and released material. We have revised the manuscript and supplementary material to make the methods, bounds, and deployment claims auditable. We respond to W2 and Q1/Q3-Q5, and clarify the experimental scope that also bears on W4.

W2/Q1/Q4 - Nine schedulers, missing baselines, and reproducibility. The reviewer is correct: the submission referred to nine schedulers but displayed only seven in its main table, and the original ablation mislabeled a Margin-greedy comparison as "Uncertainty Sampling." We corrected the nomenclature and now explicitly identify all nine. Revised Table 3 reports their original-radius main-setting coverage and first-certificate purchases:

SchedulerCoverageFirst-cert.
BRCert (FCL).19532.2
Margin-greedy.18146.2
ForcedEX (CL-UCB).16834.4
CA-greedy.15658.4
TaS-FG (CAP-UCB).111103.2
APT.07594.0
Uniform / Max-overlap / Unc..000--

We separate this inventory from revised Table 1, where five methods were rerun under the corrected common confidence radius. We do not claim that original-radius results were obtained under the corrected bound. The revised reproducibility statement specifies a supplementary archive with a nine-method runner, launch scripts, recorded results, and a README identifying the public raw datasets. This addresses the earlier mismatch between the Reproducibility Statement and the supplied code; the main text also lists the method aliases and shared evaluation protocol.

Q3 - Heterogeneous costs and degree limits. The reviewer correctly identified that the submitted main experiments used unit cost and no degree cap. We now state that explicitly (Section 7). The model permits ce>0c_e>0 and workload limits did_i; the revised reachability calculation enforces affordability through ⌊Bt/ce⌋\lfloor B_t/c_e\rfloor, and the fallback must respect feasible purchases. Additional inverse-pool and load-weighted replays probe whether cost-sensitive prioritization changes the ranking (original radius; BRCert / Margin-greedy coverage):

WeightingCoverage (BR / Mg)Notes
Unit.195 / .181sample-count budget
Inverse-pool.195 / .181sample-count budget
Load.189 / .181first-cert. gap falls to 3.4

These replays retain a sample-count budget and modify scheduler priorities, rather than implementing a fully heterogeneous monetary budget; they also impose no degree limits. We have therefore described them as cost-weighting sensitivities, not full empirical validation of heterogeneous-cost/degree-constrained deployment. Those extensions remain a limitation.

Q5/W4 - Why "federated," and what is actually tested? We agree that crowdsourced annotation replay is not a federated-learning training experiment. The model studies peer assessment among decentralized suppliers with privately held categorical reports; it does not require raw reports to be pooled for model training, nor does it certify continuous model updates. Revised Section 7.4 adds client-organized categorical-report cases (original radius):

SettingCoverage (BR / Mg)First-cert. (BR / Mg)
Fact workers as clients.220 / .20025.0 / 47.4
RTE workers as clients.147 / .14029.2 / 39.8
24 synthetic clients.233 / .24023.6 / 32.4

The synthetic case illustrates a limit: BRCert reaches a certificate earlier but has slightly lower terminal coverage. These experiments do not validate FL model training. We have narrowed the text to "peer assessment in federated data markets" understood as client-held discrete reports, and identify continuous-update FL as future work.

Scope of the empirical guarantee. All schedulers in a matched comparison share the same finite pools, random reveal order, initial 20% history, and final certificate test; the main replay uses 30 candidate edges, M=30M=30, B=200B=200, δ=0.1\delta=0.1. The Section 7.2 high-contention contrast uses the corrected bound with 50 candidates, M=60M=60, and B=200B=200, and is documented in the supplement (original BRCert is FCL; the pass-rate variant is fcl_pass_rate; remaining-pool is fcl_pool_only). The exact-pool audit found no false certificates; this tests a finite-pool payoff criterion, not ground-truth annotation correctness. At ε=0\varepsilon=0, zero-margin ties are allowed, so strictly positive incentive separation requires ε>0\varepsilon>0.

Reviewer_symXOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies budget allocation for peer assessment when each supplier pair has a finite pool of shared tasks. It proposes BRCert, which estimates the additional cost of completing an incentive certificate and prioritizes certificates that remain affordable. The method combines this allocation rule with simultaneous confidence bounds. Experiments on five annotation markets compare the resulting certified-edge coverage with alternative sampling strategies.

Critical strengths
  1. The paper identifies a meaningful operational problem. Under a hard assessment budget, reducing uncertainty across many pairs can leave the platform with few completed evaluations. Making certificate completion the allocation objective gives the work a clear motivation and leads to a simple, actionable scheduling principle.
  2. The evaluation is well aligned with that objective. Five real annotation datasets, comparisons with several allocation strategies, and sweeps over budget, pool size, and candidate-set size provide a reasonably broad picture of the proposed method. The results consistently favor BRCert in the main setting and help explain why its advantage is more visible when many candidate pairs compete for a limited budget.
Critical weaknesses
  1. The technical advance is relatively modest. The certificate construction builds on established concentration tools, and the scheduling rule is a plug-in estimate of completion cost followed by greedy selection. The theoretical results mainly establish certificate validity and completion under stable estimated margins; they offer limited insight into the effectiveness of the allocation policy itself. The contribution therefore rests primarily on the problem formulation and the empirical usefulness of this simple rule.
  2. The improvement over the closest greedy baseline is small on several datasets. In Table 1, the gains over Margin-greedy are below one percentage point on both NetEase datasets and RTE, with the larger gains concentrated on CIFAR-10N and Fact. The sensitivity results also show settings where the methods tie. This makes the practical benefit dependent on the assessment regime and limits the breadth of the empirical impact.
Questions for authors
  1. What characteristics of the overlap pools and incentive margins best explain the larger gains on CIFAR-10N and Fact? This might help readers judge when completion-cost scheduling is likely to be useful in another market.
1 comment
AuthorsOpenReview ↗

Substantial Revisions: Clarifying When Budget-Reachable Certification Helps

We sincerely thank the reviewer for the helpful feedback and recognition of our problem formulation. We have carefully considered the concerns and substantially revised the manuscript throughout. We corrected the confidence bound (Section 4), clarified the objective and scheduling rationale (Section 5), reran the main comparisons and added certificate-timing results (Section 7.1, Tables 1-2), expanded budget-contention analyses and baselines (Section 7.2), and revised the abstract and conclusion.

W1 - Technical contribution. We agree the technical ingredients are simple. Revised Section 4 makes clear that Theorem 1 uses an established without-replacement concentration inequality, with simultaneous control across edges, deviations, and sample counts; we do not claim a new inequality. This ensures certificate validity under adaptive selection. Revised Section 5, Eq. (7) now explicitly maximizes completed certificates before a hard terminal budget, not generic uncertainty reduction.

The central distinction is promising margins versus affordable completion: a high-margin edge can require more purchases than the remaining budget or pool permits. BRCert estimates evidence-to-completion, screens unreachable edges, and prioritizes affordable certificates, while always applying the unchanged valid test. We added a three-edge example in Section 5 where margin priority spends two remaining purchases without certification, whereas completion-cost priority completes two. We also clarified that cheapest-first ordering maximizes the affordable count only with fixed known costs, equal certificate values, and a scalar budget. With adaptive estimated margins, BRCert is a heuristic, not globally optimal; Proposition 1 is conditional on stable margins.

W2 - Corrected and more informative empirical evaluation. We agree that the original coverage gain was modest. We corrected Eq. (5) using the Bardenet-Maillard radius and reran the main setting, applying the same corrected rule to all compared schedulers (B=200B=200, M=30M=30, ε=0\varepsilon=0):

MetricBRCertMarginForcedEXCA-greedyUnc.
Coverage.191.181.168.156.000
First-cert.32.746.234.458.4--

Across 25 paired dataset-seed runs, there are 7 wins, 15 ties, 3 losses; the mean gain is 0.28 edges (0.93 percentage points). We present this as a modest descriptive result, not statistically established superiority. First-certificate means condition on successful runs (13.5 fewer, about 29%). For 143 corrected-bound BRCert certificates, mean ne/Me=0.984n_e/M_e=0.984, median 1.000, and none occurs before 90% revelation. The revised abstract and conclusion emphasize earlier completion across competing edges, not lower per-edge sample requirements.

Q1 - Why CIFAR-10N and Fact, and when is scheduling valuable? Revised Table 2 reports dataset-level timing and pool evidence:

DatasetFirst (BR/Mg)Certsn_e/M_eExh.
CIFAR-10N21.2/42.641.948.171
Fact24.8/47.432.999.969
NetEase-6935.6/51.0231.0001.000
RTE34.2/39.822.995.909
NetEase-12647.6/50.4251.0001.000

CIFAR-10N certificates reveal 94.8% of their pools on average, with 17.1% at exact exhaustion; Fact and NetEase certificates typically require nearly the full pool. These patterns suggest differing completion costs, without establishing which pool or margin features cause the differences.

We revised Section 7.2 with a corrected-bound high-contention contrast (B=200B=200, M=60M=60, 50 candidates, 25 paired runs). Remaining pool length approximates completion cost when certificates nearly exhaust the pool; at a positive target we also account for the chance of passing if exhausted, ranking by pe/Rep_e/R_e. Under the common corrected certificate:

SchedulerCov. (eps=0.05)First (eps=0.05)Cov. (eps=0)First (eps=0)
Pass-rate.08846.5.10141.8
Original BRCert.08548.0.09042.2
Remaining-pool.08548.9.09142.3
Margin-greedy.05888.2.06287.7

Paired W/T/L versus remaining-pool: 7/15/3 (mean +0.16) at ε=0.05\varepsilon=0.05 and 8/17/0 (mean +0.48) at ε=0\varepsilon=0; 0 false certificates. The small average gain is concentrated on RTE and Fact; there is a small net loss on NetEase-69. Original BRCert ties remaining-pool at the positive target (0/25/0). These outcomes concern this high-contention setting, not a general advantage. The main-experiment observations above continue to refer to Section 7.1. Section 7.3 remains the original-radius inventory.

Reviewer_N4RPOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BRCert, an allocation method for certifying supplier pairs when assessment purchases share a limited budget and each pair has a finite task pool. It estimates the additional observations needed for a lower confidence bound on the minimum reporting-payoff margin to reach a threshold, then prioritizes affordable completions. Its contributions are a certificate-count objective under a fixed peer-payment rule, a completion-cost heuristic, and a simultaneous confidence argument for adaptively sampled, randomly ordered finite pools. Replays of five annotation markets compare schedulers using common histories and pools, reporting higher mean coverage than margin-greedy in the main zero-target setting and auditing certificates against the complete pools.

Critical strengths

The paper turns finite assessment resources into a concrete allocation objective and provides evidence that targeting it helps. An Optimal Algorithm for the Thresholding Bandit Problem, Section 2.1, addresses fixed-budget classification of the arm set, while An Anytime Algorithm for Good Arm Identification, Algorithm 1 and Section 4, concentrates evidence toward identifying a good arm. BRCert adds a distinct operational target: completing as many certificates as possible across exhaustible pools while permitting unresolved pairs. Equation (7) connects that target to the remaining budget and overlap without changing the payment rule.

Table 1 favors BRCert over margin-greedy on mean coverage across the five datasets. In the pooled candidate sweep, the methods tie with few candidates and separate as more pairs compete for the budget (Table 4b). This supports the proposed use case, rather than a general claim that concentration always wins. The main gain is modest—roughly half an additional certificate per 30-pair run on average—but it comes from a simple scheduling change under shared pools and histories. Margin-greedy is a relevant ablation because it retains promising-edge selection while removing the completion calculation. Together, these results support a useful, narrowly scoped methodological contribution.

Critical weaknesses

The advertised validity guarantee requires a concentration step that the supplied proof does not establish. Every coverage comparison is interpreted through the common certificate, so its statistical justification is central. Equation (5) uses the squared correction (M−n)/(M−1)(M-n)/(M-1). Corollary 2.5 of Concentration Inequalities for Sampling Without Replacement instead gives 1−(n−1)/M1-(n-1)/M for n≤M/2n\le M/2, and (1−n/M)(1+1/n)(1-n/M)(1+1/n) otherwise. With K=∣E∣(∣F∣−1)Mmax⁡K=|E|(|F|-1)M_{\max}, assigning each tail failure probability δ/(2K)\delta/(2K) gives the same range multiplier 4ae4a_e and logarithm log⁡(2K/δ)\log(2K/\delta) as the manuscript, so the difference remains after matching constants.

Appendix A.1 asserts the manuscript's correction without deriving it. Another argument could justify it; the comparison above is not a counterexample. Alternatively, using the cited correction would supply the missing concentration step while preserving the overall allocation framework. This makes the issue a potentially local repair, rather than evidence against the finite-pool formulation. Its empirical consequence remains unresolved because the radius also determines purchase order and stopping. The exact-pool audits are useful checks on the reported runs, but do not replace the simultaneous probability guarantee.

Questions for authors
  1. Proof and validation: Can you justify Equation (5)'s correction, or report whether the main allocation advantage persists with the cited Hoeffding–Serfling radius?
  2. Certificate interpretation: Does the implementation use LCB≥ε\mathrm{LCB}\ge\varepsilon, as in Definition 1, or LCB>ε\mathrm{LCB}>\varepsilon, as suggested by Algorithm 1? This determines whether zero-margin ties count in the main setting.
1 comment
AuthorsOpenReview ↗

Substantial Revisions: Corrected Validity Guarantee, Experimental Evidence, and Certificate Interpretation

We sincerely thank the reviewer for the constructive assessment and for recognizing our budget-reachable certification objective. We have taken the proof gap and ambiguity about ties very seriously and substantially revised the manuscript: correcting the confidence bound and proof (Section 4; Appendix A), updating the forecast and algorithm (Section 5), rerunning the main comparison (Section 7.1; Tables 1-2), and revising the abstract, discussion, and conclusion.

W1/Q1 - Correcting Eq. (5) and establishing adaptive validity. We agree: the submitted proof did not justify the squared factor (M−n)/(M−1)(M-n)/(M-1). We replaced it with Bardenet-Maillard's (2015, Corollary 2.5) Hoeffding-Serfling correction. Revised Eq. (5) is

re(n,δ)=4aeρ(n,Me)log⁡(2K/δ)2n,K=∣E∣(∣F∣−1)Mmax⁡,r_e(n,\delta)=4a_e\sqrt{\frac{\rho(n,M_e)\log(2K/\delta)}{2n}},\quad K=|E|(|\mathcal F|-1)M_{\max},

where ρ(n,M)=1−(n−1)/M\rho(n,M)=1-(n-1)/M for n≤M/2n\le M/2 and ρ(n,M)=(1−n/M)(1+1/n)\rho(n,M)=(1-n/M)(1+1/n) otherwise. At n=Mn=M the finite-pool mean is exact, so re(M,δ)=0r_e(M,\delta)=0. Both the theorem and the algorithm now use this correction.

Rewritten Appendix A.1 now provides the missing derivation. Conditional on a declared pool, fix edge ee, deviation f≠f⋆f\ne f^\star, and prefix length nn. The gaps Ws=ae[Xe,s(f⋆)−Xe,s(f)]W_s=a_e[X_{e,s}(f^\star)-X_{e,s}(f)] lie in [−2ae,2ae][-2a_e,2a_e] and are sampled in random order without replacement. Applying the cited bound to WsW_s and −Ws-W_s bounds each tail by δ/(2K)\delta/(2K). Unioning over at most KK edge-deviation-prefix triples yields one event with probability at least 1−δ1-\delta covering all prefixes. Minimizing over deviations preserves the bound on Γe\Gamma_e. Appendix A.4 clarifies adaptivity: a scheduler selects only prefixes already covered by this event; cross-edge independence is unnecessary. Thus Theorem 1 validates every certificate under the corrected radius and Assumption 1.

W1/Q1 - Recomputing results, not just changing the proof. Because the radius affects both purchase ordering and certification, we reran the main comparison from the outset with the corrected bound in both the forecast and test (3030 candidates, M=30M=30, B=200B=200, δ=0.1\delta=0.1, ε=0\varepsilon=0, five seeds):

MetricBRCertMarginForcedEXCA-greedyUnc.
Coverage.191.181.168.156.000
First-cert.32.746.234.458.4--

Across 25 paired runs BRCert has 7 wins/15 ties/3 losses, gaining 0.28 edges (0.93 percentage points) on average: a modest descriptive, not statistically proven, gain. First-certificate means condition on runs issuing a certificate (about 29% fewer purchases than Margin-greedy). Comparisons share pools, warm starts, reveal orders, and the final test. All certificates passed exact-pool audits; audits are not a replacement for the proof.

Revised Table 2 reports certificate timing and revelation under the corrected bound:

DatasetFirst (BR/Mg)Certsn_e/M_eExh.
CIFAR-10N21.2/42.641.948.171
Fact24.8/47.432.999.969
NetEase-6935.6/51.0231.0001.000
RTE34.2/39.822.995.909
NetEase-12647.6/50.4251.0001.000

Among 143 corrected-bound BRCert certificates, mean ne/Men_e/M_e is 0.984, median 1.000, and none appears before 90% of the edge pool is revealed. The scheduling advantage concerns how a shared budget is sequenced across edges, not substantial savings in each edge's own sample requirement. Original-radius sensitivity sweeps are labeled separately in Section 7.3.

Q2 - Resolving LCB≥ε\mathrm{LCB}\ge\varepsilon versus strict inequality. We appreciate this important inconsistency. Revised Definition 1 and Algorithm 1 consistently use LCBe≥ε\mathrm{LCB}_e\ge\varepsilon to issue certificates. Thus ε=0\varepsilon=0 allows an exact zero-margin tie (including at full-pool exhaustion), establishing weak payoff dominance within the declared deviation family, not strict advantage. We added this explanation to Section 4 and the experimental analysis: 7.0% of corrected-main-run BRCert certificates have zero exact margin. For ε>0\varepsilon>0, the certified margin is strictly positive. Section 5's separate positive plug-in-slack screen only forecasts reachability; it does not alter the common certificate test. Positive-target sweeps using the original radius remain explicitly labeled.

The revised abstract and conclusion distinguish proved certificate validity from empirical scheduler effectiveness, and acknowledge near-exhaustion of individual pools. The revised proof, algorithm, experiments, and claims now align with the justified confidence bound, while preserving the finite-budget certification objective.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.