Diversity Constraints in Public Housing Allocation (d4-conf-atal-2018-0349)

Given a finite set of complete applicant types \(\Theta\) with population distribution \(\mu\), apartment classes \(J\) partitioned into blocks \(J_1,\ldots,J_l\), per-capita supplies \(\rho_j\), quota-group map \(g:\Theta\to[p]\), per-capita type-block capacities \(\lambda_{pq}\), utilities \(u_{\theta j}\), and threshold \(U\), does there exist a nonnegative mass assignment \(x_{\theta j}\) satisfying \(\sum_j x_{\theta j}\le\mu_\theta\), \(\sum_\theta x_{\theta j}\le\rho_j\), \(\sum_{\theta:g(\theta)=p}\sum_{j\in J_q}x_{\theta j}\le\lambda_{pq}\), and \(\sum_{\theta,j}u_{\theta j}x_{\theta j}\ge U\)?

A society is given by its support: a list \(\Theta\) of \(\tau\) complete applicant types with positive binary rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Each type specifies its quota group and its entire utility vector; types in the same quota group may have different utilities.
There are \(m\) apartment classes \(J\), partitioned into nonempty blocks \(J_1,\ldots,J_l\), and a surjective quota-group map \(g:\Theta\to\{1,\ldots,p\}\). Supplies \(\rho_j\), utilities \(u_{\theta j}\), and capacities \(\lambda_{aq}\) are nonnegative binary rationals, with \(\lambda_{aq}\leq\sum_{j\in J_q}\rho_j\); the threshold \(U\) is a positive binary rational. Let \(L\) be the total input bit length.
An assignment consists of divisible masses \(x_{\theta j}\in\mathbb{R}_{\geq0}\); applicants may remain unassigned and supplies may remain unused. Feasibility requires \(\sum_{j\in J}x_{\theta j}\leq\mu_\theta\), \(\sum_{\theta\in\Theta}x_{\theta j}\leq\rho_j\), and \(\sum_{\theta:g(\theta)=a}\sum_{j\in J_q}x_{\theta j}\leq\lambda_{aq}\) for every applicable index. The decision problem asks whether a feasible assignment satisfies \(\sum_{\theta\in\Theta}\sum_{j\in J}u_{\theta j}x_{\theta j}\geq U\).

Is this mass-assignment decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,p,l,L\), or is it \(\mathrm{NP}\)-hard?

For indivisible applicants and apartments, assignment with these quota-group–block upper capacities is \(\mathrm{NP}\)-complete. The discrete problem is polynomial-time solvable when utilities are identical within each quota group, or when each applicant's utility is constant within each block. No complexity result for the exact mass problem is assumed here.

Result

The mass-assignment decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,p,l,L\). This holds for arbitrary utilities within quota groups and blocks.

1. Exact linear feasibility formulation

Introduce one real variable \(x_{\theta j}\) for each explicitly listed type \(\theta\in\Theta\) and apartment class \(j\in J\). Consider the following system:

• Nonnegativity: \(\displaystyle -x_{\theta j}\leq 0\) for every \(\theta,j\).
• Type masses: \(\displaystyle \sum_{j\in J}x_{\theta j}\leq\mu_\theta\) for every \(\theta\).
• Supplies: \(\displaystyle \sum_{\theta\in\Theta}x_{\theta j}\leq\rho_j\) for every \(j\).
• Quotas: \(\displaystyle \sum_{\theta:g(\theta)=a}\sum_{j\in J_q}x_{\theta j}\leq\lambda_{aq}\) for every \(a,q\).
• Utility threshold: \(\displaystyle -\sum_{\theta\in\Theta}\sum_{j\in J}u_{\theta j}x_{\theta j}\leq -U\).

This is a system of linear inequalities with rational coefficients.

Its feasibility is equivalent to a yes answer to the problem. Indeed, an assignment meeting the threshold satisfies every displayed inequality. Conversely, any real solution gives nonnegative assignment masses satisfying exactly the stipulated mass, supply, quota, and utility conditions. There are no additional integrality or individual assignment restrictions in the mass problem.

2. Polynomial encoding size

The number of variables is \(n=\tau m\). Including nonnegativity, the number of inequalities is \(r=\tau m+\tau+m+pl+1\).

The explicit support representation is essential: variables are introduced only for the \(\tau\) listed types, without enumerating other possible types.

Write the system as \(Ax\leq b\). Every entry of \(A\) is either \(0\), \(1\), \(-1\), or a negated input utility. Every entry of \(b\) is either zero or an input mass, supply, capacity, or negated threshold. Each input numerical value used in this representation occurs once; the remaining entries have constant encoding length.

Consequently, even a dense encoding has total binary length \(B=O(L+rn+n+r)\), which is polynomial in \(m,\tau,p,l,L\). The matrix can also be constructed in polynomial time: each quota coefficient is determined by checking the explicitly given group and block memberships.

No expansion proportional to numerical denominators or to a hypothetical number of individual applicants is needed.

3. Exact polynomial-time decision

We apply the standard polynomial-time rational linear feasibility theorem: given an explicitly encoded rational matrix \(A\) and rational vector \(b\), whether there exists a real vector \(x\) satisfying \(Ax\leq b\) can be decided exactly in time polynomial in the total binary encoding length. This is the linear-programming theorem established by Khachiyan. [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239)

Its hypotheses hold here:

• All coefficients and right-hand sides are rational and explicitly encoded.
• The system has polynomially many variables and inequalities.
• Its total binary encoding length is polynomial in the requested parameters.

Applying this theorem therefore decides the mass-assignment problem in polynomial time. Incorporating the utility threshold as an inequality makes this an exact feasibility decision, including instances where the maximum utility equals \(U\).

4. Relation to the discrete problem

The stated discrete hardness does not contradict this conclusion. Indivisible assignment imposes discrete restrictions on assignment variables. Here a type’s mass may be divided among apartment classes, and every restriction is linear.

Neither identical utilities within quota groups nor constant utilities within blocks are needed for the argument. The polynomial-time conclusion also does not assert a strongly polynomial algorithm: dependence on the binary input length \(L\) is allowed, as requested.

Thus the target question is resolved: the mass-assignment problem belongs to \(\mathrm{P}\). Under polynomial-time many-one reductions, it could also be \(\mathrm{NP}\)-hard only if \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned question correctly. The argument establishes membership in \(\mathrm{P}\) for the explicitly represented mass-assignment problem. No major or minor mathematical issues were found.

• The linear formulation is exact. Each variable corresponds to one listed type and apartment class. Nonnegativity, type-mass bounds, supply bounds, and quota bounds match the task directly. Multiplying the utility-threshold inequality by negative one reverses its direction correctly. Both directions of the claimed feasibility equivalence hold, without additional assumptions about utilities or indivisibility.

• The variable and constraint counts are correct. There are \(\tau m\) variables and \(\tau m+\tau+m+pl+1\) inequalities. The quota constraints include every quota-group–block pair. Types within a quota group retain their distinct utility coefficients.

• The encoding-size bound is valid. Each supplied numerical datum appears in its corresponding coefficient or right-hand-side position; structural coefficients have constant encoding length. Negating utilities and the threshold adds at most constant overhead per entry. Consequently, the stated dense-encoding bound \(B=O(L+rn+n+r)\) is polynomial in the requested parameters. Group and block memberships suffice to construct the quota coefficients in polynomial time. No enumeration beyond the listed support is required.

• The cited theorem is stated sufficiently precisely and applies. Exact feasibility of an explicitly encoded rational linear-inequality system is decidable in time polynomial in its binary encoding length. The prover verifies rationality, explicit representation, and polynomial encoding size. The cited Khachiyan publication’s abstract confirms exact linear-programming algorithms with polynomial dependence on binary input length. [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/rus/zvmmf5239)

The theorem does not require strict feasibility, integral coefficients, or a positive gap between attainable utility and the threshold. Its application therefore covers equality at \(U\).

• Boundary cases do not undermine the argument. Zero supplies, capacities, and utilities remain valid rational coefficients. Unused supply and unassigned mass are permitted by the upper-bound inequalities. Empty intersections between a quota group and a block produce valid quota constraints. No additional edge-case argument is needed.

• The complexity conclusion follows. Constructing the system and deciding its feasibility both take polynomial time in \(m,\tau,p,l,L\). The comparison with discrete hardness is accurate: the proof uses the divisible-variable domain stipulated by the task. The final qualification concerning \(\mathrm{NP}\)-hardness assumes polynomial-time many-one reductions explicitly and is correct.

No clarification or repair is required.

⟨structured verdict parsed — rendered above⟩