| paper | d4-conf-atal-2017-0110 |
| 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}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given an agenda Φ, integrity constraint Γ, desired conclusions L, and a rational distribution μ over complete, Γ-consistent judgment sets, find the minimum total mass to transfer from types J to reports K ≠ J, subject to ∑ₖ xᵢₖ ≤ μᵢ for each J, such that every Kemeny winner under the resulting distribution ν contains L. Here Kemeny winners minimize ∑ᵢ νᵢ d(J, J⁺) over complete, Γ-consistent judgment sets J⁺.
Types are complete, Γ-consistent judgment sets; μ gives their rational population masses. Decision variables xᵢₖ transfer mass from sincere type J to report K, the objective is to minimize ∑ᵢₖ xᵢₖ, and success requires every Kemeny minimizer under the resulting distribution to include L.
The all-winners success condition is disjunctive, so the mass-transfer formulation does not itself yield a single LP; this limits tractability expectations but does not undermine the computational question.
fatal: False
The mirror covers Theorem 5's Kemeny bribery result, including its restriction to unidimensionally aligned input profiles and |L| = 1. It leaves the paper's manipulation and issue-control results, and their other variants, aside.
My lead is Fractional Kemeny Bribery for Judgment Distributions, a direct high-multiplicity version of the paper’s bribery problem.
Let \(\mathcal J(\Phi,\Gamma)\) be the complete, \(\Gamma\)-consistent judgment sets for agenda \(\Phi\). A type is one such judgment set: agents of that type have the same sincere judgments, and the model gives every agent the same cost of being persuaded to report a different judgment. An instance consists of \(\Phi,\Gamma\), the briber’s desired conclusions \(L\subseteq\Phi\), a rational distribution \(\mu\) over \(\mathcal J(\Phi,\Gamma)\) given by its support, and a budget \(\beta\in[0,1]\). A plan is a nonnegative mass transfer \(x_{J,K}\) from type \(J\) to a different report \(K\), with \(\sum_{K\ne J}x_{J,K}\le\mu_J\) for each \(J\), and total transferred mass at most \(\beta\). It induces a new distribution \(\nu\). Its objective is to minimize the total mass persuaded; the decision version asks whether success is possible within budget \(\beta\). Success means every Kemeny winner under \(\nu\)—every judgment set minimizing \(\sum_J\nu_J d(J,J^*)\)—contains all of \(L\). A transfer plan is the solution.
A plausible regime is a large public consultation on a fixed set of logically related policy questions. Many respondents can share the same complete, consistent pattern of judgments, so the number of respondents can be large while the number \(\tau\) of distinct types is relatively small. An advocacy group might seek to persuade a specified share of respondents to submit different judgments. This is not a change to the paper’s aggregation rule or strategic objective: it replaces the count of individuals bribed by their population fraction. For a profile of \(p\) discrete voters, setting \(\mu_J\) to the fraction reporting \(J\) and \(\beta=k/p\) gives the natural normalized instance. Continuous plans can split mass fractionally, so this is a relaxation rather than an automatic equivalence.
The anchor is Theorem 5, proved in this paper. It states that deciding whether a briber can change at most \(k\) individual judgment sets so that every Kemeny outcome contains the briber’s desired set \(L\) is \(\Sigma_2^p\)-complete. The hardness holds even when the input profile is unidimensionally aligned and \(|L|=1\). This theorem is presented for formula-based judgment aggregation with subset-based preferences. Its reduction uses only three individuals and \(k=1\), with the difficult combinatorics encoded in the agenda and integrity constraint.
I expect the continuous problem to be Class B, cautiously. The paper’s hardness is not driven by a huge electorate: its reduction already has three voters, while the quantified Boolean instance is encoded in the issue structure. That makes the agenda, rather than population multiplicity, the likely source of hardness. But Theorem 5 does not prove hardness for the fractional problem: splitting the bribe budget across types may create strategies unavailable in the discrete reduction. Whether the reduction survives that added flexibility is the main open step in this mirror.
The mirror covers Theorem 5’s bribery result, not the paper’s full range of results. Manipulating one named individual needs a separate continuum coalition model; control by adding or deleting issues continuizes the agenda rather than the population. Further questions include whether fractional bribery stays hard under the theorem’s alignment restriction, whether it admits efficient algorithms for fixed agenda or support size, and when its optimum agrees with the discrete optimum after scaling population counts.
I can’t honestly defeat this anchor. Theorem 5 is a named computational result, and its bribery objective depends on the profile of judgments, not on who the individuals are. Replacing repeated judgment sets with masses therefore preserves the information the problem uses. A large consultation on a fixed set of policy questions is also a plausible high-multiplicity regime: many respondents can share the same complete, consistent judgment set.
The mirror has a direct high-multiplicity dictionary. For a profile with \(n_J\) respondents of type \(J\), set \(\mu_J=n_J/n\). Changing at most \(k\) respondents corresponds to moving at most \(k/n\) mass. Integer transfers reproduce the discrete bribery choices; allowing fractional transfers makes the continuous problem a genuine relaxation. If persuasion costs or eligibility vary by respondent, those attributes can be included in the type, as the programme’s definition of high multiplicity requires. Neither step loses information relevant to the paper’s outcome.
The strongest reservation is about the promised algorithmic payoff, not the mirror’s validity. The theorem’s hardness reduction uses only three individuals and encodes its complexity in the agenda and integrity constraint. That does not establish that the continuous problem inherits the hardness, and fractional transfers may change the answer. Nor is the resulting optimization automatically a single LP: requiring every Kemeny winner to contain \(L\) can be written as \(\forall b\) with \(L\nsubseteq b\), there exists \(g\) with \(L\subseteq g\) such that \(D_\nu(g)<D_\nu(b)\). That is a disjunctive condition. These points weaken the claim that the mirror is likely Class B or readily tractable; they do not make the question unworthy. Discovering whether the added flexibility matters is itself a computational question.
The “public consultation” story is stylized: the briber can redirect persuaded mass to any consistent judgment, just as the paper lets the briber assign any consistent judgment to a bribed individual. More realistic persuasion costs can be modeled by enlarging the type. That may produce a harder problem, but it does not invalidate the paper-faithful baseline.
So the best adverse case is that the expected outcome is uncertain and the continuous optimization machinery may not apply cleanly. The actual anchor survives: it is a coherent population-continuous mirror of Theorem 5, and the high-multiplicity setting is sensible. I would not support the universal claim that no worthwhile continuous mirror exists.
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.