Answer: \(\mathsf{NP}\)-hard
Proposition 4.11 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateRobustPopularMatching can be solved in polynomial time for input instances (I𝐴, I𝐵) where I𝐵 evolves from I𝐴 by reducing availability and I𝐴 is complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite worker types \(P\) and firm types \(Q\) with rational masses \(\alpha_p\) and \(\beta_q\), strict rankings of partner types with ties among individuals of the same type, a complete scenario \(I_A\) with \(E_A=P\times Q\), and a restricted scenario \(I_B\) with \(E_B\subseteq P\times Q\) and unchanged rankings on common types, does there exist a deterministic measurable measure-preserving partial matching \(M\) of the atomless type intervals, supported on \(E_B\), such that for every feasible mass matching \(N\) in each scenario \(s\in\{A,B\}\), the total worker-and-firm mass preferring its assignment in \(M\) to its assignment in \(N\), \(\Delta_s(M,N)\), satisfies \(\Delta_s(M,N)\ge 0\)?
Definitions. Let \(E\subseteq\Theta_W\times\Theta_F\) be a compatibility graph. Each type class is an atomless set of agents of the stated rational mass; agents of a type share a strict ranking of adjacent types and are indifferent among agents of the same type. Every acceptable partner is preferred to being unmatched.
A feasible matching is a measurable partial measure-preserving bijection between workers and firms whose matched type pairs lie in \(E\); thus every individual receives one individual partner or is unmatched. For profiles \(I_A,I_B\), define \(\operatorname{vote}_I(a;M,N)\in\{-1,0,1\}\) by \(a\)'s preference between its partners in \(M\) and \(N\), and let \(\Delta_I(M,N)=\int\operatorname{vote}_I(a;M,N)\,d\lambda(a)\).
The input consists of \(\Theta_W,\Theta_F,E\), rational masses \(\mu^W,\mu^F\), and \(I_A,I_B\), where \(I_B\) is obtained from \(I_A\) by downshifting one adjacent type for each of at most four positive-mass types, preserving all other comparisons.
Target. Is deciding whether there exists a feasible measurable matching \(M\) with \(\Delta_I(M,N)\ge 0\) for every feasible \(N\) and each \(I\in\{I_A,I_B\}\) solvable in polynomial time, or is it NP-hard?
Nearest known results. The finite-agent version is NP-complete even when the two profiles differ only by a downshift performed by four agents.
The atomless rational-mass problem is \(\mathsf{NP}\)-hard, even when every type has mass \(1\) and exactly four types perform one downshift. Consequently, a polynomial-time algorithm would imply \(\mathsf{P}=\mathsf{NP}\).
The proof requires care because atomlessness permits a type to split among several partner types. The key observation is that any such fractional matching decomposes into finite matching “cohorts,” and an unpopular cohort can be challenged independently on a positive-measure subset.
Use the following known restricted version of finite RobustPopularMatching:
This problem is \(\mathsf{NP}\)-complete by [Bullinger, Gangam, and Shahkar, Theorem 4.9](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p225.pdf).
For every \(w\in W\), create one worker type \(\theta_w\) of mass \(1\). For every \(f\in F\), create one firm type \(\theta_f\) of mass \(1\). Realize every type class as a copy of the Lebesgue interval \([0,1)\).
Put \((\theta_w,\theta_f)\) in the type compatibility graph exactly when \(wf\in E\). Type \(\theta_v\) ranks adjacent partner types in exactly the order in which finite agent \(v\) ranks the corresponding finite agents.
Thus the four finite agents whose preferences change become exactly four positive-mass types whose preferences change. Each original downshift remains a downshift of the corresponding adjacent type.
The construction has polynomial size and uses only the rational mass \(1\).
For a measurable matching \(M\), define its type-pair masses by
\[ x_{wf}=\lambda\bigl(\{a\in\theta_w:M(a)\in\theta_f\}\bigr). \]
Measure preservation gives
\[ x_{wf}\geq 0,\qquad \sum_{f:wf\in E}x_{wf}\leq 1,\qquad \sum_{w:wf\in E}x_{wf}\leq 1. \]
Hence \(x\) lies in the fractional bipartite matching polytope
\[ \mathcal P(G)= \left\{ x\in\mathbb R_{\geq 0}^{E}: \sum_{e\ni v}x_e\leq 1 \text{ for every }v\in W\cup F \right\}. \]
The incidence matrix of a bipartite graph is totally unimodular. Since the right-hand side is integral, every vertex of \(\mathcal P(G)\) is the incidence vector of a finite matching. Therefore every \(x\in\mathcal P(G)\) has a decomposition
\[ x=\sum_{k=1}^{r}\lambda_k\chi^{P_k}, \qquad \lambda_k>0,\qquad \sum_{k=1}^{r}\lambda_k=1, \]
where each \(P_k\) is a finite matching of \(G\).
Let \(P\) be a finite matching popular under a profile \(I\). Construct the block matching \(M_P\) by matching the whole type \(\theta_w\) bijectively to the whole type \(\theta_f\) whenever \(wf\in P\), and leaving the whole type unmatched whenever the corresponding finite vertex is unmatched.
Consider any measurable challenger \(N\), and let \(y_{wf}\) be its type-pair masses. Then \(y\in\mathcal P(G)\), so write
\[ y=\sum_{j=1}^{s}\alpha_j\chi^{Q_j} \]
for finite matchings \(Q_j\), where \(\alpha_j\geq 0\) and \(\sum_j\alpha_j=1\).
Because every agent of type \(\theta_v\) has the same partner type under \(M_P\), the vote of such an agent against \(N\) depends only on its partner type under \(N\). Consequently the popularity margin is linear in \(y\), including the unmatched mass. Explicitly, the unmatched mass of type \(v\) is
\[ 1-\sum_{e\ni v}y_e = \sum_j\alpha_j\mathbf 1_{\{v\text{ is unmatched in }Q_j\}}. \]
It follows that
\[ \Delta_I(M_P,N) = \sum_j\alpha_j\Delta_I(P,Q_j). \]
Since \(P\) is popular, every term \(\Delta_I(P,Q_j)\) is nonnegative. Hence \(\Delta_I(M_P,N)\geq 0\). As \(N\) was arbitrary, \(M_P\) is popular in the atomless instance.
Applying this argument to both profiles shows that every finite robust popular matching induces an atomless robust popular matching.
Let \(M\) be any measurable matching popular under profile \(I\), and decompose its type-pair matrix as
\[ x=\sum_{k=1}^{r}\lambda_k\chi^{P_k}. \]
We claim that every \(P_k\) with \(\lambda_k>0\) is a finite popular matching under \(I\).
For each edge \(wf\), the \(M\)-matched subset of \(\theta_w\) assigned to \(\theta_f\) has mass
\[ x_{wf}=\sum_{k:wf\in P_k}\lambda_k. \]
By atomlessness, partition this subset into measurable pieces of mass \(\lambda_k\), one for each \(k\) satisfying \(wf\in P_k\), and partition its image under \(M\) correspondingly. Likewise, the \(M\)-unmatched subset of type \(v\) has mass
\[ 1-\sum_{e\ni v}x_e = \sum_{k:v\text{ unmatched in }P_k}\lambda_k, \]
so it can be partitioned into pieces of mass \(\lambda_k\).
This produces, for every \(k\), a cohort \(C_v^k\subseteq\theta_v\) of mass \(\lambda_k\) such that:
Suppose \(P_k\) were not popular. Then there would be a finite matching \(Q\) satisfying
\[ \Delta_I(P_k,Q)<0. \]
Define a measurable challenger \(N\) as follows:
Such measure-preserving bijections exist because these are atomless Lebesgue sets of equal mass. Only agents in the \(k\)-th cohort change partners. Their old and new partner types are exactly those in \(P_k\) and \(Q\), respectively. Therefore
\[ \Delta_I(M,N)=\lambda_k\Delta_I(P_k,Q)<0, \]
contradicting the popularity of \(M\). Thus every \(P_k\) is popular.
If \(M\) is popular under both \(I_A\) and \(I_B\), the same argument applies separately to each profile. Hence every \(P_k\) occurring with positive coefficient is popular under both profiles.
The constructed atomless instance has a robust popular measurable matching if and only if the source finite instance has a robust popular matching:
Thus the construction is a polynomial-time many-one reduction from the restricted finite RobustPopularMatching problem.
The target problem is \(\mathsf{NP}\)-hard even under the additional restrictions that all type masses equal \(1\) and only four types change their preferences. Atomless divisibility does not remove the finite hardness: every fractional candidate contains positive-measure finite matching cohorts, and any unpopular cohort can be defeated independently.
This argument proves hardness but does not establish that the general rational-mass problem belongs to \(\mathsf{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes \(\mathsf{NP}\)-hardness through a polynomial-time many-one reduction from the cited finite robust popular matching problem. The fractional decomposition and cohort argument validly prove equivalence between finite robust popularity and atomless robust popularity for the constructed unit-mass instances.
No substantive gaps or false statements were found.
The cited [Theorem 4.9](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p225.pdf) does state that RobustPopularMatching is \(\mathsf{NP}\)-complete when the second profile differs by downshifts performed by four agents. The paper’s definition of a downshift preserves all comparisons not involving the shifted alternative, matching the restriction required by the target.
Thus the source problem supplies the required \(\mathsf{NP}\)-hard family.
Replacing each finite worker or firm by a unit-mass type preserves:
Because every type has mass \(1\), finite vote counts correspond exactly to continuum vote masses in block matchings.
For any measurable matching, the type-pair masses satisfy nonnegativity and the degree constraints of the bipartite fractional matching polytope. The column constraints follow from measure preservation.
The invocation of total unimodularity is correct: the vertex-edge incidence matrix of a bipartite graph is totally unimodular, and the integral right-hand side implies that all vertices of the polytope are integral. Integral feasible points are precisely incidence vectors of finite matchings, including partial matchings.
Consequently every type-pair matrix has a finite convex decomposition into finite matching incidence vectors.
When \(M_P\) is a block matching, every member of a type receives the same partner type. Its vote against a challenger therefore depends linearly on the challenger’s partner-type masses.
The prover also accounts correctly for unmatched mass. Hence the identity
\[ \Delta_I(M_P,N)=\sum_j\alpha_j\Delta_I(P,Q_j) \]
is valid. Popularity of \(P\) makes every summand nonnegative, proving popularity of \(M_P\). Applying the same calculation under both profiles proves the robust version.
The cohort construction is consistent:
If \(P_k\) loses to a finite matching \(Q\), implementing \(Q\) solely inside cohort \(k\) produces a feasible measurable challenger. Agents outside the cohort retain their partners and cast zero votes, while each finite vote inside the cohort is scaled by \(\lambda_k\). Therefore
\[ \Delta_I(M,N)=\lambda_k\Delta_I(P_k,Q)<0, \]
contradicting popularity.
The decomposition and cohorts depend only on \(M\), not on the profile. Thus applying the argument to \(I_A\) and \(I_B\) shows that every positive-weight \(P_k\) is popular under both profiles.
Both implications are established:
The construction is polynomial and remains within the target’s restricted instances. Therefore the claimed \(\mathsf{NP}\)-hardness follows.
The prover appropriately does not claim membership in \(\mathsf{NP}\), which is unnecessary for answering the stated polynomial-time-versus-hardness question.
⟨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.