| paper | d4-conf-aaai-2018-0070 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The named theorems are computational, but the paper already represents a user population by a probability distribution over rankings and computes the mass satisfying a poset. The proposed cohort mixture only combines such distributions and sums the same inference quantities. There is no discrete-to-continuous population bridge here; the proposed mirror restates the paper’s existing distributional model.
fails bit b-already — the paper is already native to the continuum
The paper already treats its RIM and Mallows laws as population distributions over rankings, so the proposed compatible-ranking mass is the inference quantity its theorems compute.
fatal: True
The proposed query covers the exact marginal-inference results, including Theorems 2 and 3; it leaves the experiments and broader discussion of ranking models outside the query.
My strongest case is a narrow population-level extension of the paper’s inference problem. Imagine a large marketplace with millions of users and a small number \(\tau\) of preference-behavior cohorts. A cohort’s type is its complete RIM description: a reference ranking \(\sigma_t\) and insertion probabilities \(\Pi_t\). Its mass \(\mu_t\) is the fraction of users in that cohort. Given a partial order \(P\), such as “product \(a\) is preferred to \(b\),” ask what fraction of the whole population has a latent ranking compatible with \(P\).
The induced mass on rankings is
\[
\bar{\mu}(\rho)=\sum_{t=1}^{\tau}\mu_t\Pr_{\mathrm{RIM}(\sigma_t,\Pi_t)}(\rho),
\]
so the requested answer is the exact mass
\[
q=\sum_{t=1}^{\tau}\mu_t
\sum_{\rho\in\operatorname{rnk}(A\mid P)}
\Pr_{\mathrm{RIM}(\sigma_t,\Pi_t)}(\rho).
\]
An instance gives \(m\) alternatives, the poset \(P\), the \(\tau\) cohort descriptions, and their binary-rational masses; a solution is the exact rational \(q\). Millions of users can share a small number of complete behavior types, and the output is a fraction of society. That makes this a real population-mass question, rather than a continuous outcome-space or time model.
The lead anchor is Theorem 2, proved in this paper through RIMDP. It says that for a poset \(P\) and a RIM model with reference ranking \(\sigma\) of length \(m\), the probability \(\Pr(P\mid\sigma,\Pi)\) can be computed in time \(O(m^{\operatorname{cw}(\sigma)+2})\), where \(\operatorname{cw}(\sigma)\) is the maximum, over prefixes of \(\sigma\), of the number of earlier poset items directly related to a later poset item. Applied to each cohort, it gives the population-mass query above in time \(O(\tau m^{w+2})\), where \(w=\max_t\operatorname{cw}_{\sigma_t}(P)\), plus polynomial overhead for exact rational arithmetic. I expect tractability when \(w\) is bounded; the stated running time is XP in \(w\), not an FPT bound.
For unrestricted cover width, hardness is already present in the one-cohort case. In particular, under the uniform-ranking Mallows model, the probability of a poset over all \(m\) items is its number of linear extensions divided by \(m!\). Thus the continuous population query retains the counting difficulty in the alternatives; adding population mass does not remove it. The paper’s introduction cites the #P-completeness of linear-extension counting, but the paper has no numbered hardness theorem, so I do not present that citation as one of my anchors. Theorem 2 is the named result I am actually mirroring.
A second, more restricted question is worth anchoring separately. Theorem 3, also proved here, says that for a Mallows model \(M(\sigma,\phi)\), the probability of a series-parallel poset that is disjoint with respect to \(\sigma\) can be computed in \(O(m^2)\) time. In the population version, each cohort has a Mallows type \((\sigma_t,\phi_t)\), and \(P\) must be disjoint series-parallel relative to each cohort’s reference ranking. The instance and requested answer are otherwise the same: compute the exact total mass \(q\) compatible with \(P\). Applying Theorem 3 per cohort gives \(O(\tau m^2)\) time. I expect this restricted problem to be Class A: the paper’s structural condition makes the aggregate inference tractable.
The theorem results concern one RIM or Mallows model at a time; the weighted cohort aggregate is the proposed mirror, obtained by evaluating their inference query for each type and summing. It covers the paper’s exact marginal-inference results, not its experiments or its wider discussion of ranking models. Further questions include whether broader poset classes admit efficient aggregate inference, and whether the dependence on \(\tau\) can be improved when many cohorts share structure.
The weak point is that RIM and Mallows already use probability distributions over rankings to represent user populations. A referee could see this cohort formulation as a mixture wrapper around the paper’s existing model, rather than a distinct continuization. There is also a type-level choice: here agents of one type share a preference-generating law, while the realized rankings differ. If ChoCo requires types to be deterministic rankings in every instance, this mirror does not meet that requirement. Its positive case rests on treating the cohorts’ complete stochastic preference descriptions as the relevant types for this inference task.
The strongest negative case is a novelty collision: the paper’s central object is already a population measure over complete rankings. For a RIM model, set \(\mu(\rho)=\Pr_{\mathrm{RIM}(\sigma,\Pi)}(\rho)\). Then the paper’s marginal probability of a poset \(P\) is exactly the fraction of that population whose rankings satisfy \(P\):
\[
\Pr(P\mid\sigma,\Pi)=\sum_{\rho\models P}\mu(\rho).
\]
The paper even describes Mallows as representing a population of users. Interpreting the probability as a continuum fraction changes the story, not the computational question. Theorem 2 already computes that fraction for a compactly represented society.
The cohort construction does not escape this. A mixture of RIM cohorts induces the single measure \(\bar\mu=\sum_t\mu_t\mu_t^{\mathrm{RIM}}\), and the requested mass is the same poset query under \(\bar\mu\). Evaluating it component by component and adding the results is a straightforward extension of the paper’s inference task. If types must instead be realized rankings and the society is supplied by its explicit support, the query is just a weighted sum of indicators. So the proposed mirror is either the paper’s existing inference problem or a direct aggregation over the supplied types.
Theorem 3 has the same issue. Its \(O(m^2)\) algorithm computes the mass of rankings satisfying a disjoint series-parallel poset under a Mallows population. A Mallows cohort mixture again adds one such mass per cohort; an explicit ranking-support society again needs only a direct sum. The structural restriction is already part of the paper’s computational result, rather than a new continuous-population phenomenon.
One can imagine a worthwhile adjacent question about changing cohort weights, transferring mass between rankings, or optimizing an intervention. But those add an objective or constraints absent from the paper’s inference results; they do not make Theorems 2 or 3 newly continuous. The weak point in this negative case is that an intervention problem could become a valuable project of its own. That possibility does not rescue these anchors: their exact population-mass question is already the question the paper answers.
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.