| paper | Fairness in Participatory Budgeting via Equality of Resources |
| authors | — |
| venue | AAMAS 2023 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6
statement extracted from the paper’s text layer
Given rational costs \(c:P\to\mathbb{Q}_{\geq 0}\), budget \(b\), and a rational distribution \(\mu\) over approval types \(T\subseteq 2^P\), output a feasible bundle \(\pi\subseteq P\) satisfying EJS: for every \(Q\subseteq P\) and every \(Q\)-supporting mass vector \(g\) with \(0\leq g_t\leq\mu_t\) and \(\sum_t g_t\geq c(Q)/b\), some \(t\) with \(g_t>0\) has \(\operatorname{sh}_\mu(\pi,t)\geq\operatorname{sh}_\mu(Q,t)\).
A high-multiplicity participatory-budgeting model with approval types \(t\), population masses \(\mu_t\), indivisible project-bundle decision variable \(\pi\), and type share density \(\operatorname{sh}_\mu(\pi,t)=\sum_{p\in\pi\cap t}c(p)/\sum_{u:p\in u}\mu_u\).
Approval patterns can be nearly idiosyncratic in some PB consultations, limiting the practical compression benefit.
fatal: False
The mirror covers EJS allocation in Theorem 6, FS existence in Proposition 1, and the MESshare Local-FS guarantee in Theorem 4; it leaves the paper's axiomatic taxonomy and empirical evaluation otherwise unchanged.
The paper has a very natural continuous-population mirror. Keep the projects indivisible—the paper’s question is still which public projects to fund—but replace the electorate by a distribution over approval-ballot types.
Let \(T\subseteq 2^P\) be the finite set of approval types and let \(\mu_t\) be the mass of residents with ballot \(t\), with \(\sum_t\mu_t=1\). For each project \(p\), write
\[
s_p=\sum_{t:p\in t}\mu_t
\]
for its supporting mass. A selected project gives each supporting type the share-density \(c(p)/s_p\), so
\[
\operatorname{sh}_\mu(\pi,t)=\sum_{p\in \pi\cap t}\frac{c(p)}{s_p}.
\]
This is exactly the paper’s equality-of-resources idea: the cost of a project is divided equally among its supporters, except that “equally” is now per unit of population mass. A type’s fair-share entitlement is
\[
f_\mu(t)=\min\{b,\operatorname{sh}_\mu(P,t)\}.
\]
The factor may initially look different from the finite formula \(b/n\), but it is just a change from an individual’s share to a share-density. If a discrete profile has \(n_t\) voters of type \(t\), take \(\mu_t=n_t/n\). Then every continuous share and entitlement is precisely \(n\) times its discrete counterpart, so every relevant comparison is unchanged.
The regime is a citywide or regional PB process with, say, hundreds of thousands of residents and a stable menu of projects, but a far smaller set of recurring approval patterns: neighbourhood-and-service constituencies, or ballot clusters produced by a standardised consultation. A “type” is the complete approval set submitted by such a constituency. This is not a claim that every PB instance is high-multiplicity—small deliberative bodies plainly are not—but it is a persuasive regime for municipal PB, which is the paper’s own application domain.
My lead continuous question is EJS-Allocation\(_\infty\), mirroring Theorem 6 (proved in this paper):
Instance: rational project costs \(c\), budget \(b\), and a rational distribution \(\mu\) over finite approval types.
Question: output a feasible bundle \(\pi\subseteq P\) satisfying continuous EJS.
Continuous EJS: for every project set \(Q\subseteq P\) and every measurable coalition represented by masses \(0\leq g_t\leq\mu_t\), where \(g_t=0\) unless \(Q\subseteq t\), and \(\sum_tg_t\geq c(Q)/b\), there is a type \(t\) with \(g_t>0\) such that
\[ > \operatorname{sh}_\mu(\pi,t)\geq\operatorname{sh}_\mu(Q,t). > \]
A solution is such a bundle \(\pi\); the objective is feasibility with respect to EJS.
This is not merely inspired by EJS; it is its direct mass formulation. Coalitions may contain fractions of a type, as they should in a continuum society. That does not invent a new fairness demand. For a fixed \(Q\), a violating coalition exists exactly when sufficiently much mass of types failing the share threshold jointly supports \(Q\); in the discrete embedding the same statement is witnessed by the corresponding voters.
I expect Class B: hardness transfers. Theorem 6 says that computing an EJS allocation is not polynomial-time solvable unless \(\mathrm P=\mathrm{NP}\). Compress any discrete profile into its distinct approval types and use their rational frequencies. The discrete and continuous EJS inequalities agree under the scaling above, so a polynomial algorithm for EJS-Allocation\(_\infty\), measured in the finite type description and bit length, would solve the paper’s discrete search problem. This is an especially clean example of continuization locating a genuine boundary: a continuous population does not dissolve combinatorics that live in the project set and budget-selection problem.
A second, closely related but independently useful anchor is FS-Existence\(_\infty\), mirroring Proposition 1 (proved here, via a reduction from 3-Set-Cover):
Instance: the same continuous PB instance.
Question: does there exist a feasible bundle \(\pi\) such that
\[ > \operatorname{sh}_\mu(\pi,t)\geq f_\mu(t) > \quad\text{for every type }t\text{ with }\mu_t>0? > \]
A yes-instance is accompanied by such a bundle.
This is the continuous version of asking whether every positive-mass constituency receives its fair resource share. Proposition 1’s NP-completeness transfers by the same exact embedding, including from instances whose projects all have equal cost. Again, the mirror is honest about what remains discrete: no fractional-project relaxation is being smuggled in to make the problem easy.
There is also a positive, tractable anchor: Local-FS-Allocation\(_\infty\), mirroring Theorem 4 (proved here). Define Local-FS by requiring that for every unselected project \(p\), at least one positive-mass supporting type \(t\) would reach its fair-share entitlement upon adding \(p\). The question is to output a feasible Local-FS bundle.
The continuous analogue of MESshare is immediate. Give type \(t\) a load density \(\ell_t\), initially zero; at a step, its contribution density toward supported \(p\) at parameter \(\alpha\) is
\[
\gamma_t=\min\{b-\ell_t,\alpha\,c(p)/s_p\}.
\]
Project \(p\) is affordable when \(\sum_{t:p\in t}\mu_t\gamma_t=c(p)\); select a project at minimum affordable \(\alpha\), and update its supporters’ loads. This is exactly MESshare with sums over residents replaced by finite weighted sums over types. The proof of Theorem 4 carries through verbatim at that level, and the computation is polynomial in \(|T|\), \(|P|\), and rational encoding length. Thus this is a credible Class A question, not just a hardness-preserving reformulation.
The strongest aspect of the case is that the same population model both preserves the paper’s hard EJS and FS questions and preserves its constructive MESshare guarantee. The authors should recognise it immediately: their own notion of share already divides a project’s cost among a group of supporters; replacing supporter counts by supporter mass is the literal aggregate version of that operation.
The weakest point is also clear. Approval types can be numerous—up to exponentially many in the number of projects—and a real PB ballot may be idiosyncratic. So this mirror is strongest for genuinely clustered, large-population consultations, not for every PB exercise. Nor does continuizing voters make project selection convex; Theorem 6 and Proposition 1 show why it should not be advertised as a universal tractability cure. But that is a strength of the programme rather than a defect in the mirror: it produces a sensible high-multiplicity object, a direct discrete/continuous dictionary, one tractable guarantee, and explicit Class B boundaries.
I cannot make the requested universal negative case honestly. All three anchors survive the serious objections.
The key reason is that this is exactly a high-multiplicity setting in a credible regime: a large municipal electorate, a fixed project menu, and recurring approval constituencies. An approval set is a complete type for this paper’s model—there are no voter-specific costs, identities, assignments, or arrival times that mass aggregation would discard. The paper’s central quantity already divides a project’s cost across its supporters, so replacing supporter count by supporter mass is not a reinterpretation of the objective; it is its natural density form.
The EJS anchor is sound. Fractional coalitions do not create an alien axiom: for any proposed cohesive project set, an EJS violation is witnessed precisely by enough mass of supporters whose type-level share falls short. In a discrete profile embedded with \(\mu_t=n_t/n\), multiplying all density shares by \(1/n\) recovers the paper’s individual shares, and the coalition threshold is identical. Allowing a fraction of a type causes no mismatch, because agents of one approval type are indistinguishable; a violating fractional coalition exists iff the total mass of failing types reaches the threshold. Thus Theorem 6 gives a legitimate Class B mirror, not merely a superficial restatement.
The FS-existence anchor is even harder to resist. Its condition is pointwise over positive-mass approval types and is exactly the scaled finite FS condition. It retains indivisible projects, as the paper does; that is not a defect or a forbidden “failure to help,” but the correct population-only continuization. The discrete NP-completeness result can embed directly.
The Local-FS/MESshare anchor also survives. The weighted MES construction is not hand-waving: scaling an individual’s \(b/n\) allowance and load by \(n\) yields a type’s allowance and load density \(b\), while summing contributions with weights \(\mu_t\) gives precisely each project’s cost. The proof of Theorem 4 uses only these aggregate identities, so it transfers. Its polynomial weighted implementation is a genuine Class A question.
The most that can responsibly be said against the paper is a scope qualification: approval patterns may be nearly idiosyncratic in some consultations, so the mirror is not uniformly compelling for every PB instance. But municipal PB is one of the clearest plausible high-multiplicity regimes, and the proponent already confines the claim accordingly. Exponentially many possible approval types is likewise not a refutation: the input may list the occurring types, and the programme expressly treats the number of types as a relevant parameter.
I also do not find an “already done continuously” objection. Related PB work on cores, priceability, lotteries, or divisible outcomes is not a continuous-population computational treatment of these share axioms. So the negative case is weak at its foundation: this paper should be green-lit on the strength of any one of these anchors, especially EJS or Local-FS.
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.