| paper | The Core of Housing Markets from an Agent's Perspective: Is It Worth Sprucing Up Your Home? |
| authors | Ildikó Schlotter, Péter Biró, T. Fleiner |
| venue | WINE 2021 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even with strict linear preferences, equal dyadic masses, and \(\eta=\mu_a\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite agent and house types \(T\), rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), a preference order for each type over house types, and \(\mu_t\) units of house type \(t\), decide whether there exists a mass assignment \(x\ge 0\) with row and column sums \(\mu\), no nonzero blocking flow, and \(x_{ab}\ge\eta\) for designated types \(a,b\) and rational \(0<\eta\le\mu_a\).
A type-symmetric high-multiplicity Shapley–Scarf market: type \(t\) carries agent mass \(\mu_t\), owns house mass \(\mu_t\), and \(x_{tu}\) is the mass of type-\(t\) agents assigned house type \(u\); maximize or threshold \(x_{ab}\) subject to mass balance and the continuum-core blocking-flow condition.
The blocking-flow model permits a type's mass to realize both orientations of a gadget, so the proposed threshold problem is not yet known to preserve the discrete reduction; the proponent flags this issue but does not resolve it.
fatal: False
The mirror directly covers the Arc in Core component of Theorem 1 and naturally extends to its Forbidden Arc in Core and Agent Trading in Core variants; it leaves the improvement, Stable Roommates, strict-core, and Max Core results untreated.
My strongest positive case is a high-multiplicity version of the paper’s Arc in Core problem.
The relevant anchor is Theorem 1, proved in this paper by reduction from Acyclic Partition. It states that each of the following is NP-complete, even when every agent has a strict preference order: deciding whether some core allocation contains a given arc \((a,b)\) (Arc in Core); deciding whether some core allocation avoids \((a,b)\) (Forbidden Arc in Core); and deciding whether some core allocation makes a designated agent trade (Agent Trading in Core). I use the first of these as the anchor.
Call the continuous problem Mass-Arc-in-Core\(_\infty\). An instance has a finite set \(T\) of agent and house types, rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and for each type \(t\), a preference order over the house types. Type \(t\) also owns \(\mu_t\) units of house type \(t\). Thus a type is a complete profile: its endowment class and its preferences over all house classes.
A continuous allocation is a matrix \(x=(x_{tu})_{t,u\in T}\), where \(x_{tu}\) is the mass of type-\(t\) agents receiving a house of type \(u\). It must satisfy \(\sum_u x_{tu}=\mu_t\) and \(\sum_t x_{tu}=\mu_u\). Every individual still receives one whole house; only the aggregate assignment is divisible.
The appropriate continuum core condition is defined by blocking flows. A block is a nonzero collection \(z_{tuv}\ge 0\), where \(z_{tuv}\) is mass of type \(t\) agents currently receiving house type \(u\) and wanting house type \(v\), such that
\(\sum_v z_{tuv}\le x_{tu}\) for every \(t,u\);
the amount of each house type requested equals the amount owned by participating agents of that type,
\(\sum_{t,u}z_{tuv}=\sum_{u,w}z_{vuw} \)
for every \(v\); and \(u\prec_t v\) whenever \(z_{tuv}>0\). A continuous allocation is in the core if no such nonzero blocking flow exists. This is exactly the measurable, type-symmetric analogue of a coalition trading its houses along improving cycles.
Given two types \(a,b\) and a rational threshold \(\eta\le\mu_a\), Mass-Arc-in-Core\(_\infty\) asks whether there is a core allocation \(x\) with \(x_{ab}\ge\eta\). The special case \(\eta=\mu_a\) asks whether the entire \(a\)-population can receive houses of class \(b\); smaller \(\eta\) asks whether a positive mass of that population can do so. Equivalently, one can maximize \(x_{ab}\) over continuous core allocations.
This is a genuine population continuization. The mass is not merely a coefficient in a fixed score: it is the active assignment variable, and the core constraint quantifies over positive-mass coalitions. Clearing denominators gives the high-multiplicity dictionary. If \(\mu_t=n_t/N\) and \(x_{tu}\) is rational, multiplying by a common denominator produces a finite market with many identical copies of each type. Conversely, a type-symmetric finite allocation normalizes to such an \(x\). The blocking-flow definition is designed so that finite blocking cycles and positive-mass continuum blocks correspond after this normalization.
A convincing regime is a large kidney-exchange or centralized housing market. Millions of patient–donor pairs or residents may fall into a few hundred or thousand clinically or administratively indistinguishable profiles: same relevant compatibility characteristics, same preference ordering over house classes, same acceptability thresholds, and the same endowment class. The population may therefore have \(N=M\tau\) individuals with \(M\) large and \(\tau\ll N\) distinct types. The meaningful question is not whether one named patient receives one named kidney, but whether a positive fraction of a clinically defined class can receive a specified class of houses in some core outcome.
The authors should recognize this as their problem. It keeps their housing-market object, the same core solution concept, the same exchange interpretation, and the same “can this participant obtain this house?” question. It changes only the unit of description from an individually named participant to a repeated agent class. It is not a relaxation to fractional houses or lotteries: \(x_{tu}\) records the distribution of integral house assignments across a large population.
I would expect this mirror to fall in Class B, with hardness likely transferring. The reduction behind Theorem 1 encodes the hard instance in the directed preference structure generated by the input graph \(D\), not in the sheer number of separately named voters. The crucial obstruction is the existence of directed cycles in the preference/acceptability graph and the induced two-way acyclic partition. Replicating each gadget role with many identical agents should preserve that type-level graph. Thus the natural conjecture is that Mass-Arc-in-Core\(_\infty\) remains NP-hard, perhaps even for strict orders over house classes and a fixed positive threshold such as \(\eta=\mu_a\).
That transfer is not automatic. The main proof obligation is to show that fractional splitting of a type cannot create a continuous core allocation that has no finite counterpart. The discrete reduction assigns each gadget to one of two acyclic sides; a continuum allocation could potentially split a gadget’s mass between both sides. A support-preserving rounding theorem, or a direct argument that any successful fractional allocation induces an integral acyclic partition, would establish hardness transfer. If such a theorem fails, the problem could instead become tractable through a flow or LP formulation. That uncertainty is a feature of the proposed mirror, not a reason to reject it: it asks exactly whether population multiplicity was carrying the hardness.
The weakest point is the change from “some named agent \(a\) receives \(b\)” to “a positive mass of type-\(a\) agents receives house type \(b\).” In an atomless population, a singleton agent has measure zero, so retaining the literal named-agent predicate would be vacuous. The positive-mass version is therefore a necessary co-modification, but it is still recognizable as the same economic question at the scale relevant to a repeated population. A second weakness is that the paper’s strict individual rankings distinguish named houses, whereas genuine high multiplicity requires houses within a class to be indistinguishable; the mirror should therefore be stated over type-level strict or partial orders, not advertised as preserving every individual tie-breaking detail.
The natural follow-up questions are whether the threshold problem is NP-complete for \(\eta=\mu_a\), whether maximizing \(x_{ab}\) admits an LP or approximation algorithm, whether the same construction yields continuous Forbidden-Arc-in-Core and Mass-Agent-Trading variants, and whether finite markets can be rounded from a continuous solution with additive error depending only on \(\tau\) and the denominator size. That is a substantive continuous-computational programme anchored directly in the paper’s Theorem 1.
The strongest negative case is that Theorem 1’s hardness is tied to one-to-one identity, not merely to population size. In the reduction, each gadget role occurs once. The forced arc \((a^\star,b^\star)\) determines a single permutation cycle, and each \(v_i\) must choose exactly one of two orientations. That binary choice is what encodes Acyclic Partition.
Replicating every role into a type of mass does not preserve this argument. If houses remain individually named, copies are not genuinely the same type and the population has not been continuized. If houses are quotiented into classes, the designated arc disappears and must be replaced by a threshold such as \(x_{a^\star b^\star}\ge\eta\). Taking \(\eta=\mu_{a^\star}\) asks whether every \(a^\star\)-agent receives a \(b^\star\)-house; taking \(0<\eta<\mu_{a^\star}\) asks whether a positive fraction does. Neither is the paper’s question about one agent.
More seriously, the replicated gadget can split: a fraction \(\lambda_i\) of type \(c_i/d_i\) may realize one orientation and the remainder the other. The proof’s crucial “exactly one of these alternatives holds” inference then fails. The proposed blocking flow balances masses, but it does not force every copy of a type to make the same binary choice. A threshold on the distinguished arc does not repair this. Enforcing all-or-nothing type assignments would restore the reduction only by imposing an additional indivisibility constraint, effectively undoing the continuum model.
Thus the proposed problem is not yet a mirror of Arc in Core; it is a new mass-transport problem with a newly chosen threshold and a newly defined aggregate notion of possibility. A kidney-exchange interpretation is also weak: pair-specific compatibility and donor identity are precisely what make those markets non-anonymous, while collapsing them into clinical types changes the exchange problem.
That is the best case against it, but it is not decisive. The authors could reasonably study whether the continuous core admits a support-preserving integrality theorem, or whether fractional splitting destroys the reduction. Either outcome is computationally meaningful under the programme’s rules. Consequently, I cannot honestly sustain the universal claim that no worthwhile mirror exists: the proponent’s Mass-Arc-in-Core formulation is a legitimate, recognisable high-multiplicity question, even though its connection to Theorem 1 still requires substantial new work.
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.