Answer: polynomial-time solvable
Theorem 1 — class: hardness
Given finitely many family types with rational masses, at most two children per type, complete grade and initial-enrollment data, preference lists of length at most two, daycare transferable quotas normalized as masses, and threshold δ>0, does there exist a mass assignment of each type to integral preference-list tuples satisfying all quota and individual-rationality constraints in which at least δ total family mass receives an assignment different from its initial tuple?
A daycare set \(D\) includes an uncapacitated dummy \(d_0\). Each type \(\theta\) is a family with \(k_\theta\in\{1,2\}\) children, grades \(g_{\theta i}\), mass \(\mu_\theta\in\mathbb{Q}_{\ge0}\), initial tuple \(\omega_\theta\in D^{k_\theta}\), and a strict joint ranking of at most two integral daycare tuples, including \(\omega_\theta\). Let \(A_\theta\) be the tuples ranked at least as highly as \(\omega_\theta\).
For every real daycare \(d\) and grade group \(H\), \(q(d,H)\in\mathbb{Q}_{\ge0}\) is a transferable quota: the total assigned mass of children with grades in \(H\) at \(d\) is at most \(q(d,H)\). Choose \(y_{\theta,a}\ge0\) for \(a\in A_\theta\), with \(\sum_{a\in A_\theta}y_{\theta,a}=\mu_\theta\), subject to these quotas. Define \(\Delta(y)=\sum_{\theta}\sum_{a\in A_\theta\setminus\{\omega_\theta\}}y_{\theta,a}\).
Target: Is deciding whether a feasible assignment has \(\Delta(y)\ge\varepsilon\), for rational \(\varepsilon>0\) (equivalently, maximizing \(\Delta(y)\)), solvable in polynomial time or NP-hard?
Known discrete result: with indivisible families, deciding whether a feasible individually rational matching different from the initial matching exists is NP-complete, even with at most two children per family and preference lists of length at most two.
Under the standard explicit encoding of the quota constraints, the problem is polynomial-time solvable. It is a rational linear program with at most two variables per type. The known NP-completeness result for indivisible families does not extend to this divisible-mass formulation.
Let \(\mathcal Q\) denote the explicitly represented set of quota pairs \((d,H)\), where \(d\) is a real daycare.
For every type \(\theta\), tuple \(a\in A_\theta\), and quota pair \((d,H)\in\mathcal Q\), define
\[ c_{\theta,a,d,H} = \left|\left\{i\in\{1,\ldots,k_\theta\}:a_i=d\text{ and }g_{\theta i}\in H\right\}\right|. \]
Thus \(c_{\theta,a,d,H}\in\{0,1,2\}\). Allocating mass \(y_{\theta,a}\) of type \(\theta\) to tuple \(a\) contributes exactly \(c_{\theta,a,d,H}y_{\theta,a}\) units to quota \((d,H)\).
The threshold problem is therefore feasibility of the following rational linear system:
\[ \sum_{a\in A_\theta}y_{\theta,a}=\mu_\theta \qquad\text{for every }\theta, \]
\[ \sum_\theta\sum_{a\in A_\theta} c_{\theta,a,d,H}y_{\theta,a} \le q(d,H) \qquad\text{for every }(d,H)\in\mathcal Q, \]
\[ y_{\theta,a}\ge 0 \qquad\text{for every }\theta\text{ and }a\in A_\theta, \]
and
\[ \sum_\theta\sum_{a\in A_\theta\setminus\{\omega_\theta\}} y_{\theta,a}\ge\varepsilon. \]
These constraints are precisely the conditions in the question, so the linear system is feasible if and only if there is an assignment with \(\Delta(y)\ge\varepsilon\).
Because every preference list contains at most two tuples, \(|A_\theta|\le 2\). Consequently, the linear program has at most \(2|\Theta|\) variables. It has \(|\Theta|\) mass-conservation equalities, \(|\mathcal Q|\) quota inequalities, one threshold inequality, and nonnegativity constraints.
All coefficients are rational numbers represented in binary, except the incidence coefficients \(c_{\theta,a,d,H}\), which belong to \(\{0,1,2\}\). Hence the total encoding length of this linear program is polynomial in the input length.
The rational linear-programming theorem states that feasibility of a finite system of rational linear equalities and inequalities can be decided in time polynomial in its total binary encoding length. Equalities may, for example, be replaced by pairs of inequalities. All hypotheses of that theorem are therefore satisfied.
It follows that deciding whether \(\Delta(y)\ge\varepsilon\) is in \(\mathrm P\).
Replacing the threshold inequality by the objective
\[ \max\sum_\theta\sum_{a\in A_\theta\setminus\{\omega_\theta\}}y_{\theta,a} \]
gives a rational linear program. Its objective is bounded above by \(\sum_\theta\mu_\theta\), because all variables are nonnegative and the variables of each type sum to \(\mu_\theta\). Thus, whenever the quota system is feasible, a finite optimum exists and can be computed in polynomial time by rational linear programming.
For a type having one admissible improvement \(a_\theta\), set \(x_\theta=y_{\theta,a_\theta}\). Then \(y_{\theta,\omega_\theta}=\mu_\theta-x_\theta\), where \(0\le x_\theta\le\mu_\theta\). Every quota constraint becomes a linear inequality in the continuous variables \(x_\theta\), and the objective becomes \(\sum_\theta x_\theta\).
In the indivisible problem, the corresponding choice is discrete: an entire family either moves or does not move. Here, arbitrary fractions of each type may move. The integrality condition responsible for the discrete combinatorial problem is absent. No total-unimodularity or integral-extreme-point argument is needed because the desired solutions themselves are fractional.
Therefore, the stated fractional transferable-quota problem is polynomial-time solvable. It could be NP-hard only under the collapse \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly identifies the divisible-mass formulation as a rational linear program. Under an explicit finite encoding of the quota constraints and grade groups, the threshold problem and optimization problem are polynomial-time solvable.
The argument is mathematically sound. The only gap concerns the input encoding: the task itself does not specify how grade groups and the collection of quota constraints are represented, while the proof assumes they are explicitly enumerable and that membership \(g_{\theta i}\in H\) is polynomial-time decidable.
Since each ranking contains at most two tuples and includes \(\omega_\theta\), the conclusion \(\lvert A_\theta\rvert\le 2\) is correct. Thus there are at most \(2\lvert\Theta\rvert\) variables.
The equations
\[
\sum_{a\in A_\theta}y_{\theta,a}=\mu_\theta
\]
exactly express the requirement that all mass of type \(\theta\) be assigned among individually rational tuples.
The coefficient
\[
c_{\theta,a,d,H}
=
\left|\left\{i:a_i=d\text{ and }g_{\theta i}\in H\right\}\right|
\]
correctly counts the number of children from one family unit whose assignment contributes to quota \((d,H)\). Because \(k_\theta\in\{1,2\}\), the stated range \(c_{\theta,a,d,H}\in\{0,1,2\}\) is correct.
The expression
\[
\sum_\theta\sum_{a\in A_\theta}
c_{\theta,a,d,H}y_{\theta,a}
\]
is precisely the total assigned child mass covered by quota \((d,H)\). Omitting the dummy daycare from these inequalities is consistent with its being uncapacitated.
The final inequality is exactly \(\Delta(y)\ge\varepsilon\). Therefore the LP feasibility problem is equivalent to the requested decision problem.
Feasibility of an explicitly given finite rational linear system is decidable in polynomial time in its binary encoding length. The displayed LP has polynomially many variables and constraints relative to an explicitly enumerated quota list. This application of rational linear programming is valid.
The objective satisfies
\[
0\le\Delta(y)\le\sum_\theta\mu_\theta.
\]
The feasible region is closed and bounded in all variables by the mass-conservation constraints, so an optimum exists whenever the system is feasible. Exact rational linear-program optimization is polynomial-time solvable.
The explanation correctly distinguishes continuous variables \(0\le x_\theta\le\mu_\theta\) from indivisible binary family decisions. Hence the cited discrete NP-completeness result does not establish hardness of this fractional formulation.
The proof assumes that the quota pairs form an explicitly enumerated finite set \(\mathcal Q\), and that the coefficients \(c_{\theta,a,d,H}\) can be generated in polynomial time. The task does not formally specify the representation of grade groups \(H\) or of the mapping \(q(d,H)\). The prover should explicitly state that every relevant pair \((d,H)\) is listed in the input and that membership \(g_{\theta i}\in H\) is polynomial-time decidable. Under this standard encoding, the conclusion follows without further mathematical work.
⟨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.