| paper | d4-conf-aaai-2018-0394 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
For the paper's fixed-variance Gaussian location-family RUM, given \(m\) alternatives, \(k\), rational \(C,\epsilon>0\), and a rational distribution \(\mu\) of mass over \(\tau\) complete rankings, find rational mixture weights \(\alpha\) and component means \(\theta^{(r)}\) with \(\alpha\) in the simplex, \(\sum_i\theta_i^{(r)}=0\), and \(\theta_i^{(r)}\in[-C,C]\), whose objective is within \(\epsilon\) of the global minimum of \(G_\mu(\alpha,\theta)=\sum_{i<j}\left(\sum_{V:a_i\succ_V a_j}\mu_V-\sum_{r=1}^k\alpha_r\Phi((\theta_i^{(r)}-\theta_j^{(r)})/\sqrt{2})\right)^2\). What is the complexity of this task in \(m,k,\tau\), the input bit length, and \(\log(1/\epsilon)\), in the correctly specified, pairwise-identifying regime?
A society is a rational distribution \(\mu\) over complete ranking types. The decision variables are mixture weights \(\alpha\) and bounded, normalized component means \(\theta^{(r)}\); the objective is the squared mismatch between population pairwise frequencies and the \(k\)-RUM's predicted pairwise probabilities.
Theorem 3 concerns consistency from sampled rankings, while the proposed mirror asks for a global minimizer from exact population masses; the paper gives no runtime or global-optimization guarantee for that task.
fatal: False
The mirror covers Algorithm 2's GMM fitting problem and its consistency setting. It leaves Theorems 1 and 2 as identifiability results, and does not treat the experimental model comparisons as a separate computational problem.
This paper offers a plausible population mirror, but no named theorem classifies its complexity as polynomial-time, NP-hard, FPT, or similar. The closest anchor is Theorem 3, proved in the paper: when the \(k\)-RUM is identifiable and its utility means are bounded, Algorithm 2’s GMM estimator is consistent—if rankings are drawn independently from the model, its estimate converges to the true parameters with probability tending to \(1\) as the sample size grows. That is an algorithmic and statistical result, not a runtime bound.
The corresponding problem I would hand to a prover is Population \(k\)-RUM GMM Fitting. An instance gives \(m\) alternatives, a known utility family \(M\) (for example, Gaussian case V), \(k\), a compact bound on the utility means, and a distribution \(\mu\) over \(\tau\) ranking types, with binary-rational masses summing to \(1\). For each pair \(i<j\), let \(b_{ij}=\sum_{V:a_i\succ_V a_j}\mu_V\). Find mixture weights \(\alpha_r\) and component means \(\theta^{(r)}\), modulo relabeling components, that minimize
\[
G_\mu(\alpha,\theta)=
\sum_{i<j}\left(
b_{ij}-\sum_{r=1}^{k}\alpha_r
\Pr_M(a_i\succ a_j\mid\theta^{(r)})
\right)^2.
\]
The weights lie in the simplex; each mean vector is bounded and uses the usual common-shift normalization. A computational version asks for a feasible rational parameter vector whose objective is within \(\varepsilon\) of the global minimum. In the correctly specified, globally identifying case, the population minimum is zero.
The regime is large electorates ranking the same small set of candidates, proposals, or documents, where many respondents report the same ranking: \(n\gg\tau\). A type is a reported ranking, and its mass is the fraction of the population reporting it. This matches the paper’s data: its breaking matrix is already built from ranking frequencies, so aggregating repeated ballots into masses preserves the GMM question. The mixture components remain the latent model being learned; they are not a substitute for population types.
Theorem 3 is the lead anchor. The paper also proves Theorem 2: for a RUM family whose utility distributions all have support \((-\infty,\infty)\), a \(k\)-RUM is generically identifiable when \(m\ge\max\{4k-2,6\}\). That supports the recovery setting, but identifiability is not an algorithmic guarantee, and Theorem 2 does not establish the complexity of the fitting problem. I would tentatively expect tractability for generic, correctly specified population recovery at fixed \(k\), using the low-order moments and tensor structure discussed in the paper. That remains a conjecture to investigate: the authors themselves leave computationally tractable tensor-decomposition algorithms as future work. Misspecified population fitting and variable \(k\) may have a harder optimization landscape.
The scope is the paper’s learning problem, especially its GMM estimator and identifiability conditions. The mirror does not cover the paper’s experimental model comparisons as a separate computational problem. Its weakest point is that the paper already treats finite ranking samples through their frequencies, and consistency is not a complexity result. The proposed mirror therefore gives the authors a recognizable high-multiplicity version of their learning question, but the paper does not itself show that population mass makes that question easier.
The strongest objection is that the paper has no named theorem about computational complexity to mirror. Theorem 1 and Theorem 2 are identifiability results; Theorem 3 is an asymptotic consistency result. None classifies a problem as polynomial-time, hard, or tractable under some parameterization. In particular, Theorem 3 says an estimator converges as the number of sampled rankings grows; it does not bound the cost of computing that estimator.
The proposed Population \(k\)-RUM GMM Fitting problem is plausible, but its correctly specified version is already the population moment problem implicit in the paper. A \(k\)-RUM defines a distribution over ranking types, and its pairwise moments are exactly the quantities used by GMM. Supplying that distribution as masses makes those moments exact instead of empirical. Under identifiability, the target is then the same model parameter the paper studies. Theorem 2 already answers whether that parameter is generically identifiable from the ranking distribution; Theorem 1 already gives a regime where it is not. Recasting either result as one about an exact continuous society adds no computational question.
For Theorem 3, replacing the sample by its limiting distribution removes the sampling uncertainty whose disappearance the theorem establishes. It leaves the problem of globally minimizing the same nonlinear GMM objective. Given a support of \(\tau\) rankings, its pairwise moments can be computed directly from their masses; the remaining optimization is over mixture weights and utility means, as in the paper’s finite-sample algorithm. Thus the population formulation changes the data representation, but it does not expose a new mass-transfer or other population-level computational structure.
A more ambitious mirror would allow misspecified population distributions and ask for the complexity of finding the best-fitting mixture. That is a coherent extension, and the negative case is weakest there: it may be worth studying as a nonlinear optimization problem. But it is not the question Theorem 3 answers, and its difficulty would come from mixture fitting, not from continuizing the society. Large crowds with repeated rankings are a sensible high-multiplicity regime; the paper already reduces those rankings to frequencies for GMM. My case is therefore strongest as a novelty objection to these anchors, not as proof that no useful extension could ever be formulated.
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.