ΑΙhub.org
How much can fair budget-division rules resist manipulation?
Fairness, efficiency and complete resistance to manipulation cannot coexist in approval-based budget division. In our paper, we ask what the best achievable compromise is. We prove that the Nash product rule reaches the optimal frontier.
The problem we study
We study settings in which a fixed, divisible resource must be distributed among candidates or projects. The resource might be public money, research funding, charitable donations or even screen time. Each voter reports which candidates they approve, and their utility is the total share assigned to those candidates.
A good allocation rule should be efficient, should treat voters and groups fairly, and should make truthful reporting a best response. Previous work shows that no rule can satisfy all three requirements exactly. We therefore replace the all-or-nothing demand of strategyproofness with a quantitative question: how much can a voter gain by lying?
Figure 1. Left: the truthful profile. Right: one voter changes a single approval and increases utility from 1/2 to 2/3.
Measuring manipulability
We measure manipulability using the incentive ratio. An incentive ratio of 1 is exact strategyproofness. A ratio of α means that no voter can increase their utility by more than a factor of α through a misreport. This distinction matters: a rule may technically be manipulable while still placing a strong ceiling on the possible benefit.
Our main result: the Nash rule has incentive ratio 2
The Nash product rule selects an allocation that maximizes the product of the voters’ utilities. It is a natural compromise rule: improving a poorly served voter can have a large effect on the product, but the rule also remains Pareto efficient.
We prove that the incentive ratio of the Nash product rule is exactly 2. Thus, even in the worst case, a voter cannot more than double their truthful utility by manipulating. Our factor-2 upper bound continues to hold when reports range over broad classes of concave utility functions, not only approval ballots.
Why the factor 2 is genuinely optimal
A guarantee is most useful when we know whether it can be improved. We establish matching lower bounds under several natural requirements. In particular, no rule satisfying average fair share, one of the fairness conditions satisfied by the Nash rule, can have incentive ratio below 2. The same barrier applies to regular rules that are efficient and satisfy group fair share, and to additively separable strictly concave welfare maximizers.
These results show that 2 is not merely a consequence of our chosen distribution rule. It is the cost of retaining meaningful fairness and efficiency guarantees. To obtain a lower incentive ratio, a designer would have to weaken at least one of those requirements.
Figure 2. NASH is the only displayed rule combining exact efficiency and average fair share with a constant incentive ratio.
The comparison above also clarifies why the result is useful. Several familiar fair or efficient rules have incentive ratios that grow with the number of voters or candidates. By contrast, the Nash rule’s worst-case guarantee remains constant.
What we observed in synthetic experiments
Worst-case guarantees describe what can happen, but not what typically happens. We therefore tested four rules on approval profiles generated from impartial, Euclidean and Mallows models. For each profile, we searched for profitable approval misreports and measured both their frequency and their size. NASH was manipulable on essentially every sampled profile, yet the average gain remained small—between 1.11 and 1.18 across the three models. This illustrates an important distinction: the frequency of manipulation and the benefit from manipulation are different questions. A rule can often admit some profitable misreport while still making large gains impossible.
Why this matters
Our results provide a way to reason about collective funding when perfect incentive compatibility is unattainable. Instead of abandoning fairness or efficiency, system designers can ask for a rigorous bound on strategic advantage. The Nash product rule supplies such a bound, and our lower bounds show that it is the strongest one available under broad, natural conditions.
The result applies wherever a divisible resource must reflect many people’s priorities: public and participatory budgets, research or institutional funding, charitable giving and other shared-resource decisions. It gives a theoretical basis for allocation systems that remain fair and efficient while limiting the rewards from strategic behaviour.
Award and support
Our paper received a Distinguished Paper Award at IJCAI–ECAI 2026, where Jeremy Vollen presented the work. The project was supported by Fair Sequential Collective Decision-Making, jointly funded through the CSIRO–US National Science Foundation collaboration in responsible and equitable AI.
Useful links
tags: ECAI, ECAI2026, IJCAI, IJCAI2026
AUAI is supported by:
