Learning Real-Life Approval Elections

The strongest honest positive case is a direct Class A mirror for the paper’s single-component maximum-likelihood learning problem. I would not claim that the paper’s Bayesian mixture experiments already yield a tractable continuous problem.

The population type is an approval ballot \(A\subseteq C\). A society is a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\), where \(\mu_A\) is the fraction of voters casting ballot \(A\). This is exactly the paper’s object after aggregation: if \(\mu_A=n_A/N\), then for every IAM distribution \(D\),

\[ \frac{1}{N}\ln P(E\mid D)=\sum_{A\subseteq C}\mu_A\ln P(A\mid D). \]

Thus clearing denominators recovers the finite election with \(n_A\) voters of type \(A\). This is not outcome-space continuity: the population itself is the continuous object, while the IAM parameters are the decision variables.

A plausible regime is a large participatory-budgeting or referendum population voting on a fixed set of tens or hundreds of projects, with many residents using recurring approval templates: neighbourhood packages, party or association recommendations, or stable issue bundles. There may be millions of voters but only tens, hundreds, or thousands of distinct ballots. That is a genuine high-multiplicity regime. I would not claim that every Pabulib election has this property; elections with almost entirely unique ballots are a weak setting for the mirror.

My lead anchor is Theorem 4.8, proved in this paper: there is a polynomial-time algorithm that, given an election and \(t\), finds a \(t\)-parameter IAM maximizing the probability of generating it.

The corresponding continuous problem is:

Continuous \(t\)-IAM Maximum-Likelihood Learning. Given \(C\), an explicitly represented rational society \(\mu\) over approval-ballot types \(A\subseteq C\), and \(t\le |C|\), choose a partition \(C=C_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}C_t\) and probabilities \(p_1,\ldots,p_t\in[0,1]\) maximizing

\[ \mathcal L_\mu(C_1,\ldots,C_t,p) = \sum_{A\subseteq C}\mu_A \sum_{j=1}^{t} \left( |A\cap C_j|\ln p_j+ |C_j\setminus A|\ln(1-p_j) \right). \]

A solution is the partition together with the maximizing parameters. For a fixed block \(C_j\), writing \(q_c=\sum_{A\ni c}\mu_A\), the optimal parameter is \(p_j=\sum_{c\in C_j}q_c/|C_j|\).

The proof structure of the paper survives the continuization. Sort candidates so that \(q_{c_1}\ge\cdots\ge q_{c_m}\). Theorem 4.7, proved here, implies that some optimum uses consecutive blocks in this order. A dynamic program over prefixes and the number of blocks then finds the optimum, exactly as in Theorem 4.8. The expected classification is therefore Class A: polynomial in the explicit society representation, \(m\), \(t\), and the numerical precision convention. In an approximation formulation, an \(\varepsilon\)-optimal partition and parameters are sufficient.

A smaller secondary anchor is Corollary 4.3, also proved here. Its continuous mirror is Continuous Full-IAM Learning: given \(\mu\), choose \(p_c\in[0,1]\) for every candidate to maximize the same expected log-likelihood. The unique coordinatewise optimum is simply \(p_c=q_c\). It is solvable by one pass over the ballot masses, and is again Class A. Corollary 4.6 gives the corresponding \(t=2\) special case.

The authors should recognise this as their problem rather than a tractable substitute. The input remains a society of approval voters; the likelihood remains exactly their likelihood; the action remains choosing an IAM model; and the objective is just the normalized log-likelihood. Remark 2.1 is especially helpful: the paper itself observes that anonymous and non-anonymous versions differ only by a factor independent of the model parameters. Aggregating voters with the same ballot therefore removes irrelevant identities rather than changing the learning task.

This mirror covers the single-component IAM results, including Corollary 4.3, Corollary 4.6, Theorem 4.7, and Theorem 4.8. I would not present the mixture results as an established tractable mirror. They do generate a natural follow-up:

\[ \max_{\alpha,p} \sum_A\mu_A \ln\!\left( \sum_{k=1}^{K}\alpha_k \prod_{c\in A}p_{c,k} \prod_{c\notin A}(1-p_{c,k}) \right), \]

the continuous \(K\)-component IAM maximum-likelihood problem. Proposition 4.10, proved here, supports a continuous EM formulation with responsibility masses \(\rho_{A,k}\), and Proposition 4.9 gives the component weights. But the global mixture problem is nonconvex, and the paper offers no polynomial-time global guarantee. It should remain an open follow-up, potentially Class C.

The weakest point is that making \(\mu\) explicit removes the paper’s statistical sampling issue. If the authors’ real target were recovering a hidden distribution from samples, this would be a different problem. My claim is narrower: their named Theorem 4.8 already takes the election as observed input and optimizes its likelihood, so replacing repeated voters by rational masses is a faithful high-multiplicity relaxation. The mirror is strong for that computational result, but it does not cover the full Bayesian or empirical-learning programme.