| paper | d4-conf-ijcai-2016-0661 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Lemma 3.5
Given a continuum worker pool with task-specific effort costs distributed according to μ on \([0,c_{\max}]\), \(N\), \(b\), \(P_L\), and \(P_H\), and an evaluation oracle for \(F\), choose a bonus \(B ≥ 0\) maximizing the paper's relaxed PA requester objective \((PB)\). Each task draws \(N\) workers from the pool; workers use the paper's threshold effort strategy and the objective uses its stated PA cutoff equation and majority approximation. Assume the PA conditions of Lemma 3.5: \(f\) is twice differentiable with \(f''(c) ≥ 0\), and \(cF(c)\) is convex.
A mass distribution μ over worker task-cost types in a large eligible pool; each task samples a finite group of \(N\) workers, whose threshold effort choices and peer-agreement bonuses determine the relaxed requester objective. The decision is the bonus \(B\), and the objective is expected majority accuracy minus base and bonus payments under the paper's PA approximation.
Costs are redrawn independently for each worker-task pair, so the proposed mass may represent the prior \(F\) rather than persistent worker types; the proponent notes the close relationship but does not resolve this distinction.
fatal: False
The mirror covers only the known-distribution, static PA bonus optimization of Lemma 3.5, including the paper's relaxed objective and majority approximation. It leaves the GA results, equilibrium characterizations, and sequential learning and regret results aside.
The strongest case is a narrow one: mass-population PA bonus selection. The paper has no named NP-hardness result or standard \(P\)-classification. Its best computational anchor is Lemma 3.5, proved in the paper: for the requester’s relaxed static bonus-optimization problem \((PB)\), if (i) \(f\) is twice differentiable with \(f''(c)\ge 0\), and (ii) \(cF(c)\) is convex, then the objective is concave under peer output agreement (PA). It also states that under (ii) and (iii)—where \(G(c)=1-[(\alpha-1)F(c)+1]^{N-1}\), \(\alpha=e^{-2(P_H-P_L)^2}\), has a nonnegative third derivative—the objective is concave under group output agreement (GA). The appendix’s proof appears to require the opposite sign for \(G'''\); I would rely only on the PA branch. The paper says these concavity results make the relaxed optimization efficiently solvable. That is a real algorithmic anchor, though not a formal bit-complexity theorem.
Here is the mirror I would put to a prover. Mass-PA Bonus Selection takes \(N\ge2\), base payment \(b\), accuracies \(0.5<P_L<P_H\), a maximum effort cost \(c_{\max}\), and a known cost distribution \(\mu\) on \([0,c_{\max}]\) with CDF \(F\) and density \(f\) satisfying the PA conditions of Lemma 3.5. It asks for a bonus \(B^*\) maximizing the paper’s relaxed requester objective \((PB)\), evaluated at the symmetric PA equilibrium: workers with cost at most the equilibrium cutoff exert effort; workers report their binary answer truthfully; each worker’s bonus depends on agreement with a randomly selected peer; and the requester aggregates answers by majority vote. A solution is an optimal bonus, or, in an approximate version, a bonus whose relaxed utility is within \(\varepsilon\) of the maximum. As in the paper, \((PB)\) uses its stated approximation to majority correctness and drops the \(2P_L-1\) term in the PA cutoff equation. Lemma 3.5 predicts a tractable, one-dimensional concave optimization under its assumptions. A bit-complexity classification would still need a finite representation of \(F\); with an evaluation oracle, the natural claim is tractability in the convex-optimization oracle model.
In this mirror, a type is a worker’s effort cost for the task, with \(P_L\) and \(P_H\) shared across workers. The mass \(\mu(A)\) is the fraction of a very large eligible crowd whose task cost lies in \(A\). A crowdsourcing platform with a large worker pool, many workers drawn from the same cost distribution, and a fixed-size random assignment of \(N\) workers to each task is a plausible regime. The pool is the continuum; each task still uses the paper’s finite assigned group. The paper’s threshold equation makes the match especially close: equilibrium behavior depends on \(F(c)\), the mass below a cutoff.
The authors would likely recognize the question: it keeps their requester, PA mechanism, effort incentives, majority accuracy, and bonus objective intact. The mirror covers the known-distribution, static PA optimization result only. It does not claim to continuize the sequential learning problem or the GA analysis.
My weakest point is that the paper already puts a common cost distribution \(F\) at the center of its analysis. Recasting that distribution as realized population mass may be nearly a change in interpretation, and the exact relationship between a finite random sample and the mass model needs to be stated carefully. The mirror also extends the type space from a finite set to a continuous cost interval, and Lemma 3.5’s efficiency claim depends on an approximate objective and an unspecified finite encoding for the distribution. Those limitations keep this from being a strong new complexity result. Still, the population is the object represented by mass, and the paper’s named concavity result gives a concrete algorithmic question rather than a loose continuum analogy.
The PA mirror is the strongest anchor, but its proposed population interpretation leaves the interaction group finite. Each task still draws \(N\) workers, and each worker’s effort cost is redrawn for that worker–task pair. The “continuum pool” therefore enters only through the sampling distribution \(F\). The paper already uses that same \(F\) to characterize the equilibrium cutoff and optimize the requester’s relaxed objective. Recasting \(F\) as the pool’s mass distribution leaves the computational problem unchanged: it is the paper’s own one-dimensional PA optimization. Lemma 3.5 gives a concavity result for that problem, though it is not a formal bit-complexity classification; its PA claim concerns the paper’s relaxed objective, including its majority approximation.
Making the interacting group itself continuous changes the result more fundamentally. In the paper’s main regime \(P_L>1/2\), workers need no effort for each answer to be correct with probability above one half. As group size grows, majority accuracy tends to \(1\) even at \(B=0\). With per-capita costs, the requester then has no accuracy reason to pay bonuses; with the paper’s unnormalized total costs, utility instead becomes scale-dependent. A limit that retains a nontrivial accuracy–payment tradeoff would need a different scaling or objective. At \(P_L=1/2\), the limit has a discontinuity: zero effort gives chance accuracy, while any fixed positive effort mass drives majority accuracy to \(1\). That may motivate a separate mean-field analysis, but it does not preserve the anchored optimization problem.
There is a plausible way to escape both objections: give workers persistent cost types, scale the assigned group with the population, and choose a normalized objective that avoids majority saturation. But persistence changes the paper’s worker–task cost model, and the altered objective has no computational result here to mirror. My negative case is therefore strongest against the stated PA anchor, rather than a proof that no author-recognizable variant could ever be worth studying.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.