| paper | Proportionally Representative Participatory Budgeting with Ordinal Preferences |
| authors | H. Aziz, Barton E. Lee |
| venue | AAAI 2021 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even for \(\tau=1\) with all projects tied and an outcome guaranteed to exist. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 6
statement extracted from the paper’s text layer
Given projects \(C\), rational costs \(w\), budget \(L\), ordinal types \(T\), and rational masses \(\mu\), output an integral feasible \(W\subseteq C\) satisfying continuous CPSC, or report nonexistence: for every coalition \(q\) with \(0\le q_t\le\mu_t\), every solidly supported \(C'\), and every \(C''\subseteq C'\) with \(w(C'')\le q(T)L\), require \(w(\bar C(q,C')\cap W)\ge w(C'')\).
A type-mass society \(\mu\) with complete ordinal preference types; the only decision variable is an integral project set \(W\), while coalition masses \(q\) certify CPSC and project costs \(w\) define feasibility under budget \(L\).
The continuous CPSC condition is equivalent, after saturation, to the paper's weighted finite-voter condition, so the mirror may add little new computational structure; this limits novelty but does not kill the population-distribution question.
fatal: False
The mirrors cover CPSC outcome computation and EJR–IPSC committee computation; they leave the axiomatic equivalences, separation examples, compatibility results, and PAV comparisons without separate population-continuous questions.
The strongest positive case is real, although it is asymmetric: Proposition 6 is the lead anchor because it is a genuine hardness result, while Proposition 13 gives a clean tractable companion.
The natural regime is large-scale municipal participatory budgeting with a fixed catalogue of projects. There may be hundreds of thousands of residents but only \(m\) project types, and residents may fall into a relatively small number \(\tau\) of ordinal preference types. A type includes the complete weak ranking of projects and, where relevant, the voter-weight class. The population is represented by masses \(\mu_t\), with \(\sum_t\mu_t=1\). Projects remain indivisible: an outcome is still an integral set \(W\subseteq C\), with \(\sum_{c\in W}w(c)\le L\). Thus this continuizes the population, not the project space or budget.
For a coalition, use a vector \(q\) with \(0\le q_t\le\mu_t\). Its mass is \(q(T)=\sum_tq_t\). It solidly supports \(C'\subseteq C\) if every type with \(q_t>0\) weakly prefers every member of \(C'\) to every project outside \(C'\). Let \(c_t^{(j)}\) be the \(j\)-th ranked project under the paper’s tie-breaking convention, and define the coalition’s periphery by \(\bar C(q,C')=\{c\in C:\exists t,\ q_t>0,\ c\succeq_t c_t^{(|C'|)}\}\).
My lead problem is Continuous CPSC Outcome:
Given \(C\), project costs \(w\), budget \(L\), a finite rational type distribution \(\mu\), and ordinal preferences, output an integral feasible set \(W\) satisfying the continuous version of CPSC, or report that none exists. The condition is that there must be no coalition \(q\), solidly supporting \(C'\), and subset \(C''\subseteq C'\) such that \(w(C'')\le q(T)L\) but \(w(\bar C(q,C')\cap W)<w(C'')\).
The anchor is Proposition 6, proved in this paper by a reduction from knapsack:
“Computing a CPSC outcome is weakly NP-hard even for the case of one voter.”
This is precisely the kind of anchor the programme wants. The one-voter instance becomes a one-type continuous society with \(\mu_t=1\), or, substantively, a very large population of identical residents. The hardness is not hidden in named individuals: it is generated by the indivisible project costs. Indeed, taking the coalition to be the whole population and \(C'=C\), CPSC forces \(W\) to have cost at least every feasible subset of projects. Thus any CPSC outcome exposes the maximum-cost feasible subset, the knapsack core of the reduction. I would therefore expect weak NP-hardness to transfer to the continuous problem, placing it in Class B.
This is also a plausible mirror of the authors’ question rather than a simplified surrogate. The continuous problem retains ordinal preferences, heterogeneous project costs, an integral budget-constrained outcome, solid coalitions, periphery, and proportional representation. Only the electorate is represented by type masses. The finite-to-continuous dictionary is exact for rational data: a mass \(\mu_t=a_t/N\) corresponds to \(a_t\) voters of type \(t\), while the continuous coalition vector corresponds to selecting subcohorts of those voters after clearing denominators.
The main additional questions are whether CPSC existence can be characterized in the continuum, whether the weak hardness admits a pseudo-polynomial algorithm or FPTAS in the project costs, and whether some type-distribution restrictions make the problem tractable.
A second worthwhile mirror uses Proposition 13, also proved in this paper, whose full content is:
“A committee satisfying both EJR and IPSC can be computed via a polynomial-time algorithm.”
The paper identifies the algorithm as the approval-based special case of EAR, known elsewhere as Rule-X. The continuous problem is Continuous EJR–IPSC Committee:
An instance consists of candidates \(C\), committee size \(k\), and a rational distribution \(\mu\) over approval types \(A_t\subseteq C\). Output an integral committee \(W\subseteq C\) with \(|W|=k\) satisfying both continuous EJR and continuous IPSC.
For EJR, every coalition vector \(q\) of mass at least \(\ell/k\) whose common approval intersection has size at least \(\ell\) must contain some positive-mass type \(t\) with \(|A_t\cap W|\ge\ell\). For IPSC, writing \(I(q)=\bigcap_{q_t>0}A_t\) and \(U(q)=\bigcup_{q_t>0}A_t\), there must be no coalition \(q\) with \(q(T)\ge (|U(q)\cap W|+1)/k\) and \(I(q)\setminus(U(q)\cap W)\neq\varnothing\).
I expect this problem to remain in Class A. Rule-X can operate directly on residual masses of approval types: when a candidate is selected, the algorithm removes an appropriate amount of mass from the types supporting it. The committee itself remains integral, and the running time should be polynomial in \(m\), \(\tau\), and the input bit length, independent of the number of named voters. This is a particularly good population mirror because the paper already treats voter weights as divisible accounting quantities while keeping projects or committee members indivisible.
The weaker point is that Proposition 13 may yield a relatively straightforward extension of the paper’s weighted-voter algorithm. A sceptic could say that the continuous version is mainly Rule-X with rational masses. I think that objection reduces the novelty of the expected algorithmic result, but not the legitimacy of the problem: the continuum requires quantifying over arbitrary mass coalitions, gives a complexity statement in terms of type support rather than electorate size, and supplies the finite/high-multiplicity correspondence that the paper itself does not formulate.
I would not try to mirror every result in the paper. The equivalence and separation propositions are primarily axiomatic, and the statements about PAV compatibility are not themselves complexity classifications. Propositions 6 and 13 are enough: the first gives a serious Class B boundary where population continuization does not dissolve hardness; the second gives a natural Class A problem where the paper’s weighted structure becomes an algorithm over population types. Existing work on divisible PB or Rule-X is supporting prior art, not a collision, because these mirrors retain integral projects and make the population—not the outcome—the continuous object.
The case against the proposed mirrors is that both anchors are already expressed in the paper’s voter-weight formalism. The alleged continuum therefore adds no genuinely new population object.
For CPSC, take any violating coalition \(q\), and let \(S=\{t:q_t>0\}\) be its support. Replace it by the saturated coalition \(\widehat q\), where \(\widehat q_t=\mu_t\) for \(t\in S\) and \(0\) otherwise. The supported set \(C'\) and its periphery are unchanged, while \(\widehat q(T)\ge q(T)\). Hence \(w(C'')\le q(T)L\) still holds with \(\widehat q\). Every continuous CPSC violation therefore has one using all of each participating type.
So continuous CPSC depends only on type supports \(S\) and their total masses \(\mu(S)\), not on fractional coalitions. It is exactly the paper’s finite weighted model with one representative voter per type, \(n=\tau\), and \(b_t=\tau\mu_t\). The paper already permits arbitrary real voter weights and defines CPSC entirely through \(b(N')L/n\). This is an internal model identity, not the objection that some outside high-multiplicity paper already exists.
Proposition 6 is especially weak as a population anchor. Its hard instance has one voter, hence one type with \(\mu_t=1\). Taking \(C'=C\) and the whole electorate as the coalition makes CPSC require \(W\) to have cost at least every feasible subset of projects; the reduction is simply knapsack over indivisible project costs. That remains exactly the same with one named voter, one weighted voter, or a continuum of identical residents. The theorem establishes hardness, but it does not establish a computational question about a continuous society. A multi-type repair does not fix this: it is merely the same weighted CPSC problem with identical voters compressed into weighted representatives.
The proposed EJR–IPSC mirror collapses in the same way. For any coalition \(q\), saturating its support preserves its common approval intersection and union, while increasing its mass. Thus a violating coalition for continuous EJR or IPSC can always be taken to contain all mass of every type it uses. With \(b_t=\tau\mu_t\), \(L=k\), and \(w(c)=1\), continuous IPSC is exactly the paper’s weighted IPSC condition. PB-EAR already subtracts fractional voter weights, so its residual-mass operation is not a new continuum algorithm.
The proponent’s EJR statement needs an additional repair: Proposition 13 concerns unit-weight multi-winner elections, whereas the proposed condition is a weighted EJR variant. If one refuses that change, Proposition 13 does not directly establish the claimed continuous theorem. If one accepts the natural weighted version, rational masses can be replaced by cloned voters and then aggregated again by type; the resulting Rule-X/EAR computation is an immediate weighted lift, not a new population-continuization result.
This does not claim that a compressed, \(\tau\)-parameterized study could never be publishable. It could be a useful analysis of weighted CPSC or weighted EJR. But it would be a high-multiplicity encoding study of a model the paper already contains, rather than a continuous mirror that exposes new computational structure. To avoid that collapse one would need individual identity, type-internal constraints, or fractional projects/outcomes. The first contradicts the high-multiplicity premise; the second changes the paper’s problem; the third continuizes the outcome space and is outside the programme.
The negative case is therefore strongest against these two specific anchors, not against every imaginable extension of the paper. If the programme counts a weighted-profile compression as worthwhile in its own right, the universal negative cannot be airtight. Under the programme’s stricter standard of making the population itself a new continuous computational object, however, neither Proposition 6 nor Proposition 13 survives.
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.