Approximate Strategyproofness in Approval-Based Budget Division

1 Introduction

In many applications of collective decision-making, the goal is to distribute a divisible resource to some candidates based on the voters' preferences over the candidates. For instance, this task arises in (fractional) participatory budgeting [Aziz and Shah, 2021; Rey et al., 2025], where a budget needs to be distributed to projects based on the voters' preferences over the projects, and donor coordination [Brandl et al., 2022; Brandt et al., 2025], where monetary donations are allocated to charities based on the donors' preferences. In this paper, we will study such budget division problems based on approval preferences, i.e., voters only distinguish between liked and disliked candidates. This model, which we refer to as approval-based budget division, has been introduced by Bogomolnaia et al. [2005]. Moreover, this setting has attained significant attention [e.g., Aziz et al., 2020; Aziz et al., 2025; Michorzewski et al., 2020; Brandl et al., 2021; Kroer and Peters, 2025] because approval ballots offer a favorable tradeoff between the cognitive burden for voters and the expressive power of the ballot format

[Fairstein et al., 2023; Yang et al., 2025]. Formally, we will thus study distribution rules, which map each approval profile to a distribution of the resource to the candidates.

The literature on such distribution rules [e.g., Aziz et al., 2020; Brandl et al., 2021] has identified three fundamental properties known as strategyproofness, efficiency, and fairness. Roughly, strategyproofness requires that voters cannot benefit by lying about their true preferences. Or, put differently, this property ensures that it is in the best interest of the voters to reveal their preferences truthfully. Efficiency, on the other hand, states that we need to choose a distribution that is on the Pareto frontier, i.e., there is no other distribution that makes all voters weakly better off and some voters strictly better off. Lastly, fairness demands that the chosen distribution should be fair to all groups of voters: an appropriate amount of the resource should be spent on behalf of each group of voters. This idea has led to numerous fairness notions such as average fair share or the core, which postulate lower bounds on the utilities of (groups of) voters [see, e.g., Aziz et al., 2020].

Unfortunately, Brandl et al. [2021] have shown in a sweeping impossibility theorem that these three desiderata cannot be jointly satisfied: every strategyproof and efficient distribution rule violates even minimal fairness conditions. Moreover, while there are reasonable strategyproof distribution rules, such as the utilitarian rule and the conditional utilitarian rule, these severely violate efficiency or fairness conditions [Aziz et al., 2020; Aziz et al., 2025]. By contrast, nothing is known about how severely fair and efficient rules fail strategyproofness, thereby leaving it open whether we can escape the impossibility of Brandl et al. by relaxing strategyproofness.

Contribution. In this paper, we investigate whether there are distribution rules that are efficient, fair, and approximately strategyproof. To this end, we introduce the incentive ratio of a distribution rule as the worst-case ratio between the utility of a voter when manipulating and when voting honestly. Put differently, if a rule has an incentive ratio of γ, a voter can get at most γ times her original utility by manipulating. Hence, the lower the incentive ratio, the less manipulable a rule is, and an incentive ratio of 1 means that the rule is strategyproof. The incentive ratio has previously been studied in private good settings, such as Fisher markets [e.g., Chen et al., 2011; Chen et al., 2012; Chen et al., 2022] and assignment problems [e.g., Huang et al., 2024; Bei et al., 2025], where it led to several positive results: desirable, manipulable mechanisms often have a low incentive ratio. In practice, this may suffice to prohibit manipulations as the cost of a manipulation (e.g., to learn the other voters' preferences or to compute a beneficial manipulation) may exceed its benefit.

Unfortunately, it turns out that many distribution rules have a large incentive ratio. Specifically, we prove that the incentive ratios of the fair utilitarian rule (FUT) by Bogomolnaia et al. [2002], the maximum payment rule (MP) by Aziz et al. [2025], and the egalitarian rule (EGAL) grow linearly in the numbers of voters or candidates, thereby demonstrating that these rules are severely manipulable. By contrast, we show that the Nash product rule (NASH) has an incentive ratio of 2. Since this rule satisfies efficiency and demanding fairness axioms, this result answers our question about the existence of fair, efficient, and approximately strategyproof distribution rules in the positive. Moreover, we show that NASH achieves its incentive ratio of 2 even when voters are allowed to report concave utility functions over the distributions. Thus, by relaxing strategyproofness, we circumvent the impossibility theorem of Brandl et al. [2021] for a much richer class of utility functions than approval utilities.

Motivated by this positive result, we further explore whether there are distribution rules that have an incentive ratio smaller than 2 and satisfy some of the desirable properties of NASH. Perhaps surprisingly, it turns out that, under various side conditions, the incentive ratio of NASH is optimal. In more detail, we show for the following classes that all corresponding rules have an incentive ratio of at least 2: (i) distribution rules that satisfies average fair share, one of the fairness conditions of NASH; (ii) distribution rules that maximize an additively separable and strictly concave welfare function; and (iii) distribution rules that satisfy efficiency, a mild fairness axiom called group fair share, and three basic side conditions. These results demonstrate that, subject to its desirable properties, no distribution rule has a lower incentive ratio than NASH.

Lastly, we experimentally analyze the manipulability of distribution rules. Specifically, we measure the average incentive ratio and the percentage of manipulable profiles of FUT, MP, EGAL, and NASH for approval profiles sampled from several distributions. These experiments show that all four rules are frequently manipulable, with NASH and EGAL allowing for manipulations in almost all considered profiles. Further, with the exception of FUT, our theoretical results on the incentive ratio match the trends observed in the experiments. That is, while NASH is effectively always manipulable, voters never gain substantially by lying about their preferences, whereas EGAL and MP allow for much more beneficial manipulations. The outlier to this trend is FUT, whose average incentive ratio is much lower than our theoretical worst-case result indicates.

RelatedWork. The work on approval-based budget division was initiated by Bogomolnaia et al. [2005] and we refer to the survey by Suksompong and Teh [2026] for an overview of this topic as well as related models. More specifically, our paper directly builds on the work of Brandl et al. [2021], who have shown that every strategyproof and efficient distribution rule violates even minimal fairness conditions. This impossibility theorem strengthens prior results by Bogomolnaia et al. [2005] and Duddy [2015]. In light of these negative results, researchers have also examined how well distribution rules approximate efficiency and fairness properties. Specifically, Aziz et al. [2020] have proven that two strategyproof rules are severely inefficient, whereas Aziz et al. [2025] have shown that most rules severely fail a fairness notion called average fair share. We refer to Table 1 for an overview of these results.

We note that our results give a strong argument in favor of NASH as its incentive ratio is optimal subject to its fairness guarantees. Prior work has already demonstrated that this rule is appealing from other perspectives. For example, Aziz et al. [2020] showed that NASH satisfies two demanding fairness notions called average fair share and the core, and Brandl et al. [2022] proved that it gives strong participation incentives. Further, Guerdjikova and Nehring [2014] axiomatically characterized NASH based on a mild fairness notion, efficiency, and several auxiliary conditions. It is also known that, among fair rules, NASH gives almost optimal guarantees regarding the utilitarian social welfare [Michorzewski et al., 2020].

Finally, the incentive ratio has been studied before. Specifically, it was first introduced for Fisher markets, where goods are sold to agents [Chen et al., 2011; Chen et al., 2012; Chen et al., 2016; Chen et al., 2022]. For example, for linear utilities, the incentive ratio of these markets is 2. Further, the incentive ratio has also been analyzed for rank aggregation [Eberl and Lederer, 2026] and assignment mechanisms [Huang et al., 2024; Li et al., 2024; Xiao and Ling, 2020; Bei et al., 2025].

2 Preliminaries

For each integer t ∈ N, we define [t] = {1, . . . , t}. We assume there is a set of n voters N = [n] and a set of m candidates C = {x1, . . . , xm}. All voters have dichotomous preferences over the candidates, i.e., they only distinguish between liked and disliked candidates. To indicate her preferences, each voter i ∈ N reports an approval ballot Ai ⊆ C, which is the non-empty set of her approved candidates. Further, an approval profile A = (Ai)i∈N is a vector specifying the approval ballot of each voter i ∈ N. Given an approval profile A, we denote by A-i = (A1, . . . ,Ai-1,Ai+1, . . . ,An) the profile derived from A by removing voter i and by (A-i,A′i ) = (A1, . . . ,Ai-1,A′i ,Ai+1, . . . ,An) the profile where we change the approval ballot of voter i to A′i .

Given an approval profile, our goal is to distribute a continuous resource to the candidates. We will formalize this with the help of distributions, which are functions p : C → [0, 1] such that ∑x∈C p(x) = 1. Further, the set of all distributions over the set of candidates C is denoted by ∆(C). Less formally, a distribution p specifies for every candidate x ∈ C the share p(x) of the resource that is allocated to x. To select a distribution for an input profile, we will use (distribution) rules, which map each approval profile A (over any finite sets of voters N and candidates C) to a distribution p ∈ ∆(C). We denote by f(A, x) the share of the resource that a rule f assigns to a candidate x in a profile A.

Finally, we assume that the utility of every voter i ∈ N for a distribution p is the total share that p assigns to the approved candidates of the voter, i.e., ui(p) = ∑x∈Ai p(x).

2.1 Fairness and Efficiency

Since we aim to find fair and efficient rules that are approximately strategyproof, we next introduce the standard notion of (Pareto) efficiency and three fairness axioms. We note that we only define these conditions for distributions; a distribution rule satisfies a given axiom if, for every profile, its chosen distribution satisfies the axiom.

Efficiency. Efficiency requires that it is impossible to make some voter better off without making any other voter worse off. Formally, a distribution p is (Pareto) efficient for a profile A if there is no other distribution q such that ui(q) ≥ ui(p) for all i ∈ N and ui(q) > ui(p) for some i ∈ N.

Positive share. Positive share is a minimal fairness axiom demanding that each voter gets non-zero utility. Hence, a distribution p satisfies positive share (PS) for a profile A if ui(p) > 0 for all i ∈ N.

Group fair share. The idea of group fair share is that, for each group of voters S, we should spend a share proportional to the size of S on the approved candidates of the group. More formally, a distribution p satisfies group fair share (GFS) for a profile A if, for all groups of voters S ⊆ N, it holds that ∑x∈⋃i∈S Ai p(x) ≥ |S| n . GFS is a fairly mild fairness condition which is satisfied by many known rules.

Average fair share. Average fair share requires that, if all voters in a group S approve a common candidate, then the average utility of the group S should be at least proportional to the size of S. Put differently, a distribution p satisfies average fair share (AFS) for a profile A if 1 |S| ∑i∈S ui(p) ≥ |S| n for all groups of voters S ⊆ N with ⋂i∈S Ai ̸= ∅. Among all commonly studied rules, only the Nash product rule satisfies AFS.

2.2 Strategyproofness and Incentive Ratio

We now turn to the central properties of this paper, namely strategyproofness and the incentive ratio of distribution rules. First, strategyproofness requires that voters cannot increase their utility by misreporting their true approval ballots. More formally, a distribution rule f is strategyproof if ui(f(A)) ≥ ui(f(A-i, A′i )) for all voters i ∈ N, profiles A, and approval ballots A′i . Conversely, a rule is said to be manipulable if it is not strategyproof. Strategyproofness is desirable because, for manipulable rules, we cannot expect voters to report their true preferences, which may lead to suboptimal outcomes.

Unfortunately, strategyproofness is a rather prohibitive axiom for approval-based budget division. Specifically, Brandl et al. [2021] have shown that every strategyproof and efficient rule fails even the minimal condition of positive share.

Theorem 1 (Brandl et al., 2021). No strategyproof distribution rule satisfies both efficiency and positive share.

To circumvent this impossibility theorem, we will consider we will analyze the incentive ratio of distribution rules, which quantifies the worst-case multiplicative utility gain of a voter.

an approximate variant of strategyproofness. In more detail, Definition 1 (Incentive Ratio). The incentive ratio of a distri-

Put differently, if a distribution rule has an incentive ratio of γ, a voter can get at most γ times her original utility by manipulating. Since the utility of a voter can be 0 in the truthful profile A, we use the convention that 00 = 1 and x0 = ∞ for all x > 0. Further, we note that a voting rule has an incentive ratio of 1 if and only if it is strategyproof, and a smaller incentive ratio means that a rule is less manipulable. We refer to Figure 1 for an example of the incentive ratio and an illustration of the rules defined in the next section.

2.3 Distribution Rules

We next introduce the four distribution rules that we will analyze in this paper. We note that all of the following rules fail strategyproofness but are efficient (except for MP) and satisfy varying degrees of fairness: EGAL satisfies PS, FUT and MP satisfy GFS, and NASH even satisfies AFS.

Nash product rule. The Nash product rule (NASH) returns a distribution p that maximizes the Nash welfare ∏i∈N ui(p). While there can be multiple such distributions, all of them induce the same utility vector (ui(p))i∈N, so we do not need to worry about the tie-breaking for our purposes.

Egalitarian rule. The egalitarian rule (EGAL) lexicographically maximizes the minimal utility of a voter: we first maximize the utility of the worst-off voter, subject to that we maximize the utility of the second worst-off voter, and so on. To make this more formal, let umin (p) denote a vector that contains the utilities ui(p) of all voters i ∈ N in increasing order. Then, EGAL chooses a distribution p that lexicographically maximizes umin , i.e., for every other distribution q, it either holds that umin (p) = umin (q) or there is an index ℓ ∈ [n] such that umin (p)i = umin (q)i for all i ∈ [ℓ - 1] and umin (p)ℓ > umin (q)ℓ. Just as for NASH, there can be multiple distributions that lexicographically optimize umin , but all of them induce the same utility vector (ui(p))i∈N.

Maximum payment rule. The maximum payment rule (MP) was introduced by Speroni di Fenizio and Gewurz [2019] and recently studied for budget division by Aziz et al. [2025]. It computes the outcome distribution greedily and first gives to each voter control over a 1n share of the budget. Then, it repeatedly identifies the most approved candidate x (with ties broken lexicographically), assigns the shares of the voters that approve x to this candidate, and deletes x as well as all voters that approve x from the profile. This process is repeated until each voter has allocated her 1n share and the final distribution corresponds to the total shares accumulated by each candidate.

Fair utilitarian rule. The fair utilitarian rule (FUT) was first suggested by Bogomolnaia et al. [2002] and later rediscovered by Brandl et al. [2021]. In this rule, each voter i ∈ N controls a share of 1n and is assigned a weight λi, which is initially equal to 1. Moreover, we let t = maxx∈C |{i ∈ N : x ∈ Ai}| denote the maximum approval score of a candidate. Then, FUT repeats the following routine until all voters have spent their share: we first increase the weights λi of all voters who have not spent their share yet until the set of candidates X with ∑i∈N:x∈Ai λi = t is non-empty. Note that in the first round, we do not need to increase the weights for this. Next, each voter i who has not spent her share and approves a candidate in X allocates her 1n share uniformly to the candidates in X∩Ai. Lastly, we delete all candidates in X from the profile and repeat this process if some voter has not spent her share yet.

3 Theoretical Results

We are now ready to present our theoretical results. Specifically, we prove in Section 3.1 that MP, FUT, and EGAL have large incentive ratios. Further, in Section 3.2, we show that NASH has an incentive ratio of 2 and in Section 3.3 that this is optimal subject to its desirable properties. All missing proofs can be found in the full version of our paper [Aziz et al., 2026].

3.1 Distribution Rules with Large Incentive Ratios

As our first contribution, we prove that the incentive ratios of MP, FUT, and EGAL grow linearly in the number of voters and candidates, respectively. This means that, in the worstcase, these rules can be severely manipulated. Moreover, we note that all three rules satisfy axiomatic weakenings of strategyproofness: MP and FUT are monotonic [Brandl et al., 2021; Aziz et al., 2025], whereas EGAL satisfies a notion called excludable strategyproofness [Aziz et al., 2020]. Our result thus also demonstrates that these properties do not give convincing guarantees regarding strategyproofness.

Theorem 2. The following claims hold:

1. The incentive ratio of MP is in Θ(n).
2. The incentive ratio of FUT is in Θ(n).
3. The incentive ratio of EGAL is in Θ(m).

Proof of Claim (1). We only show Claim (1) here and defer the proofs of the other statements to [Aziz et al., 2026]. Now, we first note that every voter spends a share of 1n on her approved candidates, so ui(MP (A)) ≥ 1n for all voters i and profiles A. Since the utility of a voter is at most 1, this means that the incentive ratio of MP is upper bounded by n.

For the lower bound, we fix an integer k ≥ 2 and consider the following profiles with m = 3 candidates and n = 2k + 4 voters, which only differ in the ballot of the right-most voter. Further, we suppose the tie-breaking of MP favors a to c to b.

For A, MP chooses the distribution p with p(b) = k+3 2k+4 , p(a) = k-1 2k+4 , and p(c) = 2 2k+4 . Specifically, MP first assigns a share of k+3 2k+4 to b as it is approved by the most voters. After deleting b and the corresponding voters, the remaining voters report singleton ballots. By the definition of MP, it thus follows that a obtains a share of k-1 2k+4 and c of 2 2k+4 .

By contrast, both a and b are approved by k + 3 voters in A′ . By our tie-breaking assumption, this means that MP first assigns a share of k+3 2k+4 to a. Next, after deleting a and the corresponding voters, all remaining voters approve c, so MP sends the shares of these voter to c. Thus, MP selects the distribution q with q(a) = k+3 2k+4 and q(c) = k+1 2k+4 for A′ .

Finally, let i be the voter who deviates from {c} to {a, c} in our profiles. Assuming that {c} is true ballot of i, the utility of this voter is ui(p) = 2 2k+4 in A and ui(q) = k+1 2k+4 in A′ . This means for the incentive ratio of MP that γ(MP) ≥ ui(q) ui(p) = k+1 2 = n-3 4 . Hence, we conclude that γ(MP) ∈ Θ(n).

3.2 The Incentive Ratio of NASH

We now turn to NASH and show that its incentive ratio is 2. Since NASH is efficient and satisfies AFS, this result answers our original research question in the affirmative: there are efficient, fair, and approximately strategyproof distribution rules, so we can escape Theorem 1 by relaxing strategyproofness.

Even more, we will show that NASH has an incentive ratio of 2 for a much richer class of utility functions than approval preferences. To formalize this, we assume in this section that each voter i reports a utility function ui : ∆(C) → R≥0 over the distributions instead of an approval ballot. Further, we require utility functions to be (i) concave (i.e., ui(λp + (1 - λ)q) ≥ λui(p) + (1 - λ)ui(q) for all distributions p, q ∈ ∆(C) and λ ∈ [0, 1]) and (ii) non-zero (i.e., there is a distribution p ∈ ∆(C) with ui(p) > 0). Since the nonzero condition is almost trivial, we will refer to such utilities simply as concave. We note this setup is strictly more general than the approval setting since each approval ballot Ai can be treated as the (concave) utility function ui(p) = ∑x∈Ai p(x). Moreover, our assumptions on utility functions are very mild and include numerous other models, such as linear utilities, Leontief utilities, and Cobb-Douglas utilities [see, e.g., Varian, 1999, Ch. 4]. Further, a (concave) utility profile U = (ui)i∈N contains the (concave) utility function of every voter i ∈ N and we adopt notation analogous to approval profiles.

We note that the definition of the incentive ratio immediately generalizes to our enriched setting: the incentive ratio of a distribution rule f is γ(f) = supU,i,u′i ui(f (u′i ,U-i)) ui(f(U)) , where the supremum is taken over all concave utility profiles U, concave utility functions u′i , and voters i.

To prove that the incentive ratio of NASH is 2 for concave utility profiles, we discuss three auxiliary claims. The proof of the following lemma can be found in [Aziz et al., 2026].

Lemma 1. Fix an arbitrary concave utility profile U.

1. It holds that ui(NASH(U)) > 0 for all voters i ∈ N.
2. For all distributions q ∈ ∆(C), it holds that

1. For all voters i ∈ N, it holds that

Less formally, Claim (1) shows that NASH guarantees each voter strictly positive utility. Claim (2) states the separation inequality witnessing that the distribution p = NASH(U) maximizes the Nash welfare ∏i∈N ui(p). While this inequality appears also in earlier works [e.g., Airiau et al., 2019; Aziz et al., 2020], we derive it under more general conditions than these works as we do not even require that utility functions are differentiable. Lastly, Claim (3) demonstrates that the Nash welfare of the voters N \ {i} under NASH cannot decrease too much when voter i joins the election. A similar insight has been proven by Cole et al. [2013] for a private goods setting. Based on these insights, we now prove our main theorem.

Theorem 3. The incentive ratio of NASH is 2, even if voters are allowed to report concave utility functions.

Proof. We will show here only that the incentive ratio of NASH is at most 2 since a matching lower bound follows from Theorem 4. For this, we assume for contradiction that there is a concave utility profile U, a voter i, and a concave utility function u′i such that ui(NASH(U-i,u′i )) ui(NASH(U)) > 2. To ease the notation, we let p = NASH(U) and q = NASH(U-i, u′i ). We will show that ∑j∈N uj (q) uj(p) > n, which contradicts Claim (2) in uj (q)-uj (p) uj (q)

To prove this inequality, we first derive a lower bound on ∑j∈N\{i} uj (q) uj(p) . For this, we consider the term ∏j∈N\{i} uj (q) uj(p) , which is well-defined by Claim (1) of Lemma 1. Next, let ˆ p = NASH(U-i) denote the distribution chosen by NASH when voter i is absent. Clearly, it holds that ∏j∈N\{i} uj (q) uj(p) = ∏j∈N\{i} uj (q) ∏j∈N\{i} uj ( ˆ p) · ∏j∈N\{i} uj ( ˆ p) ∏j∈N\{i} uj(p) . Further, by Claim (3) of Lemma 1, we have that 1e ≤ ∏j∈N\{i} uj (q) ∏j∈N\{i} uj ( ˆ p)

and 1 ≤ ∏j∈N\{i} uj ( ˆ p) ∏j∈N\{i} uj(p) . We hence conclude that

By applying the logarithm, it follows that log 1e ≤ ∑j∈N\{i} log uj(q) uj(p) . Next, Jensen's inequality implies that

By chaining our inequalities, we infer that

Solving for ∑j∈N\{i} uj (q) uj(p) then shows that

We now conclude that ∑j∈N uj (q) uj(p) ≥ (n-1)e- 1 n-1 +2 as ui(q) ui(p) ≥ 2. We will next show that (n-1)e- 1 n-1 + 2 > n for all n ≥ 2, or equivalently that (n-1)(e- 1 n-1 -1) > -1. (We also observe that NASH is strategyproof if n = 1). For this, we note that x(e- 1x -1) > x(1- 1x -1) = -1 for all x > 0 since ey > 1+y for all y ̸= 0. By setting x = n-1, this proves our inequality. Hence, the assumption that ui(q) ui(p) > 2 contradicts Claim (2) of Lemma 1, thus proving our theorem.

Remark 1. Theorem 3 generalizes to group manipulations: under NASH, no group of voters can misreport their utility functions such that each member of the group obtains more than twice her original utility. More formally, it holds for all concave utility profiles U and groups of voters S ⊆ N that there is no group manipulation U ′S such that ui(NASH(U-S,U ′S )) ui(NASH(U) > 2 for all i ∈ S. This statement can be proven similar to Theorem 3 because Claim (3) of Lemma 1 can be generalized to show that e-|S| ≤ ∏i∈N\S ui(NASH(U)) ∏i∈N\S ui(NASH(U-S)) ≤ 1 for all groups of voters S ⊆ N.

Remark 2. Based on Claim (2) of Lemma 1, it can be shown that many of the desirable properties that NASH satisfies under approval preferences also hold under concave utility functions. In particular, by combining our lemma with the proof of Theorem 3 of Aziz et al. [2020], it follows that NASH is in the core for all concave utility functions [see also Chaudhury et al., 2022]. Thus, NASH is fair, efficient, and approximately strategyproof for all concave utility functions, whereas no rule satisfies these criteria when using full strategyproofness, even if only approval utilities are allowed [Brandl et al., 2021].

3.3 Optimality of NASH

A natural follow-up question to Theorem 3 is whether there are fair and efficient rules with a lower incentive ratio than NASH. As we will show next, such rules do not exist within three natural classes of distribution rules, even when only allowing for approval ballots. This suggests that the incentive ratio of NASH may be optimal subject to fairness and efficiency. Specifically, we will focus on the following classes of rules.

Rules satisfying AFS. First, we consider rules that satisfy AFS (see Section 2.1). By showing that each such rule has an incentive ratio of at least 2, it follows that the incentive ratio of NASH is optimal subject to its fairness guarantees.

Strictly concave welfare maximizers (SCWMs). As the second class, we study strictly concave welfare maximizers. To define these rules, we say a function h : [0, 1] → R∪{-∞} is a welfare function if (i) h(x) ̸= -∞ for all x > 0 and (ii) h is strictly increasing. Then, a distribution rule f is an (additively separable) welfare maximizer if there is a welfare function h such that f always returns a distribution maximizing the h-welfare, i.e., f(A) ∈ argmaxp∈∆(C) ∑i∈N h(ui(x)) for all profiles A. Further, f is a strictly concave welfare maximizer (SCWM) if h is strictly concave (i.e., h(λx + (1 - λ)y) > λh(x) + (1 - λ)h(y) for all distinct x, y ∈ [0, 1] and λ ∈ (0, 1)). For example, this class contains all rules that optimize a power welfare ∑i∈N (ui(p))α for α ∈ (0, 1).

We are interested in SCWMs since all rules in this class are efficient and many seem promising to obtain an incentive ratio of less than 2. For example, one may conjecture that the SCWM defined by h(x) = x1-ϵ for a very small ϵ > 0 has an incentive ratio less than 2 as it is close to maximizing the utilitarian welfare. Our result for SCWMs disproves this conjecture and, more generally, shows that tweaks in the objective of NASH do not allow to improve its incentive ratio.

Regular rules satisfying GFS and efficiency. Thirdly, we will focus on rules that satisfy efficiency and GFS (see Section 2.1). However, since both of these conditions are rather mild, we will additionally require three basic auxiliary conditions, which we summarize by regularity. Specifically, a distribution rule f is regular if it is

• anonymous: f(π(A)) = f(A) for all profiles A and permutations π : N →N (i.e., the identities of voters do not matter for the outcome),
• neutral: f(τ(A), τ(x)) = f(A, x) for all profiles A and permutations τ : C → C (i.e., the names of candidates do not matter for the outcome), and
• independent of losers: f(A) = f(A′ ) for all profiles A, A′ and candidates x such that f(A, x) = 0 and A′ = (Ai \ {x})i∈N is obtained from A by deleting x from the approval ballot of every voter.

These three properties are very mild and satisfied by all rules in this paper (except for MP which fails neutrality). Our third claim in Theorem 4 thus shows that the incentive ratio of NASH is already optimal when only requiring efficiency, a mild fairness axiom, and some basic auxiliary conditions.

We show next that every rule that belongs to one of these classes has an incentive ratio of 2. Since NASH is a member of each class, all our bounds are tight.

Theorem 4. The following claims are true:

1. Every distribution rule that satisfies AFS has an incentive ratio of at least 2.
2. Every SCWM has an incentive ratio of at least 2.
3. Every regular distribution rule that satisfies GFS and efficiency has an incentive ratio of at least 2.

Proof of Claim (1). We only show Claim (1) here; the proofs of the other statements can be found in Aziz et al. [2026]. Now, let f denote a rule satisfying AFS, and fix ℓ, k ∈ N with k ≥ ℓ ≥ 2. We consider the following profile A with 2k+ℓ+1 voters and ℓ + 1 candidates C = {x, y1, . . . , yℓ}:

• For each i ∈ [ℓ], there is one voter who reports {x, yi}.
• There are k + 1 voters who only approve x.
• There are k voters who report {y1, . . . , yℓ}.

Next, the profile A′ is derived from A by changing the approval ballot of the voter i∗ who reports {x, y1} in A to {y1}. For example, if ℓ = 3 and k = 8, the profiles look as follows.

We first analyze the distribution p = f(A). To this end, we observe that AFS implies for the k voters who report {y1, . . . , yℓ} that kk ∑i∈[ℓ] p(yi) ≥ k 2k+ℓ+1 . Without loss of generality, we assume that y1 is the candidate with the minimal probability in {y1, . . . , yℓ}, which means that p(y1) ≤ 1ℓ ∑i∈[ℓ] p(yi) and ∑i∈[ℓ]\{1} p(yi) ≥ ℓ-1 ℓ ∑i∈[ℓ] p(yi) ≥ ℓ-1 ℓ · k 2k+ℓ+1 . In turn, this implies for the utility of voter i∗ (who reports {x, y1} in A) that ui∗(p) ≤ 1 - ℓ-1 ℓ · k 2k+ℓ+1 .

Next, we turn to q = f(A′ ). By applying AFS to the sets Nx = {i ∈ N : x ∈ A′i } and Ny1 = {i ∈ N : y1 ∈ A′i }, respectively, we infer the following two inequalities for q.

By summing up these two inequalities, we derive that

Since q(x) + ∑i∈[ℓ] q(yi) = 1, this means that

This shows that q(x) ≥ k+ℓ 2k+ℓ+1 . In turn, we derive that ∑i∈[ℓ] q(yi) ≤ k+1 2k+ℓ+1 and by the AFS inequality for y1 that q(y1) ≥ k+1 2k+ℓ+1 . Since voter i∗ reports {x, yi} in A, this proves that ui∗(q) = 1. Hence, the incentive ratio of f is at least ui∗(q) ui∗(p) ≥ 1 1- ℓ-1 ℓ · k 2k+ℓ+1 . When setting k = ℓ2 and letting ℓ go to infinity, this fraction converges to 2, so every rule satisfying AFS has an incentive ratio of at least 2.

Remark 3. It is possible to design distribution rules with an incentive ratio of γ for every γ ∈ (1, 2] by mixing NASH with the uniform distribution. Specifically, consider the rule fλ(A) = λNASH(A) + (1 - λ)puni for λ ∈ (0, 1), which returns the convex combination of NASH and the uniform distribution puni over all candidates. For example, when setting λ = 1 m+1 , one can show that fλ has an incentive ratio between 65 and 43 , where the lower bounds follows by using the example of Claim (1) of Theorem 4. However, to obtain a notable reduction in the incentive ratio, one needs to use a very small λ, so we lose the desirable properties of NASH.

4 Experiments

As our last contribution, we experimentally evaluate the manipulability of the four distribution rules in Section 2.3. In particular, we are interested in how often and how severely our distribution rules are manipulable in more realistic profiles.

To answer this question, we sample 1000 approval profiles for each number of voters n ∈ {10, 20, . . . , 100} and m = 10 candidates. For each rule f ∈ {NASH, EGAL,MP, FUT} and each sampled profile A, we then compute the maximal multiplicative utility gain of a voter, defined by IR(f, A) = maxi,A′i ui(f (A-i ,A′i )) ui(f(A)) . We note that a rule f is manipulable in a profile A if and only if IR(f,A) > 1. We repeat these simulations with the following three distributions.

Impartial culture model. Each voter approves each candidate with probability p = 0.3 independently at random.

Euclidean model. Voters and candidates are placed uniformly at random in the 3d unit ball and voters approve all candidates with ℓ2-distance at most 0.4 from their position.

TruncatedMallow's model In this model, we sample for each voter i a strict preference relation ≻i from Mallow's model with a dispersion parameter of ϕ = 0.75 and a threshold ti ∈ {1, . . . , m- 1} from a uniform distribution. Each voter approves the first ti candidates in her preference relation ≻i.

Our findings of these experiments are summarized in Table 2 and Figure 2. Specifically, in Table 2 we show the average incentive ratio and the percentage of manipulable profiles of our rules when n = 100 and m = 10. Further, we display the average incentive ratio of our rules as a function of n for the euclidean model in Figure 2. Additional discussions and statistics of our simulations can be found in [Aziz et al., 2026].

Maybe the most striking insight of our experiments is that, for all distributions, all our rules are frequently manipulable, with EGAL and NASH being almost always manipulable. A possible explanation for this is that each of our rules satisfies some fairness axioms, thereby guaranteeing that each voter can influence the outcome and thus also manipulate. Secondly, we note that, while NASH is frequently manipulable, its incentive ratio is very low with an average of consistently less than 1.2. This shows that voters indeed have little incentive to manipulate under NASH. Surprisingly, the incentive ratio of FUT and its percentage of manipulable profiles are even less in our experiments. Hence, while FUT theoretically allows for severe manipulations, the corresponding instances may not occur in practice. However, we note that the maximum incentive ratio of FUT in our simulations (typically between 2 and

3) is usually higher than that of NASH (typically around 1.5). Lastly, both MP and EGAL are severely manipulable in our experiment. For EGAL, the reason is that, in almost all profiles, some voter can notably increase her utility via free-riding (i.e., only voting for approved candidates that obtained no share before the manipulation). By contrast, the average incentive ratio of MP is driven by instances where it is extremely manipulable. For example, we even encountered a profile A with IR(MP,A) = 37 in our experiments. These large incentive ratios occur consistently for MP as even the 90% percentile of the incentive ratio is often very large, which suggests that this rule can be severely manipulated on realistic profiles.

5 Conclusion

In this paper, we analyze whether there are approval-based distribution rules that are fair, efficient, and approximately strategyproof. To this end, we study the incentive ratio of such rules, which quantifies the maximal multiplicative utility gain of a voter when manipulating. While it turns out that several known rules have a large incentive ratio, we prove that the Nash product rule (NASH) has an incentive ratio of 2. Since this rule is efficient and satisfies the strongest fairness conditions in the literature, this answers our research question in the affirmative. We further show that the incentive ratio of NASH is optimal subject to some of its desirable properties. Lastly, we conduct an experimental analysis to understand the manipulability of our rules for realistic profiles.

Our paper points to several appealing follow-up questions. Firstly, we find it interesting to examine the incentive ratio also for other public good settings where strategyproofness is often challenging to satisfy. Further, for approval-based budget division, it may be desirable to analyze the tradeoff between strategyproofness, efficiency, and fairness in more depth by simultaneously approximating some of these properties.

Acknowledgements

We thank Florian Brandl for pointing out the incentive ratio to us as well as the anonymous IJCAI reviewers for their helpful feedback. This work was mainly conducted while Patrick Lederer and Jeremy Vollen were at UNSW Sydney. During that time, all of the authors were supported by the NSF-CSIRO project on "Fair Sequential Collective Decision Making".