| paper | Diversity Constraints in Public Housing Allocation |
| authors | Nawal Benabbou, Mithun Chakraborty, Vinh Ho Xuan, J. Sliwinski, Yair Zick |
| venue | ATAL 2018 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: The mass-assignment decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,p,l,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
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 high-multiplicity public-housing assignment model in which \(\mu_\theta\) is population mass of complete applicant type \(\theta\), \(x_{\theta j}\) is mass receiving an integral apartment from class \(j\), \(\rho_j\) is per-capita apartment supply, and \(\lambda_{pq}\) is a per-capita diversity cap; welfare is \(\sum_{\theta,j}u_{\theta j}x_{\theta j}\).
It directly mirrors the AssignTC decision and optimization core of Theorem 3.2; it does not claim to transfer the specific BCMatching approximation in Theorem 3.4, the finite-agent flow theorem in Theorem 3.6, the price bounds in Theorems 4.2 and 4.5, or the simulations.
The strongest positive case is a single lead mirror of Theorem 3.2.
Theorem 3.2, proved in this paper rather than cited, states that the decision version of AssignTC is NP-complete. An instance contains agents partitioned into types \(N_1,\ldots,N_k\), items partitioned into blocks \(M_1,\ldots,M_l\), utilities \(u(i,j)\), type-block capacities \(\lambda_{pq}\), and a welfare threshold \(U\). The question is whether there is a matching assigning each agent and item at most once, respecting every capacity \(\lambda_{pq}\), with total utility at least \(U\). Membership in NP is immediate; NP-hardness is proved by a polynomial reduction from Bounded Color Matching, representing each graph edge as an agent, its color as the agent type, and using two item blocks to encode the matching structure.
I would mirror this with Continuous Type-Constrained Assignment, motivated by a large public-housing authority allocating a very large stock of apartments. The many agents are households, but the relevant population types are complete applicant profiles: ethnicity or other quota attribute, household size, income category, workplace region, eligibility, and the resulting utility vector over apartment categories. A type \(\theta\) therefore contains every feature used by the allocation rule. If \(\Theta\) is the finite set of such profiles, the society is a distribution \(\mu=(\mu_\theta)_{\theta\in\Theta}\), where \(\mu_\theta\) is the fraction of applicants of type \(\theta\). A plausible regime has millions of applicants but perhaps dozens or hundreds of recurring profiles, so \(N\gg|\Theta|\).
Let \(J\) be a finite catalogue of apartment classes, partitioned into blocks \(J_1,\ldots,J_l\), with \(\rho_j\) the per-capita supply of class \(j\). These are still indivisible apartments for individuals; \(\rho_j\) records the mass of apartments of that class in a large replicated housing stock. Let \(g(\theta)\) be the quota group of type \(\theta\), and let \(\lambda_{pq}\) be the per-capita upper bound on group \(p\) receiving apartments from block \(q\). The utility of type \(\theta\) for class \(j\) is \(u_{\theta j}\).
The precise decision problem is:
Given rational \(\mu_\theta,\rho_j,\lambda_{pq},u_{\theta j}\), and a welfare threshold \(U\), does there exist a nonnegative assignment measure \(x_{\theta j}\) such that
\( \sum_j x_{\theta j}\le \mu_\theta \) for every population type,
\( \sum_\theta x_{\theta j}\le \rho_j \) for every apartment class,
\( \sum_{\theta:g(\theta)=p}\sum_{j\in J_q}x_{\theta j}\le\lambda_{pq} \) for every quota-group/block pair,
and \( \sum_{\theta,j}u_{\theta j}x_{\theta j}\ge U \)?
A solution is the matrix \(x\), together with its measurable realization: an atomless subset of each type-\(\theta\) population of mass \(x_{\theta j}\) receives one whole apartment of class \(j\). Thus \(x_{\theta j}\) is an aggregate mass, not a fractional apartment or a lottery assigned to an individual. Every individual still receives an integral bundle.
This is a genuine continuous-population version of the paper’s problem. It retains the same agents, goods, blocks, type-based caps, and utilitarian objective. The co-modification is exactly the one forced by high multiplicity: apartment supplies and quota capacities become per-capita quantities. Rational finite instances embed by setting \(\mu_\theta=n_\theta/N\), \(\rho_j=r_j/N\), and \(\lambda_{pq}=L_{pq}/N\).
The expected classification is Class A. The continuous problem is the explicit linear program
\( \max\sum_{\theta,j}u_{\theta j}x_{\theta j} \)
subject to the constraints above, and is therefore solvable in polynomial time in the number of complete types, apartment classes, blocks, quota groups, and input bit length. When quota groups coincide with complete types, it reduces further to a min-cost-flow formulation; with several preference types sharing one quota group, it remains an ordinary polynomial-size LP.
This is exactly the kind of phenomenon the programme wants to expose. The discrete NP-hardness in Theorem 3.2 depends on integral matching: an edge-agent must either take a particular item or not, and items cannot be split. In the continuum, a positive-mass type can be partitioned among several apartment classes while every individual in those portions receives one integral apartment. The reduction’s combinatorial matching obstruction disappears, even though the type-block diversity constraints and the welfare objective remain.
The authors should recognise this as their problem rather than as a generic fractional-allocation exercise: it is still welfare-maximising assignment under hard diversity caps. The natural scenario is not a seven-person committee but a national housing, school, or employment market with many repeated applicant profiles and replicated supply categories.
The main weakness is that real applicants may have highly idiosyncratic preferences, making \(|\Theta|\) comparable to \(N\). Also, if apartments must remain individually named and cannot be aggregated into recurring classes, the LP may look like an outcome-space relaxation rather than population continuization. The case survives only by insisting on a credible high-multiplicity regime—large cohorts of households with identical relevant profiles and per-capita supplies—and by keeping individual apartments indivisible. It does not claim that every public-housing instance has a useful continuum limit; it claims that the NP-complete problem studied in Theorem 3.2 has a natural, computationally meaningful regime in which its hardness dissolves.
The next questions would be finite-\(N\) rounding with additive welfare guarantees, parameterized complexity in \(|\Theta|\), and identifying geographic or eligibility constraints that prevent this LP collapse and produce genuinely continuum-specific hardness.
The strongest negative case is that Theorem 3.2’s hardness is not really caused by population multiplicity. In its reduction, every graph edge becomes an agent with a distinct utility vector: edge \((a,b)\) values its corresponding item \(j_b\), receives special padding utility, and values other items differently. Under ChoCo’s definition of complete type, two same-coloured edge-agents are therefore generally different types. Preserving named apartments and arbitrary utilities leaves essentially one type per agent, so the population has no meaningful high-multiplicity limit.
The proponent’s rescue is to replace individual apartments by interchangeable classes. But that imposes a substantial extra symmetry: utilities become constant within each class, and the arbitrary incidence structure responsible for the reduction disappears. The resulting \(x_{\theta j}\) is a capacitated transportation LP, closely related to the paper’s already tractable block-uniform special case in Theorem 3.6. One could therefore argue that this is not a continuous counterpart of general AssignTC, but a restricted, outcome-coarsened problem whose difficulty has been removed by changing the goods.
That objection does not survive the programme’s rules, however. The paper itself studies block-level utilities and explicitly lists large public-housing, school, and course-allocation markets as applications. A housing authority with many recurring applicant profiles and repeated apartment classes is a legitimate high-multiplicity regime. Scaling apartment supplies and quota capacities per capita is precisely the kind of co-modification forced by population continuization; it does not fractionalize anyone’s bundle. An atomless mass \(x_{\theta j}\) can be realized by assigning whole apartments to measurable subpopulations.
Nor is the continuous question invalid merely because its answer is an easy LP or because the discrete hardness vanishes. That is exactly a Class A outcome the programme seeks. It also supports finite-population rounding, parameterized analysis in the number of complete profiles, and a precise explanation of why the Bounded Color Matching reduction depends on individual incidence patterns rather than mass.
Thus the negative case can reject only mirrors that retain arbitrary named-item utilities while pretending the population has few types. It cannot defeat the stronger repeated-profile, repeated-housing-class model. Theorem 3.2 is therefore a surviving anchor, and I cannot honestly defend the universal claim that this paper has no worthwhile continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.