Approximate Strategyproofness in Approval-based Budget Division
For social choice theorists and mechanism designers, this provides a positive result that a specific rule can be approximately strategyproof while maintaining fairness and efficiency, with optimality guarantees under certain conditions.
The paper shows that the Nash product rule achieves an incentive ratio of 2 in approval-based budget division, circumventing the impossibility of simultaneous strategyproofness, efficiency, and fairness by relaxing strategyproofness to approximate strategyproofness.
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.