| paper | d4-conf-atal-2017-0070 |
| 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: \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
Given an agenda \(\Phi\), integrity constraint \(\Gamma\), finite support \(S\subseteq\mathcal{J}(\Phi,\Gamma)\) with positive binary-rational masses \(\mu_t\) summing to \(1\), and constraint sets \(L,L_1,\ldots,L_u\), define \(D_\mu(K)=\sum_{t\in S}\mu_t d_g(K,t)\). Is there a complete, \(\Gamma\)-consistent judgment set \(K\) minimizing \(D_\mu\) over all such judgment sets, with \(L\subseteq K\) and \(L_i\not\subseteq K\) for every \(i\)?
A society is a distribution \(\mu\) over complete, \(\Gamma\)-consistent judgment sets, with each judgment set a voter type. The decision variable is a complete, \(\Gamma\)-consistent judgment set \(K\); its objective is the population-weighted geodesic distance \(\sum_{t\in S}\mu_t d_g(K,t)\), subject to the stated inclusion and exclusion constraints on a minimizer.
The mirrors cover Theorem 4’s geodesic-sum aggregator and Theorem 2’s reversal-scoring aggregator; they leave Theorem 3’s max-Hamming aggregator and the paper’s other results aside.
The cleanest mirror is to treat a person’s type as their complete, \(\Gamma\)-consistent judgment set on the agenda, and the society as a distribution \(\mu\) over those types. Here \(\mu_t\) is the fraction of the population with judgment set \(t\). A plausible regime is a large consultation on a fixed, modest set of logically related policy questions: millions of participants, but many sharing recurring complete answer patterns, so the support has \(\tau\) types rather than one entry per person. That is a sensible high-multiplicity version of judgment aggregation. The paper’s rules use only those judgments and quantities derived from them, so agents sharing a type are indistinguishable for these problems.
My lead is Continuous Geodesic-Outcome. Its instance consists of an agenda \(\Phi\), integrity constraint \(\Gamma\), a finite support \(S\subseteq\mathcal J(\Phi,\Gamma)\) with positive binary-rational masses \(\mu_t\) summing to \(1\), and constraints \(L,L_1,\ldots,L_u\subseteq\Phi\). The distance \(d_g(K,t)\) is the paper’s geodesic distance: shortest-path distance in the graph of complete, \(\Gamma\)-consistent judgment sets, with edges defined as in the paper. Define the population objective
\[
D_\mu(K)=\sum_{t\in S}\mu_t\,d_g(K,t).
\]
The question is whether there is a complete, \(\Gamma\)-consistent judgment set \(K\) minimizing \(D_\mu\) such that \(L\subseteq K\) and \(L_i\not\subseteq K\) for every \(i\). A yes-instance has such a \(K\) as its witness; a no-instance has none.
The anchor is Theorem 4, proved in this paper: Outcome(\(F_g\)) is \(\Theta^p_3\)-complete. In full, the paper’s decision problem asks, for an agenda and integrity constraint, a finite profile of complete consistent judgment sets, and the listed inclusion and exclusion constraints, whether some winner under the geodesic-distance aggregator satisfies those constraints. The continuous question replaces the profile’s tally with rational population shares in the same sum-of-distances objective. Every finite profile embeds by assigning each judgment type its frequency divided by the profile size. This preserves the winners and the answer to the constrained-outcome query, so the paper’s hardness transfers. I expect the continuous problem to remain \(\Theta^p_3\)-complete: this is Class B, with the reduction’s complexity carried by the agenda and logical constraints. The result makes a particularly strong mirror because the population-weighted objective is exactly the paper’s sum aggregator extended to rational masses.
A second, well-supported mirror is Continuous Reversal-Outcome. Use the same instance format, and define each type’s reversal score by the paper’s rule:
\[
\operatorname{rev}(t,\varphi)=
\min_{\substack{K\in\mathcal J(\Phi,\Gamma)\\ \sim\varphi\in K}}
d_H(K,t).
\]
The society’s score for formula \(\varphi\) is
\[
r_\mu(\varphi)=\sum_{t\in S}\mu_t\,\operatorname{rev}(t,\varphi).
\]
Ask whether some complete, \(\Gamma\)-consistent \(K\) maximizing \(\sum_{\varphi\in K}r_\mu(\varphi)\) satisfies the same inclusion and exclusion constraints. Again, a qualifying \(K\) is a yes-witness. The rule uses expected reversal score per unit of population, which is the direct mass-weighted counterpart of the paper’s summed individual scores.
Its anchor is Theorem 2, proved here: Outcome(\(F_r\)) is \(\Theta^p_2\)-hard. The full result concerns whether a winner of the reversal-scoring judgment aggregator can satisfy the specified \(L,L_1,\ldots,L_u\) constraints for a given agenda, integrity constraint, and finite profile. The accompanying Lemma 1, also proved here, establishes membership in \(\Theta^p_2\), so the discrete problem is complete for that class. Finite profiles again embed as rational frequency distributions, preserving scores up to a common positive scale and therefore preserving winners. I expect hardness to transfer and the continuous problem to remain \(\Theta^p_2\)-complete, also Class B.
These mirrors cover the paper’s reversal-scoring and geodesic-sum results, not every procedure it studies. In particular, I do not rely on Theorem 3’s max-Hamming aggregator: because it depends on the farthest supported type, multiplicities do not affect its outcome. The two proposed questions instead make population shares part of the underlying aggregation objective. Neither replaces the society with fractional outcomes or introduces a noise model.
The weakest point is that these are very direct weighted extensions of the paper’s profiles. With rational masses, one can multiply by a common denominator and view the society as a finite profile with possibly many repeated voters. That makes the authors’ recognition test strong—the original sum-based rules extend naturally—but leaves little reason to expect population continuization itself to dissolve the hardness. The value of these mirrors is therefore as honest Class B questions and as starting points for studying compressed type support, parameterized algorithms, and approximation, rather than as a claim of new tractability.
The strongest case against these mirrors is that the population measure changes the encoding more than the aggregation problem. For any rational \(\mu\), choose a common denominator \(N\) and make a profile with \(N\mu_t\) copies of each judgment type \(t\). Its geodesic sum is \(N D_\mu(K)\), so it has exactly the same minimizers and constrained winners. Its reversal scores are likewise the continuous scores multiplied by \(N\), preserving all winners. Thus neither mirror creates new outcome behavior: each is the paper’s rule applied to a weighted profile.
That is a real limitation on the case for novelty, but it does not defeat either anchor. Expanding binary rational masses into repeated voters can take exponentially more space, so the weighted problem asks about a different computational representation: how winner determination depends on agenda size, support size, and mass bit length. The finite-profile embedding supplies hardness, but it does not answer the complexity of that compressed input. Nor does exact equivalence make the question a collision under the programme’s standard: the paper gives profiles, while the mirror makes a distribution the input object.
The obvious objections to the model also fail. Each rule uses only a voter’s complete, \(\Gamma\)-consistent judgment set, so that set is a defensible type for these problems. Large consultations with recurring answer patterns are a plausible high-multiplicity regime. The normalized distance objective does not collapse to zero, and winner constraints remain meaningful. In particular, the fact that Theorems 2 and 4 may remain hard is not a reason to reject the mirrors; a Class B result is within scope.
There is a narrower concern about payoff: these mirrors do not obviously expose a new mass-transfer LP or a pricing problem. The population shares are input weights, and the choice is still among discrete consistent judgment sets. That makes a tractability breakthrough from continuous-optimization tools less apparent than in the programme’s bribery examples. But it is only a concern about likely yield, not a fundamental flaw in the computational questions; the programme also values mapping where continuization leaves hardness intact.
I cannot make a persuasive case that both anchors fail. The best negative argument is that the mirrors are weighted, compressed versions of the paper’s winner-determination problems, with no clear new optimization structure. Under the stated standard, that is not enough to rule them out: both are well-posed high-multiplicity questions, and their computational representation may matter.
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.