Answer: \(\mathrm{P}\) (polynomial-time solvable)
Theorem 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-complete to decide whether a given 3dpmvi instance with a matching 𝑀 admits a matching that is more popular than 𝑀. This holds even if the preferences are derived from a 1-master list.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type sets \(\mathcal A,\mathcal B,\mathcal C\), rational masses \(\mu^A,\mu^B,\mu^C\), cyclic acceptability and preference rankings over partner types, and a finite cell-decomposed reference mass matching \(M\), does there exist an acceptable fractional mass matching \(M'\) satisfying the type-mass capacity constraints and \(\Delta(M',M)>0\), where \(\Delta\) is the total mass-weighted head-to-head vote margin?
A finite mass matching consists of finitely many cells in each type, each with rational mass and inheriting its type's cyclic strict ranking; a triple of cells is feasible exactly when its three types mutually accept their cyclic partners. A reference matching \(M\) assigns each cell wholly to one feasible triple or leaves it unmatched; unmatched is ranked below every acceptable partner.
A fractional mass matching \(M'\) assigns nonnegative mass to feasible triples of cells, with total incident mass at most each cell's mass. Each assigned mass unit votes by comparing its partner in \(M'\) with that cell's partner in \(M\); unassigned mass votes as unmatched. Let \(\Delta(M',M)\) be the sum of these votes over all three classes, weighted by mass.
Target. Is deciding whether there exists an acceptable fractional mass matching \(M'\) with \(\Delta(M',M)>0\) solvable in polynomial time, or is it NP-hard?
For finite individual agents with incomplete cyclic lists, deciding whether a given matching has a more popular matching is NP-complete, even when preferences are derived from a \(1\)-master list. No result was verified for the mass-distribution version above.
The decision problem is polynomial-time solvable. More precisely, it reduces to a rational linear program of polynomial size. Thus it lies in \( \mathrm{P} \), and is not \( \mathrm{NP} \)-hard unless \( \mathrm{P}=\mathrm{NP} \).
Let \(V\) be the set of all cells, let \(\mu_v\) be the rational mass of cell \(v\), and let \(E\) be the set of feasible triples.
For \(e\in E\) containing \(v\), write \(p_v(e)\) for the cyclic partner assigned to \(v\) by \(e\). Let \(r_v\) be the partner of \(v\) in the reference matching \(M\), with \(r_v=\bot\) when \(v\) is unmatched in \(M\).
Define the vote of mass from \(v\) assigned to \(e\) by
\(\sigma_{v,e}=1\) if \(p_v(e)\succ_v r_v\),
\(\sigma_{v,e}=0\) if \(p_v(e)=r_v\),
\(\sigma_{v,e}=-1\) if \(r_v\succ_v p_v(e)\).
Here every acceptable partner is preferred to \(\bot\). The vote of an unassigned unit of mass is therefore
\(u_v=0\) if \(r_v=\bot\), and \(u_v=-1\) if \(r_v\neq\bot\).
The assumption that \(M\) assigns every cell wholly is important: every mass unit in a given cell has the same reference partner \(r_v\).
Represent a fractional mass matching by variables \(x_e\geq 0\), where \(x_e\) is the mass assigned to feasible triple \(e\). Its load on \(v\) is
\(\ell_v(x)=\sum_{e\ni v}x_e\),
and feasibility is exactly \(\ell_v(x)\leq\mu_v\) for every \(v\).
The vote contributed by cell \(v\) is
\(\sum_{e\ni v}x_e\sigma_{v,e}+(\mu_v-\ell_v(x))u_v\).
Consequently,
\(\Delta(M_x,M)=\sum_{v\in V}\mu_vu_v+\sum_{e\in E}x_e\sum_{v\in e}(\sigma_{v,e}-u_v)\).
Define
\(B=-\sum_{v\in V}\mu_vu_v=\sum_{v:r_v\neq\bot}\mu_v\)
and
\(q_e=\sum_{v\in e}(\sigma_{v,e}-u_v)\).
Then the exact identity is
\(\Delta(M_x,M)=-B+\sum_{e\in E}q_ex_e\).
The coefficients are particularly simple. For one cell \(v\in e\):
Thus every \(q_e\) is an integer satisfying \(0\leq q_e\leq 6\).
Consider the linear program
Let its optimum be \(Q^\star\).
Every acceptable fractional mass matching gives a feasible vector \(x\) by taking its assigned mass on each triple. Conversely, every feasible vector \(x\) defines an acceptable fractional mass matching, because it uses only feasible triples and respects every cell’s mass constraint.
By the identity above,
there exists \(M'\) with \(\Delta(M',M)>0\) if and only if \(Q^\star>B\).
There is no issue of a nonattained supremum. The feasible region is nonempty because \(x=0\) is feasible, and it is bounded because \(x_e\leq\mu_v\) for every \(v\in e\). Hence the maximum is attained.
Let \(n=|V|\). Since triples contain one cell from each of three fixed classes, there are at most \(n^3\) candidate triples. Their mutual acceptability and the coefficients \(q_e\) can be determined from the input rankings in polynomial time. Thus the linear program has at most \(n^3\) variables, \(n\) mass constraints, and rational encoding length polynomial in the input length.
Linear programming with rational input is solvable exactly in polynomial time in the Turing model; this is the classical rational linear-programming theorem originating with [Khachiyan’s polynomial-time algorithm](https://www.mathnet.ru/eng/dan42319). Its hypotheses hold here: all coefficients are rational, the program is explicitly of polynomial size, and its feasible region is bounded.
Therefore \(Q^\star\) can be compared exactly with the rational number \(B\). The strict inequality \(Q^\star>B\) does not require choosing a numerical tolerance.
For unit-mass individual agents, an ordinary matching requires indivisible decisions. In the present problem, even a unit-mass cell may split its mass among several triples. Hence the variables \(x_e\) are continuous rather than integral.
The finite-agent problem optimizes over integral hypergraph matchings, whereas this problem optimizes over the fractional capacity relaxation. A discrete no-instance need not remain a no-instance after that relaxation, so the cited finite-agent reduction does not establish hardness here.
Under the definitions in the question—particularly that acceptability means using only feasible triples, with no additional stability constraint—the linear program settles the target question completely.
⟨structured verdict parsed — rendered above⟩
The prover correctly reduces the existence question to rational linear programming and establishes polynomial-time solvability. The argument is internally consistent and addresses the continuous fractional problem, rather than incorrectly importing hardness from the integral finite-agent setting.
No major or minor correctness gaps were found.
For a cell \(v\), the prover correctly distinguishes mass assigned to a feasible triple from mass left unassigned.
Thus the definitions of \(\sigma_{v,e}\) and \(u_v\) correctly encode all possible votes.
The load \(\ell_v(x)=\sum_{e\ni v}x_e\) is the total assigned mass of cell \(v\). Hence its unassigned mass is \(\mu_v-\ell_v(x)\), and the displayed contribution
\[ \sum_{e\ni v}x_e\sigma_{v,e}+(\mu_v-\ell_v(x))u_v \]
is correct. Expanding and summing over cells gives
\[ \Delta(M_x,M)=\sum_v\mu_vu_v+\sum_e x_e\sum_{v\in e}(\sigma_{v,e}-u_v). \]
The definitions of \(B\) and \(q_e\) therefore yield the exact identity
\[ \Delta(M_x,M)=-B+\sum_e q_ex_e. \]
The stated coefficient values are correct.
Since each triple has three cells, \(0\leq q_e\leq6\) follows.
A fractional matching determines nonnegative values \(x_e\) satisfying every cell-capacity constraint. Conversely, any such vector assigns equal mass \(x_e\) to the three incidences of triple \(e\), uses only feasible triples, and does not exceed any cell mass. The correspondence claimed by the prover is therefore valid.
Maximizing \(\sum_e q_ex_e\) gives \(Q^\star\). By the exact margin identity,
\[ \Delta(M_x,M)>0 \quad\Longleftrightarrow\quad \sum_e q_ex_e>B. \]
Consequently, an improving fractional matching exists exactly when \(Q^\star>B\). This equivalence is correct.
The feasible region contains \(x=0\). For every triple \(e\) and every \(v\in e\), nonnegativity and the constraint at \(v\) imply \(x_e\leq\mu_v\). Thus all variables are bounded, and the closed feasible polytope is compact. The optimum is attained.
With three fixed classes and \(n\) cells in total, there are at most \(n^3\) candidate triples. Enumerating them and checking mutual acceptability is polynomial in the explicitly represented cell and ranking data. The LP has polynomially many variables and constraints, with incidence coefficients in \(\{0,1\}\), objective coefficients bounded by \(6\), and rational right-hand sides inherited from the input masses.
Rational linear programming is polynomial-time solvable in the Turing model, including exact determination or comparison of the rational optimum. Therefore testing \(Q^\star>B\) does not require an approximate numerical tolerance. The invoked theorem applies to the explicitly represented rational LP.
The finite-agent problem imposes integral matching choices, whereas this problem expressly permits mass splitting. The cited NP-completeness result therefore does not contradict the fractional LP algorithm and does not imply hardness for the present problem.
The proof establishes that the decision problem is in \(\mathrm P\). Its final qualification concerning NP-hardness is valid under the usual polynomial-time many-one notion: membership in \(\mathrm P\) and NP-hardness together would imply \(\mathrm P=\mathrm{NP}\).
⟨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.