| paper | Maxmin Participatory Budgeting |
| authors | Gogulapati Sreedurga, Mayank Ratan Bhardwaj, Yadati Narahari |
| venue | IJCAI 2022 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given projects \(P\) with integer costs \(c(p)\), budget \(b\), approval types \(A_t\subseteq P\), and a rational distribution \(\mu\) with \(\mu_t\ge0\) and \(\sum_t\mu_t=1\), decide whether there exists \(S\subseteq P\) such that \(\sum_{p\in S}c(p)\le b\) and \(\min_{t:\mu_t>0}\sum_{p\in S\cap A_t}c(p)\ge s\).
A high-multiplicity indivisible-PB model with complete approval types \(A_t\subseteq P\), rational masses \(\mu_t\), atomic project variables \(x_p\in\{0,1\}\), budget \(\sum_p c(p)x_p\le b\), and objective \(\max q\) subject to \(q\le\sum_{p\in A_t}c(p)x_p\) for every \(t\) with \(\mu_t>0\).
The mirror covers Theorems 1–4: strong and weak NP-hardness, pseudo-polynomial solvability for constant τ, and polynomial solvability for constant τ and δ; it leaves Theorem 5's strategy-proofness bound and all axiomatic results untouched.
The strongest mirror is a high-multiplicity, continuous-population version of the paper’s own MPB problem. Projects remain indivisible; only the electorate becomes continuous.
Let \(P\) be the projects, with integer costs \(c(p)\) and budget \(b\). A voter type is an approval set \(A_t\subseteq P\). A society is a rational distribution \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the fraction of residents of type \(t\). Since the paper gives voters no characteristics beyond their approval sets, \(A_t\) is a complete type description. Define
\[ u_t(S)=c(S\cap A_t) \]
for a funded set \(S\subseteq P\), and
\[ \operatorname{MPB}_\infty(\mu) = \max_{\substack{S\subseteq P\\c(S)\le b}} \min_{t:\mu_t>0}u_t(S). \]
The decision problem asks whether there is a feasible \(S\) with
\[ \min_{t:\mu_t>0}c(S\cap A_t)\ge s. \]
Thus mass describes the population, but the action is still an indivisible project bundle. This is not divisible PB or fractional funding.
The natural regime is a municipal or district PB election with thousands or millions of residents but a small number of recurring approval patterns: neighbourhood blocs, issue coalitions, or standardized ballot templates. The paper itself reports 3,482 voters and only 16 distinct approval votes in the Powązki election, and says that many real datasets have fewer than 20% as many distinct votes as voters. The continuous regime keeps \(\tau=|T|\) moderate while the number of named residents tends to infinity. A finite profile with \(n_t\) voters of type \(t\) maps exactly to \(\mu_t=n_t/n\); conversely, if \(\mu_t=a_t/Q\), it can be expanded into \(a_t\) voters after clearing denominators.
My lead anchor is Theorem 1: “The decision version of MPB is strongly NP-hard.” This theorem is proved in the paper; the reduction uses the known strong NP-hardness of Set Cover.
The corresponding problem is the general \(\operatorname{MPB}_\infty\)-Decision problem just defined. In the paper’s reduction, take one project \(p_C\) of unit cost for each set \(C\) in a Set Cover instance. For each universe element \(a\), create a voter type
\[ A_a=\{p_C:a\in C\}, \]
give every type positive mass, say \(\mu_a=1/|U|\), and set \(b=k\) and \(s=1\). A feasible project set gives every positive-mass type utility at least \(1\) exactly when the corresponding sets cover \(U\) within the budget. Hence the continuous problem is strongly NP-hard.
This hardness survives arbitrarily large populations: replicate every type any number of times without changing \(\mu\) or the continuous instance. The combinatorics live in the project–approval incidence structure, not in individual voter identities. I would therefore classify this mirror as Class B: the discrete hardness transfers to the continuous population model. That is still a valuable outcome for ChoCo, because it identifies a natural boundary where population continuization does not make the problem tractable.
A second, more pointed anchor is Theorem 2: “The decision version of MPB is weakly NP-hard when the number of distinct votes is constant.” This is also proved in the paper, using the known weak NP-hardness of SUBSET SUM.
The corresponding fixed-type problem restricts \(\operatorname{MPB}_\infty\)-Decision to societies with at most a fixed number of positive-mass approval types. The reduction already works with one type: let \(A_1=P\), \(\mu_1=1\), let project \(p_i\) have cost \(x_i\), and set \(b=s=Z\). The decision condition becomes
\[ c(S)\le Z \quad\text{and}\quad c(S\cap A_1)=c(S)\ge Z, \]
so it asks whether some subset of the \(x_i\) sums exactly to \(Z\).
This is expected to remain Class B, but for a different reason: the hardness is numeric and resides entirely in project costs, not in population multiplicity. It is therefore a useful warning against claiming that few types automatically make the continuous problem easy. It also gives the mirror a genuine boundary case: even a society consisting of one positive-mass type can retain weak NP-hardness.
The third anchor is Theorem 4: “MPB can be solved in polynomial time when the number of distinct votes and the scalable limit are constant.” This theorem is proved in the paper, using a cited fixed-constraint, bounded-coefficient ILP result.
The corresponding problem, bounded-resolution \(\operatorname{MPB}_\infty\), is the same continuous decision or optimization problem restricted to constant \(\tau\) and constant
\[ \delta= \frac{\max_{p\in P}c(p)} {\gcd(c(p_1),\ldots,c(p_m),b)}. \]
After dividing costs and budget by the gcd, the problem has \(\tau+1\) relevant constraints and coefficient bound \(\delta\). The paper’s ILP argument therefore gives an exact polynomial-time algorithm. The masses are supplied as rational numbers, but only their positive support matters for this particular maxmin objective.
This is a Class A regime. It is not a weakened divisible-outcome surrogate: projects remain atomic, and the exact MPB objective is preserved. The gain comes from high multiplicity and bounded project-cost resolution, precisely the sort of type-level compression and integer-optimization structure that a continuous formulation makes natural. Theorem 3 gives the intermediate pseudo-polynomial result when only the number of distinct votes is constant.
The original authors should recognize this as their problem rather than a replacement for it. The approval types are exactly their “distinct votes,” the utility is exactly \(c(S\cap A_i)\), and the budget feasibility condition is unchanged. Moreover, their Proposition 3, clone independence, formally confirms that duplicate voters do not alter the MPB outcome. Replacing multiplicities by \(\mu\) is therefore an exact high-multiplicity formulation of the rule, not a simplification that changes what MPB optimizes.
The mirror covers the computational MPB results: Theorems 1–4, with Theorems 1, 2, and 4 as the principal anchors. It does not claim to continuize the axiomatic results in Theorems 6 and 7 or Propositions 2–4. Nor would I use Theorem 5 without a separate definition of cohort strategy-proofness: individual deviations have zero mass in an atomless population and could make the paper’s incentive notion vacuous.
The weakest point is that \(\mu_t\)’s numerical magnitude is largely inert under maxmin: once \(\mu_t>0\), even a tiny minority constrains the objective just as much as a large group. A sceptic could therefore call this a type-compressed high-multiplicity reformulation rather than a genuinely mass-sensitive continuous optimization problem. That criticism is real. It does not, however, invalidate the mirror under ChoCo’s stated scope. MPB is deliberately egalitarian and already clone-independent, so preserving that insensitivity is necessary for fidelity. The resulting model still gives a precise population-continuous question, an exact finite-to-continuous dictionary, a strong transferred-hardness result, and a clean tractable regime in terms of \(\tau\) and \(\delta\). Further work could study mass-sensitive extensions—quantile maxmin, weighted leximin, or robustness to small positive-mass types—but those should be labelled new problems rather than silently attributed to this paper.
The strongest case against is a degeneracy specific to MPB, not an objection to participatory budgeting as a high-multiplicity domain. MPB’s objective erases population mass:
\[ \operatorname{MPB}_\infty(\mu) = \max_{S:c(S)\le b} \min_{t:\mu_t>0} c(S\cap A_t). \]
Thus the value depends only on the support \(D(\mu)=\{A_t:\mu_t>0\}\). If one type has mass \(0.000001\) and another has mass \(0.9\), they constrain the outcome identically. Replacing every voter by a continuum of clones changes no input relevant to the optimization. Within each fixed support region of the probability simplex, the objective is constant; crossing from zero mass to positive mass creates a discrete new constraint. The purported continuous variable has disappeared.
This defeats Theorem 1 as evidence for a worthwhile continuous mirror, although not as a hardness proof. The Set Cover reduction remains formally valid, but its “continuous society” is merely a collection of approval constraints. The equal masses \(\mu_a=1/|U|\) carry no information. Replicating every element type arbitrarily many times produces the same instance, and the problem can be written more honestly as
\[ \max_{S:c(S)\le b}\min_{A\in D}c(S\cap A) \]
for a finite family \(D\) of approval sets. That is the original MPB problem after duplicate voters have been deleted, not a computational problem over a population distribution. Arbitrary positive masses do not repair this: they remain inert.
Theorem 2 makes the objection even stronger. Its reduction uses one voter type with \(\mu_1=1\), so the continuous population is fixed and the problem is simply Subset Sum encoded through indivisible project costs. Replacing that voter by a million identical voters, or by a unit-mass continuum of identical agents, produces no population problem at all. Adding several types with the same approval set is equally vacuous. The hardness is real, but this anchor contains no meaningful population axis.
Theorem 4 does not rescue the mirror. Its algorithm is already an algorithm for the discrete problem after identical approval votes are deduplicated. The parameter \(\hat n\) is precisely the number of distinct votes, and the scalable limit \(\delta\) concerns project-cost resolution, not population mass. The continuous formulation merely renames \(\hat n\) as \(\tau\) and supplies masses that the algorithm ignores. Theorem 3 has the same character: its dynamic programme tracks distinct approval patterns and cost totals, never voter proportions. There is no column-generation question, mass rounding issue, or distribution-dependent optimization to study.
Changing the scenario cannot fix this while preserving MPB. Neighbourhood blocs, issue coalitions, and recurring ballot templates are perfectly sensible high-multiplicity stories, but MPB’s egalitarian minimum deliberately treats every represented type equally. To make \(\mu\) operative one must replace MPB by a mass-sensitive objective—say a quantile guarantee, weighted leximin, or a mass-weighted welfare function. Those could be worthwhile ChoCo problems, but they are new rules: the three cited theorems would no longer be their computational anchors. Likewise, scaling the project catalogue with the population would change the indivisible-PB problem rather than continuize its society.
This is not the mistaken claim that high multiplicity is implausible, nor that transferred hardness is uninteresting. Participatory budgeting plainly has repeated approval patterns, and existing high-multiplicity evidence would support that regime. The narrower point is that MPB’s clone independence makes the distribution itself computationally irrelevant. Under a requirement that the continuous population be a genuine object rather than merely a support set, Theorems 1, 2, and 4 all fail as worthwhile mirrors.
The negative case is therefore conditional rather than airtight. If ChoCo accepts a support-only high-multiplicity formulation, the proponent’s Theorem 1 mirror survives as Class B and Theorem 4 survives as a valid tractable regime. But if “continuous society” requires population mass to matter, no faithful version of this paper’s MPB objective supplies it; rescuing the programme requires studying a different, mass-sensitive PB objective.
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.