| paper | Host Community Respecting Refugee Housing |
| authors | — |
| venue | AAMAS 2023 |
| filed under | coalition · matching |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.7
statement extracted from the paper’s text layer
Given finite host types \(H\), housing types \(P\), rational capacities \(b_p\), refugee mass \(\rho\), costs \(c_p\), exposures \(w_{hp}\), and host acceptance intervals \([\ell_h,u_h]\) with \(d_h=\sum_{p\in P}w_{hp}b_p>0\), decide whether there is \(x\in\mathbb{R}_{\geq0}^{P}\) such that \(x_p\leq b_p\), \(\sum_{p\in P}x_p=\rho\), and \(\ell_h\leq \sum_{p\in P}w_{hp}x_p/d_h\leq u_h\) for every \(h\in H\); optionally minimize \(\sum_{p\in P}c_px_p\).
A high-multiplicity municipality model with host types sharing complete interval preferences and regular local exposure vectors, housing-type capacities as masses, and allocation variables \(x_p\) assigning refugee mass to repeated housing environments.
The mirror covers anonymous, interval-approval housing feasibility represented by Theorem 3.7; Theorem 3.11 supports the same constraint language but is not a separate anchor, while the fully hedonic and diversity results remain outside it.
The strongest positive case is for the paper’s anonymous model, anchored on Theorem 3.7, proved in this paper: ARH is NP-complete even on maximum-degree-three topologies when every inhabitant approves an interval. I would call its continuous counterpart Density-Respecting Anonymous Refugee Housing (lead mirror).
An instance has a finite catalogue \(H\) of host-neighbourhood types and \(P\) of available-housing types. A host type \(h\) comprises residents with the same interval \([\ell_h,u_h]\) of acceptable refugee density and the same local exposure to the housing catalogue. A housing type \(p\) has capacity \(b_p\), and \(w_{hp}\geq0\) says how much \(p\)-capacity lies in a representative \(h\)-resident’s relevant neighbourhood. These numbers may be sparse—indeed each \(h\) can interact with at most three housing types, retaining the spirit of the theorem’s degree bound. All data are rational.
The society contains a mass \(\rho\) of otherwise anonymous incoming refugees. A solution is a vector \(x\in\mathbb{R}_{\geq0}^{P}\), where \(x_p\) is the mass assigned to housing category \(p\), satisfying
\[
0\leq x_p\leq b_p,\qquad \sum_p x_p=\rho,
\]
and, for every host type \(h\),
\[
\ell_h\leq \frac{\sum_p w_{hp}x_p}{\sum_p w_{hp}b_p}\leq u_h.
\]
The decision question is whether such an allocation exists; the natural optimisation version minimizes \(\sum_p c_px_p\), for publicly specified placement or support costs \(c_p\). The action is still housing refugees in real accommodation. What changes is that a policymaker assigns shares of a large intake to categories of homes or districts, rather than selecting named people for named individual vacancies.
This is a genuine population continuization, not fractional housing as an outcome-space trick. Housing units, residents, and refugees remain the substantive objects; \(x_p\) represents the share of a large refugee population placed in one repeated local environment. The neighbourhood condition is now a density condition because, at this scale, “how many newcomers does a resident encounter?” is naturally “what fraction of the local housing capacity is occupied by newcomers?” This is particularly close to the paper’s own anonymous preference interpretation.
The relevant regime is not one small street with a handful of empty flats. It is a municipality, regional reception programme, or national provider operating many copies of a limited catalogue of neighbourhood environments: for example, similar estates, districts, building-and-service bundles, and resident demographic/policy profiles. A host type includes the interval preference and its exposure vector \((w_{hp})_{p\in P}\); a housing type includes its capacity, cost, and exposure profile. There may be millions of residents and a large annual intake, while the number of types is tens, hundreds, or even a moderately large planning network—still vastly below the number of people and homes. This is precisely the high-multiplicity setting: identities are irrelevant after preferences and relevant local surroundings have been recorded.
The finite model has a direct high-multiplicity interpretation. Replace every unit of capacity and every representative neighbourhood by \(K\) equivalent copies, with regular incidence proportions implementing \(w_{hp}\). An allocation \(x\) is the \(K\to\infty\) limit of placing approximately \(Kx_p\) refugees in each housing class. Conversely, a large discrete allocation induces such a density vector. Rounding will generally only preserve the interval bounds up to an additive \(O(1/K)\) boundary error, which is the honest discrete-to-continuous bridge rather than a claim of exact equivalence at every finite \(K\).
I expect Density-Respecting ARH to be Class A. It is a linear-program feasibility problem, or a linear programme with the cost objective above. That is not an evasion of Theorem 3.7’s question: it asks exactly whether all host-side anonymous acceptance constraints can be met by housing a prescribed intake, with the same interval form of preferences and even sparse local interaction. Rather, it exposes where the theorem’s reduction lives. The discrete reduction needs each variable gadget to choose one indivisible port; in the high-multiplicity regime, a category of otherwise identical placements can be split across its two relevant environments. That is the relaxation’s substantive meaning, not an accidental algebraic loophole.
There is also a clean connection to Theorem 3.11, proved here: interval-approval ARH is FPT parameterized by the number of inhabitants, via an ILP. The continuous mirror replaces its binary “put a refugee in this particular empty vertex” variables by mass variables over housing types. The same lower and upper neighbourhood constraints become linear, but integrality—and with it the need to parameterize the number of inhabitants—disappears. Thus the theorem is supporting evidence that interval approvals are the right structural language, while Theorem 3.7 supplies the sharper discrete-hardness-to-continuous-tractability contrast.
The main further questions are worthwhile rather than cosmetic: which graph blow-ups admit low-discrepancy rounding with useful finite-\(K\) guarantees; whether one can optimize welfare or relocation costs while retaining polynomial pricing; and where hardness returns when approval sets are unions of intervals, when neighbourhood exposure is endogenous, or when capacities are indivisible at a mesoscopic scale.
My weakest point is the local-topology assumption. A generic small graph from Theorem 3.7 is not automatically a convincing continuum object: a street-level placement problem may retain essential named-house correlations. The case survives because it does not claim that every ARH instance should be continuized. It identifies a concrete, administratively plausible high-multiplicity regime—repeated neighbourhood categories and aggregate intake allocation—in which the original authors should recognise the same host-respecting housing question, while the continuous formulation yields a real and informative complexity change.
I cannot make a convincing universal negative case here. The proponent’s lead mirror is not a mere fractional rephrasing of the original graph problem; it identifies a plausible high-multiplicity regime in which the paper’s anonymous acceptance condition becomes a density constraint.
There is one real objection to the stated construction. The LP constrains average exposure for each host type, whereas ARH requires every individual inhabitant to approve her realised neighbourhood. Simply taking \(K\) disjoint copies of a degree-three ARH graph does not produce fractional exposure at each copy: each still sees zero, one, two, or three refugees. Its limit is a distribution over discrete local configurations, not automatically the displayed density LP. Aggregating hosts with nonidentical local incidence would also conceal dissatisfied residents.
But that objection defeats only an overbroad claim that this LP is the high-multiplicity limit of every ARH instance. It does not defeat the better mirror. A municipality can genuinely have repeated host-and-housing environments with regular, large-scale local mixing—estates, districts, or service-and-housing bundles—where a host type includes precisely its interval preference and exposure vector, and where each member of that type has the same relevant density. In that regime, the quantity a host observes is naturally a local intake rate, not the occupancy of one named adjacent flat. The move from bounded individual degree to sparse type-level incidence is substantive, but it is not a change of question: it is the appropriate population-scale version of “can we place an intake while keeping every host community within its accepted range?”
Nor can identity rescue the negative case. In the anonymous model, refugees have no preferences and hosts care only about the number of refugees nearby. Individual identities and named vacancies are therefore not information the problem intrinsically needs; they are precisely what a high-multiplicity representation may suppress when many units share the same complete relevant description. The paper’s fully hedonic model would be much more vulnerable to an identity-based objection, but Theorem 3.7 concerns the anonymous model.
Theorem 3.11 does not supply a separate anchor needing defeat; it is supporting context. If treated as one, it reinforces rather than weakens the mirror: its binary ILP already expresses interval host constraints, and replacing particular vacancies by mass over repeated housing types removes the integrality that makes the discrete formulation nontrivial. Calling the resulting LP “too easy” is not a valid objection to continuization; identifying a clean Class-A regime is exactly one of the programme’s goals.
So the strongest negative finding is narrow: the proponent should not describe its LP as the automatic limit of arbitrary bounded-degree ARH topologies, and should state the regular-mixing/repeated-environment assumption explicitly. With that correction, Theorem 3.7 survives as a 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.