Answer: Polynomial-time solvable; every input satisfying the stated assumptions yields a maximum-total-mass matching.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf the market is regular, the matchings produced by the sequence of tubes $\varphi^\ast$ minimize unfilled jobs for any assignment plan when considering only the rule of avoidance.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite rational worker masses \(\mu_{r,\pi}\) and job masses \(\nu_s\) on a common scale, where worker types have region \(r\) and a fixed ranking \(\pi\) of job regions, and jobs have region \(s\), compatibility holds exactly when \(r\neq s\). Let \(r_1\) be a region with the largest worker mass and assume \(\sum_{r\neq r_1}\mu_r\geq\sum_{s\neq r_1}\nu_s\), where \(\mu_r=\sum_\pi\mu_{r,\pi}\). Fix an order of worker types within the two worker tubes \(W_1,W_{-1}\); process each type’s mass in that order, assigning it to the earliest job tube \(J_{-1},J_1\) with compatible available mass and following \(\pi\) within that tube. Does this execution always produce a flow of maximum total mass among feasible matchings?
Let \(R\) be a finite set of \(m\geq1\) regions. Worker types are pairs \((r,\pi)\), where \(r\in R\) and \(\pi\) is a strict total ranking of \(R\); job types are regions \(s\in R\). Compatibility holds exactly when \(r\neq s\).
A society is given by its support: the list of the \(\tau\) worker and job types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. Worker masses \(\mu_{r,\pi}\) and job masses \(\nu_s\) use a common scale and need not sum to one; absent types have zero mass.
Set \(\mu_r=\sum_\pi\mu_{r,\pi}\). A designated region \(r_1\) satisfies \(\mu_{r_1}=\max_{r\in R}\mu_r\), and inputs satisfy \(\sum_{r\neq r_1}\mu_r\geq\sum_{s\neq r_1}\nu_s\).
The worker tubes are \(W_1=\{(r,\pi):r=r_1\}\) and \(W_{-1}=\{(r,\pi):r\neq r_1\}\); the job tubes are \(J_{-1}=R\setminus\{r_1\}\) and \(J_1=\{r_1\}\). A strict order of supported worker types within each worker tube is part of the input.
Process \(W_1\) before \(W_{-1}\). For each type, repeatedly select the earliest job tube in \((J_{-1},J_1)\) containing compatible positive residual mass, then its highest-ranked available compatible region under \(\pi\). Transfer the minimum of the worker and job residual masses, irrevocably, until the worker mass is exhausted or no compatible mass remains; leave any remaining worker mass unmatched.
A feasible matching is a nonnegative flow \(x_{r,\pi,s}\), zero when \(r=s\), with \(\sum_s x_{r,\pi,s}\leq\mu_{r,\pi}\) and \(\sum_{r,\pi}x_{r,\pi,s}\leq\nu_s\). Its total matched mass is \(\sum_{r,\pi,s}x_{r,\pi,s}\).
Is deciding whether the specified execution yields a feasible matching of maximum total mass solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite unit agents, this two-by-two procedure produces a maximum-cardinality matching under the stated regularity condition for every strict worker and job order (Bó and Chen, 2026). That result does not explicitly treat rational masses.
The decision problem is polynomial-time solvable. In fact, every input satisfying the stated assumptions yields a maximum-total-mass matching, regardless of the specified within-tube orders and rankings.
The proof applies directly to rational masses.
Write
\(a=\mu_{r_1},\qquad B=\sum_{r\neq r_1}\mu_r,\qquad C=\sum_{s\neq r_1}\nu_s,\qquad d=\nu_{r_1}.\)
Thus the total worker and job masses are \(M=a+B\) and \(N=C+d\). The assumptions give
\(B\geq C\quad\text{and}\quad \mu_r\leq a\text{ for every }r\in R.\)
Every feasible matching has total mass at most \(M\) and at most \(N\). Moreover, workers in \(W_1\) can only match jobs in \(J_{-1}\), so their matched mass is at most \(C\). Workers in \(W_{-1}\) contribute at most \(B\). Consequently, every feasible matching has total mass at most
\(U=\min\{M,N,B+C\}.\)
We will prove that the specified execution attains \(U\).
Each transfer preserves feasibility: it uses a compatible pair and transfers no more than either residual mass. Each positive transfer exhausts a worker type or job region, which remains exhausted thereafter. Hence the execution terminates after finitely many transfers.
Every worker in \(W_1\) is compatible with every region in \(J_{-1}\), and incompatible with \(J_1\).
Therefore, during the first phase, workers continue taking mass from \(J_{-1}\) until either all worker mass \(a\) is exhausted or all job mass \(C\) is exhausted. The matched mass in this phase is exactly
\(w=\min\{a,C\}.\)
The residual job mass in \(J_{-1}\) is \(C-w\), and the job mass \(d\) in \(J_1\) is unchanged.
If \(a\geq C\), the first phase already fills all of \(J_{-1}\).
Suppose instead that \(a<C\). The second phase starts with residual job mass
\(D=C-a>0\)
in \(J_{-1}\). Assume, for a contradiction, that some region \(t\neq r_1\) has positive residual job mass at the end of the execution.
Job residual masses only decrease. Thus region \(t\) has positive residual job mass throughout the second phase.
Consider any worker type in \(W_{-1}\) whose origin is different from \(t\). Throughout its processing, region \(t\) supplies compatible positive residual mass in \(J_{-1}\). The procedure therefore always selects \(J_{-1}\) for this worker type and cannot stop before exhausting its worker mass.
It follows that all worker mass in \(W_{-1}\) with origin different from \(t\) is matched to \(J_{-1}\). This mass is
\(B-\mu_t.\)
Since \(J_{-1}\) starts the second phase with mass \(D\) and retains positive mass at the end, its matched mass during that phase is strictly less than \(D\). Hence
\(B-\mu_t<D=C-a.\)
But the assumptions imply
\(B-\mu_t\geq C-a=D,\)
because \(B\geq C\) and \(\mu_t\leq a\). This is a contradiction.
Thus, in both cases, every job in \(J_{-1}\) is filled.
Let \(q\) be the mass matched to \(J_1\). Only workers in \(W_{-1}\) can contribute to \(q\).
By Sections 2 and 3, workers in \(W_{-1}\) match exactly \(C-w\) mass to \(J_{-1}\). Feasibility therefore gives
\(q\leq d,\qquad q\leq B-C+w.\)
If \(q<d\), then \(J_1\) retains positive mass at the end, and hence throughout the second phase. Every worker in \(W_{-1}\) is compatible with \(J_1\), so none can finish processing with unmatched mass. Therefore,
\(B=(C-w)+q,\)
giving \(q=B-C+w\).
If \(q=d\), feasibility already gives \(d\leq B-C+w\). Together, these cases establish
\(q=\min\{d,B-C+w\}.\)
The execution’s total matched mass is consequently
\(T=C+q=\min\{C+d,B+w\}.\)
Since \(w=\min\{a,C\}\), we have
\(B+w=\min\{B+a,B+C\}=\min\{M,B+C\}.\)
Therefore,
\(T=\min\{M,N,B+C\}=U.\)
Section 1 bounds every feasible matching by \(U\), and the execution is feasible and attains \(U\). This proves its optimality.
The argument also covers \(m=1\): then \(B=C=0\), and compatibility permits no positive matching.
On inputs promised to satisfy the assumptions, the decision algorithm can simply return YES. Validating those assumptions requires only polynomial-time rational arithmetic.
The execution itself can also be computed in polynomial time. Let \(k\) be the number of supported worker types and \(j\) the number of supported job regions, so \(k+j=\tau\).
Every positive transfer permanently exhausts a worker type or job region. Thus there are at most \(\tau\) positive transfers. Finding the selected region by scanning a worker’s ranking takes \(O(m)\) time per selection; there are also at most \(k\) unsuccessful terminal selections.
For exact arithmetic, write the supported masses as \(n_i/d_i\) with binary-encoded integers and take the common denominator \(D=\prod_i d_i\). Its bit length is \(O(L)\). Scaling every mass by \(D\) produces integers of polynomial bit length, and all subsequent residual masses are bounded by the scaled input totals. Each subtraction, comparison, and minimum therefore has polynomial bit complexity.
Hence exact simulation, computation of the optimal value above, and comparison all run in time polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the task. It establishes the stronger claim that every promised input produces a maximum-total-mass matching. No major or minor mathematical issues were found.
The notation correctly partitions worker and job masses:
\(M=a+B\) and \(N=C+d\). The input assumptions give \(B\geq C\) and \(\mu_r\leq a\) for every region \(r\).
The upper bound
\(U=\min\{M,N,B+C\}\)
is valid. The first two bounds follow from total supply and demand. For the third, workers in \(W_1\) can match at most \(C\), and workers in \(W_{-1}\) can match at most \(B\). These bounds apply to every feasible matching, independently of the execution.
The feasibility and termination claims are also correct. Each transfer uses a compatible pair and respects both residual capacities. Each positive transfer permanently exhausts at least one supported worker type or job region, so infinitely many transfers are impossible.
Every worker in \(W_1\) is compatible with every job region in \(J_{-1}\) and incompatible with \(J_1\). Therefore, processing all supported types in \(W_1\) matches exactly \(w=\min\{a,C\}\).
This conclusion holds for arbitrary specified rankings and within-tube orders. It also covers zero total worker or job mass in the relevant tube.
When \(a\geq C\), the first-phase conclusion immediately establishes exhaustion of \(J_{-1}\).
For \(a<C\), the contradiction argument is sound:
The contradiction is valid. The strict inequality is justified by the assumed positive final residual mass. No property of the rankings or worker orders has been omitted.
Once exhaustion of \(J_{-1}\) is established, second-phase workers have matched exactly \(C-w\) into that tube. Thus feasibility gives \(q\leq d\) and \(q\leq B-C+w\).
The case distinction correctly establishes equality with the smaller bound:
These cases are exhaustive, including \(d=0\). Therefore \(q=\min\{d,B-C+w\}\) is justified.
The algebra is correct:
\(T=C+q=\min\{C+d,B+w\}\), and
\(B+w=\min\{B+a,B+C\}\).
Substituting \(M=a+B\) and \(N=C+d\) yields
\(T=\min\{M,N,B+C\}=U\).
Since the execution is feasible and attains an upper bound applying to every feasible matching, its optimality follows. The proof does not need an independent characterization of all optimal matchings.
The stated treatment of \(m=1\) is correct: \(B=C=0\), every worker and job has the same region, and no positive matching is compatible.
Absent types, empty support in individual tubes, and zero aggregate masses cause no failure in the argument. The proof uses neither integrality nor normalization of masses. It therefore applies to the rational masses specified in the task.
The finite-unit-agent result is contextual only; the prover does not invoke it or require an unproved extension of it.
Returning YES is a correct decision algorithm on the promised input domain, because the preceding proof establishes optimality for every such input.
The additional simulation claim is also justified:
Thus exact arithmetic and simulation require polynomial time in \(m,\tau,L\). There is no hidden dependence on the number of possible unsupported worker types or on the numerical magnitude of masses.
No repair or additional clarification is required. The stronger universal optimality claim is fully supported by the written proof.
⟨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.