| paper | Shortlisting Rules and Incentives in an End-to-End Model for Participatory Budgeting |
| authors | Simon Rey, U. Endriss, Ronald de Haan |
| venue | IJCAI 2021 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even for every fixed positive integer multiplier, fixed \(\theta=1/2\), unit costs, and proposal sets of size at most two. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite project set \(P\), rational costs \(c(p)>0\), rational budget \(b\), integer \(k>0\), rational \(\theta\in(0,1)\), and a rational population distribution \(\mu\) over proposal-set types \(A\subseteq P\), output the canonical shortlist \(Q^\star\) maximizing \(\Phi_{\mu,\theta}(Q)=\sum_A\mu_A\sum_{\ell=0}^{|A\cap Q|-1}\theta^\ell\) subject to \(c(Q)\le kb\).
A high-multiplicity participatory-budgeting model with proposal-set types \(A\subseteq P\) carrying mass \(\mu_A\); the decision variable is an integral shortlist \(Q\), and the objective is the population-average discounted representation score \(\Phi_{\mu,\theta}(Q)\) under the cost bound \(c(Q)\le kb\).
The paper's \(1/n^\ell\) weighting has no nondegenerate scale-free limit: fixing \(\theta\) produces a parameterized family of mass problems rather than a literal \(n\to\infty\) limit.
fatal: False
The mirror covers the computational hardness of \(k\)-equal-representation shortlisting in Proposition 1. It leaves the axiomatic results and the first-stage strategy-proofness results, including Theorem 6 and Propositions 2–11, unmirrored.
The strongest positive case is a single anchor: Proposition 1, and the mirror should be a continuous version of the \(k\)-equal-representation shortlisting problem.
Proposition 1 states that, for \(k\in\mathbb N_{>0}\), no polynomial-time algorithm can compute the outcome of \(k\)-equal representation shortlisting, unless \(\mathrm{P}=\mathrm{NP}\). This proposition is proved in the paper, though its proof invokes the reduction of Aziz et al. (2015). The paper observes that an equal-cost special case becomes a Thiele committee-selection problem with decreasing weights \(1,1/n,1/n^2,\ldots\), for which the cited NP-hardness result applies.
My lead mirror is Continuous Equal-Representation Shortlisting.
An instance consists of a finite project set \(P\), rational project costs \(c(p)>0\), a rational budget \(b\), a positive integer \(k\), and a rational population distribution \(\mu\) over proposal-set types \(A\subseteq P\). Here \(\mu_A\) is the fraction of residents who submit exactly the proposal set \(A\). Let \(\theta\in\mathbb Q\cap(0,1)\) be the normalized discount parameter; for an \(N\)-agent instance of the paper’s rule, take \(\theta=1/N\). For a candidate shortlist \(Q\subseteq\bigcup_{\mu_A>0}A\), define
\[ \Phi_{\mu,\theta}(Q) = \sum_A \mu_A \sum_{\ell=0}^{|A\cap Q|-1}\theta^\ell . \]
The task is to output the canonical maximizer
\[ Q^\star = \operatorname{CanonUntie} \left( \arg\max_{\substack{Q\subseteq \bigcup_{\mu_A>0}A\\ c(Q)\le kb}} \Phi_{\mu,\theta}(Q) \right). \]
The shortlist remains an integral set of indivisible projects. Only the electorate has been continuized: a mass \(\mu_A\) of residents has type \(A\), and the objective is the population-average representation score. The parameter \(\theta\) is the necessary normalization of the paper’s \(1/n^\ell\) weights once absolute population size disappears.
This is a faithful high-multiplicity version of the paper’s problem. Given a finite profile with \(N\) agents, group agents with identical proposal sets into types and set \(\mu_A=n_A/N\) and \(\theta=1/N\). Then
\[ \Phi_{\mu,\theta}(Q) = \frac{1}{N} \sum_{i=1}^{N} \sum_{\ell=0}^{|P_i\cap Q|-1} \left(\frac{1}{N}\right)^\ell , \]
which differs from the paper’s objective only by the positive factor \(1/N\). Hence it produces exactly the same canonical shortlist.
The regime is plausible in participatory budgeting. A large municipality may have tens or hundreds of thousands of residents, while proposal behaviour is concentrated in a much smaller set of recurring types: neighbourhood associations, school communities, housing blocks, disability advocates, environmental groups, or residents who submit the same bundle of related projects. For the shortlisting rule itself, two participants with the same proposal set are indistinguishable, so the proposal set is a complete type description. If the full strategic model is retained, the type can be refined to include awareness and preferences as well.
The expected classification is Class B: hardness transfers. Any finite hard instance of Proposition 1 can be normalized into a rational population distribution. Therefore, a polynomial-time algorithm for Continuous Equal-Representation Shortlisting would yield a polynomial-time algorithm for the paper’s discrete shortlisting problem. The continuous mirror consequently remains computationally hard, not because residents are individually named, but because the integral project-selection problem retains the combinatorics.
This also gives useful follow-up questions. Is the problem fixed-parameter tractable in the number \(\tau\) of proposal-set types? Does hardness persist when \(\tau\ll N\), or does the genuinely compressed regime become tractable? What approximation guarantees are possible as a function of \(k\), the number of projects, or the number of distinct proposal cardinalities? One could also study how much population mass must change its proposal type before the selected shortlist changes.
I would not use Theorem 6 or Propositions 8–11 as additional computational anchors: they are impossibility and strategy-proofness results, not named complexity classifications. Proposition 1 is therefore both the strongest and the only anchor I would rely on.
The weakest point is that the continuous problem does not make the paper’s hardness disappear; for rational masses it can reproduce the finite problem exactly. Moreover, the paper’s geometric weights depend on \(n\), so introducing \(\theta\) is a genuine co-modification. A sceptic could call this a normalized restatement rather than a new continuous phenomenon. Still, it is a legitimate population continuization: the population is represented by masses over repeated proposal types, projects and budget feasibility remain discrete, and the resulting Class B boundary is precisely the kind of outcome the programme is meant to chart.
I cannot honestly defeat this anchor. The negative case has one real point, but it is not enough.
The vulnerability is the paper’s \(1/n^\ell\) weighting. A genuine limit \(n\to\infty\) makes every term with \(\ell\ge1\) vanish, leaving essentially a maximum-coverage rule. Conversely, the proposed \(\theta=1/N\) retains the finite population size as an external parameter, so it is better described as a normalized family of high-multiplicity instances than as a scale-free continuum limit.
But the stronger repair survives. Fix a discount parameter \(\theta\in(0,1)\) and define the population-average Thiele objective over proposal-set types. This is a recognizable mass variant: repeated residents with the same proposal set are genuinely interchangeable, projects remain indivisible, and the budget constraint remains exactly the paper’s combinatorial object. The proposal-set type is complete for Proposition 1; no identity information used by that result is lost. Large municipalities with recurring neighbourhood or community proposal bundles provide a credible high-multiplicity regime.
Nor can the mirror be rejected because hardness transfers. That is precisely a valid Class B outcome under the programme: rational empirical masses recover every finite hard instance, while the compressed type representation creates further questions about dependence on the number of types, approximation, and sensitivity to mass changes.
Thus the best objection is that the mirror may be less conceptually rich than the programme’s LP-based examples, and that the literal \(1/n^\ell\) rule has no nondegenerate population-size limit. It does not establish that no worthwhile mirror exists. Proposition 1 remains a legitimate, if modest, continuous-population computational anchor.
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.