| paper | d4-conf-aaai-2018-0759 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), with exact probabilities represented by binary-encoded integer numerators and denominators. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite alternative set \(A\) and \(\tau\) complete weak-order types \(t\), each with positive binary-rational mass \(\mu_t\) summing to \(1\), compute the exact RMEC lottery. For each \(a\in A\) and rank \(j\), set \(r_{\mu,j}(a)=\sum_t\mu_t\mathbf{1}[a\in E_j(t)]\), where \(E_j(t)\) is type \(t\)’s \(j\)-th indifference class. For each type \(t\), let \(F_\mu(t)\) be the alternatives in its top class whose rank vectors are lexicographically maximal within that class; output \(p_\mu(a)=\sum_{t:a\in F_\mu(t)}\mu_t/|F_\mu(t)|\) for every \(a\in A\).
A society is a distribution \(\mu\) over complete weak-order types. Each type contributes its mass equally across its top-ranked alternatives with lexicographically maximal population rank vectors, yielding the lottery \(p_\mu\).
The mirror covers Proposition 1’s computation of the RMEC lottery. It leaves the participation, efficiency, fairness, strategyproofness, and experimental results unmirrored.
The strongest honest mirror is a high-multiplicity version of computing RMEC itself. Its type is a complete weak preference order over the alternatives; its mass is the fraction of listeners with that order. A plausible regime is a radio service with millions of listeners but comparatively few recurring preference patterns over a manageable set of genres. Since RMEC uses only preferences, listeners with the same order are indistinguishable for this problem.
My anchor is Proposition 1, proved in this paper: RMEC is anonymous and neutral, and for an \(n\)-agent, \(m\)-alternative profile its outcome can be computed in \(O(m^2n)\) time and consists of rational probabilities. The paper has no numbered NP-hardness, \(\#\mathrm{P}\)-hardness, or other comparable hardness result to anchor instead. It mentions that computing RSD shares is \(\#\mathrm{P}\)-complete, citing earlier work, but that is not a numbered result of this paper.
Here is the continuous question I would hand to a prover:
Continuous RMEC evaluation (\(\mathrm{RMEC}_\infty\); lead). An instance consists of a finite alternative set \(A\), with \(|A|=m\), and a list of \(\tau\) complete weak orders \(t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). For the indifference classes \(E_1(t),\ldots,E_{k_t}(t)\) of type \(t\), define the population rank vector of alternative \(a\) by
\[
r_{\mu,j}(a)=\sum_t \mu_t\,\mathbf{1}[a\in E_j(t)].
\]
For each type \(t\), let \(F_\mu(t)\) be the alternatives in its top class \(E_1(t)\) whose rank vectors are lexicographically maximal among alternatives in that class. Compute the exact lottery
\[
p_\mu(a)=\sum_{t:\,a\in F_\mu(t)}\frac{\mu_t}{|F_\mu(t)|}
\qquad (a\in A).
\]
The solution is this probability vector. There is no optimization objective in the paper’s problem: this is the exact evaluation of a voting rule.
This is a direct extension, not a change to the rule’s purpose. If \(\mu_t=n_t/n\) for an ordinary electorate, each of the \(n_t\) voters of type \(t\) contributes \(1/n\), so their combined contribution is \(\mu_t\); the rank vectors are also just the original count vectors scaled by \(1/n\). Thus every finite profile has exactly the same outcome under this definition. For rational input, the weighted rank vectors and lottery can be computed exactly in time polynomial in \(m,\tau,L\), where \(L\) is the mass encoding length: accumulate the rank vectors by type, find each type’s best alternatives, and sum its mass across them. This is the tractable, Class A expectation. The mirror asks whether the rule can be evaluated from a compact description of a very large society, rather than from one record per person.
The authors should recognize this as their problem: it preserves RMEC’s weak-order handling, rank comparison, tie-breaking by equal contribution, and lottery output. The population is what has become continuous; the lottery over alternatives was already part of their model. It also supplies a useful follow-up question: do RMEC’s participation guarantees, especially Proposition 2’s very strong SD-participation, have a meaningful mass-based analogue when a positive-mass cohort joins or abstains? A single person has zero mass in a literal continuum, so that analogue needs care.
The soft spot is substantial: this is not a case where discrete hardness dissolves. RMEC is already polynomial-time computable, and for rational masses the mirror reproduces the same outcome as a suitably scaled finite electorate. Its computational value is the support-compressed representation: \(\tau\) types and binary masses can describe a population far larger than the explicit \(n\)-voter input. That is a modest but genuine high-multiplicity question, not a new complexity separation.
Proposition 1 is the only strong computational anchor, and it survives the basic objections. A population of listeners with recurring weak preference orders is a plausible high-multiplicity setting. Those who share an order are indistinguishable for RMEC, and the lottery is still an outcome over alternatives; the fact that the outcome is probabilistic does not make the population continuous.
The strongest case against is about priority, not whether the mirror is well-posed. RMEC already depends on aggregate rank counts: an implementation can group identical orders in an explicit profile, then compute each type’s contribution from its count. Replacing counts by rational masses gives the proposed \(\mathrm{RMEC}_\infty\) formula directly. It yields an algorithm polynomial in \(m,\tau,L\), but calls for no column generation, continuous optimization, or new structural insight. The gain is a compact input for a large repeated electorate. That may be too routine to deserve much of the programme’s attention, but “the answer is easy” is not a sound reason to reject a well-posed mirror.
A stronger follow-up might study how RMEC’s lottery or SD-efficiency changes as type masses vary. The rank comparisons switch across linear boundaries in the mass space, so this could expose a richer sensitivity problem. But it is not a computational result established in this paper; it would need to be sold as a new question the authors would recognize, not as a mirror of Proposition 1.
Proposition 2 offers less leverage for a negative case. An individual has zero mass in a literal continuum, so the strict part of very strong participation degenerates. But a positive-mass cohort is a sensible repair. For rational masses, adding a homogeneous cohort can be represented by scaling to a finite profile and adding identical agents one at a time; the paper’s participation result then gives a direct route to the cohort guarantee. That makes the continuous version look elementary, not incoherent—and the programme explicitly allows a same-answer result to count.
So the honest negative case is that this is a modest, nearly immediate high-multiplicity extension, with limited algorithmic depth. It cannot support the universal claim that no worthwhile continuous mirror exists: the proposed RMEC mirror is a genuine population-continuous computation in a plausible regime, and the stated grounds do not defeat it.
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.