Structure in Dichotomous Preferences

The strongest honest positive case is a Class A mirror for the paper’s approval-based committee-selection results. It is important, however, that the paper contains no numbered hardness theorem of its own: its statements that unrestricted PAV and MAV are NP-hard are literature summaries citing other papers. I therefore use the paper’s numbered algorithmic theorems as anchors, and treat those hardness statements only as motivation.

Take a finite candidate set \(C\), \(|C|=m\), and let a voter type be an approval set \(A\subseteq C\). A continuous society is a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\), with \(\mu_A\ge 0\) and \(\sum_A\mu_A=1\). Only the \(\tau\) positive-mass types are listed. The mass \(\mu_A\) is the fraction of the population with approval type \(A\). The decision remains an integral size-\(k\) committee \(W\subseteq C\), \(|W|=k\): only the population is continuized.

For \(w\)-PAV, write \(u_w(r)=\sum_{j=1}^r w_j\). The continuous objective is

\[ \Phi_w(W)=\sum_{A}\mu_A\,u_w(|W\cap A|). \]

For ordinary PAV, \(w_j=1/j\). The continuous MAV objective is

\[ \operatorname{MAV}_\mu(W) = \max_{A:\mu_A>0} \bigl(|W\setminus A|+|A\setminus W|\bigr). \]

This is an exact high-multiplicity lift. If every \(\mu_A\) has denominator dividing \(N\), expanding the distribution into \(N\mu_A\) voters of type \(A\) multiplies every PAV score by \(N\) and leaves MAV unchanged. Conversely, every finite profile compresses to such a distribution. Thus the input size depends on \(\tau\) and the mass bit-length rather than on the potentially enormous electorate size \(N\).

This regime is plausible for large approval elections, public consultations, party or demographic blocs, or institutional electorates in which millions of agents share one of relatively few complete approval patterns. The structural restrictions in the paper also have a natural population interpretation: type blocks can be arranged along a one-dimensional social axis, while candidates remain ordered on a policy axis. For example, continuous-VEI means that, after arranging the type blocks along \([0,1]\), each candidate is approved by a prefix or suffix of the population; continuous-CI means that some candidate order makes every approval set an interval.

My lead anchor is Theorem 13, proved in this paper. It states:

Given a dichotomous profile \(P\), candidate set \(C\), and target committee size \(k\), if \(P\) satisfies VEI, CEI, WSC, or PART, then a winning committee under both MAV and PAV can be found in polynomial time.

The corresponding problem is Continuous Structured Approval Winner Determination. An instance consists of \(C\), \(k\), a rational distribution \(\mu\) over approval types, and the promise that the positive-mass type blocks satisfy one of VEI, CEI, WSC, or PART. The task is to output a size-\(k\) committee maximizing \(\Phi_{\mathrm{PAV}}(W)\), or, in the MAV variant, minimizing \(\operatorname{MAV}_\mu(W)\).

I would expect this problem to remain in Class A, with running time polynomial in \(m\), \(\tau\), and the mass encoding length. The proof of Theorem 13 does not fundamentally use named voters. Under VEI, CEI, WSC, and PART, voters fall into a constant number of approval-pattern classes or nested candidate groups. PAV merely replaces integer multiplicities by rational weights \(\mu_A\); the same category comparisons and greedy choices can be performed with exact rational arithmetic. MAV is even more direct: its objective is the worst dissatisfaction among positive-mass types.

This is not an outcome-space relaxation. The committee remains integral, and the candidate set is unchanged. What disappears is only the irrelevant distinction between millions of agents with the same approval vote. The natural follow-up questions are whether the unrestricted distributional PAV and MAV problems retain discrete hardness, whether approximate winner determination is possible when \(\tau\) is large, and whether one can handle “almost-VEI” or “almost-CI” populations.

My second anchor is Theorem 9, also proved here. It states:

Given a dichotomous profile \(P=(v_1,\ldots,v_n)\), candidate set \(C\), and committee size \(k\), if every voter approves at most \(s\) candidates and \(P\) satisfies VI, then a PAV-winning committee can be found in time \(O(2^{2s}kn)\).

The matching problem is Continuous VI-Small-Approval PAV. An instance consists of \(C\), \(k\), a rational distribution \(\mu\) over \(\tau\) approval types, a VI ordering of those types, and the bound \(|A|\le s\) for every positive-mass type. The task is to output a size-\(k\) committee maximizing

\[ \sum_A \mu_A H_{|W\cap A|}, \qquad H_r=\sum_{j=1}^r \frac{1}{j}. \]

The natural continuous analogue of the theorem’s dynamic programme processes the \(\tau\) type blocks rather than \(n\) individual voters. Its state space is unchanged except that the contribution of type \(A_i\) is multiplied by \(\mu_{A_i}\). Thus I would expect \(O(2^{2s}k\tau)\) arithmetic operations, and fixed-parameter tractability in \(s\), with polynomial dependence on the rational input length.

This second mirror is useful because it makes the high-multiplicity gain explicit: the running time depends on the number of distinct approval types, not on the number of voters represented by those types. If the approval-size bound is removed, or VI is removed, I would expect the unrestricted problem to fall into Class B whenever the known discrete PAV hardness reductions can be encoded using rational masses.

The paper’s Theorem 8 provides useful supporting machinery, although I would not make it a third anchor. It proves that CEI, CI, VI, and VEI can be detected in \(O(mn)\) time using the consecutive-ones property. In the continuous version, duplicate voters are discarded and only the \(\tau\) support types remain, so the corresponding recognition problem should run in \(O(m\tau)\), again with rational input processing. This means the winner problems need not hide behind an unverifiable structural promise.

The weakest point is that these mirrors may look like weighted finite-profile problems rather than a dramatic new continuum theory. That criticism is fair, especially for MAV, whose objective depends only on which types have positive mass and not on their magnitudes. The defence is that high multiplicity is precisely the intended object: a society represented by type masses, with integral committees and exponentially compressed populations. The paper already studies approval profiles whose voters are interchangeable whenever they share a vote; replacing their multiplicities by rational masses is therefore faithful to the authors’ problem, not a tractability-motivated change of subject. The positive claim should remain modest: this paper supports a credible, concrete Class A continuous-population programme for structured approval elections, rather than a claim that all of its discrete hardness disappears.