Answer: —
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatepop-ha𝑈 𝐿 is NP-complete even if 𝑙 max = 2 = 𝑢 max and Δ𝑃= 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite applicant types \(T\) with rational masses \(\mu_t\ge0\) summing to \(1\), projects \(P\), strict preferences over \(P\cup\{\bot\}\), and rational mass quotas \(0\le\ell_p\le u_p\), decide whether there exists a feasible mass assignment \(x_{tq}\ge0\) and opening variables \(y_p\in\{0,1\}\) satisfying \(\sum_q x_{tq}=\mu_t\) and \(\ell_p y_p\le\sum_t x_{tp}\le u_p y_p\), such that no feasible challenger \((x',y')\) admits a coupling \(z_{t,p,q}\ge0\) with \(\sum_q z_{t,p,q}=x_{t,p}\), \(\sum_p z_{t,p,q}=x'_{t,q}\), and positive vote mass \(\sum_{t,p,q}z_{t,p,q}\sigma_t(q,p)>0\), where \(\sigma_t(q,p)\) is \(1\), \(-1\), or \(0\) according as \(q\succ_t p\), \(p\succ_t q\), or \(p=q\).
Let \(Q=P\cup\{\bot\}\). A feasible mass assignment consists of \(x_{tq}\ge0\) for \(t\in T,q\in Q\) and \(y_p\in\{0,1\}\) for \(p\in P\), with \(\sum_{q\in Q}x_{tq}=\mu_t\) and \(\ell_py_p\le\sum_t x_{tp}\le u_py_p\).
It is popular if no feasible \((x',y')\) has a coupling \(z_{t,p,q}\ge0\) with marginals \(x_{t,p}\) and \(x'_{t,q}\) whose vote mass \(\sum_{t,p,q}z_{t,p,q}\sigma_t(q,p)\) is positive, where \(p,q\in Q\) and \(\sigma_t(q,p)\in\{-1,0,1\}\) records type \(t\)'s strict preference between \(q\) and \(p\).
Is deciding whether a popular feasible mass assignment exists in \(\mathrm{P}\), or is it NP-hard?
For the finite, indivisible-applicant counterpart, deciding whether a popular matching exists is NP-complete even when \(\ell_p=u_p=2\) for every project and every project is acceptable to at most two applicants.
That result concerns indivisible applicants and does not settle the mass-assignment problem above.
For the literal formulation in the question, the existence problem is not resolved here as polynomial-time solvable or NP-hard.
Two substantial conclusions can nevertheless be proved:
Thus the omitted acceptability constraints are mathematically decisive.
Complexity is defined under the standard encoding in which \(T\) and \(P\) are finite, all masses and quotas are rational numbers encoded in binary, and every preference relation is given explicitly.
The literal feasibility definition permits \(x_{tp}>0\) for every \(t\in T\) and \(p\in P\). Ranking \(p\) below \(\bot\) does not prohibit assignment to \(p\).
Fix a feasible assignment \((x,y)\). Its maximum defeat margin equals the optimum of
\[ \max \sum_{t\in T}\sum_{p,q\in Q}z_{t,p,q}\sigma_t(q,p) \]
subject to
\[ \sum_{q\in Q}z_{t,p,q}=x_{tp} \]
for every \(t,p\), and
\[ \ell_qy'_q\leq\sum_{t\in T}\sum_{p\in Q}z_{t,p,q}\leq u_qy'_q \]
for every \(q\in P\), where \(z\geq0\) and \(y'_q\in\{0,1\}\). The challenger is recovered by setting \(x'_{tq}=\sum_pz_{t,p,q}\).
This equivalence follows directly from the two marginal conditions in the definition. The candidate is popular exactly when this optimum is at most \(0\). The diagonal coupling shows that the optimum is always at least \(0\), so popularity is equivalent to the optimum being exactly \(0\).
For every fixed vector \(y'\), this is a rational linear program. The binary choice of the challenger’s open projects is the only nonconvex part.
Suppose that, for some type \(t\), three alternatives \(q_1,q_2,q_3\) satisfy \(q_1\succ_tq_2\succ_tq_3\) and \(x_{tq_i}>0\) for all \(i\). Then \(x\) is not popular.
Let \(\varepsilon=\min_i x_{tq_i}>0\), and use \(x'=x\). Start with the diagonal coupling and replace mass \(\varepsilon\) on the three diagonal pairs by
\[ (q_1,q_3),\qquad(q_2,q_1),\qquad(q_3,q_2), \]
where the first coordinate is the current alternative and the second is the challenger alternative.
All marginals remain unchanged. The first pair contributes \(-\varepsilon\), while the other two contribute \(+\varepsilon\) each. The total vote is therefore \(+\varepsilon\). Hence \(x\) defeats itself under an admissible non-diagonal coupling and cannot be popular. \(\square\)
Consequently, under strict rankings, every popular assignment has at most two positive entries in each row \(x_{t,\cdot}\).
This condition is exact for self-comparison: if a row is supported on at most two strictly ranked alternatives, every coupling of that row with itself has vote \(0\), because the mass transported upward must equal the mass transported downward.
Take three types of unit mass and three projects \(a,b,c\), each with \(\ell_p=u_p=3\). Give the types preferences
\[ a\succ b\succ c\succ\bot,\qquad b\succ c\succ a\succ\bot,\qquad c\succ a\succ b\succ\bot. \]
If a project is open, it must receive all mass. Hence the only feasible assignments are the three unanimous project assignments and the all-\(\bot\) assignment.
The assignment to \(a\) defeats that to \(b\), the assignment to \(b\) defeats that to \(c\), and the assignment to \(c\) defeats that to \(a\), each by \(2\) votes against \(1\). Every project assignment defeats the all-\(\bot\) assignment unanimously. Thus no feasible assignment is popular.
Therefore the existence problem is not an always-\(\mathrm{YES}\) problem.
Under the literal complete-feasibility definition, verifying whether a specified rational feasible assignment is popular is \(\mathrm{coNP}\)-complete. This remains true with strict complete rankings and integral masses and exact integral quotas.
Non-popularity has a certificate consisting of \(y'\) and a coupling \(z\) with positive vote.
If a positive-vote coupling exists for a fixed \(y'\), the corresponding rational linear program has a positive optimal basic feasible solution whose encoding length is polynomially bounded by the input length. Feasibility and positivity can then be checked in polynomial time. Thus non-popularity belongs to \(\mathrm{NP}\), and popularity verification belongs to \(\mathrm{coNP}\).
Reduce from Exact Cover by \(3\)-Sets. Let \(X\) contain \(3m\) elements and let \(\mathcal S=\{S_1,\ldots,S_n\}\), where every \(S_j\) has size \(3\).
Set
\[ s=2m,\qquad H=s(6m-1),\qquad K=12m-1. \]
Create:
The total mass of the element and guard types is exactly
\[ 3ms+s(3m-1)=s(6m-1)=H. \]
The preferences are as follows.
Complete all rankings arbitrarily and strictly inside these blocks.
Let \(x^0\) assign all element and guard mass to \(p_0\), and all filler mass to \(\bot\). This is feasible.
Suppose a challenger moves total current mass \(A\) out of \(p_0\). Because \(p_0\) has exact quota \(H\), exactly \(A\) filler mass must enter \(p_0\).
Let \(c\leq A\) be the element mass moved to incident set projects. This mass wins. The remaining \(A-c\) departing mass loses, and the \(A\) filler mass entering \(p_0\) also loses. Any additional filler mass sent to set projects loses as well. Hence the vote is at most
\[ c-(A-c)-A=2c-2A\leq0. \]
Thus a positive challenger must close \(p_0\).
Let \(k\) set projects be open, let \(c\) be the winning element mass assigned to incident projects, and let \(b\) be the filler mass assigned outside \(\bot\).
All \(H-c\) remaining element-and-guard mass loses. Therefore the vote is
\[ V=2c-H-b. \]
The open set projects require total mass \(Kk\). Since at most \(H\) of this can come from the element and guard types,
\[ b\geq\max\{0,Kk-H\}. \]
If \(\mathcal C\) is the collection of the \(k\) selected sets, only element types in \(\bigcup\mathcal C\) can contribute winning mass, so
\[ c\leq s\left|\bigcup\mathcal C\right|\leq3sk. \]
There are three cases.
\[ V\leq6sk-H<0. \]
\[ V\leq2s(3m-1)-H-m=-3m<0. \]
\[ V\leq6ms-Kk\leq6ms-K(m+1)=1-11m<0. \]
Conversely, suppose \(m\) sets form an exact cover. Assign every element type to its unique selected set project. These types contribute winning mass \(3ms=6m^2\). Use all guard mass and exactly \(m\) filler mass to complete the selected projects’ quotas. This is possible because
\[ m(K-3s)=6m^2-m=s(3m-1)+m. \]
The guard and filler masses lose, giving vote margin
\[ 6m^2-s(3m-1)-m=m>0. \]
Therefore \(x^0\) is non-popular exactly when the Exact Cover instance is positive. This proves \(\mathrm{coNP}\)-hardness of popularity verification. \(\square\)
Suppose the intended feasibility conditions additionally include \(x_{tp}=0\) whenever project \(p\) is unacceptable to type \(t\).
The known discrete reduction creates one unit applicant for every vertex and one project of exact quota \(2\) for every graph edge; that project is acceptable only to the two endpoint applicants. This is the construction in [Cseh, Friedrich, and Peters, Theorem 3](https://arxiv.org/abs/2107.03801).
Create a mass type of mass \(1\) for every applicant. If a project is open, it needs mass \(2\), but its two acceptable types can each contribute at most \(1\). Hence both must contribute their full mass. It follows that every feasible mass assignment is integral, and the open projects form an ordinary matching. Every type is deterministic in both compared assignments, so its coupling is unique and its mass vote equals the corresponding applicant’s discrete vote.
Thus the discrete and mass instances have popular assignments simultaneously. Under explicit acceptability constraints, popular mass-assignment existence is therefore NP-hard.
This proof does not apply to the literal definition because ranking a nonincident project below \(\bot\) does not impose \(x_{tp}=0\).
The exact existence problem in the question remains open in this analysis. The principal established facts are:
The verification result alone does not imply NP-hardness of existence: an instance might admit some other popular assignment even when a specified candidate is not popular. A reduction must control all possible fractional candidates, which is precisely the missing step.
⟨structured verdict parsed — rendered above⟩
The prover correctly labels its output as partial. It establishes several relevant auxiliary results, but it does not resolve the stated existence problem under the literal feasibility definition. Therefore, the target question—polynomial-time solvable versus NP-hard—remains unanswered.
The auxiliary arguments are largely correct. The only technical defect found is an untreated boundary case in the Exact Cover reduction. There is also an imprecise claim about the acceptability constraints being “decisive.”
The formulation is correct.
\(\sum_q x'_{tq}=\sum_{p,q}z_{t,p,q}=\sum_p x_{tp}=\mu_t\).
No missing coupling or feasibility constraint was found.
The lemma is correct under strict rankings.
Removing \(\varepsilon\) from the diagonal pairs and inserting
\((q_1,q_3)\), \((q_2,q_1)\), and \((q_3,q_2)\)
preserves both marginals. With \(q_1\succ_t q_2\succ_t q_3\), the contributions are respectively \(-\varepsilon\), \(+\varepsilon\), and \(+\varepsilon\), giving total \(+\varepsilon\).
Consequently, three positive coordinates in one row indeed contradict popularity.
The statement about self-comparison on support of size at most two is also correct: equality of the two marginals forces the two off-diagonal transport quantities to be equal, so their opposite votes cancel.
The example is correct.
Since every open project has exact quota \(3\), while the total mass is \(3\), at most one project can be open, and opening it forces all mass into it. Hence the only assignment outcomes are the three unanimous project assignments and the all-\(\bot\) assignment.
The stated majority cycle is correct:
All project assignments defeat the all-\(\bot\) assignment unanimously. Thus no popular feasible assignment exists.
The argument is sound.
For a fixed binary vector \(y'\), the challenger problem is a bounded rational linear program. If a positive solution exists, a positive optimal basic feasible solution of polynomial encoding length exists by standard rational linear-programming bit-complexity bounds. The vector \(y'\) and this coupling form a polynomial certificate of non-popularity.
The write-up could have named the standard bit-complexity fact explicitly, but its use here is routine and does not constitute a gap.
Apart from the untreated case \(m=0\), the reduction checks out.
The identities
\(s=2m\),
\(H=s(6m-1)=12m^2-2m\),
and \(K=12m-1\)
are used consistently.
If mass \(A\) leaves \(p_0\), exact quota \(H\) forces exactly \(A\) filler mass to enter \(p_0\). If \(c\) is winning incident element mass, the remaining \(A-c\) departing mass loses, and the incoming filler mass also loses. Therefore
\(V\leq c-(A-c)-A=2c-2A\leq0\).
This accounting is correct.
The vote formula
\(V=2c-H-b\)
is correct: winning element mass contributes \(c\), the other \(H-c\) element-and-guard mass loses, and the \(b\) displaced filler mass loses.
The bounds
\(b\geq\max\{0,Kk-H\}\)
and
\(c\leq s|\bigcup\mathcal C|\leq3sk\)
are valid.
All three numerical cases are correct:
For an exact cover, each selected project receives \(3s=6m\) winning element mass and has deficit \(K-3s=6m-1\). The aggregate deficit is
\(m(K-3s)=6m^2-m=s(3m-1)+m\),
so the guard mass and \(m\) filler mass exactly fill it. The vote margin is
\(6m^2-s(3m-1)-m=m>0\).
Thus, for \(m\geq1\), the equivalence between an exact cover and non-popularity of the specified candidate is established.
The missing \(m=0\) qualification is real: then \(K=-1\), which is not a valid quota. This is a minor boundary-case omission because the reduction only needs an explicitly stated nonempty restriction or separate treatment.
The transfer argument is correct.
The cited construction creates one unit applicant per graph vertex and one exact-quota-\(2\) project per edge, with only the two endpoint applicants finding that project acceptable. This matches Theorem 3’s construction in the [cited paper](https://arxiv.org/abs/2107.03801).
Under hard acceptability constraints, an open edge project must receive its entire mass \(2\) from its two endpoint types. Since each has total mass \(1\), both must contribute exactly \(1\). Thus fractional splitting cannot create additional feasible outcomes, open projects form a matching, and each type’s coupling between two feasible assignments is unique. The discrete and mass popularity comparisons therefore agree.
This proves NP-hardness only for the augmented acceptability-constrained model.
The literal target has no hard acceptability constraints. The prover explicitly says:
“The exact existence problem in the question remains open in this analysis.”
Neither fixed-candidate \(\mathrm{coNP}\)-completeness nor NP-hardness of the augmented model classifies existence in the literal model. As the prover correctly observes, hardness of verifying one candidate does not prevent a different popular candidate from existing.
This is the central blocking issue. Repairing it requires new mathematics—either an algorithm for the literal existence problem or a reduction controlling every possible candidate—not merely an expositional clarification.
The phrase “the omitted acceptability constraints are mathematically decisive” is too strong if read as a statement about the final complexity classification. The output proves only that they are decisive for the applicability of the discrete reduction; it does not prove that the literal and augmented problems have different complexity.
⟨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.