| paper | Proportionally Representative Participatory Budgeting: Axioms and Algorithms |
| authors | H. Aziz, Barton E. Lee, Nimrod Talmon |
| venue | ATAL 2018 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\); deciding existence is \(\mathrm{NP}\text{-complete}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3.4
statement extracted from the paper’s text layer
Given a finite project set \(C\), integer costs \(w\), budget limit \(L\), finite approval-type set \(T\subseteq 2^C\), and rational distribution \(\mu\) over \(T\), find an indivisible budget \(W\subseteq C\) with \(w(W)\le L\) satisfying continuous Strong-BJR-\(L\), or report that none exists. The condition forbids a submass \(\nu\) with \(0\le\nu_A\le\mu_A\), \(\sum_A\nu_A\ge 1/L\), \(w(\bigcap_{\nu_A>0}A)\ge1\), and \(w((\bigcup_{\nu_A>0}A)\cap W)=0\).
Finite approval types \(A\in T\) carry masses \(\mu_A\); the decision variable is an indivisible project set \(W\), constrained by \(w(W)\le L\), and the task is feasibility of continuous Strong-BJR-\(L\).
Coalition witnesses can be saturated to whole approval types, so the continuum adds no new optimization variable beyond weighted aggregation.
fatal: False
The mirror covers Propositions 3.4, 3.8, and 3.9, while leaving GPseq and Local-BPJR, the W-variants, testing results, and most axiom relations unaddressed.
There is a credible continuous mirror here, with Proposition 3.4 as my lead anchor. The mirror should make the population continuous while keeping projects indivisible. That distinction matters: this is not the divisible-funding model studied elsewhere.
Let \(C\) be the projects, \(w(c)\in\mathbb{N}\) their costs, and \(L\) the budget limit. A voter type is an approval set \(A\subseteq C\). The society is a distribution \(\mu=(\mu_A)_{A\in T}\), where \(\mu_A\) is the fraction of residents of type \(A\) and \(\sum_A\mu_A=1\). A finite electorate with \(n_A\) voters of type \(A\) gives the rational special case \(\mu_A=n_A/n\).
For a possible cohesive subpopulation, let \(0\leq \nu_A\leq\mu_A\), write \(\|\nu\|=\sum_A\nu_A\), and define
\[ I_\nu=\bigcap_{\nu_A>0} A, \qquad U_\nu=\bigcup_{\nu_A>0} A. \]
Thus \(\nu\) is a mass of voters, \(I_\nu\) is what they unanimously approve, and \(U_\nu\) is what at least one of them approves. A budget is still an indivisible set \(W\subseteq C\) with \(w(W)\leq L\).
This is a plausible high-multiplicity regime for participatory budgeting. A city may have hundreds of thousands of residents but only dozens or hundreds of relevant approval types, representing neighbourhoods, demographic cohorts, or recurring patterns of demand. Within a type, residents are indistinguishable for the paper’s model. The ratio \(N\gg |T|\) is exactly the regime in which proportions such as “\(16\%\) support this project” are more natural than named-voter identities.
My lead anchor is Proposition 3.4, proved in this paper: “Computing Strong-BJR-\(L\) and Strong-BPJR-\(L\) budgets is NP-hard.” The continuous problem I would hand to a prover is:
Continuous Strong-Proportional Budgeting. Given \((C,w,L,T,\mu)\), output a feasible budget \(W\) satisfying either the continuous Strong-BJR-\(L\) or Strong-BPJR-\(L\) condition, or report that none exists.
The continuous Strong-BJR-\(L\) condition forbids a submass \(\nu\) with
\[ \|\nu\|\geq \frac1L,\qquad w(I_\nu)\geq 1,\qquad w(U_\nu\cap W)=0. \]
The continuous Strong-BPJR-\(L\) condition forbids, for every integer \(\ell\in\{1,\ldots,L\}\), a submass \(\nu\) with
\[ \|\nu\|\geq \frac{\ell}{L},\qquad w(I_\nu)\geq \ell, \]
and
\[ w(U_\nu\cap W) < \max\{w(B):B\subseteq I_\nu,\; w(B)\leq \ell\}. \]
This is not a weakened version of the paper’s question. It replaces the normalized coalition size \(|V'|/n\) by population mass, while preserving the projects, their costs, the indivisibility of \(W\), and the exact proportionality requirement.
The paper’s Restricted-X3C reduction lifts directly. Give each universe element \(x_i\) a type approving precisely the set-projects containing \(x_i\), with mass \(1/(3m)\), set \(L=3m\), and give each set-project cost \(3\), together with the paper’s dummy cost-one item. There can be an arbitrarily large cohort of identical residents for each element type, so this is genuinely high multiplicity: the number of residents can be \(q(3m)\) while the number of types is at most \(3m\).
A Strong-BJR budget must represent every positive-mass element type, because each has mass \(1/L\). Since the budget can afford at most \(m\) set-projects, representing all \(3m\) elements is equivalent to selecting an exact cover. The Strong-BPJR hardness follows as in the paper; with equal type masses, any fractional violating coalition can be reduced to a violating collection of whole supported types. Thus the expected classification is Class B: hardness transfers, because the combinatorics live in the project-incidence structure, not in the number of individually named voters.
This is my strongest mirror because the population aspect is substantive rather than decorative. It asks whether a large city with stable approval cohorts can satisfy proportional representation, and the answer remains computationally hard even when individual identities disappear.
A second independent anchor is Proposition 3.8, also proved here: “Computing a BPJR-\(L\) budget is NP-hard.” Its continuous counterpart is:
Continuous BPJR Budgeting. Given \((C,w,L,T,\mu)\), output any feasible budget \(W\) satisfying the continuous BPJR-\(L\) condition.
The BPJR condition is obtained by using the same mass threshold \(\|\nu\|\geq \ell/L\), but requiring
\[ w(U_\nu\cap W) \geq \max\{w(B):B\subseteq I_\nu,\; w(B)\leq \ell\}. \]
This mirror remains hard even with a single voter type. Take one type \(A\) with \(\mu_A=1\), approving all the Partition projects, whose costs are \(x_1,\ldots,x_m\), with total \(2B\), and set \(L=B\). At \(\ell=L\), the condition requires the chosen approved projects to have the maximum total cost achievable under \(B\). That maximum is \(B\) exactly when the Partition instance is positive. Hence the paper’s NP-hardness survives in a society consisting of an arbitrarily large population of identical residents.
This is a useful Class B boundary case: continuization removes individual voter multiplicity entirely, but it does not dissolve hardness caused by choosing an indivisible project bundle with encoded costs. It also shows why “all voters have the same type” is not an illegitimate scenario; it is the purest high-multiplicity regime.
For a positive tractability anchor, Proposition 3.9 states, and proves here, that “There is a polynomial-time algorithm which computes an exhaustive budget satisfying BJR-\(L\).” The corresponding question is:
Continuous Exhaustive BJR Budgeting. Given \((C,w,L,T,\mu)\), output a feasible exhaustive budget \(W\) satisfying continuous BJR-\(L\).
The continuous BJR condition forbids a submass \(\nu\) with
\[ \|\nu\|\geq \frac1L,\qquad c\in I_\nu,\quad w(c)=1,\qquad w(U_\nu\cap W)=0. \]
The paper’s greedy proof extends by replacing approval counts with approval mass. For each unit-cost project \(c\), compute the currently unrepresented mass
\[ \rho_W(c)= \sum_{\substack{A\in T:\\ A\cap W=\varnothing,\;c\in A}} \mu_A. \]
If there are at most \(L\) unit-cost projects, select all of them. Otherwise, repeatedly select the unit-cost project with maximum \(\rho_W(c)\), for \(L\) iterations, and then add arbitrary projects while preserving feasibility until the budget is exhaustive. If an unselected unit project still had unrepresented mass at least \(1/L\), every greedy choice would have covered at least \(1/L\) new mass; after \(L\) choices this would exceed total mass \(1\), a contradiction. The algorithm is polynomial in \(|C|+|T|\) and the encoding length of \(\mu\).
This third mirror is expected to be Class A. It is not merely an algorithm for a finite electorate with a renamed parameter: the input is a distribution over types, and the proof operates directly on mass. It gives a natural tractable boundary beside the two hardness mirrors.
The authors should recognise all three questions as their own problems. Their axioms are already formulated in terms of group-size fractions, and their motivation is explicitly to represent large cohesive segments of a population. Replacing \(|V'|/n\) by \(\|\nu\|\) is therefore the canonical high-multiplicity version, not a change of normative question. The mirror covers the paper’s computational results on Strong-BJR, Strong-BPJR, BPJR, and BJR; it does not claim to continuize every axiom or every rule in the paper.
The weakest point is that these mirrors do not automatically produce the LP-and-separation structure characteristic of the broader continuization programme. In particular, Proposition 3.8 can look like ordinary weighted knapsack hardness with a homogeneous electorate, and the weighted approval representation could be dismissed as a measure-theoretic restatement of a finite weighted instance. But that limitation is itself informative. Proposition 3.4 supplies the stronger population-level case, while Proposition 3.8 identifies hardness that survives after population multiplicity has completely disappeared. Together with Proposition 3.9, they give a meaningful computational map: some proportional-budgeting questions remain hard because of project combinatorics, while others become transparently tractable once voter identities are replaced by mass.
The strongest negative case is that the proposed mirrors are valid weighted reformulations, but not worthwhile continuizations in the ChoCo sense. In the paper’s model, a voter contributes only an approval set, the output is an integral project set \(W\), and all costs are common project costs. Once voters with the same approval set are aggregated, nothing in the problem refers to their identities. A distribution \(\mu\) is therefore only a compressed weighted approval profile.
This collapse is especially clear for coalitions. If a submass \(\nu\) has support \(S\subseteq T\), replacing it by the full mass of every type in \(S\) preserves \(I_\nu\) and \(U_\nu\) while increasing its total mass. Thus every continuous witness can be replaced by a finite collection of whole types. Even allowing an apparently richer continuum of residents cannot change this: with \(m\) projects, approval information induces at most \(2^m\) relevant types. The atomless population contributes no new optimization variable, transport problem, or separation problem.
Proposition 3.4 therefore gives, at most, a weighted version of the paper’s Restricted-X3C reduction. The masses \(\mu_A=1/(3m)\) are forced, and the reduction uses \(3m\) distinct approval types. Multiplying every type into \(q\) identical residents makes the electorate arbitrarily large without changing the instance or the computation. The hard object remains the choice of an integral set of projects. That surviving hardness is not itself a defect—Class B results are allowed—but it shows that the proposed continuum has done no computational work. A “neighbourhood cohort” interpretation does not repair this unless neighbourhood, geography, or eligibility constraints are added; those would be new structure absent from the paper.
Proposition 3.8 is weaker still. With one type of mass \(1\), define
\[ f(\ell)=\max\{w(B):B\subseteq A,\;w(B)\leq \ell\}. \]
Every feasible budget \(W\subseteq A\) satisfies \(w(U_\nu\cap W)=w(W)\), so BPJR reduces to requiring \(w(W)\geq f(\ell)\) for the relevant \(\ell\). The population distribution disappears completely. Cloning the single type only replaces one voter by many identical voters. This is a legitimate knapsack boundary case, but it cannot support a population-continuous research programme: the anchored problem is already fully determined before a society is introduced.
Proposition 3.9 does not provide much more. Continuous BJR is exactly the finite weighted condition
\[ \rho_W(c)= \sum_{\substack{A\cap W=\varnothing\\c\in A}}\mu_A <\frac{1}{L} \]
for every unit-cost project \(c\). The proposed greedy algorithm is simply the paper’s approval-count algorithm with counts replaced by weighted sums. That is a correct implementation observation, but not a new continuous optimization result. Making projects divisible would create a richer model, but it would be outcome-space continuity, which the programme explicitly excludes.
The obvious escape routes all change the problem. Adding individual prices or identities violates the paper’s type semantics; adding locations or eligibility constraints introduces a different PB model; allowing fractional project funding moves to divisible PB; and adding an objective such as maximising represented mass creates a new optimization problem rather than continuizing one proved in the paper.
This negative case is not airtight. Proposition 3.4 is genuinely recognizable as a high-multiplicity PB question with indivisible projects, and the programme explicitly permits such Class B mirrors. The honest conclusion is therefore not that the mirror is impossible, but that the paper offers no strong ChoCo exemplar: one anchor is a plausible yet population-inert weighted reformulation, one is completely degenerate in population, and one is a routine weighted extension. A universal claim that no worthwhile mirror exists overreaches; the best defensible negative verdict is that the proposed mirrors are too thin to justify programme priority.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.