| paper | d4-journals-mss-2014-0050 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard; nevertheless fixed-parameter tractable in \(\tau\), with bit running time \(2^{O(\tau)}\operatorname{poly}(m,L)\). · discrete side: parameterized · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Corollary 2
statement extracted from the paper’s text layer
Given a finite alternative set \(A\), a support \(\mathcal T\) of complete weak preference orders, positive binary rational masses \(\mu_t\) summing to \(1\), and a target \(a\in A\), draw an independent exponential clock of rate \(\mu_t\) for each type \(t\). Process types in clock order, replacing the feasible set \(B\) by \(\max_{R_t}(B)\) at each step, then select uniformly from the final feasible set. Compute the exact probability that the selected alternative is \(a\).
A distribution \(\mu\) over complete weak preference types, with one exponential priority clock of rate \(\mu_t\) per type; each processed type refines the feasible alternative set, and the objective is the exact RSD probability of target \(a\).
The mirror covers Corollary 2’s voting probability computation via a support size algorithm; it leaves the assignment results and the paper’s other voting parameterizations alone.
I would anchor the case on Corollary 2, proved in this paper. It says that, in the voting setting, for any alternative \(a\), computing its RSD probability is fixed parameter tractable in the number \(T\) of agent types, with running time \(O(|R|+mT2^T)\). The introduction cites earlier \(\#\mathrm P\)-completeness results, but those are not numbered results in this paper; Corollary 2 is the clearest eligible anchor.
The mirror is Limit-RSD Vote Probability. An instance is a finite alternative set \(A\), a support \(\mathcal T\) of \(\tau\) complete weak preference orders over \(A\), binary rational masses \(\mu_t>0\) summing to \(1\), and a target \(a\in A\). Each type describes everything the problem uses about an agent; its mass is the fraction of the population with that preference order. The task is to compute the exact probability that RSD selects \(a\).
Here is a precise mass-based definition. Give each type \(t\) an independent clock \(E_t\sim\mathrm{Exp}(\mu_t)\). Process types in increasing clock order, starting with \(B=A\) and replacing \(B\) by the alternatives tied for best under the next type’s preference. Stop if \(B\) is a singleton; after all types have been processed, use the paper’s uniform lottery over any remaining tied alternatives. The solution is the resulting probability \(p_\mu(a)\).
These clocks encode the high-multiplicity limit of random priority. In a finite electorate with \(n_t=k\mu_t\) agents of each type, only the first occurrence of each type in the random permutation can change the feasible set: later agents of that type cannot refine it further. The order of first occurrences has size-biased probabilities proportional to the masses \(\mu_t\), exactly the order generated by the clocks. For rational \(\mu\), this correspondence holds for every common scaling \(k\) that makes the counts integral. The model therefore makes population mass the input while retaining the paper’s RSD lottery as the quantity to compute; it does not continuize the outcome space.
For a target-specific algorithm, group types by their signature relative to \(a\): \(C_\sigma\) contains alternatives tied with \(a\), and \(D_\sigma\) those strictly preferred to \(a\). Let \(w_\sigma\) be the total mass of types with signature \(\sigma\), and \(B_X=\bigcap_{\sigma\in X}C_\sigma\). Conditional on \(a\) having survived the signatures in \(X\), the next unseen signature is \(\sigma\notin X\) with probability \(w_\sigma/\sum_{\rho\notin X}w_\rho\). It eliminates \(a\) exactly when \(D_\sigma\cap B_X\ne\varnothing\). A subset dynamic program over \(X\) therefore computes \(p_\mu(a)\) with \(2^{|\Sigma_a|}\) states, where \(|\Sigma_a|\le\tau\). This gives an FPT mirror in support size, with polynomial dependence on \(m\) and the mass bit length apart from the parameter-dependent factor.
The regime is a large electorate with many people but relatively few recurring weak preference orders over a fixed, modest menu—for example, a survey-based electorate where respondents may be indifferent among options. Types are identical in every respect RSD uses, and \(\tau\ll n\). The weak-order condition matters: the paper notes that strict preferences make the voting probabilities easy to compute, so that regime would not showcase its anchor.
I expect this mirror to be FPT in \(\tau\), as the anchor suggests, but that is not a claim of polynomial time for unrestricted support. The main follow-up is whether the cited \(\#\mathrm P\)-hardness persists when support grows—particularly whether the hard instances can be represented with distinct types and uniform masses, whose clock order is a uniform permutation. Another useful question is how the lottery changes when estimated masses are perturbed.
The soft spot is also the mirror’s strength: it may be an exact normalization of the finite type-count problem, rather than a new tractability phenomenon. The paper already groups voters by type and proves an FPT result in that number. Still, the mass model is a sensible high-multiplicity object: it gives a direct type-distribution input, a precise priority process, and an exact bridge back to finite electorates. The case covers the voting result in Corollary 2; it makes no claim about the assignment results.
The strongest case against is that the proposed mirror adds almost no new computational structure. For counts \(d_t=k\mu_t\), a uniform permutation can be generated by giving each voter an independent \(\mathrm{Exp}(1)\) clock. The first clock among voters of type \(t\) is \(\mathrm{Exp}(d_t)\); scaling all rates by \(1/k\) gives \(\mathrm{Exp}(\mu_t)\) without changing their order. Since applying the same preference type twice is idempotent, those first arrivals determine the RSD outcome. The clock model therefore reproduces the finite lottery exactly at every common scaling. Corollary 2 already gives an FPT algorithm in the number of types, so this mirror appears to inherit a solved type-level computation rather than open a new complexity frontier.
That is a real limitation on novelty, but it does not defeat the anchor under ChoCo’s stated standard. An exact discrete-to-continuous identity is a result, and existing high-multiplicity tractability supports the regime. The mass distribution is still the society’s input, and large electorates with recurring weak preference orders are plausible. The remaining objection—that the type-clock race is a special extreme-priority construction rather than an ordinary continuum of agents—is also weak here: the exact finite-population bridge makes it a construction the RSD authors could recognize as their problem.
So I cannot honestly rule out this mirror. My negative case is that it may offer little beyond translating Corollary 2 into mass notation; by the programme’s own criteria, that is not enough to dismiss a well-posed mirror.
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.