Approximate Strategyproofness in Approval-based Budget Division
Haris Aziz, Patrick Lederer, Jeremy Vollen
IJCAI'26
cs.GT, econ.TH
2026-05-12
Relaxing strategyproofness to incentive ratio, the Nash product rule is fair, efficient, and at most doubles a liar’s utility; 2 is optimal under several fairness conditions.
Participatory budgeting and donor coordination both split a divisible resource across projects from voters' preferences. This paper studies approval-based budget division: each voter marks liked versus disliked candidates, the rule returns a share for every candidate, and a voter's utility is the total share on her approved set.
Three demands collide. Strategyproofness: lying must not help. Efficiency: nobody can be made better off without hurting someone else. Fairness: groups of voters should be guaranteed a share in proportion to their size. Brandl et al. (2021) proved that strategyproofness plus efficiency already kill even the weakest fairness axiom (strictly positive utility for every voter). Known strategyproof rules (utilitarian, conditional utilitarian) fail efficiency or fairness badly. How manipulable the fair-and-efficient rules actually are was an open quantitative question.
The paper relaxes strategyproofness to the incentive ratio: the worst-case multiplicative utility gain a voter can get by misreporting. A ratio of 1 is strategyproof; larger means a worse worst case.
Theory first delivers three negative bounds. The maximum payment rule (MP) and the fair utilitarian rule (FUT) have incentive ratio \(\Theta(n)\); the egalitarian rule (EGAL) has \(\Theta(m)\). The positive result is the Nash product rule (NASH), which maximises the product of utilities: its incentive ratio is exactly 2, and the same bound holds when voters may report arbitrary concave utilities, not only approval ballots. A group version also holds: no coalition can make every member more than twice as well off.
The constant 2 is tight in several natural classes. Every rule that satisfies average fair share (AFS), every strictly concave additively separable welfare maximiser, and every regular rule (anonymous, neutral, independent of losers) that is efficient and satisfies group fair share has incentive ratio at least 2. NASH sits in all three classes, so the upper and lower bounds meet.
Experiments sample 1000 profiles for each n in {10,...,100} with m=10 candidates, under three ballot models (impartial culture with independent approval probability 0.3, a Euclidean model in the 3d unit ball with radius 0.4, and truncated Mallows with dispersion \(\phi=0.75\)), then enumerate single-voter manipulations.
The theoretical picture:
| Rule | Incentive ratio | Efficiency | Fairness |
| NASH | 2 | yes | AFS and the core |
| EGAL | \(\Theta(m)\) | yes | weak only |
| FUT | \(\Theta(n)\) | yes | group fair share |
| MP | \(\Theta(n)\) | no | group fair share, factor 2 |
Average incentive ratio and fraction of manipulable profiles at n=100, m=10:
| Rule | Impartial | Euclidean | Mallows |
| NASH | 100%, 1.12 | 100%, 1.18 | 100%, 1.11 |
| EGAL | 97%, 1.74 | 100%, 1.74 | 99%, 1.73 |
| FUT | 92%, 1.17 | 75%, 1.14 | 70%, 1.10 |
| MP | 99%, 2.52 | 89%, 1.79 | 90%, 1.29 |
NASH is manipulable on essentially every profile, yet the average gain stays below 1.2 and the experimental maximum is about 1.5. FUT's worst-case \(\Theta(n)\) does not show up in typical draws: its mean sits next to NASH, while its maximum is usually 2 to 3. EGAL is driven by free-riding (approving only currently zero-share liked candidates) to a mean near 1.74. MP's mean is pulled by extremes; the authors saw a profile with ratio 37.
Mixing NASH with the uniform distribution can push the incentive ratio into the 6/5 to 4/3 range, but only with a small mixing weight that washes out NASH's fairness and efficiency.
If a participatory-budgeting or donation platform wants a rule that is both fair and efficient, NASH is the option that currently stands on axioms: lying at most doubles utility, and that factor cannot be improved under the fairness conditions above. For a practitioner, that sentence is more useful than "NASH is manipulable". The experiments also warn against quoting worst-case bounds for FUT as typical behaviour: the mean looks tame, the tail does not.
For mechanism design, the incentive ratio turns Brandl's impossibility from "you cannot have all three" into "once strategyproofness is relaxed, 2 is the optimal constant under fairness". Linear-utility Fisher markets have the same incentive ratio of 2, so the constant is not an artefact of approval ballots.
NASH is almost always manipulable. The incentive ratio caps the multiplicative gain; it says nothing about how hard a manipulation is to find or to coordinate. The paper does not study computational complexity, and it does not put strategyproofness, efficiency, and fairness into one joint approximation. Mixing with the uniform distribution buys a smaller ratio only by giving up NASH's axioms, and the authors do not recommend that path.
Experiments freeze m=10 and use three synthetic ballot models, with no real participatory-budgeting traces. Single-voter manipulations are enumerated; group manipulations have only the theoretical "not everyone can more than double" guarantee, and no experiment. The gap between FUT's worst case and its mean is reported, not explained.