pith. machine review for the scientific record. sign in

arxiv: 2605.11736 · v1 · submitted 2026-05-12 · 💻 cs.GT · econ.TH

Recognition: no theorem link

Approximate Strategyproofness in Approval-based Budget Division

Haris Aziz , Patrick Lederer , Jeremy Vollen
Authors on Pith no claims yet

Pith reviewed 2026-05-13 04:23 UTC · model grok-4.3

classification 💻 cs.GT econ.TH
keywords approval-based budget divisionincentive ratioNash product ruleapproximate strategyproofnessfair divisionmechanism designparticipatory budgeting
0
0 comments X

The pith

The Nash product rule achieves an incentive ratio of 2 in approval-based budget division, allowing fairness and efficiency while limiting manipulation gains.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

In approval-based budget division, no rule can be exactly strategyproof, efficient, and fair at once. This paper demonstrates that the Nash product rule satisfies fairness and efficiency with an incentive ratio of only 2, meaning no voter can multiply their utility by more than 2 through misreporting. The bound is tight under the rule's other properties. The same incentive ratio of 2 holds when voters report arbitrary concave utility functions rather than strict approvals. An experimental analysis is provided to complement the theoretical bounds.

Core claim

The Nash product rule (NASH) has an incentive ratio of 2. This quantifies that the maximum multiplicative utility gain any single voter can obtain by misreporting their preferences is 2. The result bypasses the impossibility of exact strategyproofness, efficiency, and fairness by relaxing to approximate strategyproofness. The bound of 2 is optimal given the fairness and efficiency properties satisfied by NASH, and the guarantee extends to settings where voters may report any concave utility functions.

What carries the argument

The Nash product rule, which maximizes the product of all voters' utilities, paired with the incentive ratio defined as the supremum of the maximum multiplicative utility gain from any single voter's misreport.

If this is right

  • Several classical distribution rules exhibit large incentive ratios and therefore do not achieve the same approximate strategyproofness.
  • An incentive ratio of 2 is the best possible bound that is compatible with the fairness and efficiency properties of NASH.
  • The incentive ratio of 2 continues to hold when voters report arbitrary concave utility functions instead of approval sets.
  • Theoretical results are complemented by an experimental analysis of the rule's behavior on concrete instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bounded manipulation gain suggests the rule remains attractive for participatory budgeting applications even if voters have limited information or computational power for strategic deviation.
  • Similar relaxations to approximate strategyproofness could be tested in other resource allocation settings where exact strategyproofness is known to be incompatible with fairness.
  • The experimental analysis may reveal whether the worst-case ratio of 2 is frequently attained in practice or whether typical instances show much smaller gains.

Load-bearing premise

The incentive ratio is defined as the supremum of multiplicative utility gains from misreporting, and the Nash product rule satisfies the fairness and efficiency properties used to establish optimality of the bound.

What would settle it

An explicit instance of approval-based budget division in which some voter obtains more than twice their truthful utility by misreporting under the Nash product rule, while the rule continues to meet its fairness and efficiency axioms.

Figures

Figures reproduced from arXiv: 2605.11736 by Haris Aziz, Jeremy Vollen, Patrick Lederer.

Figure 1
Figure 1. Figure 1: Approximation ratios of common distribution rules to strategyproofness, efficiency, and fairness. In each row, we show for [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of our distribution rules and the incentive ratio. The pie charts display the distributions chosen by [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Profiles for the proof of Claim (3) of Theorem [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Summary of our experiments. For each rule, we show the percentage of manipulable profiles (Freq) and the average [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Average incentive ratio of our rules in dependence of the number of voters in the euclidean model. [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Full summary of our simulations with the impartial culture model. Avg, Max, 0.9P, and Std respectively indicate the [PITH_FULL_IMAGE:figures/full_fig_p023_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Full summary of our simulations with the euclidean model. Avg, Max, 0.9P, and Std respectively indicate the average, [PITH_FULL_IMAGE:figures/full_fig_p024_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Full summary of our simulations with the truncated Mallow’s model. Avg, Max, 0.9P, and Std respectively indicate the [PITH_FULL_IMAGE:figures/full_fig_p024_8.png] view at source ↗
read the original abstract

In approval-based budget division, the task is to allocate a divisible resource to the candidates based on the voters' approval preferences over the candidates. For this setting, Brandl et al. [2021] have shown that no distribution rule can be strategyproof, efficient, and fair at the same time. In this paper, we aim to circumvent this impossibility theorem by focusing on approximate strategyproofness. To this end, we analyze the incentive ratio of distribution rules, which quantifies the maximum multiplicative utility gain of a voter by manipulating. While it turns out that several classical rules have a large incentive ratio, we prove that the Nash product rule ($\mathsf{NASH}$) has an incentive ratio of $2$, thereby demonstrating that we can bypass the impossibility of Brandl et al. by relaxing strategyproofness. Moreover, we show that an incentive ratio of $2$ is optimal subject to some of the fairness and efficiency properties of $\mathsf{NASH}$, and that the positive result for the Nash product rule even holds when voters may report arbitrary concave utility functions. Finally, we complement our results with an experimental analysis.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies approximate strategyproofness in approval-based budget division. It proves that the Nash product rule (NASH) has an incentive ratio of exactly 2 (the supremum of multiplicative utility gain from misreporting), shows that this bound is tight for any rule satisfying the same fairness and efficiency axioms as NASH, establishes that the bound continues to hold when voters may report arbitrary concave utility functions, and complements the theory with experimental analysis. This circumvents the impossibility of Brandl et al. (2021) by relaxing exact strategyproofness.

Significance. If the proofs are correct, the result supplies a tight, parameter-free bound on approximate strategyproofness for a canonical rule that retains the fairness and efficiency properties used in the impossibility theorem. The extension to general concave utilities and the matching lower bound under the same axioms strengthen the contribution. The experimental component provides practical calibration of the ratio. These elements together offer a concrete, falsifiable relaxation that is directly usable in mechanism design for divisible resource allocation.

minor comments (3)
  1. [Section 2] The definition of the incentive ratio (supremum over all instances and all misreports) is introduced early but its relation to the specific utility normalization used in the Nash product is not restated before the main theorem; a one-sentence reminder would improve readability.
  2. [Section 5] The experimental section reports average and worst-case ratios but does not specify the distribution over approval profiles or the number of Monte-Carlo repetitions; adding these details would make the numerical claims reproducible.
  3. [Theorem 3] The statement that the bound of 2 is optimal 'subject to some of the fairness and efficiency properties of NASH' should explicitly list the axioms used in the lower-bound construction (e.g., which form of proportionality or efficiency).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their supportive summary of our results on the incentive ratio of the Nash product rule, its tightness under the relevant axioms, the extension to concave utilities, and the experimental analysis. We appreciate the positive significance assessment and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; proofs are self-contained mathematical bounds

full rationale

The paper derives an incentive ratio bound of exactly 2 for the Nash product rule via explicit analysis of multiplicative utility gains under misreporting, shows tightness under the rule's fairness/efficiency axioms, and extends the result to concave utilities. These steps rely on the standard definition of incentive ratio (supremum of gain) and direct bounding arguments rather than any reduction to fitted inputs, self-definitional constructs, or load-bearing self-citations. The cited impossibility from Brandl et al. serves only as external motivation and is not used to force the positive result. The derivation chain is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard definitions from social choice theory; full details of any additional assumptions are not visible from the abstract alone.

axioms (2)
  • domain assumption Voters report approval sets or concave utility functions over budget allocations.
    This is the preference model used to define utilities and manipulation gains.
  • domain assumption Incentive ratio is the supremum over all instances of the ratio of manipulated utility to truthful utility.
    This is the standard quantitative measure of approximate strategyproofness employed in the analysis.

pith-pipeline@v0.9.0 · 5491 in / 1422 out tokens · 125814 ms · 2026-05-13T04:23:08.539560+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Airiau, H

    S. Airiau, H. Aziz, I. Caragiannis, J. Kruger, J. Lang, and D. Peters. Portioning using ordinal preferences: Fairness and efficiency. InProceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 11–17, 2019

    work page 2019

  2. [2]

    Aziz and N

    H. Aziz and N. Shah. Participatory budgeting: Models and approaches. In T. Rudas and G. Péli, editors, Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations, pages 215–236. Springer International Publishing, 2021. 14

    work page 2021

  3. [3]

    H. Aziz, A. Bogomolnaia, and H. Moulin. Fair mixing: the case of dichotomous preferences.ACM Transactions on Economics and Computation, 8(4):18:1–18:27, 2020

    work page 2020

  4. [4]

    H. Aziz, P. Lederer, X. Lu, M. Suzuki, and J. V ollen. Approximately fair and population consistent budget division via simple payment schemes. InProceedings of the 26h ACM Conference on Economics and Computation (ACM-EC), page 349, 2025

    work page 2025

  5. [5]

    X. Bei, B. Tao, J. Wu, and M. Yang. The incentive guarantees behind nash welfare in divisible resources allocation. Artificial Intelligence, 344:104335, 2025

    work page 2025

  6. [6]

    Boehmer, P

    N. Boehmer, P. Faliszewski, L. Janeczko, A. Kaczmarczyk, G. Lisowski, G. Pierczy ´nski, S. Rey, D. Stolicki, S. Szufa, and T. W ˛ as. Guide to numerical experiments on elections in computational social choice. InProceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 7962–7970, 2024

    work page 2024

  7. [7]

    Bogomolnaia, H

    A. Bogomolnaia, H. Moulin, and R. Stong. Collective choice under dichotomous preferences. Mimeo, 2002

    work page 2002

  8. [8]

    Bogomolnaia, H

    A. Bogomolnaia, H. Moulin, and R. Stong. Collective choice under dichotomous preferences.Journal of Economic Theory, 122(2):165–184, 2005

    work page 2005

  9. [9]

    Brandl, F

    F. Brandl, F. Brandt, D. Peters, and C. Stricker. Distribution rules under dichotomous preferences: Two out of three ain’t bad. InProceedings of the 22nd ACM Conference on Economics and Computation (ACM-EC), pages 158–179, 2021

    work page 2021

  10. [10]

    Brandl, F

    F. Brandl, F. Brandt, M. Greger, D. Peters, C. Stricker, and W. Suksompong. Funding public projects: A case for the Nash product rule.Journal of Mathematical Economics, 99:102585, 2022

    work page 2022

  11. [11]

    Brandt, M

    F. Brandt, M. Greger, E. Segal-Halevi, and W. Suksompong. Coordinating charitable donations with Leontief preferences.Journal of Economic Theory, 230:106096, 2025

    work page 2025

  12. [12]

    B. R. Chaudhury, L. Li, M. Kang, B. Li, and R. Mehta. Fairness in federated learning via core-stability. In Proceedings of the 36th International Conference on Neural Information Processing Systems, pages 5378–5750, 2022

    work page 2022

  13. [13]

    N. Chen, X. Deng, and J. Zhang. How profitable are strategic behaviors in a market? InProceedings of the 19th European Symposium on Algorithms (ESA), pages 106–118, 2011

    work page 2011

  14. [14]

    N. Chen, X. Deng, H. Zhang, and J. Zhang. Incentive ratios in Fisher markets. InProceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pages 464–475, 2012

    work page 2012

  15. [15]

    N. Chen, X. Deng, B. Tang, and H. Zhang. Incentives for strategic behavior in Fisher market games. InProceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pages 453–459, 2016

    work page 2016

  16. [16]

    N. Chen, X. Deng, B. Tang, H. Zhang, and J. Zhang. Incentive ratio: A game theoretical analysis of market equilibria.Information and Computation, 285:104875, 2022

    work page 2022

  17. [17]

    R. Cole, V . Gkatzelis, and G. Goel. Mechanism design for fair division: allocating divisible items without payments. InProceedings of the 14th ACM Conference on Electronic Commerce (ACM-EC), pages 251–268, 2013

    work page 2013

  18. [18]

    C. Duddy. Fair sharing under dichotomous preferences.Mathematical Social Sciences, 73:1–5, 2015

    work page 2015

  19. [19]

    Eberl and P

    M. Eberl and P. Lederer. The impossibility of strategyproof rank aggregation. InProceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2026. Forthcoming

    work page 2026

  20. [20]

    Fairstein, G

    R. Fairstein, G. Benadè, and K. Gal. Participatory budgeting designs for the real world. InProceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5633–5640, 2023

    work page 2023

  21. [21]

    Guerdjikova and K

    A. Guerdjikova and K. Nehring. Weighing experts, weighing sources: The diversity value. 2014. Mimeo. 15

    work page 2014

  22. [22]

    Huang, Z

    H. Huang, Z. Wang, Z. Wei, and J. Zhang. Bounded incentives in manipulating the probabilistic serial rule. Journal of Computer and System Sciences, 140:104875, 2024

    work page 2024

  23. [23]

    Kroer and D

    C. Kroer and D. Peters. Computing Lindahl equilibrium for public goods with and without funding caps. In Proceedings of the 26th ACM Conference on Economics and Computation (ACM-EC), page 129, 2025

    work page 2025

  24. [24]

    B. Li, A. Sun, and S. Xing. Bounding the incentive ratio of the probabilistic serial rule. InProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1128–1136, 2024

    work page 2024

  25. [25]

    Michorzewski, D

    M. Michorzewski, D. Peters, and P. Skowron. Price of fairness in budget division and probabilistic social choice. InProceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020. Forthcoming

    work page 2020

  26. [26]

    S. Rey, F. Schmidt, and J. Maly. The (computational) social choice take on indivisible participatory budgeting. Technical report, https://arxiv.org/pdf/2303.00621.pdf, 2025

    work page arXiv 2025

  27. [27]

    Speroni di Fenizio and D

    P. Speroni di Fenizio and D. A. Gewurz. The space of proportional voting systems and the most majoritarian among them.Social Choice and Welfare, 52:663–683, 2019

    work page 2019

  28. [28]

    Suksompong and N

    W. Suksompong and N. Teh. V oting in divisible settings: A survey. InProceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 39789–39796, 2026

    work page 2026

  29. [29]

    H. R. Varian.Intermediate Microeconomics - A Modern Approach. W. W. Norton & Company, 5th edition, 1999

    work page 1999

  30. [30]

    Xiao and J

    M. Xiao and J. Ling. Algorithms for manipulating sequential allocation. InProceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2303–2309, 2020

    work page 2020

  31. [31]

    J. C. Yang, C. I. Hausladen, D. Peters, E. Pournaras, R. H. Fricker, and D. Helbing. Designing digital voting systems for citizens: Achieving fairness and legitimacy in participatory budgeting.Digital Government: Research and Practice, 5(3):1–30, 2025. 16 A Omitted Proofs from Section 3.1 In this appendix, we prove Claims (2) and (3) of Theorem 2. Theorem...

    work page 2025