| paper | Evaluation of Project Performance in Participatory Budgeting |
| authors | Niclas Boehmer, Piotr Faliszewski, Łukasz Janeczko, Dominik Peters, Grzegorz Pierczyński, Šimon Schierreich, Piotr Skowron, Stanisław Szufa |
| venue | IJCAI 2024 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.5
statement extracted from the paper’s text layer
Given projects \(P\), budget \(B\), costs \(c\), tie order \(\prec\), losing target \(p\), explicit approval-set types \(\mathcal A\subseteq 2^P\), and rational society distribution \(\mu\), choose \(x_A\in[0,\mu_A]\) for each \(A\not\ni p\), transferring mass from \(A\) to \(A\cup\{p\}\). Compute \(Q(\mu,p)=\sup\{\sum_{A\not\ni p}x_A:p\notin\operatorname{PH}_\infty(\mu_x)\}\), or decide whether \(Q(\mu,p)\ge\alpha\).
Approval-set types \(A\subseteq P\) carry masses \(\mu_A\); variables \(x_A\) transfer mass to \(A\cup\{p\}\); PHRAGMÉN evolves on type balances, and the objective is maximum safe transferred mass under the rule's exact tie convention.
The intervention changes every subset of \(\ell\) voters into divisible recruited mass, so fidelity to the paper's operational campaign interpretation depends on accepting a substantial repeated-type regime.
fatal: False
The mirror covers Theorem 3.5 and the PHRAGMÉN component of Theorem 3.6; it leaves the EQUAL-SHARES component, other approval-addition variants, rivalry reduction, cost reduction, sampling results, and experiments untouched.
My strongest honest case is a high-multiplicity mirror of the paper’s PHRAGMÉN pessimistic-add measure. I would not claim that every measure in the paper has an equally compelling continuous form.
Take a PB instance with projects \(P\), budget \(B\), project costs \(c(q)\), and a fixed tie-breaking order. A voter type is an approval set \(A\subseteq P\). A continuous society is a rational distribution \(\mu=(\mu_A)\) over a listed family of approval sets, with \(\sum_A\mu_A=1\). The mass \(\mu_A\) is the fraction of residents with ballot \(A\). Costs and the budget are normalized by population size, so an \(n\)-voter instance with \(n_A\) voters of type \(A\) maps to \(\mu_A=n_A/n\), \(c_\infty(q)=c(q)/n\), and \(B_\infty=B/n\). This preserves the PHRAGMÉN execution exactly.
A plausible regime is a large city or recurring institutional PB election with tens or hundreds of thousands of residents, hundreds of projects, and perhaps dozens or hundreds of repeated approval blocs created by neighbourhoods, campaign slates, or issue communities. The relevant comparison is \(n\gg\tau\), where \(\tau\) is the number of distinct approval sets. This is not a claim about every PB election, but it is a sensible instance regime, especially since the paper itself is motivated by elections with tens of thousands of voters and hundreds of projects.
In the continuous PHRAGMÉN rule, each unit of population receives funds at rate one. A type-\(A\) resident has a common per-capita balance \(b_A\); the total funds available to project \(q\) are \(\sum_{A:q\in A}\mu_A b_A\). When a project is selected, the balances of its supporters are reset to zero. This is the direct aggregate version of the paper’s rule, not a different proportionality rule.
The lead continuous problem is:
\[ \textsf{Continuous-PH-Pessimist-SafeMass}. \]
Its instance consists of \((P,\mathcal A,\mu,c,B,\prec,p)\), where \(p\) is a losing project. For every type \(A\not\ni p\), choose a mass \(x_A\in[0,\mu_A]\) and change those residents’ ballots from \(A\) to \(A\cup\{p\}\). Thus this is not fractional approval by an individual: it moves mass between two complete voter types.
Let \(I_x\) be the resulting society. The problem asks for
\[ Q(I,p)=\sup\left\{\sum_{A\not\ni p}x_A: p\notin \operatorname{PH}_\infty(I_x)\right\}. \]
A solution is the exact value \(Q(I,p)\), together with a mass allocation \(x\) witnessing it when the supremum is attained. Equivalently, given rational \(\alpha\), the decision version asks whether there is an adversarial allocation of at least \(\alpha\) mass that still leaves \(p\) unfunded. In an \(n\)-voter instance, if \(q\) voters can be added without funding \(p\), then the paper’s discrete pessimistic measure is \(q+1\), whereas the continuous boundary is \(q/n\). Thus this is the natural high-multiplicity form of the same worst-case question.
The strongest anchor is Theorem 3.5, proved by the authors, not cited: for PHRAGMÉN, deciding whether \(\operatorname{pessimist\mbox{-}add}_E(p)\) is at least \(\ell\) is coNP-complete, even when all projects have unit cost. The reduction uses an exact-cover choice among individual voters. That is precisely the sort of multiplicity-driven integrality that a continuous mirror should test.
For the continuous problem, run PHRAGMÉN on the unmodified society and record its at most \(k+1\) relevant stages. For each type \(A\not\ni p\), let \(b_{A,i}\) be its per-capita balance at stage \(i\), and let \(r_i\) be the remaining funding gap before the additional supporters would make \(p\) fundable. With \(p\) placed last in the tie-breaking order, the maximum safe mass is given by the linear program
\[ \max \sum_{A\not\ni p}x_A \]
subject to
\[ 0\le x_A\le\mu_A \]
and
\[ \sum_{A\not\ni p} b_{A,i}x_A\le r_i \]
for every relevant stage \(i\), with the same boundary convention as the rule’s tie-breaking. If \(p\) remains unfunded, the other projects follow exactly the original PHRAGMÉN execution, so these constraints are sufficient. The integer variables in the paper’s exact-cover argument have become real mass variables. Consequently, with the approval types explicitly listed, this mirror is expected to be polynomial-time solvable by linear programming, in \(\operatorname{poly}(m,\tau,L)\). I classify it as Class A: the continuous relaxation removes the population-integrality obstruction.
A second, closely related anchor is Theorem 3.6, also proved by the authors: for PHRAGMÉN and EQUAL-SHARES, pessimistic-add can be computed in FPT time parameterized by the number of funded projects. I use only the PHRAGMÉN part here. The corresponding continuous optimization problem is the exact-value problem \(\textsf{Continuous-PH-Pessimist-Value}\) defined above.
The paper’s FPT proof partitions voters by their balance vectors and then solves an ILP with at most \(O(2^k)\) variables, using Lenstra’s algorithm. In the continuous mirror, voters with the same balance vector can be aggregated into one mass capacity, and the ILP becomes an LP. Thus the continuous problem is again polynomial in the explicit number of types, and in particular is fixed-parameter tractable in \(k\). This is not merely inheriting the paper’s algorithm: it exposes why the algorithm becomes simpler under continuization. The discrete difficulty is selecting whole voters from overlapping balance-vector classes; the continuous difficulty is allocating mass among those classes.
The authors should recognise this as their problem. The rule, project costs, budget, approval sets, losing target, and intervention are unchanged. Only the population representation changes from counts to proportions, exactly as their experiments already treat large approval counts as aggregate support. The mirror also preserves the paper’s explanatory interpretation: \(Q(I,p)\) says how much additional support can be recruited adversarially without making the project win, while its complementary threshold says how much support guarantees success.
The weakest point is that exact repeated approval sets may be less common than the paper’s raw voter counts suggest. If nearly every voter has an idiosyncratic ballot, then \(\tau\) is close to \(n\), and the high-multiplicity advantage is weak. The mirror also deliberately excludes individual-specific campaign costs or budgets, although those are not part of this paper’s model. Finally, if approval types are given succinctly rather than explicitly, the LP may acquire a pricing or separation problem and could become hard again. Those are real boundaries, not defects to hide.
This case therefore covers Theorem 3.5 and the PHRAGMÉN portion of Theorem 3.6, but not the paper’s sampling-based \(50\%\)-add or rivalry-reduction measures. Its central claim is narrower: the paper contains a particularly clean continuous mirror because its main negative result is driven by choosing integral subsets of voters, while the high-multiplicity version replaces that choice by a directly solvable mass-allocation LP.
The strongest negative case is that the proponent’s two anchors are really one observation: take the ILP in Theorem 3.6 and drop integrality. The resulting LP is immediate once the execution of PHRAGMÉN is fixed. It introduces no new type-space structure, separation problem, or genuinely new robustness notion. Theorem 3.5’s coNP-hardness is therefore being used mainly as motivation for a standard fractional relaxation.
The proposed quantity also changes the operational meaning of pessimistic-add. The paper asks for the least integer \(\ell\) such that *every subset of \(\ell\) named voters* makes \(p\) win. The continuous quantity asks for the largest divisible mass that can safely be recruited. Those coincide only after choosing a particular high-multiplicity limit and allowing an adversary to split every approval type fractionally. If one preserves the finite campaign interpretation—whole voters, or indivisible blocs—the integrality that drives Theorem 3.5 remains. If one allows arbitrary splitting, the question becomes a fractional sensitivity calculation rather than the paper’s intervention problem.
The same issue applies to Theorem 3.6. The paper has already identified the relevant sufficient statistic: the balance vector. Aggregating equal vectors and replacing integer counts by real masses is mathematically clean, but it is simply the continuous relaxation of the authors’ existing FPT formulation. With approval types explicitly listed, the LP is routine; with types represented succinctly, the problem may again inherit the combinatorial difficulty of generating or optimizing over approval sets. Thus the proposed mirror either has little computational content or relies on an input representation that puts the original difficulty back.
That is the best negative argument, but it is not strong enough under ChoCo’s rules. The intervention does not fundamentally depend on voter identity: under PHRAGMÉN, voters with the same approval set have the same balance history, and the paper’s own proof aggregates them by precisely that information. A city with repeated neighbourhood or issue-bloc ballots is a plausible high-multiplicity regime. In that regime, the normalized discrete optimum converges to the mass-allocation LP, and the disappearance of exact-cover integrality is itself a legitimate Class A result.
Nor does the continuous quantity degenerate: the safe mass can be a nontrivial fraction of the electorate, and the balance-vector constraints retain the paper’s substantive “where should support be added?” distinction. Theorem 3.5 and Theorem 3.6 therefore survive as a genuine continuous mirror. I would register reservations about novelty and programme priority, but I could not honestly defend the universal claim that no worthwhile mirror exists.
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.