| paper | Proportional Budget Allocations: Towards a Systematization |
| authors | Maaike Los, Zoé Christoff, Davide Grossi |
| venue | IJCAI 2022 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The high-multiplicity participatory-budgeting model is credible, and both proposed continuous questions are recognizable extensions of the paper. However, the paper contains no numbered result with computational character, so bit (a) objectively fails regardless of the mirror's quality. The opponent correctly identifies the proposed certificate and separation tasks as new computational projects rather than continuizations of computational results in this paper.
fails bit a — no named computational result to mirror
The proposed mirror covers high-multiplicity price certification for laminar instances and continuous core separation, while leaving the paper's remaining axiomatic relations and rule-property classifications untouched; no named computational result is mirrored.
The strongest honest positive case is that the paper has a very natural population mirror, but it does not contain a qualifying computational anchor. None of its numbered results states NP-hardness, membership in P, FPT, W[1]-hardness, approximation complexity, or a related computational classification. Its named results are axiomatic: for example, Theorem 6 proves that laminar proportionality implies priceability, and Theorem 9 proves a restricted core implication. Both are proved in this paper, not cited. Thus, strictly under the ChoCo standard, the paper supplies zero eligible anchors.
The best mirror nevertheless concerns high-multiplicity participatory budgeting. Let \(C\) be the finite project set, with rational costs and budget \(l\). A voter type is a complete approval set \(A_t\subseteq C\) for Phragmén and PAV, or a complete rational utility vector \(u_t\in[0,1]^C\) for Rule X. The society is a rational mass vector \(\mu\), with \(\mu_t\) the fraction of residents of type \(t\). A coalition is represented by \(z_t\in[0,\mu_t]\), and its mass is \(\sum_tz_t\). Outcomes remain bundles \(W\subseteq C\) with \(\operatorname{cost}(W)\le l\): only the population, not the projects, is continuized.
This is a credible regime for city-wide annual budgeting: tens or hundreds of thousands of residents, a fixed catalogue of perhaps dozens of projects, and many residents sharing identical approval lists or utility profiles. It is not credible for a seven-person committee. Rational masses retain the exact high-multiplicity bridge: multiplying by a common denominator produces a finite election with cloned voters, and all coalition-size conditions become the corresponding mass inequalities.
My lead derived problem is \(\mathrm{Laminar\mbox{-}PriceCert}_{\infty}\), motivated by Theorem 6.
Given a finite-type mass society \((C,\operatorname{cost},l,\mu)\), a laminar decomposition of that society, and a candidate bundle \(W\), decide whether \(W\) has a continuous price system and, if so, minimize the initial per-unit budget \(b\). Output \(b\) and payments \(p_t(c)\) per unit mass of type \(t\), satisfying
\[ \sum_{c}p_t(c)\le b \]
for every type \(t\), \(p_t(c)=0\) whenever type \(t\) derives zero utility from \(c\), and
\[ \sum_t\mu_t p_t(c)= \begin{cases} \operatorname{cost}(c),&c\in W,\\ 0,&c\notin W. \end{cases} \]
For every unselected project \(c\),
\[ \sum_{t:u_t(c)>0} \mu_t\left(b-\sum_{c'\in W}p_t(c')\right) \le \operatorname{cost}(c). \]
The continuous laminar definitions replace voter cardinalities by masses. In particular, a decomposition into two subinstances uses
\[ \mu_1l_2=\mu_2l_1 \]
in place of \(|P_1|l_2=|P_2|l_1\).
I expect \(\mathrm{Laminar\mbox{-}PriceCert}_{\infty}\) to be Class A. Once \(W\) is supplied, the price-system search is a rational linear program with \(O(\tau m)\) payment variables. With a laminar decomposition supplied, Theorem 6’s inductive proof gives an even more direct certificate-construction algorithm. This is a genuine population formulation rather than outcome-space continuity: the projects remain indivisible, while proportional budgets and coalition power are measured in mass.
The main further questions are whether the laminar decomposition can be found efficiently rather than supplied, whether the minimum \(b\) has a useful economic interpretation, and whether the LP remains tractable when approval types are given implicitly rather than listed explicitly.
A second, weaker derived problem is \(\mathrm{CoreSep}_{\infty}\), motivated by Theorem 9. Given a bundle \(W\) and a finite-type mass society, find a blocking project set \(T\subseteq C\) and coalition masses \(z_t\) such that
\[ \sum_t z_t\ge \frac{\operatorname{cost}(T)}{l}, \qquad 0\le z_t\le\mu_t, \]
and every type with \(z_t>0\) strictly prefers \(T\) to \(W\):
\[ u_t(T)>u_t(W). \]
If no such \(T,z\) exists, certify that \(W\) is in the continuous core. Theorem 9 predicts a negative answer whenever \(W\) is laminar proportional and satisfies the paper’s \(u\)-affordability condition. For fixed \(m\), this is tractable by enumerating \(T\subseteq C\) and summing the masses of types that strictly benefit. With unrestricted \(m\), the subset search may itself become hard; that would be new complexity of the derived problem, not hardness inherited from this paper.
The authors would likely recognise both formulations: the paper already defines proportionality through coalitions, budget shares, and project bundles, and its proofs repeatedly manipulate ratios such as \(|S|/n\). Replacing those ratios by \(\mu(S)\) preserves the mathematics exactly for rational clone populations. Existing high-multiplicity election work would support this interpretation rather than count against it.
The weakest point is decisive: these are computational questions extracted from axiomatic theorems, not computational results established by the paper. The paper therefore supports a plausible and potentially useful ChoCo extension—especially \(\mathrm{Laminar\mbox{-}PriceCert}_{\infty}\)—but it cannot honestly be presented as evidence that a discrete computational hardness result dissolves under continuization.
The negative case is stronger than the proponent admits: this paper fails the source-level anchor test. It contains no theorem, lemma, or corollary about polynomial time, hardness, approximation, parameterized complexity, or an algorithmic classification. Its results are all logical relations among axioms. Theorem 6 is an implication from laminar proportionality to priceability; Theorem 9 is a restricted implication from laminar proportionality and \(u\)-affordability to the core. Neither asserts that anything is computed.
The proposed \(\mathrm{Laminar\mbox{-}PriceCert}_{\infty}\) therefore is not a continuization of Theorem 6 in the relevant sense. Once \(W\) and its laminar decomposition are supplied, the price certificate is simply a finite linear feasibility problem with \(O(\tau m)\) variables. The same certificate problem can be written over the original individual voters with \(O(nm)\) variables; grouping identical voters into masses merely aggregates identical rows. That is legitimate high-multiplicity compression, but it is not a computational question exposed by the theorem. Indeed, Theorem 6’s inductive proof already gives the certificate directly on the restricted instances.
The proposed minimization of \(b\) is also a new objective: the paper asks only whether some price system exists, with the prescribed budget convention. If one removes the supplied bundle or decomposition and asks the algorithm to find them, the task becomes a new bundle-selection or laminar-recognition problem. It may be worthwhile, but its content is no longer Theorem 6, and any complexity comes from the newly introduced search problem rather than from continuizing the population.
Theorem 9 fares no better. Its exact mass translation is perfectly sensible. For a fixed bundle \(W\), define
\[ M_\mu(T)=\sum_{t:u_t(T)>u_t(W)}\mu_t. \]
Then \(W\) fails the continuous core precisely when some project set \(T\) satisfies
\[ M_\mu(T)\ge \frac{\operatorname{cost}(T)}{l}. \]
This is a faithful high-multiplicity reformulation of the paper’s coalition condition. But it also shows why it supplies no computational anchor: the population appears only through a weighted sum of explicitly listed types, while the substantive search is over project bundles \(T\). Theorem 9 itself neither gives a separation algorithm nor studies the complexity of finding such a \(T\); it only proves a sufficient condition under a restricted laminar hypothesis. Replacing the pointwise existential condition by an essential or positive-mass version would be a reasonable measure-theoretic repair, but it would be a new axiom, not an algorithmic result in the paper.
The strongest possible direct mirror would define high-multiplicity PAV, Phragmén, and Rule X on a mass distribution and then compute their bundles before testing PJR, EJR, priceability, or the core. A city-wide budgeting population with repeated approval or utility types is entirely credible, and existing high-multiplicity work would support that regime. The problem is not the model. It is that this paper has already written the population dependence in normalized, anonymous form and offers no computational theorem for the resulting rules. The mirror would be a sensible new PB-algorithmics project, but not a continuization of this paper’s contribution.
So the honest negative verdict is strong as a ChoCo triage decision, though not a proof that continuous PB is never worth studying. The paper supplies a plausible high-multiplicity setting but no qualifying computational anchor; its two proposed anchors are certificate and separation problems invented beyond the paper, and the better repaired versions remain independent research questions rather than mirrors of its results.
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.