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.
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet k ∈N>0. There is no algorithm running in polynomial-time that computes, given a shortlisting instance I and profile P , the outcome of the k-equal representation shortlisting rule, unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\).
Given an indexed project set \(P=\{p_1,\ldots,p_m\}\), binary rational budget \(b>0\) and costs \(0<c(p)\le b\), binary integer \(k>0\), and binary rational \(\theta\in(0,1)\), consider the following shortlisting problem.
A society is given by its support \(\mathcal S\): the list of the \(\tau\) proposal-set types \(A\subseteq P\) with positive binary rational masses \(\mu_A\), where \(\sum_{A\in\mathcal S}\mu_A=1\). Here \(\tau\) is the support size, not the number of possible types; empty proposal sets are allowed.
A shortlist is an indivisible subset \(Q\subseteq\bigcup_{A\in\mathcal S}A\), feasible when \(c(Q)=\sum_{p\in Q}c(p)\le kb\). Its score is \(\Phi_{\mu,\theta}(Q)=\sum_{A\in\mathcal S}\mu_A\sum_{\ell=0}^{|A\cap Q|-1}\theta^\ell\), with an empty inner sum equal to zero.
The output \(Q^\star\) maximizes this score; between distinct tied sets, prefer the set containing the lowest-index project in their symmetric difference. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\), and \(k\).
Is computing \(Q^\star\) polynomial-time solvable, or is it \(\mathrm{NP}\)-hard?
For finite agent lists, equal-representation shortlisting with geometric marginal weights \(1,n^{-1},n^{-2},\ldots\) is computationally hard for every fixed positive budget multiplier unless \(\mathrm P=\mathrm{NP}\). [Rey, Endriss, and de Haan](https://arxiv.org/pdf/2010.10309v2)
Geometric Thiele committee optimization also has verified approximation algorithms and matching inapproximability bounds in the discrete setting. [Dudycz et al.](https://www.ijcai.org/proceedings/2020/0039.pdf) No result explicitly addressing this support-encoded mass formulation was located.
Computing \(Q^\star\) is \(\mathrm{NP}\)-hard, even under all of the following restrictions:
The associated score-threshold decision problem is \(\mathrm{NP}\)-complete. The deterministic tie rule does not affect the hardness.
We use the standard \(\mathrm{NP}\)-complete Independent Set problem: given a finite simple undirected graph \(G\) with \(n\) vertices and an integer \(t\), where \(1\le t\le n\), determine whether \(G\) has an independent set of size at least \(t\).
Fix a positive integer \(K\). Add \(K\) isolated vertices to \(G\), obtaining a graph \(H=(V,E)\). Write \(m=n+K\) and \(r=t+K\). Then
\(\displaystyle G\text{ has an independent set of size at least }t \quad\Longleftrightarrow\quad H\text{ has an independent set of size }r.\)
Indeed, an independent set in \(G\) can be enlarged using the isolated vertices. Conversely, deleting the added vertices from an independent set of size \(r\) leaves at least \(t\) vertices in \(G\).
Create one project \(p_v\) for each vertex \(v\in V\), with arbitrary distinct indices. Set
\(\displaystyle c(p_v)=1,\qquad k=K,\qquad b=\frac rK,\qquad \theta=\frac12.\)
Because \(r=t+K>K\), every project satisfies \(0<c(p_v)\le b\). The shortlist budget is \(kb=r\), so feasibility is exactly the condition \(|Q|\le r\).
Let \(d(v)\) denote the degree of \(v\) in \(H\), and define
\(\displaystyle D=1+\max_{v\in V}d(v),\qquad W=mD-|E|.\)
The support contains:
All these types are distinct. Every singleton numerator is positive. By the degree-sum identity,
\(\displaystyle |E|+\sum_{v\in V}(D-d(v)) =|E|+mD-2|E|=W.\)
Thus \(W>0\), every mass is positive, and the masses sum to one. Every project belongs to a supported singleton, so the allowed project union is precisely \(P\).
Identify a shortlist with its vertex set \(S\subseteq V\). Let \(e_H(S)\) be the number of edges with both endpoints in \(S\).
For an edge \(\{u,v\}\), put \(x_u=\mathbf 1[u\in S]\) and \(x_v=\mathbf 1[v\in S]\). Its unweighted geometric satisfaction is
\(\displaystyle x_u+x_v-(1-\theta)x_ux_v.\)
This identity follows by checking the three possible intersection sizes: zero gives satisfaction zero, one gives satisfaction one, and two gives satisfaction \(1+\theta\).
Summing the edge and singleton contributions gives
\(\displaystyle W\Phi_{\mu,\theta}(S) =\sum_{v\in S}d(v)-(1-\theta)e_H(S) +\sum_{v\in S}(D-d(v)) =D|S|-(1-\theta)e_H(S). \)
For our fixed parameter, therefore,
\(\displaystyle \Phi_{\mu,1/2}(S)=\frac{D|S|-\tfrac12e_H(S)}W.\)
Set the score threshold to \(T=Dr/W\). For every feasible shortlist \(S\),
\(\displaystyle T-\Phi_{\mu,1/2}(S) =\frac{D(r-|S|)+\tfrac12e_H(S)}W. \)
Both numerator terms are nonnegative. Consequently,
\(\displaystyle \Phi_{\mu,1/2}(S)\ge T \quad\Longleftrightarrow\quad |S|=r\text{ and }e_H(S)=0. \)
The right-hand condition says exactly that \(S\) is an independent set of size \(r\). Hence
\(\displaystyle G\text{ is a yes-instance} \quad\Longleftrightarrow\quad \max_{Q\text{ feasible}}\Phi_{\mu,1/2}(Q)\ge T. \)
An algorithm computing \(Q^\star\) would decide this by evaluating its score and comparing with \(T\). Every score maximizer has the same score, so the prescribed tie rule cannot change the answer.
The constructed instance has
\(\displaystyle m=n+K,\qquad \tau=m+|E|.\)
Moreover, \(D\le m\) and \(W\le m^2\). For fixed \(K\), every numerical field has \(O(\log(m+1))\) bits. Even encoding every proposal set by its full incidence vector gives total length
\(\displaystyle L=O\!\left(m\tau+(m+\tau)\log(m+1)\right).\)
The construction takes polynomial time in these quantities. It explicitly writes the supported types and their masses; no expansion into a potentially enormous agent list is used. This proves the asserted hardness for every fixed \(K\).
The score identity also works for every other fixed rational \(\theta\in(0,1)\): its strictly positive edge penalty \(1-\theta\) gives the same threshold equivalence.
Binary rational encoding does not prevent polynomial-time verification of a proposed shortlist.
Write \(\theta=a/d\) and \(\mu_A=u_A/v_A\), with positive integer denominators. Define
\(\displaystyle R=\prod_{A\in\mathcal S}v_A,\qquad \Delta=Rd^m.\)
Every score multiplied by \(\Delta\) is an integer, since
\(\displaystyle \Delta\Phi_{\mu,\theta}(Q) =\sum_{A\in\mathcal S} u_A\frac{R}{v_A} \sum_{\ell=0}^{|A\cap Q|-1}a^\ell d^{m-\ell}. \)
All integers in this calculation have \(O((m+1)(L+1))\) bits. For example, the denominator product has at most \(L\) bits, and raising \(d\) to the power \(m\) uses at most \(mL\) bits. Feasibility can likewise be checked by clearing the denominators of the costs and \(b\); multiplication by binary \(k\) adds only its encoded bit length.
After precomputing the geometric sums, a conservative bound for evaluating feasibility and score, using schoolbook integer arithmetic, is
\(\displaystyle O\!\left((m\tau+m+\tau+1)(m+1)^2(L+1)^2\right) \)
bit operations. Comparing with a supplied rational threshold remains polynomial in the combined input length. A shortlist is thus a polynomial-size certificate, proving membership of the threshold problem in \(\mathrm{NP}\). Together with the reduction, it is \(\mathrm{NP}\)-complete.
Enumerating all subsets, evaluating feasible ones, and comparing tied incidence vectors computes the exact prescribed output in
\(\displaystyle O\!\left(2^m(m\tau+m+\tau+1)(m+1)^2(L+1)^2\right) \)
bit operations. The dependence on \(k\) is through its binary length already included in \(L\), rather than its numerical value.
For completeness, the function problem belongs to \(\mathrm{FP}^{\mathrm{NP}}\). Since \(0\le\Phi_{\mu,\theta}(Q)\le m\), binary search for the optimal scaled integer score uses \(O((m+1)(L+1))\) threshold queries. Once that score is known, process projects in index order: include a project whenever an optimal feasible completion exists with that inclusion and the previously fixed choices. Each such query is in \(\mathrm{NP}\), and these \(m\) queries implement exactly the specified tie rule. In particular, if \(\mathrm P=\mathrm{NP}\), computing \(Q^\star\) is polynomial-time solvable.
[Rey, Endriss, and de Haan, Proposition 1](https://arxiv.org/pdf/2010.10309v2) states hardness for the finite-agent equal-representation rule with geometric weights depending on the agent count. The reduction above directly establishes hardness for the support-encoded rational-mass formulation, including fixed \(\theta\) and fixed \(k\), without requiring a transfer of that theorem.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed hardness. The reduction is correct, respects all input restrictions, and has polynomial encoding size. The exact-arithmetic and function-complexity claims also stand. I found no major or minor mathematical issues requiring repair.
The stated source problem is the standard NP-complete Independent Set problem on finite simple undirected graphs, restricted to \(1\le t\le n\). This restriction does not remove its hard instances.
For each prescribed positive integer constant \(K\), adding exactly \(K\) isolated vertices gives \(m=n+K\) and \(r=t+K\), with \(r\le m\).
The claimed equivalence is correct:
The padding is polynomial in the source input size because \(K\) is fixed. The prover correctly restricts its construction-time claim accordingly.
Setting \(c(p_v)=1\), \(k=K\), and \(b=r/K\) satisfies the individual-cost restriction: since \(t\ge1\), \(r>K\), so \(b>1\). The total shortlist budget is exactly \(kb=r\). Consequently, feasibility is precisely \(|S|\le r\).
The support construction is valid:
Thus the construction meets the mass normalization, positivity, support-size, and project-domain requirements.
The edge satisfaction formula is correct for each possible intersection size:
Summing \(x_u+x_v\) over edges counts each selected vertex exactly \(d(v)\) times. Summing \(x_ux_v\) counts exactly \(e_H(S)\). The singleton contribution then cancels the degree term, yielding the stated identity
\(W\Phi_{\mu,\theta}(S)=D|S|-(1-\theta)e_H(S)\).
Specializing to \(\theta=1/2\) gives exactly the formula used in the reduction. No approximation is involved.
For every feasible \(S\), the displayed threshold difference is correct:
\(T-\Phi_{\mu,1/2}(S)=[D(r-|S|)+e_H(S)/2]/W\).
Here \(W>0\), \(D>0\), \(r-|S|\ge0\), and \(e_H(S)\ge0\). Therefore the score reaches or exceeds \(T\) exactly when both numerator terms vanish, meaning \(|S|=r\) and \(e_H(S)=0\).
This proves both directions of the reduction. In particular, no assumption that an optimum exhausts the budget is needed.
An algorithm returning the prescribed \(Q^\star\) would decide the source instance by evaluating its score against \(T\). The tie rule cannot affect this comparison because all maximizers share the optimal score.
The extension to any other fixed rational \(\theta\in(0,1)\) is also justified by the same identity: its edge penalty \(1-\theta\) is strictly positive.
The counts \(m=n+K\) and \(\tau=m+|E|\) are exact. Because \(H\) is simple, \(D\le m\); also \(0<W\le mD\le m^2\).
For fixed \(K\), all constructed numerical fields, including the decision threshold \(T=Dr/W\), have \(O(\log(m+1))\) bits. The stated full-incidence-vector length bound is valid and polynomial in the source size.
The reduction explicitly encodes supported types and rational masses. It requires no expansion into individual agents.
The scaling argument is correct. With \(R=\prod_A v_A\) and \(\Delta=Rd^m\), each term in the displayed scaled-score formula is an integer. Every occurring exponent satisfies \(0\le\ell\le m-1\), so \(m-\ell\) is nonnegative.
The claimed integer bit-length bound \(O((m+1)(L+1))\) accommodates denominator products, powers, numerators, and accumulated sums. Clearing cost and budget denominators likewise permits exact polynomial-time feasibility checks; the contribution of \(k\) is through its binary length.
The evaluation bound is conservative and sufficient under schoolbook integer arithmetic. Comparing against an additional rational threshold is polynomial in the combined input length. Hence the threshold problem belongs to NP and, together with the reduction, is NP-complete.
The exhaustive-search bound correctly accounts for \(2^m\) candidates and polynomial evaluation and tie comparison. Empty proposal sets contribute zero and cause no exception.
The \(\mathrm{FP}^{\mathrm{NP}}\) claim is justified. Scores are nonnegative and at most \(m\), and scaled scores are integers. Thus binary search over the scaled range requires polynomially many threshold queries.
After finding the optimal score, the proposed completion queries are in NP. Processing projects in increasing index order and preferring inclusion whenever an optimal completion exists implements the stated symmetric-difference tie rule. Completion queries must retain the original allowed-project restriction, as their wording indicates.
The literature description agrees with [Definition 3 and Proposition 1 of the cited paper](https://arxiv.org/pdf/2010.10309v2): the finite-agent rule uses weights depending on agent count, and Proposition 1 states hardness for each positive integer multiplier. The submitted reduction independently establishes the support-encoded result.
Required prover feedback: None. The target and the additional complexity claims are established as written.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.