Proportionally Representative Participatory Budgeting with Ordinal Preferences (d4-conf-aaai-2021-0427)

Given projects \(C\), rational costs \(w\), budget \(L\), ordinal types \(T\), and rational masses \(\mu\), output an integral feasible \(W\subseteq C\) satisfying continuous CPSC, or report nonexistence: for every coalition \(q\) with \(0\le q_t\le\mu_t\), every solidly supported \(C'\), and every \(C''\subseteq C'\) with \(w(C'')\le q(T)L\), require \(w(\bar C(q,C')\cap W)\ge w(C'')\).

Let \(C\) contain \(m\ge1\) indivisible projects, with positive binary-rational costs \(w(c)\) and budget \(B>0\); write \(w(S)=\sum_{c\in S}w(c)\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) weak-order preference types, each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
A coalition is any real vector \(q\) with \(0\le q_t\le\mu_t\); write \(q(T)=\sum_{t\in T}q_t\). It solidly supports nonempty \(C'\subseteq C\) if every type with \(q_t>0\) weakly prefers every project in \(C'\) to every project outside \(C'\).
Let \(c_t^{(k)}\) be the project at position \(k\) after arbitrarily ordering projects within each indifference class, and define \(\bar C(q,C')=\bigcup_{t:q_t>0}\{c\in C:c\succsim_t c_t^{(|C'|)}\}\). This set is independent of those arbitrary orders; the empty union is empty.
An integral outcome \(W\subseteq C\) satisfies continuous Comparative PSC (CPSC) if \(w(W)\le B\) and, for every coalition \(q\), every nonempty set \(C'\) it solidly supports, and every \(C''\subseteq C'\) with \(w(C'')\le q(T)B\), one has \(w(\bar C(q,C')\cap W)\ge w(C'')\).

Is the task of outputting a continuous CPSC outcome, or correctly reporting nonexistence, solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite weighted societies, computing a CPSC outcome is weakly \(\mathrm{NP}\)-hard even with one voter (Aziz and Lee, 2021). Such outcomes can fail to exist even with one voter whose preferences are strict.

Result

The task is \(\mathrm{NP}\)-hard, even when \(\tau=1\), the sole type ties all projects, and a continuous CPSC outcome is guaranteed to exist. Consequently, a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).

1. Characterization for one fully indifferent type

Let \(T=\{t\}\), with \(\mu_t=1\), and suppose \(t\) is indifferent among all projects. Define

\(\displaystyle M=\max\{w(S):S\subseteq C,\ w(S)\le B\}.\)

This maximum exists because there are finitely many subsets and the empty subset is feasible.

Lemma. An outcome \(W\subseteq C\) satisfies continuous CPSC exactly when \(w(W)\le B\) and \(w(W)=M\).

Proof. A coalition is specified by a real number \(q_t\in[0,1]\). Every such coalition solidly supports every nonempty \(C'\subseteq C\): when \(q_t>0\), all required weak-preference comparisons hold by indifference; when \(q_t=0\), the condition is vacuous.

For \(q_t>0\), every project is weakly preferred to the project at position \(|C'|\). Hence

\(\bar C(q,C')=C.\)

First suppose \(W\) satisfies continuous CPSC. Take \(q_t=1\) and \(C'=C\), which is nonempty by assumption. For every subset \(S\subseteq C\) with \(w(S)\le B\), choosing \(C''=S\) gives

\(w(W)=w(\bar C(q,C')\cap W)\ge w(S).\)

Thus \(w(W)\ge M\). Budget feasibility gives \(w(W)\le M\), so equality holds.

Conversely, suppose \(w(W)\le B\) and \(w(W)=M\). Consider any coalition \(q\), any nonempty supported set \(C'\), and any \(C''\subseteq C'\) satisfying \(w(C'')\le q_tB\).

If \(q_t>0\), then \(q_t\le1\), so \(w(C'')\le B\). Since \(C''\subseteq C\), the definition of \(M\) gives

\(w(\bar C(q,C')\cap W)=w(W)=M\ge w(C'').\)

If \(q_t=0\), affordability requires \(w(C'')\le0\). Positive project costs force \(C''=\varnothing\). Also \(\bar C(q,C')=\varnothing\), so the required inequality is \(0\ge0\).

This covers every real coalition and proves the lemma. In particular, any subset attaining \(M\) is a continuous CPSC outcome. \(\square\)

2. Reduction from SUBSET SUM

We use the standard \(\mathrm{NP}\)-hard SUBSET SUM problem: given positive integers \(a_1,\ldots,a_n\) and a positive target \(K\), encoded in binary, decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=K\). See [Koiliaris and Xu, *Subset Sum Made Simple*](https://arxiv.org/abs/1807.08248).

Construct the following instance:

• \(C=\{c_1,\ldots,c_n\}\), with \(w(c_i)=a_i\);
• \(B=K\);
• one preference type \(t\), with mass \(\mu_t=1\), indifferent among all projects.

All costs and masses are positive binary-rational numbers, the masses sum to one, and the budget is positive. The construction has polynomial encoding length and takes polynomial time.

Suppose an algorithm outputs a continuous CPSC outcome or correctly reports nonexistence. By the lemma, the constructed instance always has an outcome, so the algorithm must return some \(W\) satisfying

\(\displaystyle w(W)=\max\left\{\sum_{i\in I}a_i:I\subseteq\{1,\ldots,n\},\ \sum_{i\in I}a_i\le K\right\}.\)

Therefore:

• If the SUBSET SUM instance is a yes-instance, a feasible subset has cost \(K\), so every returned CPSC outcome has cost \(K\).
• If the returned outcome has cost \(K\), its project indices themselves constitute a SUBSET SUM witness.

Thus we decide SUBSET SUM by constructing one instance, calling the proposed algorithm once, and testing whether \(w(W)=K\). Exact addition and comparison of these binary integers take polynomial time.

This proves \(\mathrm{NP}\)-hardness of the requested output task, including under the promise that an outcome exists. The reduction directly checks the continuous coalition quantifier; it does not require transferring the finite-society hardness result.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the requested complexity question. It establishes \(\mathrm{NP}\)-hardness of the output task, even with one fully indifferent type and guaranteed existence. No mathematical gaps or false steps were found.

1. Characterization of continuous CPSC

• The maximum is well-defined. There are finitely many subsets of \(C\), and the empty subset has cost zero, so the feasible family defining \(M\) is nonempty and its maximum is attained.

• Solid support is checked correctly. With one fully indifferent type, every coalition with \(q_t>0\) solidly supports every nonempty \(C'\subseteq C\). For \(q_t=0\), the support condition is vacuous.

• The comparison set is computed correctly. Since \(1\le |C'|\le m\), the reference project at position \(|C'|\) exists. Full indifference implies that every project is weakly preferred to it. Thus \(\bar C(q,C')=C\) whenever \(q_t>0\), independently of the arbitrary ordering within the tie.

• Necessity is valid. The choices \(q_t=1\) and \(C'=C\) are permitted. Every budget-feasible subset \(S\subseteq C\) can then serve as \(C''\), giving \(w(W)\ge w(S)\). Therefore \(w(W)\ge M\). Budget feasibility makes \(W\) itself a candidate in the definition of \(M\), giving \(w(W)\le M\).

• Sufficiency covers every real coalition. For any \(q_t>0\), affordability implies

\[ w(C'')\le q_tB\le B. \]
Hence \(w(C'')\le M=w(W)\), which is exactly the required inequality because the comparison set is \(C\). The reasoning uses no discretization of \(q_t\).

• The zero coalition is handled correctly. When \(q_t=0\), positivity of costs forces every affordable \(C''\) to be empty. The comparison set is also empty, so both sides of the required inequality are zero.

The lemma therefore proves the stated equivalence and guarantees existence on this restricted family. It also covers instances where every project exceeds the budget: then \(M=0\), attained by the empty outcome.

2. Reduction from SUBSET SUM

• The source problem is appropriate. The prover states the positive-integer, binary-encoded decision version of SUBSET SUM. Its cited source identifies the positive-integer subset-sum problem and its \(\mathrm{NP}\)-hardness. [Koiliaris and Xu, *Subset Sum Made Simple*](https://arxiv.org/abs/1807.08248)

• The constructed instance satisfies the task’s restrictions. Positive integers are positive binary rationals; \(B=K>0\); the unique mass is one; and the fully indifferent preference is a valid weak order. Using the standard nonempty-list source instances gives \(m=n\ge1\) and \(\tau=1\).

• The construction is polynomial. It copies the binary integers and writes one preference type. Both its running time and total encoding length are polynomial in the source input length.

• The algorithm must return an outcome. The lemma establishes existence for every constructed instance, so a correct algorithm cannot report nonexistence.

• Every valid returned outcome reveals the source answer. The lemma forces its cost to equal the maximum feasible subset sum. If an exact sum of \(K\) exists, that maximum is \(K\), since the budget prohibits larger values. Conversely, an outcome of cost \(K\) directly identifies a subset summing to \(K\). These implications hold for every permissible output, regardless of how ties among optimal subsets are resolved.

• Postprocessing is polynomial. Summing at most \(n\) binary integers increases their maximum bit length by at most a logarithmic term in \(n\). Exact comparison with \(K\) therefore takes polynomial time.

This is a valid polynomial-time reduction using one call to the requested output algorithm. It establishes hardness of producing an outcome, including under the existence promise; it does not assert hardness of merely deciding existence.

3. Verdict and repair feedback

The continuous-coalition quantifier, budget feasibility, empty subsets, and positivity assumptions are all handled correctly. The proof independently establishes the claimed hardness without relying on a transfer from finite societies.

No repair or additional clarification is needed. The argument establishes \(\mathrm{NP}\)-hardness, without claiming strong \(\mathrm{NP}\)-hardness or membership in a complexity class.

⟨structured verdict parsed — rendered above⟩