Constrained Approval Models for Testing Whether Synthetic Elections Can Stand In for Real Ones

Researchers who study voting rules, especially rules for participatory budgeting (where residents vote on which city projects get funded), mostly test those rules on synthetic elections drawn from simple statistical models. The standard model treats each ballot as a set of independent coin flips, one per candidate. That model has a known failure: it forces the number of projects each voter approves to cluster around one average value. Real ballots don't behave that way. Some voters approve one project and others approve twenty. This proposal replaces "independent coin flips" with "independent coin flips conditioned on the ballot's length or total cost." Candidate popularity and the voter's ballot constraint then become two separate, fittable parts of the model. The one hard computation in such a model is the probability that the coin flips land on a given length or cost. We compute it exactly with fast Fourier transforms (FFTs, an algorithm that turns repeated sums of distributions into cheap pointwise products). With that likelihood in hand, we ask the question synthetic-data research actually cares about: when a paper draws a conclusion about a voting rule from synthetic elections, does that conclusion hold on the held-out real election the generator was fit to?

In two sentences: we fit a "popularity plus ballot-constraint" generator to real participatory-budgeting elections by exact spectral maximum likelihood. We then measure, rule by rule and statistic by statistic, how many synthetic elections it takes to substitute for one real election, and when substitution fails outright.

Core Claim

Real approval ballots are better described as independent candidate attractiveness filtered through a per-voter constraint than as mixtures of unconstrained independent-approval models. Getting the constraint right matters more for downstream conclusions about voting rules than adding mixture components does. Learning Real-Life Approval Elections motivates this claim. That paper showed that single-component independent approval models cannot reproduce Pabulib ballot-length distributions, and that a 4-component mixture of such models fixes this. Its model log-likelihood correlated at 0.993 with the model's voter-anonymous Hamming distance to real data. Our view is that a mixture fixes ballot length indirectly, by spending whole popularity vectors on what is really a one-dimensional length or budget effect. A conditioned model captures any ballot-length distribution with a single popularity vector plus a free length distribution. That leaves mixture components free to capture genuine voter blocs.

The new element is not faster fitting of an existing model. It is a different model class, conditional Poisson in length and in cost. It needs an exact, differentiable normalizer, and in the cost-conditioned case that normalizer is only practical to compute spectrally. We pair this model class with a substitutability evaluation that no prior work in this area performs.

The Model and Its Computation

Let $w_c > 0$ be the popularity odds of candidate $c$ among $m$ candidates. Under the length-conditioned model, a ballot $S$ of size $k$ has probability

$$P(S \mid w, k) = \frac{\prod_{c \in S} w_c}{e_k(w)}, \qquad P(k) = \pi_k,$$

where $e_k(w)$ is the $k$-th elementary symmetric polynomial of the odds (the sum over all size-$k$ subsets of the product of their odds), and $\pi$ is a free categorical distribution over ballot lengths. This is exactly the conditional Poisson form that SFESS: Score Function Estimators for $k$-Subset Sampling uses for differentiable subset sampling. That work supplies the method: $e_k$ is read off a polynomial product computed by FFT, and its gradient comes from automatic differentiation.

The cost-conditioned variant replaces "size exactly $k$" with "total cost of approved projects at most $B$." Project $c$ has an integer cost $a_c$ on a discretized grid of size $K$. The normalizer becomes the cumulative distribution of $\sum_c a_c X_c$, where the $X_c$ are independent Bernoulli variables. This is a weighted Poisson-binomial sum over a large integer support, which is the probabilistic-integer-arithmetic setting of A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetics. A dynamic program over cost states costs roughly $m \cdot K$ per evaluation. A divide-and-conquer FFT product of the $m$ two-term polynomials costs roughly $K \log K \log m$ and batches across elections on a GPU.

Numerical stability is the known weak point. Exactly Computing the Tail of the Poisson-Binomial Distribution shows that plain FFT evaluation loses all accuracy below roughly $10^{-16}$. It fixes this with an exponential tilt, which keeps more than 10 digits of accuracy down to $10^{-400}$. Learning from Label Proportions via Proportional Value Classification had to clip probabilities to keep FFT backpropagation stable. Our conditioned models have a useful property here. Multiplying all odds by a common factor $e^{\lambda}$ leaves the length-conditioned distribution unchanged. We can therefore tilt the odds so that the expected length equals the observed $k$ before transforming. This keeps the relevant coefficient near the peak of the distribution, where FFT error is smallest, and costs nothing in modelling terms. The cost-conditioned case borrows the tilt directly from that tail-probability work.

Mixtures of $t$ conditioned components are fit by expectation-maximization. The M-step is gradient ascent on exact per-component likelihoods. We stay honest about the independence assumption: within a component, candidates are still independent given the constraint. Correlations between projects must come from the mixture.

Research Program

The program has three stages. First, we build the estimator, covering length- and cost-conditioned mixtures with tilted FFT normalizers. We validate it against brute-force enumeration on small elections and against the dynamic program on all elections.

Second, we fit every model class to the 271 Pabulib approval elections with at least 2,000 voters used by Learning Real-Life Approval Elections, drawn from the Pabulib library. The cost-conditioned model is fit only on instances whose metadata record project costs and a ballot cap. Voters in each election are split into training and held-out halves.

Third, and centrally, we run a substitutability study in the spirit of On the Equivalency, Substitutability, and Flexibility of Synthetic Data. That paper measured an exchange rate of about 30 synthetic frames per real frame for tracking. It also found that behavioral structure mattered more than surface fidelity, with multi-group synthetic scenes raising DanceTrack HOTA from 68.8 to 73.5. We transpose this question to elections. We compute rule-level statistics on the held-out real voters and on synthetic electorates sampled from each fitted generator, then measure the gap between them. The statistics are the winning committee and budget allocation under PAV and seq-PAV, overlap with the real outcome, axiom-satisfaction rates such as priceability, and pairwise committee distances between rules. The last two follow An Experimental Comparison of Multiwinner Voting Rules on Approval Elections, which reported PAV and seq-PAV satisfying priceability in 100% of its tested cases. We then ask whether that finding survives on generators fit to real data.

Baselines

The naive reference point is voter bootstrap. Synthetic electorates are resampled from the training-half voters, and we see how well they reproduce held-out statistics. This gives the noise floor any generator should approach, since a model cannot beat the data it was fit to. We also include a lower reference: generators from the classic synthetic cultures surveyed in How to Sample Approval Elections?. These are Impartial Culture and resampling models, which that paper showed fail to cover the region real Pabulib elections occupy. They stand in for current community practice.

The strongest existing method is the $t$-component independent-approval mixture fit by expectation-maximization from Learning Real-Life Approval Elections. It is the only generator in the file explicitly fit to real Pabulib data and shown to match real ballot-length distributions. That paper reports a 0.993 correlation between log-likelihood and distance to real data, and it reports that 4 components bring voter-anonymous Hamming distance down to the variance among real elections. We found no reported held-out per-voter log-likelihood or rule-level statistic for it on Lacuna, so we will re-run it ourselves. The comparison will be fair: same voter splits, same expectation-maximization initialization budget, the same random-restart count, and component counts from 1 to 8 for both families. Results will be reported against total parameter count as well as component count.

Beating it means two things. First, higher held-out log-likelihood per voter at equal or smaller parameter count, on a clear majority of elections under a paired test. Second, a smaller real-versus-synthetic gap on the rule-level statistics.

Three ablations isolate the key ingredient. The first compares length conditioning alone against cost conditioning. The second compares a single conditioned component against conditioned mixtures, which tells us whether conditioning or mixing carries the gain. The third evaluates the identical length-conditioned model with a dynamic-program normalizer instead of the FFT one. This last ablation should change runtime and numerical error but not fit quality, and we will report it that way.

Why not just…?

Why not just add more components to the existing independent-approval mixture? This is the most serious threat. With enough components, a mixture can approximate any ballot-length distribution, and the mixture from Learning Real-Life Approval Elections already fits well at 4 components. Our bet is that it does so inefficiently: components get spent on length rather than on voter blocs, and this distorts candidate co-approval, the quantity proportional rules are sensitive to. The component sweep at matched parameter count settles the question. If independent-approval mixtures match our held-out likelihood and rule-level gaps at equal parameters, the conditioning claim fails and we will report that.

Why not just sample a ballot length from the empirical histogram, then draw that many candidates in proportion to popularity? This heuristic generator needs no spectral computation and may produce realistic-looking ballots. However, sequential draws without replacement do not give a closed-form subset likelihood. Its popularity weights can only be set by moment matching, and it cannot be scored on held-out likelihood, which is the metric that tracks realism at 0.993. We include it as a baseline in the substitutability study. If it matches our generator on rule-level gaps, we will conclude that exact likelihood matters for model selection but not for downstream use.

Why not just use a dynamic program instead of FFTs? For length conditioning with tens to low hundreds of candidates, a dynamic program is fast enough, and we will use it as a correctness check. The FFT is justified only where it is actually needed. In the cost-conditioned model, the support is a discretized budget grid, and FFT products batch on GPUs. That mirrors the more than 10-fold FFT speedup over dynamic programming at bag size 512 reported by Learning from Label Proportions via Proportional Value Classification. The ablation reports wall-clock time for both normalizers so readers can see where the crossover occurs.

Why not just evaluate generators with Approvalwise distance? Approvalwise distance correlates at 0.989 with isomorphic Hamming distance according to How to Sample Approval Elections?, and we report it. But it compares sorted approval scores. It is blind to how ballot length and co-approval structure interact, and it cannot train a generator. Our substitutability test asks whether a low distance actually predicts a small gap on rule-level conclusions.

Proposed Experiments and Decisive Checks

The first check is fit quality. We measure held-out log-likelihood per voter across the 271 elections, along with total variation between synthetic and real ballot-length distributions and, where costs are recorded, ballot-cost distributions. All generators are compared at matched parameter counts.

The second check is substitutability. For each generator and statistic, we compute the gap between real and synthetic values. We then compute an exchange rate: the number of synthetic electorates needed to estimate the held-out statistic with the same error as a bootstrap from $n$ real training voters. This is the election analogue of the roughly 30:1 tracking ratio.

The decisive outcome has two sides. If conditioned models achieve a finite and small exchange rate for PAV and seq-PAV committee overlap and for priceability rates, while unconstrained cultures show a gap that does not shrink with more samples, then the validation gap is structural, not a matter of volume. The same pattern holds if the 100% priceability figure measured on 6,000 synthetic instances of 100 candidates and 100 voters shifts noticeably on fitted generators. The claim fails if the matched-parameter independent-approval mixture closes the same gaps.

A final robustness check refits on only the first 20% of each election's training voters. This shows whether constrained generators reach bootstrap-level fidelity from less real data, which is the practical promise of substitution.