Auditing Randomized Mechanisms on Synthetic Voters

When money cannot change hands, as in organ exchange, school choice, or deciding which city projects get funded, a designer can still keep people honest by verification: checking some of what agents claim and punishing lies that are caught. Checking is costly, so the designer wants to check only the lies that would actually pay off. Partial Verification as a Substitute for Money shows how much checking that requires depends on the kind of mechanism. A deterministic rule has a wide "harmless set", the set of lies that gain the liar nothing, so only a few boundaries need policing. A randomized rule that is only truthful in expectation (honest reporting is optimal on average over the rule's coin flips, but not for every coin outcome) has razor-thin harmless sets and needs checks almost everywhere. In practice the designer rarely knows the true population of agent types. So which lies to audit is typically decided by simulating agents from a synthetic generator.

This note asks what happens to that audit plan when it meets real people. Our claim is that audit plans calibrated on synthetic agents transfer well for deterministic and universally truthful mechanisms, but fail badly for truthful-in-expectation mechanisms. We further claim that the size of the failure is predicted by one measurable property of the generator: how accurately it reproduces the share of agents whose honest-versus-lying payoff gap is close to zero. It is not predicted by how close the synthetic data looks to real data overall. We test this on real participatory-budgeting ballots, where the generators, the real data, and the mechanisms can all be computed exactly.

Core Claim

Consider an allocation rule $f$ that is not truthful on its own, a set $A$ of misreports the designer audits, and a truthful type $\theta$. Define the agent's incentive margin as

$$ m_A(\theta) = \min_{\hat\theta \notin A} \big[ u_\theta(f(\theta)) - u_\theta(f(\hat\theta)) \big], $$

where $u_\theta$ is the agent's expected utility over the rule's randomness and the minimum runs over misreports $\hat\theta$ that escape auditing. The agent can profitably lie undetected exactly when $m_A(\theta) < 0$.

For a randomized rule, a misreport shifts only probabilities, so utility differences are products of small probability changes. Margins therefore pile up near zero. For a deterministic rule, or a lottery over deterministic truthful rules, a misreport either flips an outcome or does nothing, so margins stay away from zero except at a few boundaries.

This leads to a concrete prediction. Suppose $A$ is chosen to minimize violations under a synthetic distribution $Q$ and then deployed on the real distribution $P$. The rise in violations is roughly the difference between $P$ and $Q$ in the mass they place on margins in $(-\delta, 0]$. For the fragile mechanism class this mass is large and very sensitive to local structure in the data. The central empirical claim is therefore that margin-mass error, and not global fidelity, governs the synthetic-to-real transfer of audit plans. It does so strongly for truthful-in-expectation rules and weakly for universally truthful ones.

Relation to Prior Work

Four papers motivate the question.

  • Partial Verification as a Substitute for Money supplies the harmless-set geometry and the fragility result. It assumes the designer knows the continuous type space analytically. We instead calibrate and evaluate from samples.
  • Estimating Approximate Incentive Compatibility estimates an auction's maximum gain from lying from $N$ samples, with error shrinking at $\tilde O(1/\sqrt N)$. It assumes the samples come from the true distribution and uses no verification. We keep its estimator as a baseline but draw from misspecified generators and add audits.
  • Limitations of Incentive Compatibility on Discrete Type Spaces shows that constraints enforced only on sample points can produce "phantom" revenue and fail to extend to continuous types. It treats only deterministic, money-based mechanisms and explicitly leaves truthful-in-expectation extensions open. That open case is ours, with verification in place of money.
  • Distributionally Robust Optimal Allocation with Costly Verification handles an unknown type distribution through moment-based ambiguity sets for a single good. We replace moment bounds with fitted generators on a combinatorial problem.

Two papers supply methods.

  • Learning Real-Life Approval Elections fits Impartial Culture and mixtures of Independent Approval Models to Pabulib. It shows single-component models fail on polarized electorates, while four-component mixtures come close to the real data's own internal variation in voter-anonymous Hamming distance. This gives us a graded ladder of generators whose global fidelity is already measured.
  • On the Equivalency, Substitutability, and Flexibility of Synthetic Data defines an exchange rate between synthetic and real samples (about 30:1 for tracking) and a substitutability fraction. We port both notions to audit calibration.

One paper constrains the design. Escaping Model Collapse via Synthetic Data Verification shows that filtering synthetic data drives learning toward the filter's own center rather than the truth. This warns that simply generating more synthetic agents should plateau at the generator's bias, and we test for that plateau.

One result seems to cut against us. The estimation paper argues that randomness in other agents' types smooths expected-utility landscapes. If so, fragility might wash out. Our answer is that this smoothing applies to interim, averaged gains. Ex post violations for a specific real voter, facing a specific real profile of other voters, can persist beneath a smooth average. We therefore measure both quantities rather than assume one.

Research Program

The testbed is approval-based participatory budgeting drawn from the Pabulib archive. Following Learning Real-Life Approval Elections, we use the 271 elections with at least 2,000 voters. Each voter's type is an approval set. To make every harmless set computable by enumeration rather than approximation, we restrict each election to its 12 most-approved projects, which gives 4,096 possible ballots. Utility is the cost-weighted share of funded approved projects.

Verification means auditing a claimed approval. This could be a post-hoc check of residency or use, in the spirit of verification after the fact in Combinatorial Auctions Without Money. Lies that include an audited claim are detected and punished.

We compare three mechanism families matched on welfare as closely as possible:

  • Deterministic. Budget-feasible greedy funding by approval weight.
  • Universally truthful. Lotteries over deterministic rules, each of which is truthful given the audits.
  • Truthful-in-expectation. Welfare-maximizing lotteries whose incentive constraints hold only in expectation, obtained by linear programming over funding probabilities.

For each mechanism, generator, and audit budget, we choose the audit set by greedy coverage. The procedure repeatedly audits the misreport that removes the most sampled violations per unit audit cost. Generators, in increasing fidelity, are:

  • Impartial Culture;
  • a one-component Independent Approval Model;
  • a four-component mixture;
  • bootstrap resampling of real ballots from other cities;
  • in-sample resampling of the target election itself, which serves as an oracle.

Deployment is always on held-out real profiles in a leave-one-city-out split.

We then record, for each generator, three quantities: its global distance to the real data, its margin-mass error, and the realized rise in violations at deployment. The test is which of the first two predicts the third.

Baselines

Naive reference points. The first is no auditing at all, which shows each mechanism's raw manipulability on real ballots. The second is an audit plan calibrated on Impartial Culture, the default synthetic voter model in social choice. Beating these is necessary but not interesting.

Strongest existing method. This is sample-based manipulability estimation in the style of Estimating Approximate Incentive Compatibility, applied to draws from the best-fitting four-component approval mixture of Learning Real-Life Approval Elections. Audits are chosen to drive the estimated gain from lying below a tolerance.

This combination is the strongest competitor for two reasons: it is the most principled sample-based incentive estimate available, and it runs on the generator with the best documented fidelity. That paper reports a Pearson correlation of 0.993 between model log-likelihood and distance from real data. It also reports that mixture models reach voter-anonymous Hamming distances close to the real data's internal baseline. For manipulability or audit performance on Pabulib, no reported result was found on Lacuna for this combination. Likewise, the estimation paper reports only its convergence rate, not numbers on this data. We therefore establish the baseline number ourselves.

Real-data oracle. An audit plan calibrated on held-out real ballots from the target election sets the ceiling.

Fairness conditions. Every method receives the same audit budgets, the same number of calibration profiles, the same greedy audit-selection routine, and the same held-out deployment profiles.

What counts as success. The proposal wins in one of two ways. The first is a synthetic-calibrated audit plan, informed by margin mass, that reaches oracle-level deployed violations with at least 20% less audit cost than the strongest baseline for truthful-in-expectation rules. The second, more modestly, is margin-mass error predicting deployment failure where global distance does not.

Key ablation. We keep the four-component generator but reweight its samples toward low-margin types, and compare against uniform sampling at an equal sample count. This isolates the key ingredient: whether attention to near-zero margins, rather than extra fidelity, closes the gap.

Why not just…?

Why not just use universally truthful mechanisms and avoid fragility altogether? This is the most serious threat. Universally truthful lotteries keep the wide harmless sets of their deterministic parts (Partial Verification as a Substitute for Money). In facility location, the universally truthful random-sample median already achieves a $1+\epsilon$ approximation (Verifiably Truthful Mechanisms). Against this, universally truthful rules cannot beat a 5/4 approximation in combinatorial allocation without money (Combinatorial Auctions Without Money). Whether that gap matters for budgeting is unknown. We therefore report welfare against deployed violations and audit cost for both families on the same elections. If universally truthful lotteries lose under 2% welfare on Pabulib, the practical recommendation is simply to use them, and we will say so. The margin diagnostic then remains useful mainly for settings where randomization in expectation is unavoidable.

Why not just calibrate on real data? Pabulib has abundant ballots, but a new city launching budgeting does not have its own ballots yet. The leave-one-city-out split represents this case. The in-sample oracle and the cross-city bootstrap bracket what real data can do. We also measure an audit exchange rate: how many synthetic profiles buy the same deployed violation rate as one real profile, analogous to the 30:1 tracking ratio of On the Equivalency, Substitutability, and Flexibility of Synthetic Data. If a few hundred real ballots from a pilot suffice, that is itself the answer.

Why not just add a uniform safety buffer, or use moment-based robust sets? Distribution-free robustness in Distributionally Robust Optimal Allocation with Costly Verification produces conservative favored-agent rules for a single good. For truthful-in-expectation rules, the fragility result implies that any buffer wide enough to be safe covers nearly every misreport. We test this directly by sweeping buffer width and plotting audit cost against deployed violations next to the data-calibrated plans.

Why not just generate more synthetic voters? The error rate of the estimation paper holds only for draws from the true distribution. Under a biased generator, Escaping Model Collapse via Synthetic Data Verification predicts convergence to the generator's own center. We scale synthetic sample count by three orders of magnitude and check whether the deployment gap plateaus at a level set by margin-mass error.

Proposed Experiments and Decisive Checks

The first check tests the fragility-transfer claim directly. At a fixed audit budget, we compute the difference between violations measured on synthetic calibration data and violations realized on real deployment profiles. If fragility transfers as predicted, this difference should be at least several times larger for truthful-in-expectation rules than for universally truthful ones, across every generator short of the in-sample oracle. It should also stay large even for the four-component mixture, despite that model's near-baseline Hamming distance. If the gap is similar across mechanism classes, the core claim is false.

The second check is predictive. Across all combinations of generator, city, and budget, we regress the deployment gap on global Hamming distance and on margin-mass error separately. The claim survives only if margin-mass error explains substantially more variance for truthful-in-expectation rules.

The third check is the reweighting ablation described under Baselines.

The fourth check is the scaling sweep for a plateau.

Throughout, we report both ex post violations and interim average gains. This settles whether the smoothing argument of the estimation paper hides real, per-voter manipulability.

MOT17, DanceTrack, and the other file benchmarks are outside this game-theoretic setting and are not used. Pabulib is the only benchmark here with real strategic-agent preferences.