The setting in which the projects are divisible (can receive any amount of money) is called portioning,[4][5] fractional social choice, or budget-proposal aggregation.
[9] They prove that finding an egalitarian budget-allocation is NP-hard, but give pseudo-polynomial time and polynomial-time algorithms when some natural paramerters are fixed.
They propose an algorithm that achieves an additive approximation for restricted spaces of instances, and show that it gives exact optimal solutions on real-world datasets.
Annick Laruelle studies welfare maximization under weak ordinal voting, where a scoring rule is used to translate ranking to utility.
[12][13] Since this method (called "individually-best knapsack") might be unfair to minority groups, they suggest two fairer alternatives: Unfortunately, for general utility domains, both these rules are NP-hard to compute.
[6] It chooses a rule that maximizes the total score, which is defined by a harmonic function of the cardinality-based satisfaction.
[19] Pierczynski, Peters, and Skowron present a variant of the method of equal shares for weak-ordinal ballots, and show that it is an expanding approvals rule.
[6] The notion of fairness to groups is formally captured by extending the justified representation criteria from multiwinner voting.
This property is too strong, even in the special case of approval ballots and unit-cost projects (committee elections) For example, suppose n=4 and B=2.
But with cardinality-based satisfaction and approval ballots, the method of equal shares finds an EJR budget allocation.
[21] Proportional justified representation (PJR) means that, for every group N of voters who can afford a set P of projects, the group-utility of N from the budget-allocation - defined as
Aziz, Lee and Talmon[16] present local variants of the above JR criteria, that can be satisfied in polynomial time.
[6] One way to assess both fairness and stability of budget-allocations is to check whether any given group of voters could attain a higher utility by taking their share of the budget and dividing in a different way.
For the setting of divisible PB and cardinal ballots, a there are efficient algorithms for calculating a core budget-allocation for some natural classes of utility functions.
Then voters 2 and 3 can take their proportional share of the budget (which is 1) and fund project c, which will give both of them a higher utility.
With only 2 utility values (i.e., approval ballots), it is an open question whether a weak-core allocation always exists, with or without unit costs; both with cardinality-satisfaction and cost-satisfaction.
This stronger notion is satisfied by equal shares with cardinality satisfaction, sequential Phragmen, and maximin support.
[14] Maly, Rey, Endriss and Lackner[28][29] defined a new fairness notion for PB with approval ballots, that depends only on equality of resources, and not on a particular satisfaction function.
[30][31] They explain the rationale behind this new notion as follows: "we do not aim for a fair distribution of satisfaction, but instead we strive to invest the same effort into satisfying each voter.
A weaker relaxation, called local fair-share (Local-FS), requires that, for every unfunded project y, there exists at least one agent i who approves y and has share(X+y, i) > B/n.
Hershkowitz, Kahng, Peters and Procaccia[32] study the problem of welfare maximization subject to district fairness.
Moreover, if it is allowed to overspend (by up to 65%), it is possible to find an allocation that maximizes social welfare and guarantees district-fairness up-to one project.
[7][33][34] A PB rule is called strategyproof if no voter can increase his utility by reporting false preferences.
With unit costs, the rule that maximizes the utilitarian welfare (choosing the B projects with the largest number of approvals) is strategyproof.
For example: Rey, Endriss and de Haan[36] develop a general framework to handle any constraints that can be described by propositional logic, by encoding PB instances as judgement aggregation.
Motamed, Soeteman, Rey and Endriss[42] show how to handle categorical constraints by reduction to PB with multiple resources.
They model this shortlisting stage as a multiwinner voting process in which there is no limit on the total size or cost of the outcome.
They show that it is impossible to both maintain a low risk of over-spending, and guarantee that all projects complete in their due time.
He considers four satisfaction functions: For cardinality-satisfaction, maximizing the utilitarian welfare can be done in polynomial time by dynamic programming.
For the other satisfaction functions, welfare maximization is NP-hard, but can be computed in pseudo-polynomial time or approximated by an FPTAS, and also fixed-parameter tractable for some natural parameters.