| paper | d4-conf-atal-2015-0215 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\Sigma_2^p\)-complete for decision and \(\mathrm{F}\Sigma_2^p\)-complete for search; hardness holds with \(\Gamma=\top\), \(u=0\), and \(\tau=8\) equally weighted types. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given an agenda \(\Phi\), integrity constraint \(\Gamma\), a support list of complete \(\Gamma\)-consistent judgment types \(t\) with positive binary-rational masses \(\mu_t\) summing to \(1\), and constraints \(L_0,\ldots,L_u\), define each formula’s strength as \(M_\mu(\varphi)=\sum_{t:\,\varphi\in t}\mu_t\). Order the formulas by nonincreasing strength, allowing any order among ties, and scan that order, adding each formula exactly when the resulting judgment set remains \(\Gamma\)-consistent. Does some permitted ordering produce a winner \(J^\star\) with \(L_0\subseteq J^\star\) and \(L_i\not\subseteq J^\star\) for every \(i>0\)? The search version outputs such a winner and a witnessing order, if one exists.
The society is a distribution \(\mu\) over complete judgment types on a shared agenda. A permitted ordering of formulas is the witness choice, and the resulting \(\Gamma\)-consistent complete judgment set is the outcome; there is no optimization objective.
The formula masses capture only marginal support, so the mirror offers no evident configuration-LP pricing structure and keeps the main difficulty in agenda consistency. The proponent acknowledges the compressed-profile character but does not establish new optimization leverage from the continuum.
fatal: False
Covers unrestricted-tie Ranked-Agenda winner determination from Theorem 3 and the Kemeny component of Theorem 1; leaves Slater, Young, and fixed-tie Ranked-Agenda outside these stated mirrors.
The strongest mirror is the unrestricted-tie Ranked-Agenda result, Theorem 3, with Kemeny from Theorem 1 as a second, distinct anchor. In both cases, the population consists of agents giving complete, \(\Gamma\)-consistent judgment sets on a shared agenda. A type is one such judgment set; \(\mu_t\) is the fraction of the population with that type. The instance lists the \(\tau\) types with positive mass and their binary-rational masses summing to one. This suits, for example, a large membership organization or public consultation where many respondents choose among a moderate number of recurring, internally coherent positions. The relevant regime is many people but relatively few distinct judgment types.
For the lead mirror, call the problem Continuous Ranked-Agenda Winner Determination. An instance gives \(\Phi,\Gamma\), a distribution \(\mu\), and the same constraints \(L_0,\ldots,L_u\) used in the paper. For each formula \(\varphi\), its strength is
\[
M_\mu(\varphi)=\sum_{t:\,\varphi\in t}\mu_t.
\]
Order the agenda formulas by nonincreasing strength, allowing any order among tied formulas. Scan that order, adding a formula to the current judgment set exactly when the result remains \(\Gamma\)-consistent. The decision question is whether some permitted ordering yields a winner \(J^\star\) with \(L_0\subseteq J^\star\) and \(L_i\not\subseteq J^\star\) for every \(i>0\). A search version outputs such a winner. Its decision variable is the collective judgment; in the search version, an ordering witnessing that outcome can also be supplied. There is no optimization objective here: the procedure is the ranked, consistency-preserving scan.
The anchor is Theorem 3, proved in this paper: \(\mathrm{WinDet}(\mathrm{RA})\) is \(\Sigma_2^p\)-complete, and its search problem \(\mathrm{FWinDet}(\mathrm{RA})\) is \(\mathrm{F}\Sigma_2^p\)-complete. The continuous mirror preserves the rule’s operative choices: majority strengths determine the priority order, and arbitrary tie resolution determines which consistent outcome is produced. I expect hardness to transfer (Class B). Given any discrete profile of \(n\) agents, set \(\mu_t\) to the number of agents of type \(t\), divided by \(n\). This preserves every comparison and tie between formula strengths, so it preserves the possible winners and the constraints on them. The reduction’s hard choices lie in the agenda, logical consistency, and ordering of tied issues, not in fine-grained control of individual voters. With rational masses, the paper’s membership argument also carries over: strengths are computable exactly, a tie order can be guessed, and the consistency checks can be made with an NP oracle. Thus the same \(\Sigma_2^p\) and \(\mathrm{F}\Sigma_2^p\) classifications are plausible for this mirror.
The second mirror is Continuous Kemeny Winner Determination. It uses the same instance format and constraints, but scores each complete, consistent candidate judgment set \(J\) by its expected Hamming distance from the population:
\[
K_\mu(J)=\sum_t \mu_t\,d(J,t).
\]
The decision question is whether a score-minimizing \(J^\star\) meets the \(L_i\) constraints; the search version returns one. Here the collective judgment is the decision variable, and \(K_\mu\) is the objective. This is a direct weighted form of the paper’s Kemeny problem, not a simplified outcome space.
Its anchor is Theorem 1, proved in this paper, which states that for each \(F\in\{\mathrm{Kemeny},\mathrm{Slater},\mathrm{Young}\}\), \(\mathrm{WinDet}(F)\) is \(\mathrm{P}^{\mathrm{NP}[\log]}\)-complete and \(\mathrm{FWinDet}(F)\) is \(\mathrm{F}\mathrm{P}^{\mathrm{NP}[\log,\mathrm{wit}]}\)-complete. The mirror here relies specifically on the Kemeny component. The paper notes that Kemeny’s decision result was already shown in [13]; it gives an alternative hardness proof and proves the theorem’s search result as well. Again, the discrete-to-mass map preserves winners: the weighted objective is the original sum of distances divided by \(n\). So I expect hardness to transfer (Class B). A useful further question is the exact complexity of the binary-rational version: its scores can have polynomially many bits but exponentially large scaled values, so the paper’s logarithmic-query upper bound does not automatically carry over. A direct weighted-score search gives a polynomial-query NP-oracle upper bound; where the compressed rational problem sits between that and the inherited \(\Theta_2^p\)-hardness is worth establishing.
These mirrors cover only winner determination for unrestricted-tie Ranked-Agenda and Kemeny. They do not continuize outcomes, time, or axioms. I would not stretch them to cover every result in the paper: in particular, I am not claiming a Young mirror without resolving how fractional deletion interacts with its strict-majority condition.
The weakest point is that these are especially clean high-multiplicity mirrors: every rational distribution can be expanded into a finite electorate with a common denominator, and aggregation depends only on the distribution over judgment types. That makes the connection to the continuous model exact, but also means these examples may look like compressed weighted-profile problems rather than new continuum phenomena. The positive case is therefore a credible computational continuation of the population model, with a sharp transferred-hardness boundary—not a claim that the continuum makes these two tasks easier.
The strongest case against these mirrors is that they offer little of the continuous-optimization opportunity that motivates ChoCo. For both rules, the population distribution matters only through each agenda formula’s marginal mass. Ranked-Agenda orders formulas by those marginals; Kemeny’s expected Hamming score can be written as a sum of per-formula disagreement masses. Correlations between judgments on different formulas disappear. The hard part remains logical consistency over the agenda, while population mass supplies weights. Neither result naturally becomes the kind of configuration LP with a pricing problem that makes the bribery examples especially promising.
That concern applies to both anchors, but it does not defeat either. For Ranked-Agenda, the best mirror keeps arbitrary ordering among tied formulas. Given a finite profile with \(n_t\) agents of type \(t\), set \(\mu_t=n_t/n\); every formula-strength comparison and tie is preserved, so the possible winners and the \(L_i\) constraints are preserved. Conversely, any rational mass vector can be expanded using a common denominator into a finite profile. The continuous question is therefore an exact high-multiplicity version of Theorem 3. The paper’s hardness may come from agenda consistency and tie choices, but that cannot count against the mirror under the stated standard.
Kemeny has the same exact bridge. Its weighted score is \(K_\mu(J)=\sum_t\mu_t d(J,t)\); multiplying by a common denominator recovers the finite-profile score, so minimizers and constrained winners agree. The result may add no new outcome semantics, and its central difficulty is still choosing a consistent judgment set. But rational masses can encode a profile whose expanded electorate is exponentially large in the input bit length. The change in representation is precisely what makes this a high-multiplicity computational question, rather than a mere restatement.
So the negative case is a case about priority: these two mirrors may be less fruitful for continuous-optimization methods than problems whose mass transfers create a pricing problem. It is not a case that the mirrors are ill-posed or that no useful continuous question exists. The best versions of both anchors survive, and I can’t honestly make the universal “no worthwhile mirror” claim without relying on objections the brief rules out.
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.