| paper | d4-conf-atal-2017-0283 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), tree order \(k\), and a support of ballot types \(t\) with rational masses \(\mu_t\), compute the restricted Markov tree’s maximum-likelihood transition table. For each context \(S\) and eligible next candidate \(c\), use the total mass \(W_{S,c}\) of ballots contributing the transition \(S\to c\) and the context mass \(W_S=\sum_c W_{S,c}\), returning \(\hat\theta_{S,c}=W_{S,c}/W_S\) when \(W_S>0\), with the model’s fixed default distribution otherwise.
A large electorate is represented by a distribution \(\mu\) over complete or contiguous partial ballot types. The fitting procedure scans the \(\tau\) supported types and their windows, accumulates rational transition masses, and returns the same categorical estimates as the paper’s estimator.
The mirror covers transition-parameter fitting and its relationship to the paper’s sample-data requirement. It leaves the most-probable-sequence computation, imputation results, empirical comparisons, and coordination simulation aside.
The strongest honest case is narrow: the paper has no named theorem classifying a problem as polynomial-time solvable or hard. Its best computationally relevant anchor is a statistical sample-complexity result, which supports a continuous mirror of the model-fitting stage.
Theorem 1, proved in this paper, bounds the error in estimating a restricted Markov tree parameter \(\theta_{S,c,|S|}\). It says that, after observing the stated number \(N\) of sequences drawn from the tree, the estimate’s error is \(O(\theta_{S,c,|S|}\sqrt{\epsilon})\) with probability at least \((1-\alpha)^k\). The paper’s bound for \(N\) depends on the target transition probability, the probabilities of the prefixes needed to observe that transition, and the confidence and accuracy parameters; in the displayed formula, its numerator is \(-\ln((\alpha/|C|)^2)\). Thus rare contexts require more samples. This is a sample-complexity theorem, not a P-versus-NP result.
A plausible regime is a recurring election or large consultation over a fixed slate of candidates, with many voters submitting the same rankings. For example, party-aligned voters may produce millions of ballots but only a moderate number \(\tau\) of distinct ranking types. A type is the exact ballot used by the paper’s fitting procedure; if partial ballots are included, it also records which candidates were left unranked. Its mass \(\mu_t\) is that ballot’s fraction of the electorate. Here \(n\) can be very large while \(\tau\) remains much smaller.
I would ask the prover this:
Exact-Mass Restricted-Markov Tree Fitting. The input is a candidate set \(C\), a tree order \(k\), and a support of \(\tau\) ballot types with binary-rational masses \(\mu_t\) summing to one. For each context \(S\) used by the paper’s window-based training procedure and eligible next candidate \(c\), let \(W_{S,c}\) be the total mass of ballots contributing the transition \(S\to c\), and let \(W_S=\sum_c W_{S,c}\). Return the maximum-likelihood transition table, represented sparsely:
\[
\hat\theta_{S,c}=\frac{W_{S,c}}{W_S}\quad\text{when }W_S>0.
\]
For contexts with zero mass, use the model’s fixed default distribution. Equivalently, the solution maximizes the weighted local log-likelihood
\[
\ell(\theta)=\sum_{S,c} W_{S,c}\log\theta_{S,c}
\]
over the categorical distributions for each context.
This is a continuous-population version of fitting the paper’s transition parameters: masses replace ballot counts, and the model still learns the same sequence dependencies. It preserves the paper’s question about preference data and incomplete rankings; it does not turn the task into outcome-space continuity. The authors should recognize it as the exact-mass counterpart of their estimator.
I expect this problem to be tractable. The weighted counts and their ratios can be computed by scanning the \(\tau\) supported ballots and their windows, with exact rational arithmetic; a sparse representation avoids listing unobserved contexts. The running time depends on \(m,\tau,L\), and the input sequence lengths, rather than on the number of represented voters. Theorem 1 then supplies a useful bridge back to sampled electorates: it quantifies how many sampled sequences suffice to approximate the parameters of the underlying population model. The continuous fitting problem itself is an extension of the estimator, not a runtime result proved by Theorem 1.
This mirror covers the paper’s parameter-learning and data-requirement result, not its experimental comparisons or the full downstream task of extracting a most probable ranking. That latter task is a natural follow-up: given the fitted transition table, compute the most probable sequence without enumerating all \(m!\) rankings. Its complexity would need its own analysis.
The weak point is that the paper already defines a probability distribution over ballots and treats voter rankings as i.i.d. draws from it. A reader could see exact ballot masses as nearly the same object, while the mirror replaces finite-sample inference with a supplied population profile. And the fitting problem is easy even on explicitly listed discrete data; the gain is dependence on \(\tau\) rather than \(n\), not the dissolution of a discrete hardness result. So this is a defensible, author-recognizable continuous mirror of one result, but not evidence that the paper contains the kind of hard-to-easy complexity transition at the heart of the programme.
Theorem 1 is the only anchor, and it does not state the complexity of a computational problem. It bounds how many IID rankings must be sampled to estimate a restricted Markov tree’s parameters. The continuous society \(\mu\) in the proposed mirror is already the distribution from which those samples are drawn. Supplying exact masses changes the task: it removes sampling uncertainty, rather than continuizing the theorem’s computational problem.
A recurring election over a fixed slate could plausibly have millions of voters but only \(\tau\) distinct ballots. In that regime, the proposed estimator is sensible: sum the masses contributing each transition and divide by the mass of its context. But those weighted counts are sufficient statistics for the estimator. If the finite sample is restored, Theorem 1 applies as written, with its sample-size guarantee. If exact masses are supplied, the theorem’s question about how many observations are needed has disappeared. Compressing repeated ballots may save time, but it turns the anchor into weighted counting, not a new complexity question.
The strongest broader version would use those weighted transitions to impute incomplete ballots and aggregate the resulting preferences. For the output the paper actually defines, the most-probable sequence is built greedily: at each step choose the most likely remaining candidate given the current context. Luce renormalization has the same denominator for every eligible candidate, so it does not change that choice. The transition table can be built from the supported ballots’ windows, then the sequence and weighted election totals computed in passes over the input. A global maximum-likelihood permutation or a new robustness objective could pose a harder question, but that would introduce a different objective, not mirror a result in this paper.
The negative case is weakest at the universal claim. Large electorates with repeated ballot types are credible, and a new continuous aggregation or robustness problem might be worthwhile. But that possibility does not rescue this anchor: the paper’s formal result concerns statistical sample requirements for a model that already posits a distribution over rankings. Its exact-mass counterpart either leaves that theorem unchanged or reduces to deterministic parameter estimation. The paper offers no named computational result whose complexity landscape a continuous mirror would chart.
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.