Condorcet Winners and Anscombe's Paradox Under Weighted Binary Voting

The strongest positive case is a faithful high-multiplicity mirror in which only the population becomes continuous. The proposals remain discrete vectors in \(\{+1,-1\}^t\); there is no fractionalization of outcomes.

A voter type is \(v\in\{+1,-1\}^t\) in the external-weight model, and \((v,q)\) in the internal-weight model, where \(q\in\Delta_{t-1}\) is that type’s issue-weight vector. A society is a finite-support rational distribution
\[ \mu=\sum_{a=1}^{\tau}\mu_a\delta_{(v^a,q^a)}. \]
The mass \(\mu_a\) is the fraction of voters of that complete type. Thus a population of \(N\) voters may have \(N\) arbitrarily large but only \(\tau\ll N\) distinct preference-and-weight types. This is plausible for large electorates organised into recurring party, regional, demographic, or organisational blocs. The type definition is not weakening the paper’s model: two voters are grouped only when they agree on both issue opinions and issue importance.

My lead anchor is the paper’s Theorem 8, proved by the authors:

“There is an \(O(nt)\) algorithm computing (or deciding the inexistence of) an SSW presentation of a profile \(P\).”

The corresponding continuous problem is:

Continuous Single-Switch Certification. Given a rational society \(\mu\) over binary preference types \(v\in\{+1,-1\}^t\) and an external weight vector \(w\), decide whether there exist a column permutation \(\pi\) and column signs \(\sigma\in\{+1,-1\}^t\) such that, for every type \(v\) in the support of \(\mu\), the positions \(r\) satisfying
\[ \sigma_{\pi(r)}v_{\pi(r)}=+1 \]
form a prefix or a suffix of the ordered issues. If so, output \((\pi,\sigma)\); otherwise output “not single-switch.”

This is not merely a matrix-theoretic curiosity. Once the certificate is found, the society’s IWM proposal can be computed from its masses, and the paper’s single-switch result guarantees that every IWM proposal is Condorcet-winning under external weights. The recognition algorithm can be run on the support profile, so its relevant population parameter is \(O(\tau t)\), not \(O(Nt)\). The mirror is especially plausible because the paper itself stresses that the single-switch domain is defined independently of vote multiplicities: duplicating a row does not change membership in the domain.

I expect this problem to be Class A. The natural further questions are whether a forbidden subprofile can always be returned in \(O(\tau t)\) time in the continuous representation, how to find the largest single-switch subpopulation, and whether an analogous certificate exists for internal weights.

The second anchor is Theorem 12, proved by the authors in the full version; the conference version defers the proof. It gives polynomial-time algorithms for constructing majority-supported proposals with explicit distance guarantees.

For a society over internal types \((v,q)\), define
\[ \bar q_j=\sum_a\mu_aq^a_j \]
and, assuming \(\bar q_j>0\),
\[ m_j= \frac{\sum_a\mu_aq^a_j\mathbf 1[v^a_j=+1]}{\bar q_j}. \]
An IWM proposal \(p_{\mathrm{IWM}}\) chooses a majority opinion in every issue. A type \((v,q)\) supports a proposal \(p\) when
\[ \sum_{j=1}^t q_j\mathbf 1[v_j\ne p_j]<\frac12, \]
opposes it when the sum is greater than \(\frac12\), and is indifferent at equality. The continuous analogue of the paper’s representative-proposal problem is:

Continuous Majority-Supported Representative. Given \(\mu\), a selected \(p_{\mathrm{IWM}}\), and \(\ell=\max_j\bar q_j\), output a proposal \(p\in\{+1,-1\}^t\) such that the \(\mu\)-mass supporting \(p\) is at least the \(\mu\)-mass opposing it, and
\[ d_H(p,p_{\mathrm{IWM}},\bar q) =\sum_{j=1}^t\bar q_j\mathbf 1[p_j\ne p_{\mathrm{IWM},j}] \le B(\ell), \]
where
\[ B(\ell)= \begin{cases} \frac12+\frac{\ell}{2},&0<\ell<\frac13,\[2mm] 1-\ell,&\frac13\le\ell\le\frac12,\[2mm] \ell,&\frac12<\ell<1. \end{cases} \]

This retains the paper’s internal-weight model exactly, replacing voter counts by population mass. I expect this bounded-search problem to be Class A: Theorem 12 already supplies the required polynomial-time construction, and the continuous input permits the average weight vector \(\bar q\) to be computed directly from type masses. The natural stronger question is exact minimization of \(d_H(p,p_{\mathrm{IWM}},\bar q)\), rather than merely attaining the theorem’s bound. Other questions include closing the remaining gaps in the bounds for \(g_\ell\), characterising strict rather than weak majority support, and determining whether the optimum depends only on \(\bar q\) or on the full joint distribution of \((v,q)\).

The third anchor is the paper’s Theorem 1, also proved by the authors:

“Deciding whether an instance \(I=P\) admits a Condorcet winner is co-NP-hard in the unweighted setting with odd \(n\).”

Here the continuous problem is particularly direct:

Continuous Condorcet Existence. Given a rational distribution \(\mu\) over \(v\in\{+1,-1\}^t\), with unweighted issue comparison \(w_j=\frac1t\), decide whether some proposal \(p\in\{+1,-1\}^t\) satisfies
\[ \sum_a\mu_a\, \operatorname{sgn}\!\left( \sum_{j=1}^t \frac1t\,v^a_j(p_j-p'_j) \right)\ge0 \]
for every competing proposal \(p'\in\{+1,-1\}^t\). A yes-solution is such a proposal \(p\).

I expect this problem to be Class B: hardness transfers from the discrete problem. Given a discrete profile \(P\) with \(n\) voters, set
\[ \mu_v=\frac{|\{i:v_i=v\}|}{n}. \]
For every pair \(p,p'\), the continuous comparison is exactly the discrete comparison divided by \(n\). Hence the Condorcet winners are identical. A polynomial algorithm for the continuous problem, parameterised by \(t\), support size \(\tau\), and mass encoding length, would solve the paper’s discrete instances as well. This is useful evidence rather than a defect: the mirror preserves the paper’s central combinatorial hardness, which appears to live in the agenda of issues rather than in the number of named voters.

The further questions here are whether bounded \(t\), bounded support \(\tau\), or special type distributions yield tractable cases; whether approximate Condorcet winners admit continuous algorithms; and whether a sharper classification separates hardness caused by the issue agenda from hardness caused by population multiplicity.

These three mirrors cover the paper’s Theorems 8, 12, and 1: a tractable structural certificate, a tractable representative-selection guarantee, and a hardness result that survives continuization. They do not claim to mirror every topological, axiomatic, or extremal observation in the paper.

My weakest point is the lead mirror’s apparent insensitivity to mass: single-switch recognition depends only on which types occur, not on their frequencies. A sceptic could call that mere deduplication rather than a genuinely continuous social-choice problem. The answer is that the masses still determine the IWM and the resulting Condorcet winner; the certificate is deliberately a robust guarantee valid for every mass assignment on that support. More importantly, the second mirror makes mass enter the problem essentially through \(\bar q\) and support measures, while the third shows that even the exact population-distribution version can retain the paper’s co-NP-hardness. Together they make a credible positive case without pretending that every result becomes easier under continuization.