| paper | d4-conf-ijcai-2019-0587 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a fixed question set \(\mathcal Q\), answer sets \(\mathcal C_q\), and a distribution \(\mu\) with binary-rational masses over the observed answer signatures \(t=(t_q)_{q\in\mathcal Q}\), let \(a(t,u)=|\{q\in\mathcal Q:t_q=u_q\}|\) and \(p_\mu=\frac{1}{|\mathcal Q|}\sum_{t,u}\mu_t\mu_u a(t,u)\). Define \(Q_\mu(t,u)=\sum_{j=a(t,u)}^{|\mathcal Q|}\binom{|\mathcal Q|}{j}p_\mu^j(1-p_\mu)^{|\mathcal Q|-j}\), \(\gamma_\mu(t,u)=-\log Q_\mu(t,u)\), and \(d_R(t)=\sum_{u\in R}\mu_u\gamma_\mu(t,u)\). Find a nonempty set of signatures \(R\) maximizing \(\min_{t\in R}d_R(t)\).
A continuous crowd whose types are complete observed answer signatures on a fixed calibration batch, with mass \(\mu_t\) for each signature. The decision selects a set of signature types, and the objective maximizes the weakest selected type’s mass-weighted confidence degree under the population’s average agreement rate.
The mirror covers Theorem 1’s expert-core extraction objective. It leaves aside Theorem 2’s purity guarantee, Theorems 3 and 4’s majority-vote accuracy bounds, Top-2 aggregation, and the experimental claims.
My lead is Mass Expert-Core Extraction. The type is a complete answer signature \(t=(t_q)_{q\in\mathcal Q}\): two workers with the same signature are indistinguishable for the expert-core extraction problem, since they have the same agreement with every other worker. The society is a distribution \(\mu\) over the \(\tau\) signatures that occur, with \(\mu_t\) the fraction of workers having signature \(t\).
This is plausible for a large crowd repeatedly answering a fixed, relatively small calibration batch. If the batch and its answer options are fixed while the number of workers grows, the number of possible signatures is bounded by \(\prod_q |\mathcal C_q|\), and many workers can share each observed signature. The mirror is deliberately limited to core extraction: signatures suffice for that task, but not for every later question about workers’ latent accuracy or aggregation.
The anchor is Theorem 1, proved in this paper: “The expert core can be found in \(O(n^2m)\) time.” It constructs a complete graph whose vertices are workers and whose edge weight is \(-\log\) of a binomial-tail probability determined by their number of matching answers. Peeling the graph finds the subset maximizing its minimum weighted degree, equivalently minimizing the paper’s \(\theta(W)\). The peeling routine is standard prior work; the stated expert-core result and its runtime are established here.
Here is the continuous problem. Let \(m=|\mathcal Q|\), let \(a(t,u)=|\{q:t_q=u_q\}|\), and define the population’s average agreement rate by
\[
p_\mu=\frac{1}{m}\sum_{t,u\in T}\mu_t\mu_u a(t,u).
\]
For each pair of signatures, set
\[
Q_\mu(t,u)=\sum_{j=a(t,u)}^m \binom{m}{j}p_\mu^j(1-p_\mu)^{m-j},
\qquad
\gamma_\mu(t,u)=-\log Q_\mu(t,u).
\]
For a nonempty set of signatures \(R\subseteq T\), its selected mass is \(\mu(R)=\sum_{t\in R}\mu_t\), and its per-capita confidence degree at type \(t\in R\) is
\[
d_R(t)=\sum_{u\in R}\mu_u\gamma_\mu(t,u).
\]
Mass Expert-Core Extraction asks: given \(m\), the answer sets, and the binary-rational masses \(\mu_t\), find a nonempty \(R\subseteq T\) maximizing
\[
\min_{t\in R} d_R(t).
\]
A solution is the maximizing set \(R\) and its value. Equivalently, it minimizes \(\exp(-\min_{t\in R}d_R(t))\), the per-capita version of the paper’s worst-case product of tail probabilities. In a population of \(N\) workers, the corresponding log score scales as \(N d_R(t)\); the exclusion of an individual from their own neighborhood disappears in the high-multiplicity limit. A type’s mass is either all included or all excluded at an optimum: adding the rest of an already selected type cannot reduce anyone’s degree, since all the kernel weights are nonnegative and its members have identical neighborhoods.
The expected direction is tractable. The type-pair agreements and confidence weights can be formed in \(O(\tau^2m)\) arithmetic operations; weighted peeling then operates on the \(\tau\)-type graph. This preserves the question Theorem 1 answers while replacing a vertex for each worker with mass for each repeated signature. The paper’s stated runtime, like its peeling analysis, abstracts away exact bit-level comparisons of weighted degrees; a bit-complexity treatment of comparisons involving rational masses and logarithmic weights is a further question.
This mirror covers Theorem 1’s exact extraction problem, not the paper’s experiments or its claims about recovering true experts and correctly aggregating answers. Theorem 2 gives a probabilistic purity guarantee, but its sufficient number of questions grows as \(n^4\); I would not claim that guarantee transfers to this fixed-batch high-multiplicity regime. Nor do Theorems 3 and 4 provide complexity anchors: they analyze majority-vote accuracy. The paper supplies no comparable named hardness result, so Theorem 1 is the right anchor despite being algorithmic.
My weakest point is that the paper observes individual answer histories, while the continuous input groups identical histories. That compression is exact for core extraction, but the article does not study whether repeated signatures are common in its real datasets or whether its statistical guarantees survive this limit. The case stands as a mirror of the extraction problem and its graph-mining structure; it should not be read as a continuous version of the paper’s full latent-expertise and answer-aggregation theory.
Theorem 1 is a real computational anchor: it gives an \(O(n^2m)\) algorithm for extracting the paper’s core. The strongest objection is that its natural type, a worker’s full answer transcript on the fixed question batch, is an observed random outcome rather than a stable kind of worker. Under the paper’s noisy model, transcript classes can mix experts and non-experts. With a fixed batch, repeated transcripts may be common, but Theorem 2’s purity guarantee does not cover that limit: its sufficient bound on \(m\) grows as \(n^4\). In a regime where \(m\) grows rapidly, full transcripts are likely to be unique, so the compression disappears.
A more stable type would describe a worker’s conditional response behavior across questions. That gives a plausible population model, but it no longer supplies the realized pairwise agreements used by Theorem 1. Replacing those agreements with expected ones creates a new population-level inference problem; it does not directly mirror the paper’s exact extraction algorithm. And if the response-behavior types and their masses are given, the difficult question of inferring expertise from answers has already been bypassed.
This makes the proposed mirror narrower than the paper’s substantive aim. It covers a deterministic graph-selection routine, but not the claim that the selected workers are experts or that their answers improve aggregation. Its likely computational result is also modest: form a weighted graph on the \(\tau\) observed transcript types and run peeling in \(O(\tau^2m)\) time.
Still, that objection does not defeat the anchor. For Theorem 1 itself, transcripts are a complete type description: the extraction objective uses only the observed answers, and grouping identical rows preserves that information. With a fixed, bounded questionnaire and a large crowd, a distribution over those transcripts is a coherent high-multiplicity input. The mass-weighted peeling formulation is therefore a legitimate continuous mirror, even if it says little about latent expertise and offers limited new algorithmic insight.
So the negative case is weak at its central point. The paper has a computational result, and its extraction task admits a sensible continuous formulation. I would argue that the mirror’s scope and payoff are limited, but I cannot honestly support the universal claim that no worthwhile mirror exists.
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.