| paper | Proportionality in Approval-Based Participatory Budgeting |
| authors | — |
| venue | AAAI 2023 |
| 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.3
statement extracted from the paper’s text layer
Given projects with rational costs and budget, finitely many approval types with rational masses summing to one, and cost-based satisfaction, compute an integral feasible project set W satisfying mass-EJR: for every positive-mass coalition q and every commonly approved T with cost at most q's mass times the budget, some type in q must receive at least the satisfaction of T.
A finite type distribution over approval ballots with masses λ_t; the decision variable is an integral project set W with c(W)≤b, and the task is to find W satisfying the continuous mass analogue of cost-based EJR.
The mirror covers Theorem 3.3 and its corresponding hardness phenomenon, while leaving the paper's positive MES, PJR-x, priceability, incompatibility, and axiomatic results untreated.
The strongest honest positive case is a faithful Class B mirror of the paper’s main computational result. It does not claim that continuization makes this problem easier; it shows that the paper’s hardness survives the population relaxation, which is itself one of ChoCo’s intended outcomes.
The anchor is Theorem 3.3, proved in this paper: for any satisfaction function that is strictly cost-responsive on single-voter instances, no polynomial-time algorithm can always compute an outcome satisfying \(\mu\)-EJR unless \(P=NP\).
Call the mirror Continuous Cost-EJR\(_\infty\). An instance consists of:
A solution is an integral project set \(W\subseteq P\) with \(c(W)\le b\). It must satisfy the following continuous EJR condition. For every positive-mass coalition \(q=(q_1,\ldots,q_\tau)\) with \(0\le q_t\le\lambda_t\), every nonempty coalition mass \(q(S)=\sum_tq_t>0\), and every project set \(T\) such that
\[ T\subseteq\bigcap_{t:q_t>0}a_t \qquad\text{and}\qquad c(T)\le q(S)b, \]
there must exist a type \(t\) with \(q_t>0\) such that
\[ \sigma(a_t\cap W)\ge \sigma(a_t\cap T). \]
This is exactly the paper’s EJR condition with voter subsets replaced by measurable submasses. The project decision remains integral: this is population continuization, not fractional project selection or lotteries.
The natural regime is a large municipal PB process: hundreds of thousands or millions of residents, but comparatively few approval patterns because residents’ choices are shaped by a limited set of districts, issue bundles, or recurring civic priorities. Two residents with the same approval ballot are the same type for this problem; project costs and the budget are global parameters. Thus \(n\gg\tau\), and a rational mass \(\lambda_t=n_t/n\) is the exact high-multiplicity representation of \(n_t\) identical voters.
The hardness transfers immediately. Take any single-voter instance from Theorem 3.3 and represent it by one approval type of mass \(1\). For that society, every affordable project set \(T\) is a cohesive coalition target, and Continuous Cost-EJR\(_\infty\) requires \(W\) to have at least as much satisfaction as every affordable \(T\). Under cost-based satisfaction, this means finding a feasible bundle of maximum attainable cost—the same subset-selection difficulty used by the discrete theorem. The same instance can also be interpreted as an arbitrarily large population of identical voters, so the reduction is compatible with a genuine high-multiplicity story.
I would therefore classify this mirror as Class B: the combinatorics live in the project agenda and binary-encoded costs, not in voter individuation. Continuization does not dissolve the obstacle. That is a meaningful result for the programme because it identifies a boundary where the continuous population model stops helping.
The mirror should be convincing to the original authors. Their definitions already depend only on approval sets, project costs, the budget, and the fraction \(|N'|/n\) of a cohesive group. Every one of those ingredients has a direct mass analogue. No named voter identity, interpersonal relation, or arrival order is being discarded. For rational masses, the continuous instance is also exactly expandable into a finite profile of clones.
The weakest point is that the hard subfamily has only one distinct type. A sceptic could say this demonstrates merely that a subset-selection problem remains hard after being relabelled as a continuum, rather than revealing new computational content about population distributions. That criticism is fair. The answer is that ChoCo explicitly includes hardness-transfer mirrors, and this theorem is particularly valuable because it proves that the relaxation’s benefit is not universal: even maximal multiplicity cannot remove hardness caused by projects and budget arithmetic.
The main follow-up questions are whether bounded or unary project costs yield a pseudopolynomial continuous algorithm, whether parameterization by the number of projects or approval types helps, and whether the paper’s positive MES results—especially Theorem 3.5 and Corollary 4.6—extend to an explicitly compressed algorithm for continuous EJR-x or PJR-x. Those are separate Class A questions, but Theorem 3.3 already supplies a precise and defensible continuous mirror for this paper.
The strongest negative case is that the proposed mirror smuggles all of its hardness through a point mass. In the continuous EJR definition, fix the support \(S\) of a coalition \(q\). If a project set \(T\) is affordable for \(q\), it remains affordable after enlarging \(q\) to the full mass \(\lambda\) on \(S\). Hence it suffices to check coalitions consisting of whole voter types. The apparent continuum of submasses collapses to a finite weighted approval instance.
For the anchor itself, \(\tau=1\) and \(\lambda_1=1\). With cost-based satisfaction, EJR then says that \(W\) must achieve at least the cost of every affordable approved project set. Computing such a \(W\) is simply the underlying knapsack/subset-sum optimisation over projects. The population distribution contributes no information whatever. Adding many tiny extra types does not repair this: they can be given masses too small to afford any project, leaving the hard one-type component unchanged. Thus the proposed theorem does not expose a computational phenomenon caused by a continuous society; it is a project-selection hardness result surviving a relabelling.
That is the best substantive objection, but it is not decisive under ChoCo’s rules. A finite distribution over approval types is exactly the programme’s high-multiplicity model, and participatory budgeting has a credible large-electorate interpretation. The outcome’s remaining integrality is not forbidden, and the programme explicitly counts Class B hardness transfers as valuable. The single-type instance is also a legitimate high-multiplicity society, not an identity-sensitive construction.
Nor can one object that the hardness lives in the project agenda: the brief expressly disallows that objection. A stronger mirror could impose nontrivial mass on many approval types and study weighted EJR/PJR systematically; that would be a new and potentially worthwhile problem, even if the theorem’s one-type slice supplied only its lower bound.
So the negative case is weak. The proposed EJR mirror is formally faithful, naturally situated in high-multiplicity PB, and anchored by a genuine named computational theorem. I would not expect a careful reader to reject this paper on the ground that it has no worthwhile continuous mirror.
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.