Answer: The ordinary problem is $\mathrm{coNP}$-complete under polynomial many-one reductions, even with unit applicant masses, employer masses in $\{1,2\}$, complete acceptability, and zero budget. The diligent variant is in $\mathrm{P}$ with running time polynomial in $m,\tau,L$. The ordinary problem is in $\mathrm{P}$ exactly if $\mathrm{P}=\mathrm{NP}$, and is $\mathrm{NP}$-hard exactly if $\mathrm{NP}=\mathrm{coNP}$.
Theorem 4.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe optimality certificate decision problem is NP-hard, even if the partial preference ordering is an equivalence class ordering. PROOF. The proof is by reduction from the feedback arc set (FAS) problem [Karp 1972]. Let G = (V, D) be a directed graph with no self-loops or multiple arcs. The feedback arc set problem is to decide whether there exists a set of arcs C of size ≤K such that C contains at least one arc from every directed cycle in G; i.e., such that removing all arcs in C breaks all directed cycles of G. We construct an instance of the optimality certificate (OC) problem from (G, K) as follows.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite employer types \(E\) and applicant types \(A\) with rational masses \(w\) and \(v\), partial orders, admissible type-level strict refinements, a realized refinement profile \(\rho\), batch interview costs \(c_{ea}\), and budget \(B\), does there exist an interview-mass allocation \(q\) of cost \(\sum_{e,a} c_{ea}q_{ea}\le B\) whose revealed comparisons certify that the employer-optimal stable mass matching \(x^\rho\) remains employer-optimal for every compatible refinement? In the diligent variant, every positive edge of \(x^\rho\) must be covered by an interview.
A society is given by its support: nonempty finite sets of employer types \(E\) and applicant types \(A\), each with positive mass \(w_e\) or \(v_a\) encoded as a binary rational. Masses need not sum to one or have equal totals across sides. Let \(\tau=|E|+|A|\) be the support size, not the number of possible preference types, let \(m=\max\{|E|,|A|\}\), and let \(L\) be the total input bit length.
Each type has a fixed acceptable subset of opposite-side types and a strict partial order on that subset. Admissible refinements are all independently chosen strict linear extensions, with every acceptable type preferred to being unmatched and every unacceptable type ranked below it. All members of a type share its refinement; a realized admissible profile \(\rho\) is supplied.
A mass matching is a real matrix \(x\ge0\) with \(\sum_a x_{ea}\le w_e\), \(\sum_e x_{ea}\le v_a\), and \(x_{ea}=0\) unless the pair is mutually acceptable. Unassigned mass is unmatched.
Under a refinement \(\sigma\), a mutually acceptable pair \((e,a)\) blocks precisely when both \(w_e-\sum_{b\succeq_e^\sigma a}x_{eb}>0\) and \(v_a-\sum_{f\succeq_a^\sigma e}x_{fa}>0\); stability means that no pair blocks. A stable matching is employer-optimal if each employer’s assigned distribution first-order stochastically dominates its distribution in every other stable matching, with unmatched mass included. Write \(x^\rho\) for the employer-optimal stable mass matching under \(\rho\).
An interview allocation is a real matrix satisfying \(0\le q_{ea}\le\min\{w_e,v_a\}\). A type may interview several opposite-side types, so there are no aggregate row or column bounds. Interviews with unacceptable types are permitted but reveal comparisons only among acceptable interviewed types.
For each employer \(e\), all comparisons under \(\rho_e\) between acceptable types \(a,b\) with \(q_{ea}>0\) and \(q_{eb}>0\) are revealed; symmetrically, each applicant type learns comparisons between its positively interviewed acceptable employer types. These comparisons are shared throughout the type. A compatible refinement extends the initial partial orders and all revealed comparisons.
Given nonnegative binary-rational costs \(c_{ea}\) and budget \(B\), decide whether some allocation satisfies \(\sum_{e,a}c_{ea}q_{ea}\le B\) and makes \(x^\rho\) employer-optimal under every compatible refinement. In the diligent variant also require \(x^\rho_{ea}>0\Rightarrow q_{ea}>0\).
Is this continuous optimality-certificate decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it NP-hard? What is the classification of its diligent variant?
The discrete minimum-interview optimality-certificate problem is NP-hard even for ranked equivalence classes; the diligent version is also NP-hard ([source](https://users.eecs.northwestern.edu/~nickle/pubs/interviews.pdf)).
For discrete societies, existence of a matching that is employer-optimal under every refinement of given partial orders is decidable in polynomial time ([source](https://immorlica.com/pubs/matchingInference.pdf)). No result settling the mass-allocation problem defined above was located.
Under polynomial many-one reductions, the ordinary problem is $\mathrm{coNP}$-complete, even when all applicant masses equal $1$, all employer masses belong to $\{1,2\}$, and every pair is mutually acceptable. The diligent variant is in $\mathrm{P}$, with running time polynomial in $m,\tau,L$.
Thus the proposed $\mathrm{P}$-versus-$\mathrm{NP}$-hard dichotomy misses a third classification. The ordinary problem is in $\mathrm{P}$ exactly if $\mathrm{P}=\mathrm{NP}$, and it is $\mathrm{NP}$-hard exactly if $\mathrm{NP}=\mathrm{coNP}$.
Positive budgets have an immediate certificate because arbitrarily small positive interviews reveal comparisons. The substantive complexity occurs at budget zero.
Write $x=x^\rho$.
If $B<0$, feasibility is impossible because interview costs are nonnegative. Hence assume $B\geq 0$.
Suppose $B>0$. Define
$$
h=\min_{e,a}\min\{w_e,v_a\},
\qquad
C=\sum_{e,a}c_{ea},
\qquad
\varepsilon=\min\left\{h,\frac{B}{2(1+C)}\right\}.
$$
Every mass is positive, so $\varepsilon>0$. Set $q_{ea}=\varepsilon$ for every pair. This allocation satisfies the individual bounds, and
$$
\sum_{e,a}c_{ea}q_{ea}
=C\varepsilon
\leq \frac{BC}{2(1+C)}
<B.
$$
Every type interviews every acceptable opposite-side type. Consequently, all relevant comparisons under $\rho$ are revealed, and every compatible refinement agrees with $\rho$ on its acceptable types. This certifies $x$, and the allocation is diligent.
The rational number $\varepsilon$ has polynomial encoding length.
Suppose $B=0$, and put
$$
F=\{(e,a):c_{ea}=0\}.
$$
Nonnegativity gives
$$
q_{ea}>0\quad\Longrightarrow\quad (e,a)\in F.
$$
Consider the maximal free allocation
$$
q^F_{ea}=
\begin{cases}
\min\{w_e,v_a\},&(e,a)\in F,\\
0,&(e,a)\notin F.
\end{cases}
$$
Every zero-budget allocation reveals a subset of its comparisons. Adding comparisons only restricts compatible refinements. Therefore:
$$ x_{ea}>0\quad\Longrightarrow\quad c_{ea}=0. $$
Let $P_e,P_a$ be the transitive closures of the initial orders together with the comparisons revealed by $q^F$. They are strict partial orders because every added comparison agrees with $\rho$.
For a fixed strict profile, say that one distribution dominates another if every preference prefix contains at least as much mass, with unmatched mass placed below all acceptable types.
We use the following stable-allocation facts: the employer-optimal allocation exists uniquely; it dominates every stable allocation for employers and is dominated by every stable allocation for applicants; and every stable allocation assigns the same total mass to each individual type. These follow from Lemma 8 and Theorems 3, 5, and 10 of the [corrected Baïou–Balinski paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302). Its comparison relation transfers mass from worse positions to better positions and hence implies prefix dominance.
The hypotheses apply here. Retain mutually acceptable edges and give edge $(e,a)$ capacity $\min\{w_e,v_a\}$. At this capacity, one endpoint has its entire quota on the edge, so the pair cannot block. Below capacity, their blocking condition coincides with the question’s condition. Arbitrary positive quotas, unequal side totals, and unmatched mass are allowed.
The preferred-side optimum is computable in polynomial time by the algorithm of [Dean–Munshi](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf), with unmatched mass represented by dummy vertices.
For bit complexity, multiply all rational quotas by the product of their denominators. This product has polynomial bit length. The resulting integral allocation algorithm uses polynomially many additions, subtractions, minima, and comparisons; allocation values are bounded by the total scaled quota. Scaling back therefore computes exact rational allocations in polynomial bit complexity.
For every mutually acceptable pair $(e,a)$, define
$$
G_e(a)=\{a\}\cup\{b:b\succ_{P_e}a\},
\qquad
G_a(e)=\{e\}\cup\{f:f\succ_{P_a}e\},
$$
and
$$
D_e(a)=w_e-\sum_{b\in G_e(a)}x_{eb},
\qquad
D_a(e)=v_a-\sum_{f\in G_a(e)}x_{fa}.
$$
Lemma 1. The allocation $x$ is stable under every compatible refinement exactly when every mutually acceptable pair satisfies
$$
D_e(a)=0\quad\text{or}\quad D_a(e)=0.
$$
Proof. Every compatible extension puts the forced predecessors of $a$ before $a$, so its employer deficit at $(e,a)$ is at most $D_e(a)$.
This bound is attainable. The forced predecessors form a predecessor-closed set. Order them consistently first, then place $a$, then order the remaining types consistently. No remaining type must precede $a$ or one of its forced predecessors. The resulting order is a linear extension whose prefix through $a$ is exactly $G_e(a)$.
The analogous construction attains $D_a(e)$. Refinements of different types are independent, so both positive deficits can be attained simultaneously. Conversely, if one bound is zero, that endpoint’s deficit is zero in every extension. $\square$
This test uses transitive closure and exact rational arithmetic, hence runs in polynomial time.
Fix a strict profile $\sigma$ under which $x$ is stable.
An employer is full if its assigned total equals its quota. For every full employer $e$, let $t_e$ be its worst positively assigned applicant.
Call $e$ willing at $a$ if $(e,a)$ is mutually acceptable and
$$
w_e-\sum_{b\succeq_e^\sigma a}x_{eb}>0.
$$
An underfull employer is willing at every mutually acceptable applicant. A full employer is willing exactly when
$$
a\succ_e^\sigma t_e.
$$
For each applicant $a$, let $h_a$ be its most preferred willing employer, when one exists. Define a directed graph $G_\sigma(x)$ on applicants: if $h_a$ exists and is full, insert
$$
a\longrightarrow t_{h_a}.
$$
Lemma 2. A stable allocation $x$ is employer-optimal under $\sigma$ exactly when $G_\sigma(x)$ is acyclic.
Suppose there is a simple directed cycle
$$
a_i\longrightarrow a_{i+1},
\qquad
h_{a_i}=e_i,
\qquad
t_{e_i}=a_{i+1},
$$
with indices interpreted cyclically. The employers $e_i$ are distinct: repeated employers would have identical successor applicants.
Choose
$$
0<\delta<\min_i x_{e_i,a_{i+1}}.
$$
Increase $x_{e_i,a_i}$ by $\delta$ and decrease $x_{e_i,a_{i+1}}$ by $\delta$. Let $z$ be the resulting allocation.
Each affected row and column has unchanged total, so $z$ is feasible. Each affected employer replaces tail mass by strictly preferred mass, and therefore strictly improves.
To check stability, consider a mutually acceptable pair $(f,a)$.
If its employer deficit was zero in $x$, it remains zero in $z$, because every employer’s prefixes weakly increase.
Otherwise $f$ was willing at $a$, and stability of $x$ implies that the applicant deficit was zero. An unchanged applicant retains zero deficit. For a changed applicant $a$, its deficit can become positive only if its newly received employer $h_a$ is worse than $f$: otherwise the added mass remains inside the prefix through $f$ and offsets any removed mass. But $f$ was willing, contradicting the definition of $h_a$.
Thus $z$ is stable and strictly improves some employers. Therefore $x$ is not employer-optimal.
Suppose $x$ is not employer-optimal, and let $y\neq x$ be the employer-optimal stable allocation. Employers’ distributions in $y$ dominate those in $x$, applicants’ distributions in $x$ dominate those in $y$, and corresponding assigned totals agree.
We use an elementary prefix fact: if $u$ dominates $v$, their totals agree, and $u$ has strictly more mass at one position, then $u$ has strictly less mass at some worse position. Indeed, the cumulative difference becomes positive at that position and must return to zero by the final position.
First consider a removed entry
$$
x_{eb}>y_{eb}.
$$
Applicant $b$’s dominance implies that $y$ assigns positive mass to an employer worse than $e$. Its deficit at $(e,b)$ in $y$ is consequently positive. Stability forces the employer deficit there to be zero: $e$ is full in $y$ and has no positive allocation worse than $b$.
Equal row totals make $e$ full in $x$ too. Its original tail entry decreases: if $t_e=b$, this is the assumed decrease; if $t_e$ is worse than $b$, then
$$
y_{e,t_e}=0<x_{e,t_e}.
$$
Every changed employer has a removed entry because its total is unchanged. Thus every changed employer is full and loses original tail mass.
Let $T$ be the set of applicants losing mass at some employer’s original tail. It is nonempty. For $a\in T$, equal column totals give an employer $e'$ such that
$$
y_{e'a}>x_{e'a}.
$$
Employer dominance implies that $e'$ loses mass at a worse applicant, so $e'$ was willing at $a$ in $x$. Hence $h_a$ exists.
If $h_a=e'$, it is a changed employer and loses its original tail. If $a$ prefers $h_a$ to $e'$, then $y_{e'a}>0$ makes the applicant deficit at $(h_a,a)$ positive in $y$. Stability forces $h_a$ to be full and to have no positive allocation worse than $a$. Equal totals make it full in $x$. Since it was willing there, its original tail is worse than $a$, and that tail entry decreases to zero.
Therefore
$$
a\longmapsto t_{h_a}
$$
maps the nonempty finite set $T$ into itself. Iteration gives a directed cycle in $G_\sigma(x)$. This proves the lemma. $\square$
Section 1 handles positive budgets and eliminates allocation search at zero budget.
For a zero-budget NO-instance, a certificate is a compatible strict profile $\sigma$ under which $x^\rho$ is not employer-optimal. Its encoding length is polynomial. A verifier checks compatibility, computes $x^\rho$ and $x^\sigma$, and checks
$$
x^\rho\neq x^\sigma.
$$
Uniqueness of the employer-optimal allocation makes this inequality equivalent to failure of the certificate requirement.
Thus the ordinary problem belongs to $\mathrm{coNP}$.
A rainbow directed cycle is a simple directed cycle whose vertices have pairwise distinct colors.
We first prove that detecting such a cycle is $\mathrm{NP}$-complete even when every color occurs on at most two vertices and no edge joins equally colored vertices.
Membership in $\mathrm{NP}$ is immediate. For hardness, start with a formula having variables $X_1,\ldots,X_n$ and clauses $C_1,\ldots,C_r$, each containing three literal occurrences. Give each occurrence $(j,k)$ its own color $\chi_{jk}$.
Construct a directed acyclic graph with consecutive variable stages followed by consecutive clause stages.
For variable $X_i$, create two internally disjoint directed chains between the stage’s entrance and exit, representing its two truth values. Each chain contains:
For clause $C_j$, create three parallel paths of length two between its entrance and exit. Their middle vertices have colors
$$
\chi_{j1},\chi_{j2},\chi_{j3}.
$$
Every marker and stage boundary has a fresh color. Let $s$ and $t$ be the first and last boundaries.
A directed $s$-to-$t$ path selects a truth value for every variable and one literal occurrence per clause. During the variable stages it visits exactly the occurrence colors of false literals. Therefore the path has distinct colors exactly when each selected clause literal is true.
Hence a rainbow $s$-to-$t$ path exists exactly when the formula is satisfiable.
Add the edge $t\to s$. Every directed cycle must use this edge because the original graph was acyclic. A rainbow cycle therefore exists exactly when a rainbow $s$-to-$t$ path exists.
Every occurrence color occurs exactly twice: once on the branch falsifying that occurrence and once in its clause stage. All other colors occur once. Consecutive vertices always have distinct colors. The construction has polynomial size, proving the auxiliary hardness claim.
Let $D=(V,R)$ be a graph from this construction, with coloring $\kappa$. For each color $e$, let
$$
S_e=\{a\in V:\kappa(a)=e\}.
$$
Construct the society as follows:
$$ w_e=|S_e|\in\{1,2\}. $$
$$ b\succ_{P_e}a \quad\text{whenever}\quad b\in S_e,\ a\notin S_e,\ (a,b)\notin R. $$
The employer relations are strict partial orders. Every comparison starts in $S_e$ and ends outside $S_e$, so there are no directed paths of length two and no cycles.
Supply a realized refinement $\rho$ in which every employer places all of $S_e$ before all applicants outside $S_e$. Supply any applicant refinement placing its owner first.
Define
$$
x_{ea}=
\begin{cases}
1,&a\in S_e,\\
0,&a\notin S_e.
\end{cases}
$$
This allocation is feasible and stable under every compatible refinement. Indeed, each applicant is fully assigned to its first-choice owner, making its deficit zero at every pair.
Moreover, $x=x^\rho$. To see this directly, under $\rho_e$ the first $|S_e|$ applicants are precisely $S_e$. For a prefix of $k\leq |S_e|$ such applicants, $x$ assigns mass $k$, while any feasible allocation assigns at most $k$ because each applicant has mass one. Every later prefix already contains the full employer quota under $x$. Thus $x$ dominates every feasible allocation for every employer.
At zero budget, all costs are positive, so the only feasible interview allocation is the zero matrix. Compatibility therefore means extending just these initial partial orders.
We prove
$$
\exists \sigma\text{ compatible with }x\text{ not employer-optimal}
\quad\Longleftrightarrow\quad
D\text{ has a rainbow directed cycle}.
$$
Suppose $x$ is not employer-optimal under a compatible profile $\sigma$. It is stable, so Lemma 2 gives a cycle in $G_\sigma(x)$.
Every arc in that graph ends at an employer’s tail. Therefore every cycle vertex is some employer’s tail. Since $x$ assigns each applicant only to its owner, that employer is the vertex’s owner. An employer has only one tail, so distinct cycle vertices have distinct owners, hence distinct colors.
For a cycle arc
$$
a\longrightarrow b,
$$
the willing employer is $\kappa(b)$, and $b$ is its tail. Since the cycle colors are distinct, $a\notin S_{\kappa(b)}$. Willingness means
$$
a\succ^\sigma_{\kappa(b)}b.
$$
If $(a,b)\notin R$, the initial order requires the opposite comparison. Consequently $(a,b)\in R$.
Thus the graph cycle is a rainbow directed cycle in $D$.
Conversely, suppose
$$
a_0\longrightarrow a_1\longrightarrow\cdots
\longrightarrow a_{\ell-1}\longrightarrow a_0
$$
is a rainbow cycle in $D$, with cyclic indices.
For employer $e=\kappa(a_{i+1})$, choose the following order:
The rainbow condition makes $a_i$ external to $S_e$. This order extends $P_e$: comparisons starting at another member of $S_e$ are respected because that member comes first; comparisons starting at $a_{i+1}$ are respected because all external applicants other than $a_i$ come later. The comparison $a_{i+1}\succ_{P_e}a_i$ is absent because $(a_i,a_{i+1})\in R$.
These employers are distinct, so their choices are independent. For every employer outside the cycle, put all owned applicants before all external applicants. Choose any compatible applicant orders.
The cycle employer $\kappa(a_{i+1})$ now has tail $a_{i+1}$ and is willing at exactly one external applicant, namely $a_i$.
Applicant $a_i$ is its owner’s tail, so its owner is unwilling there. Every other employer except $\kappa(a_{i+1})$ is also unwilling there. Thus
$$
h_{a_i}=\kappa(a_{i+1}),
$$
and $G_\sigma(x)$ contains the displayed cycle. Lemma 2 shows that $x$ is not employer-optimal.
This proves the equivalence.
Combining the formula construction and society construction gives
$$
\text{formula unsatisfiable}
\quad\Longleftrightarrow\quad
\text{ordinary certificate instance is YES}.
$$
All constructions have polynomial size. The supplied realized profile and its employer-optimal allocation were explicitly verified, and all masses and costs have constant-size encodings.
Thus the ordinary problem is $\mathrm{coNP}$-hard. Together with membership,
$$
\boxed{\text{The ordinary problem is }\mathrm{coNP}\text{-complete}.}
$$
We now prove the polynomial criterion needed for diligence.
Assume:
The second condition means that every other positively assigned applicant satisfies
$$
b\succ_{P_e}t_e.
$$
Indeed, a strict comparison holds in every linear extension exactly when it belongs to the transitive partial order.
For a mutually acceptable pair, define
$$
\operatorname{Def}(e,a)=
\begin{cases}
\text{true},&e\text{ is underfull},\\
a\succ_{P_e}t_e,&e\text{ is full},
\end{cases}
$$
and
$$
\operatorname{Poss}(e,a)=
\begin{cases}
\text{true},&e\text{ is underfull},\\
a\neq t_e\text{ and }t_e\not\succ_{P_e}a,&e\text{ is full}.
\end{cases}
$$
These respectively mean that $e$ is willing at $a$ in every compatible refinement, or in at least one.
Construct a graph $H$ on applicants. For every full employer $e$, insert
$$
a\longrightarrow t_e
$$
if:
$$ \operatorname{Def}(f,a) \quad\text{and}\quad f\succ_{P_a}e. $$
Lemma 3. Under the two assumptions, $x$ is employer-optimal under every compatible refinement exactly when $H$ is acyclic.
Every arc of every $G_\sigma(x)$ belongs to $H$. If $h_a=e$, then $e$ is possibly willing. A definitely willing employer forced above $e$ would contradict $h_a=e$.
Thus acyclicity of $H$ implies acyclicity of every $G_\sigma(x)$. Lemma 2 proves universal employer optimality.
Suppose $H$ contains a shortest directed cycle
$$
a_i\longrightarrow a_{i+1}=t_{e_i},
$$
where $e_i$ witnesses the indicated arc. The employers $e_i$ are distinct because their tails are distinct cycle successors.
For a full employer outside the cycle, choose an extension placing its tail immediately after its forced predecessors. It is then willing exactly at its definitely willing applicants.
For cycle employer $e_i$, add
$$
a_i\succ_{e_i}t_{e_i}.
$$
This is consistent by $\operatorname{Poss}(e_i,a_i)$. In the augmented order, place the tail immediately after its predecessors. The willing applicants are exactly those $b$ satisfying at least one of
$$
\operatorname{Def}(e_i,b),
\qquad b=a_i,
\qquad b\succ_{P_{e_i}}a_i.
$$
This follows because the added predecessors of the tail are precisely $a_i$ and its original predecessors.
Underfull employers may choose arbitrary compatible extensions.
We claim that no employer willing at a cycle applicant $a_i$ is forced above $e_i$ in $P_{a_i}$.
Suppose such an employer $f$ exists. The condition defining the original arc excludes $\operatorname{Def}(f,a_i)$. Therefore $f$ must be another cycle employer, say $f=e_j$ with $j\neq i$, whose added willingness gives
$$
a_i\succ_{P_f}a_j.
$$
Because $\operatorname{Poss}(f,a_j)$ holds, this implies
$$
a_i\neq t_f,
\qquad
t_f\not\succ_{P_f}a_i.
$$
Either contrary possibility would force $t_f\succ_{P_f}a_j$. Hence $\operatorname{Poss}(f,a_i)$ holds.
Also, no definitely willing employer $g$ is forced above $f$ at $a_i$. Otherwise transitivity with $f\succ_{P_{a_i}}e_i$ would put $g$ above $e_i$, contradicting the original arc’s condition.
Consequently $H$ contains the shortcut
$$
a_i\longrightarrow t_f=a_{j+1}.
$$
Its endpoint is neither $a_i$, by $\operatorname{Poss}(f,a_i)$, nor the original successor $a_{i+1}$, because $j\neq i$ and the cycle vertices are distinct. Together with the appropriate segment of the original cycle, it gives a strictly shorter directed cycle. This contradiction proves the claim.
For each cycle applicant $a_i$, now choose an extension placing $e_i$ above every other willing employer. Such an extension exists: none of those employers is forced above $e_i$. More explicitly, adding comparisons from $e_i$ to all those employers cannot create a cycle, since a resulting cycle would require an original path from one of them back to $e_i$.
Thus $h_{a_i}=e_i$ for every cycle applicant. The resulting $G_\sigma(x)$ contains the chosen cycle. Universal stability ensures that $x$ is stable under this profile, and Lemma 2 proves that it is not employer-optimal. $\square$
All predicates and graph operations in this lemma are polynomial-time computable.
The algorithm is:
It remains to verify the fixed-tail hypothesis in step 6.
After step 3 succeeds, every positively assigned pair is zero-cost and is therefore positively interviewed by $q^F$. For each employer, all comparisons among its positively assigned applicants are revealed. In particular, its realized worst positively assigned applicant remains worst under every compatible refinement. Every full employer consequently has a fixed tail.
Lemma 3 now applies. Section 1 proves that using maximal free revelation loses no feasible diligent certificate. Hence all steps are correct.
Fixed-profile allocation computation, transitive closure, rational deficit calculations, construction of $H$, and cycle detection have polynomial bit complexity in $m,\tau,L$. Therefore
$$
\boxed{\text{The diligent variant belongs to }\mathrm{P}.}
$$
The ordinary problem is $\mathrm{coNP}$-complete under polynomial many-one reductions.
If it were in $\mathrm{P}$, then every $\mathrm{coNP}$ problem would be in $\mathrm{P}$; taking complements gives $\mathrm{NP}\subseteq\mathrm{P}$. Conversely, $\mathrm{P}=\mathrm{NP}$ puts it in $\mathrm{P}$.
If it were $\mathrm{NP}$-hard, its membership in $\mathrm{coNP}$ would imply
$$
\mathrm{NP}\subseteq\mathrm{coNP},
$$
hence $\mathrm{NP}=\mathrm{coNP}$. Conversely, under that equality, its $\mathrm{coNP}$-completeness makes it $\mathrm{NP}$-hard.
The unconditional classifications are therefore $\mathrm{coNP}$-complete for the ordinary variant and $\mathrm{P}$ for the diligent variant.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance. I found no false central step, invalid reduction, or gap requiring new mathematics. It establishes the ordinary problem as $\mathrm{coNP}$-complete and the diligent variant as belonging to $\mathrm{P}$.
There is one minor omission: the hardness proof implicitly uses the $\mathrm{NP}$-completeness of satisfiability for formulas with three literal occurrences per clause without explicitly identifying that starting problem and stating the standard complexity result.
The construction is correct.
Because both supports are finite and nonempty and all masses are positive,
$$
h>0.
$$
For $B>0$, the proposed $\varepsilon$ is positive and satisfies every individual interview bound. The cost calculation is correct, including when $C=0$:
$$
C\varepsilon\leq \frac{BC}{2(1+C)}<B.
$$
Interviewing every pair reveals the complete realized order on each type’s acceptable subset. Remaining freedom concerning unacceptable types cannot affect feasible matchings, blocking, or the relevant stochastic-dominance comparisons.
The allocation also satisfies diligence. The polynomial encoding-length claim is valid: sums, minima, and the displayed rational division produce numbers with polynomial bit length.
Nonnegative costs and nonnegative interview amounts imply that every positive-cost entry must receive zero interviews.
The maximal free allocation is feasible because there are no aggregate interview bounds. It reveals every comparison that any zero-budget allocation could reveal. Additional comparisons restrict the compatible-profile set, so the claimed monotonicity is valid.
The diligent characterization is also exact: every positive matching entry must have zero interview cost, and the maximal free allocation interviews every such entry positively.
The resulting partial orders are consistent because every revealed comparison agrees with the supplied refinement $\rho$.
Assessment: Correct.
The fixed-profile facts needed later are:
The cited corrected Baïou–Balinski paper supports the first three facts through the results identified in the output. Its comparison relation supports the prefix-dominance interpretation used here. The model allows positive real quotas and nonnegative edge capacities. [Corrected Baïou–Balinski paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302).
The capacity translation is correct. Every feasible matrix already satisfies the proposed edge capacities. At a saturated edge, an endpoint with the smaller quota has its entire quota assigned on that edge, so the task’s blocking condition fails. At an unsaturated edge, the two stability definitions coincide. Removing non-mutually acceptable edges is also valid.
The Dean–Munshi algorithm computes the preferred-side optimum for this stable-allocation model. The cited paper includes dummy vertices for unmatched allocation and uses polynomially many augmentations based on residual capacities. [Dean–Munshi paper](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
The scaling argument establishes polynomial bit complexity. The denominator product has polynomial bit length; scaled quotas and capacities are integral; and the relevant allocation operations preserve integrality with polynomially bounded numerical encoding lengths. Unequal totals and unmatched mass do not invalidate the application.
Assessment: The cited results apply; no blocking citation gap remains.
The upper bounds $D_e(a)$ and $D_a(e)$ are valid. Every compatible extension includes all forced predecessors in the relevant prefix, and nonnegative allocation entries make its deficit no larger than the displayed bound.
The attainment argument is correct. The forced predecessors are predecessor-closed, and placing them first, followed by the designated type, respects the partial order. The remaining types can then be ordered consistently.
The two extremal deficits can be attained simultaneously because the employer’s and applicant’s refinements are independently chosen.
Thus:
Feasibility ensures that the displayed deficits are nonnegative, so the equality-to-zero formulation is correct.
Assessment: Both directions are proved.
A full employer has positive assigned mass because its quota is positive, so its worst positively assigned applicant exists.
The willingness characterization is correct on mutually acceptable pairs. An underfull employer always has positive deficit. For a full employer, the deficit is positive exactly when its tail is strictly worse than the proposed applicant.
The employers on a simple cycle are distinct: a repeated employer would produce a repeated successor applicant.
The chosen $\delta$ keeps every decreased entry positive. Each affected row and column has unchanged total, and every increased pair is mutually acceptable. Consequently the perturbed matrix is feasible.
Each affected employer transfers mass from its tail to a strictly preferred applicant, so its prefixes weakly increase and its distribution strictly improves.
The stability check is exhaustive:
No additional upper-bound restriction on $\delta$ is missing: unchanged row and column totals already enforce the task’s feasibility constraints.
The dominance directions and equal-total properties invoked here are justified by Section 2.
The elementary prefix fact is correct. At a position with positive entrywise difference, the cumulative difference is positive; equal totals require a negative difference at some later position.
For a removed entry, applicant dominance supplies positive allocation in $y$ to a worse employer. This creates positive applicant deficit, so stability forces the stated zero employer deficit. The resulting fullness and loss of original tail mass follow.
The set $T$ is nonempty because $y\neq x$ and changed employer rows have unchanged totals.
For each $a\in T$, the argument correctly establishes that $h_a$ exists, is full, and loses mass at its original tail. Therefore its tail belongs to $T$, and the displayed map really does map $T$ into itself. Finiteness then supplies a directed cycle.
Assessment: Both directions are correct.
A compatible strict profile has polynomial encoding length. Compatibility and both preferred-side allocations can be checked in polynomial time.
By uniqueness, the inequality
$$
x^\rho\neq x^\sigma
$$
is equivalent to failure of the required optimality under $\sigma$. This covers both instability and stability without employer optimality.
Positive and negative budgets are already handled directly.
Assessment: Correct.
The variable branches visit exactly the occurrence colors corresponding to false literals. Clause stages select one occurrence per clause. Hence a complete path has distinct colors exactly when all selected clause literals are true.
The construction satisfies the stated restrictions:
Every directed cycle after adding the return edge corresponds to a complete path through the stages. The construction has polynomial size.
Minor issue: The proof should explicitly name three-literal satisfiability as the starting decision problem and state its $\mathrm{NP}$-completeness. The formula format already matches that standard problem, so this is an expositional omission.
The employer relations are strict partial orders: comparisons run only from owned applicants to external applicants, preventing directed comparison paths of length two.
The supplied realized profile extends these orders. The proposed allocation is feasible and universally stable because every applicant receives its entire mass from its forced first-choice owner.
The prefix calculation establishing $x=x^\rho$ is correct. For an early prefix, unit applicant capacities bound the allocated mass by the prefix size; later prefixes already contain the employer’s full quota.
From a bad refinement, Lemma 2 supplies a cycle. Each cycle vertex is an employer’s unique tail, so distinct cycle vertices have distinct owners. Every cycle arc must be an original graph edge, since a missing edge would impose the opposite employer comparison.
Conversely, the proposed employer orders extend the initial partial orders. The graph edge permits the one external applicant placed ahead of the selected tail. Each cycle employer is willing at exactly that external applicant.
At each cycle applicant, its owner is unwilling, and exactly the designated incoming employer is willing. The resulting optimality graph therefore contains the desired cycle.
The reduction correctly maps unsatisfiable formulas to YES-instances, establishing $\mathrm{coNP}$-hardness. The claimed mass and acceptability restrictions are satisfied.
Assessment: Correct, subject only to the minor starting-problem clarification.
The predicates $\operatorname{Def}$ and $\operatorname{Poss}$ correctly express necessary and possible willingness when tails are fixed.
Every realized graph arc belongs to $H$, so acyclicity of $H$ is sufficient.
The converse is also valid:
Universal stability permits applying Lemma 2 to the constructed profile.
Assessment: The shortest-cycle realization argument is complete.
After the positive matching entries pass the zero-cost check, all comparisons among each employer’s positively assigned applicants are revealed. Thus every full employer has the same tail in every compatible refinement.
The algorithm checks universal stability before applying Lemma 3, so both hypotheses are established. Maximal free revelation preserves certificate existence by Section 1.
All remaining operations—transitive closure, rational sums, predicate evaluation, graph construction, and cycle detection—have polynomial complexity in the stated input parameters.
The final conditional statements about $\mathrm{P}=\mathrm{NP}$ and $\mathrm{NP}=\mathrm{coNP}$ correctly follow from ordinary-problem $\mathrm{coNP}$-completeness under polynomial many-one reductions.
The two variants having different classifications does not constitute an encoding-dependent “split.”
Explicitly identify the starting satisfiability problem in the auxiliary hardness proof and state its standard $\mathrm{NP}$-completeness. No additional lemma, counterexample repair, or change to either algorithm is needed.
⟨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.