| paper | d4-conf-ijcai-2017-0056 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: rank alternatives in nonincreasing order of their total approval masses \(w_a=\sum_{(r,S):\,a\in S}\mu_{r,S}\), resolving equal scores arbitrarily. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(m\), a known \(0<\phi<1\), and binary-rational masses \(\mu_{r,S}\) summing to one over randomized-approval types \((r,S)\), where \(r\in[m-1]\) and \(|S|=r\), find a ranking \(\hat{\sigma}\) maximizing \(\sum_{r,S}\mu_{r,S}\log\Pr[(r,S)\mid\hat{\sigma},\phi]\).
Model a large crowdsourcing panel as a distribution \(\mu\) over approval-size and ballot types \((r,S)\). Compute the Mallows maximum-likelihood ranking by minimizing \(\sum_{r,S}\mu_{r,S}\delta(S,\sigma)\); sorting alternatives by total approval mass \(q(a)=\sum_{r,S:a\in S}\mu_{r,S}\) solves this in polynomial time.
The mirror covers the approval-scoring and MLE task on exact population masses for randomized approval. It leaves out the finite-sample dependence on \(n\), \(\epsilon\), and \(p^*\), Theorem 1’s lower bound on observations, the experiments, and Theorem 3’s equivalence of vote-generation processes.
There is a narrow positive case. The paper has no named worst-case computational-complexity result: no theorem puts a problem in P or proves NP-hardness, FPT, or the like. Its named results are about sample complexity. The mirrors below use those results as anchors for the computational task they study: finding a Mallows maximum-likelihood ranking from approval votes. They do not turn the sample bounds themselves into computational-complexity results.
A natural regime is a large crowdsourcing panel ranking a modest set of public projects. Suppose workers have the same known reliability level, and each submits an approval set. A type is the observed ballot \(S\); in the randomized-size protocol it is \((r,S)\), where \(r\) is the requested number of approvals. Mass \(\mu_t\) is the fraction of workers with that type. With many workers and a modest agenda, there can be many repeated ballots, so \(N\) can greatly exceed the number \(\tau\) of observed types. These proportions are also the natural way to report results such as “23% of workers approved project \(c\).”
My lead anchor is Theorem 1, proved in this paper. It states that for every \(k\in[m-1]\) and every \(\epsilon\in[0,1/4]\), at least \(\Omega(\phi^{-m/2})\) Mallows \(k\)-approval votes are necessary to recover the ground-truth ranking among \(m\) alternatives with probability at least \(1-\epsilon\). For fixed \(0<\phi<1\), that is exponential in \(m\).
The corresponding continuous problem is Fixed-\(k\) Approval-Mass MLE. An instance gives \(m\), \(k\), a known rational \(0<\phi<1\), and binary-rational masses \(\mu_S\) over the \(k\)-subsets \(S\subseteq A\), summing to one. The task is to return a ranking \(\hat\sigma\) maximizing the aggregate likelihood
\[
\ell_\mu(\sigma)=\sum_{|S|=k}\mu_S\log\Pr[S\mid\sigma,\phi].
\]
The Mallows approval-set likelihood is proportional to \(\phi^{\delta(S,\sigma)}\), where
\[
\delta(S,\sigma)=\sum_{a\in S,\ b\notin S}\mathbf{1}[\sigma(a)>\sigma(b)].
\]
Thus the task is equivalently to minimize \(\sum_S\mu_S\delta(S,\sigma)\). Its solution ranks alternatives by decreasing approval mass \(q(a)=\sum_{S\ni a}\mu_S\), with a fixed tie-breaking rule. This takes polynomial time in \(m,\tau,L\), where \(L\) is the mass bit length. The proposed mirror is the computation on the mass profile; Theorem 1 remains a lower bound on how many finite random ballots are needed to make that profile recover the truth reliably.
Theorem 2 is a useful second anchor, also proved here. It states that if the \(n\) agents have possibly different Mallows parameters \(p_\ell\), with average \(p^*=\frac1n\sum_\ell p_\ell\), then randomized approval—each agent is asked uniformly at random to approve \(r\in[m-1]\) alternatives—recovers the ground truth with probability at least \(1-\epsilon\) when
\[
n\ge \frac{2(m-1)^2}{(2p^*-1)^2}\ln(m/\epsilon).
\]
For this mirror I take the homogeneous-reliability case, which is included in the theorem. Randomized-Approval Mass MLE takes rational masses \(\mu_{r,S}\) over types \((r,S)\), where \(|S|=r\) and \(r\in[m-1]\), and returns a likelihood-maximizing ranking. Its objective is the same inversion sum, now \(\sum_{r,S}\mu_{r,S}\delta(S,\sigma)\). Sorting alternatives by total approval mass \(q(a)=\sum_{r,S:\,a\in S}\mu_{r,S}\) solves it in polynomial time. Theorem 2 supplies the statistical reason to study this protocol; the mass problem asks for the ranking from the aggregate.
Both mirrors are Class A computational problems. They keep the paper’s alternatives, approval ballots, Mallows noise model, ground-truth ranking, and estimator. The further questions are whether recovery remains robust when the supplied masses are approximate, how many bits of precision preserve the ranking, and how the minimum gap between adjacent approval masses depends on \(m\), \(k\), and \(\phi\). For randomized approval, one can also ask whether changing the distribution over \(r\) improves that gap.
The weak point is substantial: the paper’s headline question concerns the number of finite random observations needed, while these mirrors start with exact mass proportions. Exact masses remove the sampling uncertainty that Theorems 1 and 2 measure. In a real panel, estimating those proportions is part of the original problem. So I would defend this as a plausible continuous mirror of the paper’s MLE computation on a population profile, not as a continuous version that explains away the exponential sample bound. If the authors or referee require the mirror to preserve the finite-sample question itself, this case does not meet that bar.
The two anchors are sample complexity theorems, not computational results. They ask how many independent, noisy ballots are needed before the rule recovers the ground truth. The proposed mass MLE asks a different question: given exact ballot proportions, which ranking maximizes likelihood? It is a sensible high multiplicity version of applying approval voting, but it does not mirror either theorem’s sample requirement.
For Theorem 1, the lower bound comes from ballots that distinguish particular alternatives being exponentially rare. In an exact mass profile, those rare ballots have their precise proportions already; there is no sampling error and no need to wait for them to appear. The MLE can rank from approval masses directly. For Theorem 2, exact masses over \((r,S)\) likewise supply the proportions for every approval size, removing the random variation whose concentration the theorem bounds. In both cases, the continuum removes the finite sampling uncertainty that makes the result interesting.
A stronger alternative would put worker reliability \(p\) into the type and ask for the sample size needed to recover the truth for a given mass distribution over reliability types. That is a plausible crowd model, and grouping workers by reliability is sensible. But it retains finite random samples as the central resource; the mass distribution parameterizes a statistical question rather than becoming the society input to a continuous computational problem. A mass-perturbation robustness question is also possible, but adversarially changing ballot proportions is a different uncertainty model from the independent Mallows draws in the paper.
So the negative case is strongest on the paper’s actual results: their continuous versions lose the finite-sample question, while the exact-mass ranking problem is not one of the results the paper establishes. The case is not airtight in a broader sense. A population-level analysis of reliability types or approval-score stability could be useful research, and this paper’s crowdsourcing setting makes high multiplicity entirely plausible. I would classify those as worthwhile adjacent questions, though, rather than continuous computational mirrors of Theorems 1 or 2.
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.