d4-conf-ecai-2016-0040

The strongest mirror is in the paper’s constraint-based framework. A type is a complete rational ballot: a full assignment to the issues that satisfies the integrity constraint \(\Gamma\). A society is a finite support \(S\subseteq R(I,\Gamma)\) with positive binary-rational masses \(\mu_r\) summing to \(1\). Mass is the fraction of the population with that ballot. The collective decision remains one integral rational ballot \(r^\star\); it minimizes the population’s average Hamming disagreement,
\[ D_\mu(r^\star)=\sum_{r\in S}\mu_r\,d(r^\star,r). \]
So this changes the population into a distribution, while keeping the paper’s feasible opinions, distance, and Kemeny objective.

Call the resulting decision problem Continuous Kemeny Outcome. An instance consists of \(I=\{x_1,\ldots,x_n\}\), an integrity constraint \(\Gamma\), the supported ballots and their masses, and partial ballots \(\ell,\ell_1,\ldots,\ell_u\). It asks whether there is an \(r^\star\in R(I,\Gamma)\) that minimizes \(D_\mu\), agrees with \(\ell\), and does not agree with any \(\ell_j\). Such an \(r^\star\) is a witness solution. The input includes the bit lengths of the masses and the full encodings of \(\Gamma\) and the partial ballots.

This is a direct high-multiplicity version of the paper’s problem: a discrete profile with \(p\) voters induces masses \(\mu_r\) equal to each ballot’s frequency divided by \(p\). The continuous objective is then the discrete cumulative Hamming distance divided by \(p\), so its minimizers are exactly the same. Conversely, any rational mass vector can be realized by duplicating ballot types to a common denominator. This is a plausible model for a large consultation over interdependent policy issues where many constituents share complete, recurring positions. The number \(N\) of constituents can be enormous while the number \(\tau\) of distinct ballots is moderate. Those ballots are the types: each is a complete description of the attributes this problem uses.

My lead anchor is Proposition 15, proved in this paper by a reduction from MAX-MODEL. It states that \(OUTCOME(KEMENY)_{cb}\), parameterized by the number \(p\) of individuals, is \(\mathrm{para}\text{-}\Theta_2^p\)-hard. Its instance is the constraint-based outcome question just defined in the discrete setting: given issues, \(\Gamma\), a profile, and partial ballots, ask whether some Kemeny outcome agrees with the required partial ballot and avoids the forbidden ones. The paper’s reduction uses \(p=3\). Replacing those three profile entries with masses \(1/3\) (combining equal ballots if needed) gives the same yes/no answer. Thus the continuous version is already \(\Theta_2^p\)-hard with support \(\tau\leq 3\), and therefore \(\mathrm{para}\text{-}\Theta_2^p\)-hard when parameterized by \(\tau\). This is my strongest result: even a population with only three complete opinion types retains the hardness. The reduction’s combinatorics lie in the issues and integrity constraint, not in population size, so this is hardness that transfers.

Proposition 14, also proved here, adds a parameterized hardness result. It states that \(OUTCOME(KEMENY)_{cb}\), parameterized by \(h\) and \(p\), is W[SAT]-hard, where \(h\) is the maximum Hamming distance between two ballots in the profile. The paper reduces from MONOTONE-WSAT; its construction has three profile ballots and \(h=6k+6\), where \(k\) is the source parameter. Giving each ballot mass \(1/3\) preserves the Kemeny outcomes, so the corresponding continuous problem is W[SAT]-hard parameterized by \(h\) and \(\tau\). This is another transferred-hardness result. It also shows why a small number of opinion types alone does not make the problem easy when the issue structure can grow.

Proposition 11, proved here, states that \(OUTCOME(KEMENY)_{cb}\) is fixed-parameter tractable when parameterized by the number \(n\) of issues. It is the same outcome decision, with the same partial-ballot requirements. Its continuous lift is FPT in \(n\): enumerate the \(2^n\) ballots, discard those violating \(\Gamma\), compute each remaining ballot’s exact rational expected distance, and check the minimizers against the partial ballots. The running time is \(f(n)\operatorname{poly}(M)\), where \(M\) is the full encoded input, including \(\tau\) and the mass bit lengths. This supplies the tractable side of the mirror: regardless of population size or support, a bounded issue set gives an efficient outcome algorithm.

I would expect the Proposition 11 version to be tractable and the Proposition 14 and 15 versions to retain hardness from the discrete problem. The three are parameterizations of one continuous outcome problem, rather than three different models. Together they cover the paper’s constraint-based outcome results just described; they do not claim a mirror for its formula-based classifications or for other judgment aggregation rules. Further questions include how the tractability boundary changes with \(\tau\), \(h\), and structural restrictions on \(\Gamma\), and whether binary-rational weights enable useful algorithms for instances whose explicit discrete realization would be huge.

The weakest point is that a distribution with rational masses can always be expanded into a finite discrete profile. The continuous mirror therefore has less new mathematical structure than a problem whose continuum changes the feasible decisions; its computational significance is the compressed high-multiplicity input and its mass-based description. There is also a plausibility limit in the hardness examples: three exact whole-agenda opinion blocs are a strong simplification of real consultation data. Still, large constituencies organized around a small number of stable platforms are a credible regime, and the proposed objective is precisely the Kemeny problem the authors study, expressed in population proportions.