| paper | Fair Lotteries for Participatory Budgeting |
| authors | — |
| venue | AAAI 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 5.11
statement extracted from the paper’s text layer
Given rational project costs, budget B, a finite set of binary approval types T, and a rational mass distribution μ over T, compute in time polynomial in m, |T|, and input bit-length a feasible marginal vector p and a sampler over integral project portfolios W such that each type t receives approval mass at least the maximum attainable with budget μ_tB, every sampled W satisfies mass-scaled EJR, and every sampled W satisfies BB1.
High-multiplicity binary participatory budgeting: approval-set types carry rational masses; decision variables are project marginals, weighted MES payments, and an implicit portfolio sampler; the objective is constructive feasibility under Strong UFS, EJR, and BB1, with no optimization objective.
The paper does not prove that Algorithm 2 admits exact implementation in time polynomial in the number of types and the bit-length of their masses, so the proposed high-multiplicity algorithm remains conjectural.
fatal: False
The mirror covers Theorem 5.11's binary-utility Strong UFS, EJR, BB1, and lottery implementation, with Theorem 3.2 supporting rounding; it leaves the FJR, GFS/JR, and general-cardinal IFS/JR results aside.
The strongest case is a population-level mirror of the paper’s best-of-both-worlds result, Theorem 5.11, which is proved in this paper. The theorem states:
In PB with binary utilities, Algorithm 2 computes an integral outcome sampled from a lottery that is ex-ante Strong UFS, ex-post BB1, and ex-post EJR in polynomial time.
The appropriate continuous setting is a municipal participatory-budgeting process with a large, nonatomic population. There is a finite project set \(C\), rational project costs, a rational budget \(B\), and a finite set of binary approval types \(T\). A type \(t\) is an approval set \(A_t\subseteq C\), and the society is a rational distribution \(\mu\), where \(\mu_t\) is the fraction of residents with approval type \(t\). A realistic instance might have \(10^5\) residents, \(m=30\)–\(100\) projects, and perhaps \(20\)–\(200\) recurring approval profiles arising from neighbourhoods, service needs, or demographic cohorts. The point is not that every resident has identical preferences, but that the budget process records only a relatively small number of preference profiles.
The continuous object is \(\mu\), not the project outcome. We retain the paper’s integral project portfolios and its lottery over them. A solution consists of a rational marginal vector \(p\in[0,1]^m\), with \(\sum_c p_c\operatorname{cost}(c)=B\), and a finite lottery \(\Delta\) over integral project sets \(W\) such that
\[ p_c=\Pr_{W\sim\Delta}[c\in W]. \]
As in the paper, the algorithm need not print an exponentially large support explicitly; a polynomial-time sampler for \(W\), together with \(p\), is an acceptable representation.
The ex-ante Strong UFS condition becomes a mass-scaled condition. For every type \(t\) with \(\mu_t>0\),
\[ \sum_{c\in A_t}p_c \;\ge\; \max\left\{ \sum_{c\in A_t}q_c: 0\le q_c\le1,\ \sum_c q_c\operatorname{cost}(c)=\mu_t B \right\}. \]
Thus a type occupying \(17\%\) of society receives the utility that its \(17\%\) share of the budget could obtain fractionally. This is exactly the paper’s Strong UFS benchmark with \(|S|/n\) replaced by population mass \(\mu_t\), not a weakened requirement.
For ex-post EJR, define, for an integral outcome \(W\) and project set \(R\),
\[ \operatorname{Bad}_W(R) = \{t:R\subseteq A_t,\ |A_t\cap W|<|R|\}. \]
The continuous outcome satisfies EJR if, for every \(R\subseteq C\),
\[ \sum_{t\in\operatorname{Bad}_W(R)}\mu_t < \frac{\operatorname{cost}(R)}{B}. \]
This is equivalent to saying that no cohesive population mass large enough to afford \(R\) consists entirely of types receiving fewer than \(|R|\) approved funded projects. Every sampled \(W\) must satisfy this condition, as well as the paper’s BB1 condition.
Call this problem Continuous Strong-UFS/EJR Implementation for Binary PB:
Given \((C,\operatorname{cost},B,T,\mu)\), output a marginal vector \(p\) and a lottery sampler \(\Delta\) such that \(p\) satisfies continuous Strong UFS and every sampled integral outcome satisfies continuous EJR and BB1.
I expect this problem to be Class A, although that is a new high-multiplicity theorem rather than something Theorem 5.11 proves automatically. The natural route is a type-compressed version of Algorithm 2. Give type \(t\) a budget \(\mu_tB\), run a weighted Method of Equal Shares on the \(\tau\) types rather than the \(n\) named voters, and aggregate all payments made by identical types. The EJR proof uses population-size inequalities and additive budget accounting, so its intended invariants should survive replacing voter counts by rational masses. The remaining budget of each type can then be assigned to approved projects exactly as in Algorithm 2, producing \(p\). Finally, the paper’s Theorem 3.2, proved here, supplies the dependent-rounding sampler with ex-post BB1. Since the MES outcome is funded with marginal one, every rounded outcome contains it and therefore preserves EJR.
The relevant complexity question is whether this can be done in time polynomial in \(m,\tau\), and the bit-length \(L\) of the costs, budget, and masses, without expanding a rational mass \(\mu_t\) into \(\mu_t n\) individual voters. That is a genuine continuization question: the paper gives polynomial time in the number of named voters, whereas the mirror asks for polynomial time in the number of distinct population types. It also exposes the continuous-optimization issue directly—weighted budget allocation, fractional knapsack calculations, and dependent rounding—without replacing the paper’s integral PB outcomes by divisible projects.
The authors should recognise this as their problem. The project set, heterogeneous costs, budget constraint, binary approvals, Strong UFS guarantee, EJR guarantee, BB1 relaxation, and lottery implementation are all retained. Only irrelevant voter labels disappear, and the cardinality ratios become population masses. A lottery over public project portfolios is also faithful to the paper’s own model: it can represent randomized selection in a repeated annual PB process, a randomized tie-breaking procedure, or a portfolio selected for a large municipality over repeated deployments.
I would not use Theorem 6.2 as an anchor. Its IFS guarantee is tied to an individual entitlement of \(1/n\), which tends to zero in an atomless population and would make the naïve continuous analogue vacuous. Strong UFS is the better mirror precisely because it is already a group/mass guarantee. Nor am I claiming that the paper’s fractional outcome is itself a population continuization: \(p\) remains merely the expectation of a lottery; \(\mu\) is the continuous society.
The weakest point is that the compressed algorithm is not actually proved in the paper. “Polynomial time” for Algorithm 2 means polynomial in the explicitly listed voters, and a weighted MES implementation with rational type masses requires a bit-complexity proof. Moreover, real PB populations may have many idiosyncratic approval sets, and randomizing an entire public portfolio may be politically less natural than randomizing private allocations. Those are genuine limitations. But they concern the strength of the scenario and the missing high-multiplicity analysis, not a mismatch between the proposed mirror and the paper’s question.
The mirror generates three natural follow-ups: whether the stronger FJR guarantee from Theorem 5.6 also admits a type-compressed algorithm; whether the paper’s Theorem 5.4 incompatibility between GFS and JR survives unchanged under mass notation; and which mass-scaled analogue, if any, preserves the meaning of general-cardinal IFS. That is a useful boundary map rather than an attempt to mirror every theorem.
The strongest negative case is that Theorem 5.11 is not really a new population problem. Its algorithm is anonymous: voters matter only through approval sets and residual budgets. Replacing \(n\) identical voters by a type of mass \(\mu_t\) merely replaces \( |S|B/n \) by \(\mu_tB\). The project lottery, BB1 rounding, and EJR certificate remain entirely finite-dimensional. The proposed mirror therefore looks like weighted PB with binary-encoded multiplicities, not a genuinely new continuous model.
There are two genuine concerns behind that objection. First, the paper proves polynomial time in the number of explicitly listed voters, not in \((m,\tau,L)\); weighted MES and its bit complexity still require a proof. Second, the municipal story may be optimistic: approval sets can be highly idiosyncratic, and a lottery over a public portfolio is randomization over outcomes rather than a population-level allocation.
Neither concern defeats the mirror, however. Binary approval sets are complete voter types for this paper: no relevant identity information is lost. The continuous EJR condition is not ad hoc either. For a fixed project set \(R\), the discrete EJR condition is equivalent to saying that the total mass of voters approving \(R\) but receiving fewer than \(|R|\) approved projects is below \(\operatorname{cost}(R)/B\). Likewise, Strong UFS for the maximal group of a type subsumes the condition for every smaller identical-preference group.
The weighted problem is also not computationally vacuous. A mass \(\mu_t\) encoded in \(L\) bits may represent exponentially many voters, so proving an algorithm polynomial in \((m,\tau,L)\) is precisely a high-multiplicity result. The fact that the proof may compress cleanly is evidence that the mirror is well chosen, not that it is illegitimate. Theorem 3.2 does not settle this question: it handles project-side rounding, while the unresolved issue is whether the fairness construction itself admits exact type compression.
A stronger mirror is available as well: replace EJR by FJR in Theorem 5.6 and ask whether the stronger guarantee, currently obtained only by an exponential-time algorithm, has a polynomial high-multiplicity implementation. That is plainly a computational question. The mass-scaled incompatibility in Theorem 5.4 is another legitimate boundary question, though less algorithmically central.
So the negative case can reasonably say “the proponent has proposed a promising high-multiplicity research direction, but has not yet shown that the compression is nontrivial.” It cannot honestly say that no worthwhile continuous mirror exists. The principal anchor survives, and the universal negative claim is weak.
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.