Answer: Polynomial-time solvable; every assignment maximizing total match value admits stable support. The running time is \(\operatorname{poly}(m(\tau-m)+\tau+K,L)\) bit operations.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose that for each firm $f$ the constraint structure $\H_f$ is an intersecting family and for some submodular function $g_f$ on $\H_f \times \{f\}$ the upper bound hiring quotas $\Bar{\llambda}_f$ satisfy $\Bar{\lambda}_{D_f} = g_f(D_f \times \{f\})$ for all $D_f \in \H_f$. Then, there exists a stable arrangement and this stable arrangement can be computed, using linear programming, in polynomial time in the number of firms, workers and the cardinality of the constraint set $\H$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational worker-type masses \(\mu_i\), firm-type masses \(\nu_j\), values \(a_{ij},c_{ij}\), and for each firm type \(j\) an intersecting family \(\mathcal H_j\) with integer submodular quota function \(g_j\), find a mass assignment \(x\) maximizing \(\sum_{i,j}(a_{ij}+c_{ij})x_{ij}\), together with transfers and payoffs supporting stability, subject to \(x_{ij}\ge0\), \(\sum_jx_{ij}\le\mu_i\), and \(\sum_{i\in D}x_{ij}\le\nu_jg_j(D)\) for every \(D\in\mathcal H_j\), with no positive mass \(q\le\nu_j\) of firm type \(j\) and feasible worker bundle \(y\in qP_j\) able to make all participants weakly better off and some strictly better off, where \(P_j=\{z\ge0:\sum_{i\in D}z_i\le g_j(D)\text{ for all }D\in\mathcal H_j\}\).
A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses; \(\tau\) is the support size, not the number of possible types. Let \(I\) be the worker types and \(J\) the firm types, with \(m=|J|\) and \(\tau=|I|+|J|\). Masses \(\mu_i,\nu_j\) need not sum to one; values \(a_{ij},c_{ij}\) are arbitrary signed binary rationals.
For each \(j\), explicitly list \(\mathcal H_j\subseteq 2^I\setminus\{\emptyset\}\) and quotas \(g_j:\mathcal H_j\to\mathbb Z_{\ge0}\). Whenever \(A,B\in\mathcal H_j\) have \(A\cap B,A\setminus B,B\setminus A\) all nonempty, require \(A\cap B,A\cup B\in\mathcal H_j\) and \(g_j(A)+g_j(B)\ge g_j(A\cap B)+g_j(A\cup B)\).
Define \(P_j=\{z\ge0:\sum_{i\in D}z_i\le g_j(D)\text{ for every }D\in\mathcal H_j\}\). A feasible divisible assignment satisfies \(x\ge0\), \(\sum_jx_{ij}\le\mu_i\), and \(x_{\cdot j}\in\nu_jP_j\). Its value is \(U(x)=\sum_{i,j}(a_{ij}+c_{ij})x_{ij}\).
Payoffs are constant per unit within each type. Signed salary rates \(s_{ij}\) support worker payoffs \(u_i\ge0\) and firm payoffs \(v_j\ge0\) when \(a_{ij}+s_{ij}=u_i\) whenever \(x_{ij}>0\), \(u_i=0\) whenever \(\sum_jx_{ij}<\mu_i\), and \(\nu_jv_j=\sum_i(c_{ij}-s_{ij})x_{ij}\). Outside options are zero; each firm type uses the per-unit bundle \(x_{\cdot j}/\nu_j\).
A block consists of \(j\), real \(0<q\le\nu_j\), a bundle \(y\in qP_j\) with \(y_i\le\mu_i\), and signed salary rates \(r_i\), such that \(a_{ij}+r_i\ge u_i\) for every \(i\) with \(y_i>0\), and \(\sum_i(c_{ij}-r_i)y_i\ge qv_j\), with strict inequality for the firms or for a worker type of positive participating mass. The deviating firms replace their entire bundle and may recruit currently assigned workers; stability means no block.
Is finding a feasible assignment maximizing \(U(x)\), together with salaries and payoffs supporting stability, or reporting that no such support exists, solvable in polynomial time, or is it NP-hard?
State running times in \(m\), \(\tau\), \(K=\sum_j|\mathcal H_j|\), and the total input bit length \(L\).
For finite individual workers and firms, stable arrangements under these quota conditions exist and can be computed in polynomial time in the numbers of workers, firms, constraints, and input bits ([Jalota–Ostrovsky–Pavone](https://arxiv.org/pdf/2202.05232)); their assignments maximize total match value.
No result settling exactly the mass problem defined here was located in the literature search.
The problem is solvable in polynomial time. Stable support always exists, and every assignment maximizing total match value admits such support.
The proof applies to arbitrary explicitly listed nonnegative upper quotas; the crossing-submodularity assumption is unnecessary for this divisible model.
If either side is empty, the zero assignment and zero payoffs suffice. Below, let \(n=|I|=\tau-m\) and \(w_{ij}=a_{ij}+c_{ij}\).
The assignment problem is exactly the following linear program:
\(\displaystyle \max_{x\ge 0}\ \sum_{i\in I,j\in J}w_{ij}x_{ij},\)
subject to
\(\displaystyle \sum_{j\in J}x_{ij}\le\mu_i\qquad(i\in I),\)
\(\displaystyle \sum_{i\in D}x_{ij}\le\nu_jg_j(D)\qquad(j\in J,\ D\in\mathcal H_j).\)
Indeed, because \(\nu_j>0\), the second family is equivalent to \(x_{\cdot j}/\nu_j\in P_j\).
The feasible region is nonempty: it contains the zero assignment because all quotas are nonnegative. It is closed and bounded, since \(0\le x_{ij}\le\mu_i\). Consequently, an optimum exists even when some \(P_j\) is unbounded.
Introduce a dual variable \(u_i\ge0\) for each worker constraint and a dual variable \(\lambda_{jD}\ge0\) for each quota constraint. The dual is
\(\displaystyle \min_{u,\lambda\ge0}\ \sum_i\mu_i u_i+\sum_j\sum_{D\in\mathcal H_j}\nu_jg_j(D)\lambda_{jD},\)
subject to
\(\displaystyle u_i+\sum_{\substack{D\in\mathcal H_j\\i\in D}}\lambda_{jD}\ge w_{ij}\qquad(i\in I,\ j\in J).\)
The dual is feasible: take \(\lambda=0\) and \(u_i=\max\bigl(\{0\}\cup\{w_{ij}:j\in J\}\bigr)\). Linear programming strong duality therefore supplies optimal primal and dual solutions with equal objective values.
Fix any optimal assignment \(x\) and any optimal dual solution \((u,\lambda)\).
Define the dual slacks
\(\displaystyle h_{ij}=u_i+\sum_{\substack{D\in\mathcal H_j\\i\in D}}\lambda_{jD}-w_{ij}\ge0.\)
The dual objective minus the primal objective equals
\(\displaystyle \sum_i u_i\left(\mu_i-\sum_jx_{ij}\right) +\sum_j\sum_{D\in\mathcal H_j}\lambda_{jD} \left(\nu_jg_j(D)-\sum_{i\in D}x_{ij}\right) +\sum_{i,j}h_{ij}x_{ij}. \)
Every summand is nonnegative by primal and dual feasibility. Strong duality makes their sum zero, so every summand vanishes. In particular:
Set
\(\displaystyle s_{ij}=u_i-a_{ij},\qquad v_j=\sum_{D\in\mathcal H_j}g_j(D)\lambda_{jD}.\)
These salaries are permitted because signed rates are allowed. They satisfy \(a_{ij}+s_{ij}=u_i\), including on every positive assignment. Both \(u_i\) and \(v_j\) are nonnegative.
It remains to verify the firm payoff identity. Since \(h_{ij}x_{ij}=0\),
\(\displaystyle \sum_i(c_{ij}-s_{ij})x_{ij} =\sum_i(w_{ij}-u_i)x_{ij} =\sum_{D\in\mathcal H_j}\lambda_{jD}\sum_{i\in D}x_{ij}. \)
Quota complementarity now gives
\(\displaystyle \sum_i(c_{ij}-s_{ij})x_{ij} =\sum_{D\in\mathcal H_j}\lambda_{jD}\nu_jg_j(D) =\nu_jv_j. \)
Thus all stipulated support and outside-option conditions hold.
Fix any proposed deviation involving firm type \(j\), mass \(0<q\le\nu_j\), bundle \(y\in qP_j\), and salary rates \(r_i\).
Dual feasibility gives
\(\displaystyle w_{ij}-u_i\le \sum_{\substack{D\in\mathcal H_j\\i\in D}}\lambda_{jD}. \)
Multiplying by \(y_i\ge0\), summing over workers, and applying the quotas for \(y\in qP_j\), we obtain
\(\displaystyle \sum_i(w_{ij}-u_i)y_i \le\sum_{D\in\mathcal H_j}\lambda_{jD}\sum_{i\in D}y_i \le q\sum_{D\in\mathcal H_j}\lambda_{jD}g_j(D) =qv_j. \)
This bound holds for every such bundle, including those satisfying the additional recruitment bounds \(y_i\le\mu_i\).
Suppose the participating workers weakly prefer the deviation. For each \(i\) with \(y_i>0\), define
\(\displaystyle \delta_i=a_{ij}+r_i-u_i\ge0,\)
and put \(\delta_i=0\) when \(y_i=0\). The deviating firms’ payoff satisfies
\(\displaystyle \sum_i(c_{ij}-r_i)y_i =\sum_i(w_{ij}-u_i)y_i-\sum_i\delta_i y_i \le qv_j-\sum_i\delta_i y_i. \)
There are two possibilities required by the definition of a block:
Hence no block exists. This proves stability, including deviations that recruit currently assigned workers or replace the firms’ entire bundle.
The algorithm is:
The primal has \(mn=m(\tau-m)\) variables and \(n+K=\tau-m+K\) inequalities, apart from nonnegativity. The dual has the reversed numbers of variables and inequalities.
For a conservative encoding bound, put \(d=m(\tau-m)+(\tau-m)+K+1\). Both LPs can be encoded densely in \(O(d^2+dL)\) bits: their constraint matrices have only zero and one entries, and the rational sums \(a_{ij}+c_{ij}\) and products \(\nu_jg_j(D)\) have bit lengths bounded by \(O(L)\).
We use the standard exact rational LP theorem: explicitly encoded rational linear programs can be solved in polynomial bit time. This applies to the LPs above, whose feasibility and finite optimal values have already been verified. See the discussion of polynomial bit complexity in [Dadush–Huiberts–Natura–Végh](https://link.springer.com/article/10.1007/s10107-023-01956-2).
Consequently, the total running time is
\(\displaystyle \operatorname{poly}\bigl(m(\tau-m)+\tau+K,\ L\bigr) \subseteq (m\tau+\tau+K+L+1)^{O(1)}\)
bit operations. Exact rational outputs have polynomial encoding length, and their reconstruction also takes polynomial time. There is no expansion into individual workers or firms.
Under the stated hypotheses, the algorithm always returns an optimal assignment with stable support; the “no such support exists” outcome never occurs.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the specified divisible problem is solvable in polynomial bit time, and every optimal assignment admits stable support. No major or minor mathematical issues were found.
The primal LP correctly represents feasibility. Since every firm mass satisfies \(\nu_j>0\), the condition \(x_{\cdot j}\in\nu_jP_j\) is equivalent to the listed inequalities
\[
\sum_{i\in D}x_{ij}\le \nu_jg_j(D).
\]
There are no omitted assignment constraints.
The zero assignment is feasible because every quota is nonnegative. Worker constraints and nonnegativity imply \(0\le x_{ij}\le\mu_i\), so the feasible region is bounded, even when an individual \(P_j\) is unbounded. It is also closed. Thus the linear objective attains a finite maximum. Signed values cause no difficulty.
The empty-side case is handled correctly. With no firms there is no possible block; with no workers, every bundle has zero value and cannot yield a strict improvement over zero payoffs.
The dual has the correct variables, signs, objective coefficients, and constraints. Each variable \(x_{ij}\) contributes to worker constraint \(i\) and precisely those quota constraints for firm \(j\) whose sets contain \(i\).
The proposed feasible dual point satisfies every constraint: with \(\lambda=0\), the chosen \(u_i\) is nonnegative and at least every \(w_{ij}\).
The invocation of LP strong duality is valid. The primal is feasible with finite optimum, and the dual is feasible. Consequently, optimal dual solutions exist and have the same objective value as primal optima.
The statement “Fix any optimal assignment” is justified: any optimal primal solution and any optimal dual solution have zero duality gap, so the subsequent complementarity argument applies to every optimal assignment.
The displayed duality-gap identity is algebraically correct. All its summands are nonnegative:
Because their finite sum is zero, every summand vanishes. All three stated complementarity consequences follow, including the requirement that a worker type with unused mass receives zero payoff.
The salary definition \(s_{ij}=u_i-a_{ij}\) satisfies the worker payoff identity on every assigned pair. Signed salary rates are expressly permitted. The definition
\[
v_j=\sum_{D\in\mathcal H_j}g_j(D)\lambda_{jD}
\]
also guarantees \(v_j\ge0\).
The firm payoff calculation is correct. The equality replacing \(w_{ij}-u_i\) by the sum of quota multipliers is justified after multiplication by \(x_{ij}\), because \(h_{ij}x_{ij}=0\). Reordering the finite sums is valid. Quota complementarity then gives exactly the required identity
\[
\sum_i(c_{ij}-s_{ij})x_{ij}=\nu_jv_j.
\]
These arguments also cover empty quota families and zero quotas.
The deviation argument covers every firm type, every real mass \(0<q\le\nu_j\), and every admissible real bundle.
Dual feasibility gives the stated coordinatewise upper bound on \(w_{ij}-u_i\). Multiplication by \(y_i\ge0\) preserves the inequality. Since \(y\in qP_j\), each quota sum is at most \(qg_j(D)\); multiplication by the nonnegative \(\lambda_{jD}\) therefore preserves the second inequality. The resulting bound
\[
\sum_i(w_{ij}-u_i)y_i\le qv_j
\]
is valid.
The proof establishes this bound for a larger collection of bundles than the block definition permits. Consequently, omitting the recruitment bounds \(y_i\le\mu_i\) from this calculation does not leave a gap.
For participating workers, weak improvement implies \(\delta_i\ge0\). Defining \(\delta_i=0\) on nonparticipating types preserves the weighted payoff identity because those types have \(y_i=0\).
Both forms of strict improvement are correctly excluded:
Thus the argument rules out every block in the task’s definition, including recruitment of currently assigned workers and replacement of the deviating firms’ entire bundle.
The variable and constraint counts are correct: the primal has \(m(\tau-m)\) variables and \(\tau-m+K\) inequalities apart from nonnegativity; the dual reverses these counts.
The dense encoding bound \(O(d^2+dL)\) is valid. Matrix coefficients are zero or one, and forming \(a_{ij}+c_{ij}\) and \(\nu_jg_j(D)\) requires only polynomially many bits. Explicit set membership can also be processed within the stated polynomial bound.
The exact rational LP theorem is applicable: both programs are explicitly encoded rational LPs with feasible, finite optima. The cited article’s introduction confirms polynomial LP complexity in the bit description length. [Dadush–Huiberts–Natura–Végh](https://link.springer.com/article/10.1007/s10107-023-01956-2).
Polynomial-length rational optimal solutions can be returned, and the finite sums and differences constructing salaries and payoffs preserve polynomial output length and computation time. The stated running time
\[
\operatorname{poly}\bigl(m(\tau-m)+\tau+K,L\bigr)
\]
therefore follows. It does not require expanding rational masses into individuals.
The proof never uses crossing-submodularity. Its stronger claim for arbitrary explicitly listed nonnegative upper quotas is justified by the same argument.
The output fully resolves the assigned question. No additional mathematical clarification or repair 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.