Voting with Ties: Strong Impossibilities via SAT Solving

The strongest honest case is a continuous-population mirror of the paper’s central impossibility problem, led by Theorem 5.2. It is a genuine mirror of the society, not of the outcome space: the population becomes a distribution over weak-preference types, while alternatives and choice sets remain finite.

One qualification matters. The paper contains no named result of the programme’s narrow complexity kind—no theorem saying that a problem is NP-hard, in P, FPT, or similar. Its named results are axiomatic impossibility theorems, established partly through SAT solving. Thus this would be a mirror of a computationally certified feasibility problem, not yet a complexity-landscape mirror.

Take a fixed finite alternative set \(A\), with \(m\ge3\), and let \(T\) be the finite set of complete weak orders over \(A\). A type \(t\in T\) is a complete description of an agent’s ordinal preferences, including indifferences. A continuous society is \(\mu\in\Delta(T)\), where \(\mu_t\) is the fraction of the population of type \(t\). This is plausible, for example, for millions of residents choosing among a small number of public projects when preferences are recorded using a coarse ranking language. With three alternatives there are only finitely many weak-order types, while the population may be arbitrarily large.

The decision variable is a set-valued social choice rule

\[ F:\Delta(T)\longrightarrow 2^A\setminus\{\varnothing\}. \]

There is no numerical objective: the question is whether one can find a rule satisfying the paper’s axioms for every society \(\mu\). Anonymity is built into the representation, since \(F\) sees only type masses and not agent identities.

The continuous Pareto condition should be defined as follows. An alternative \(x\) is dominated by \(y\) at \(\mu\) if \(y\succeq_t x\) for \(\mu\)-almost every type \(t\), and \(y\succ_t x\) for a positive amount of mass. Pareto-optimality requires \(F(\mu)\) to contain no dominated alternative.

For pairwise rules, define the normalized majority margin

\[ g_\mu(x,y) = \sum_{t\in T}\mu_t \bigl( \mathbf 1[x\succeq_t y] - \mathbf 1[y\succeq_t x] \bigr). \]

The continuous rule is pairwise if \(F(\mu)=F(\nu)\) whenever \(g_\mu(x,y)=g_\nu(x,y)\) for every pair \(x,y\).

The only nontrivial co-modification concerns manipulation. A single atomless individual has zero effect on \(\mu\), so literal individual strategyproofness would become vacuous. The natural population analogue is a positive-mass type-level deviation. If a mass \(\alpha\in(0,\mu_t]\) of type \(t\) agents changes its report to \(t'\), let

\[ \mu^{\alpha,t\to t'} = \mu-\alpha e_t+\alpha e_{t'}. \]

Mass-Fishburn-strategyproofness requires

\[ F(\mu^{\alpha,t\to t'}) \not\succ_F^t F(\mu) \]

for every such deviation. Mass-Kelly-strategyproofness uses \(\succ_K^t\) instead. These are exactly the paper’s Fishburn and Kelly extensions applied to the same choice sets. Restricting to \(\alpha=1/n\) on distributions with denominator \(n\) recovers the original one-agent deviation.

My lead question is therefore:

\[ \mathsf{Continuous\text{-}Fishburn\text{-}Feasibility}(m): \]

Given \(m\ge3\) and the weak-order type set \(T\), does there exist a rule \(F:\Delta(T)\to2^A\setminus\{\varnothing\}\) that is Pareto-optimal and mass-Fishburn-strategyproof? A solution is an explicit rule satisfying these conditions on every distribution \(\mu\); a negative answer is an impossibility proof.

The anchor is Theorem 5.2, proved in this paper using a SAT-based argument and independently formalized in Isabelle/HOL:

“There is no anonymous SCF that satisfies Pareto-optimality and Fishburn-strategyproofness for \(m\ge3\) and \(n\ge3\).”

The continuous version should also be infeasible. If such an \(F\) existed, define a three-agent rule by

\[ f(t_1,t_2,t_3) = F\!\left( \frac{1}{3}e_{t_1} + \frac{1}{3}e_{t_2} + \frac{1}{3}e_{t_3} \right). \]

Because \(F\) depends only on masses, \(f\) is anonymous. Continuous Pareto-optimality gives finite Pareto-optimality, and a one-agent deviation is exactly a mass deviation with \(\alpha=1/3\). Hence \(f\) would contradict Theorem 5.2. This is not merely an analogy: the finite theorem embeds directly into the continuous domain. In the programme’s trichotomy, this is a Class-B-style inherited impossibility rather than a continuum-specific obstruction.

The paper’s authors should recognize this as their problem. The mirror retains their weak preferences, set-valued outcomes, Pareto-optimality, Fishburn comparison, and anonymity. The only modification is forced by the population limit: strategic influence is measured by a positive mass rather than by an individual of vanishing mass. It also captures their interpretation of Fishburn-strategyproofness for chairman tie-breaking and, via the paper’s discussion, its connection with even-chance lotteries.

A second, genuinely distinct anchor is Theorem 5.4, proved in the paper with a human-readable five-profile argument:

“There is no pairwise SCF that satisfies Pareto-optimality and Kelly-strategyproofness for \(m\ge3\) and \(n\ge3\).”

Its continuous counterpart is:

\[ \mathsf{Continuous\text{-}Pairwise\text{-}Kelly}(m): \]

Given \(m\ge3\), does there exist \(F:\Delta(T)\to2^A\setminus\{\varnothing\}\) that is pairwise, Pareto-optimal, and mass-Kelly-strategyproof? Again, a solution is a rule satisfying all three conditions for every \(\mu\).

This question is also infeasible by the same three-agent restriction. The normalized margins \(g_\mu\) are exactly the finite majority margins divided by three, so pairwiseness is preserved; a one-agent misreport is again a deviation of mass \(1/3\). Thus a continuous solution would induce the forbidden three-agent rule from Theorem 5.4.

I would not add Corollary 5.3 as a third anchor. It is a useful weaker result—no neutral and anonymous rule satisfies Pareto-optimality and Fishburn-strategyproofness for \(m\ge3\) and \(n\ge2\)—but Theorem 5.2 already gives the stronger non-neutral statement, so including it would mostly pad the case.

The weakest point is the manipulation concept. If the authors insist that only a single infinitesimal individual may deviate, then strategyproofness is vacuous in an atomless population, and the mirror loses the central content of the paper. Mass-strategyproofness is therefore a substantive co-modification, not a formal detail. It is defensible because the programme explicitly permits co-modification forced by population continuization, because it recovers the finite problem at rational masses, and because homogeneous cohorts are precisely what high multiplicity means. But a referee could reasonably say that the resulting question studies resistance to coordinated type-mass deviations rather than the paper’s literal individual manipulation.

So the positive case is strong for the existence of a meaningful continuous-population formulation, especially for the two impossibility theorems. It is weaker as a case for new continuous computational complexity: the known negative answer transfers immediately from the embedded three-agent corner, and the paper itself supplies no named complexity classification to mirror.