| paper | The Strong Core of Housing Markets with Partial Order Preferences |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.4 (★)
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), partial orders \(\succ_t\) over house types, and forbidden type-arcs \(F\), where type \(t\) owns mass \(\mu_t\) of house type \(t\), decide whether there exists \(x_{t,u}\ge 0\) with \(\sum_u x_{t,u}=\mu_t\), \(\sum_t x_{t,u}=\mu_u\), and \(x_{t,u}=0\) on unacceptable or forbidden arcs, such that no nonzero \(z_{t,u,v}\) with \(0\le z_{t,u,v}\le x_{t,u}\) satisfies \(v\succeq_t t\), \(v\succeq_t u\), strict preference for at least one positive-mass class, and \(\sum_{u,v}z_{q,u,v}=\sum_{t,u}z_{t,u,q}\) for every \(q\in T\); if so, output \(x\).
A clone-symmetric high-multiplicity Shapley–Scarf market: each type \(t\) fixes the complete partial order, endowment type, acceptability, and restriction data used by the model; \(\mu_t\) is both agent and house mass, \(x\) is a capacitated transportation plan, and stability is the mass version of the strong core.
The paper’s named-agent peak-set decomposition does not automatically carry over when a type’s mass is split among several house types; equivalence between the mass blocking circulation and finite replicated markets, together with a weighted peak-set lemma, remains unproved.
fatal: False
The mirror covers SCFA, including Theorem 4.4 (★), Corollary 4.5, and the forced-and-forbidden reduction in Corollary 4.6; it leaves the strategyproofness, structural, enumeration, improvement, and ILP results outside.
My strongest positive case is built around Theorem 4.4 (★), restated as Corollary 4.5. The authors prove that Algorithm SCFA solves Strong Core with Forbidden Arcs in \(O(|N|^2|E|^{1+o(1)})\) time. The conference paper defers the proof to the full version [42], but this is the authors’ own result, not a cited theorem. I would not use the paper’s strategyproofness or respecting-improvement results as computational anchors.
The natural mirror is a high-multiplicity kidney-exchange market. Let \(T\) be a finite set of complete agent types. A type includes the patient’s partial order over donor-house types, the type of the donor initially owned by the pair, and all relevant acceptability or restriction data. Let \(\mu_t\in\mathbb{Q}_{\ge 0}\) be the fraction of the population of type \(t\), with \(\sum_{t\in T}\mu_t=1\). For simplicity, type \(t\) initially owns a house of type \(t\), so there are \(\mu_t\) units of every house type \(t\). Agents of the same type are indistinguishable in every respect used by the market.
This is plausible in a deliberately typed exchange pool: many patient–donor pairs may share the same blood-group category, donor-age band, HLA-compatibility profile, acceptance thresholds, and logistical restrictions. A pool might contain \(10^5\) or more pairs but only \(10^2\)–\(10^3\) clinically meaningful types. This is not a claim that every kidney-exchange instance has low type complexity; it is a specific, sensible high-multiplicity regime supported by the paper’s own clinical motivation.
The continuous problem I would submit is:
\[ \textsc{Continuous-SCFA}_{\infty} \]
An instance consists of \(T\), the rational mass vector \(\mu\), a partial order \(\succ_t\) over house types for every \(t\in T\), and a forbidden set \(F\) of type-arcs. Write \(u\succeq_t v\) when \(u\) is weakly preferred to \(v\) under the paper’s convention. An allowed assignment arc is \((t,u)\) with \(u\succeq_t t\).
The decision variable is a mass-allocation matrix \(x\), where \(x_{t,u}\) is the mass of type-\(t\) agents receiving houses of type \(u\). It must satisfy
\[ \sum_{u\in T}x_{t,u}=\mu_t \quad(t\in T), \]
\[ \sum_{t\in T}x_{t,u}=\mu_u \quad(u\in T), \]
and \(x_{t,u}=0\) whenever \((t,u)\) is unacceptable or forbidden. Thus every agent receives one actual house and every house is allocated once; \(x\) is only the aggregate description of a measurable assignment, not a lottery over outcomes.
The allocation \(x\) is in the continuous strong core if there is no positive-mass blocking coalition. Equivalently, there must be no nonzero collection \(z_{t,u,v}\) in which \(z_{t,u,v}\) is mass of type-\(t\) agents currently holding \(u\) who deviate to houses of type \(v\), with
\[ 0\le z_{t,u,v}\le x_{t,u}, \]
\[ v\succeq_t t \quad\text{and}\quad v\succeq_t u \]
whenever \(z_{t,u,v}>0\), with strict preference \(v\succ_t u\) for at least one positive-mass class, and with conservation of the houses owned by the coalition:
\[ \sum_{u,v}z_{q,u,v} = \sum_{t,u}z_{t,u,q} \qquad(q\in T). \]
The left side is the mass of participating type-\(q\) agents, who collectively own type-\(q\) houses; the right side is the mass of coalition members receiving such houses. The task is to output such an \(x\), or report that none exists. There is no welfare objective: the objective is exactly the feasibility objective of SCFA.
This is recognisably the authors’ problem. It retains the same housing-market exchange structure, the same partial-order preferences, the same notion of blocking cycle, and the same forbidden allocation arcs. Only the population is aggregated. For rational \(\mu\), multiplying by a common denominator produces a finite market with many copies of each type; a rational \(x\) is the normalized incidence matrix of an ordinary allocation, and a \(z\)-certificate is the normalized collection of blocking cycles. Conversely, a large replicated market produces such a mass instance. The mirror is therefore a genuine high-multiplicity relaxation rather than a change to divisible outcomes or probabilistic social choice.
I expect \(\textsc{Continuous-SCFA}_{\infty}\) to be in Class A. The structural part of Algorithm SCFA uses undominated arcs, strongly connected components, dominance of arcs leaving a candidate peak set, and recursive deletion. Those are type-level operations. Its main numerical primitive is the existence of an allocation inside a submarket, implemented in the paper by perfect matching. In the continuous version, that primitive becomes rational capacitated bipartite flow or transportation feasibility:
\[ \sum_u x_{t,u}=\mu_t,\qquad \sum_t x_{t,u}=\mu_u. \]
This remains polynomial in \(|T|\), the number of type-arcs, and the encoding length of \(\mu\). The expected complexity should depend on the number of types, not on the enormous number of individual patient–donor pairs.
The main technical caveat is important. The paper’s peak sets are sets of named agents. In a mass market, a peak set may contain only part of a positive-mass type, so Theorem 3.5 and Algorithm SCFA do not automatically extend by replacing perfect matching with flow. One needs a weighted or fractional peak-set lemma showing that the recursive construction can split type mass without creating a new obstruction. That is the weakest point of the mirror, and I would present the continuous algorithm as a conjectured Class A result rather than claim it is already proved.
I nevertheless think the case survives this caveat. The difficulty is precisely the sort of aggregate matching structure for which high-multiplicity flow and LP techniques are appropriate. No combinatorics is being hidden in the number of kidney-exchange pairs; the remaining structure lies in the finite type graph and the partial orders. If the weighted peak-set extension fails, that would identify a genuine boundary of continuization, not show that the typed housing-market mirror is conceptually illegitimate.
This mirror covers the paper’s SCFA result, Theorem 4.4 and Corollary 4.5. Corollary 4.6 suggests a further variant with forced and forbidden type-arcs, but I would not count it as an independent anchor because it is a reduction of the same algorithm. Theorem 4.8, Lemma 5.1, and Theorem 5.4 generate interesting future questions about type-level manipulation and improvement, but they are not part of this computational mirror.
The immediate follow-up questions are whether the weighted peak-set characterization holds, whether exact finite-population rounding preserves strong-core feasibility, and whether the paper’s weak group-strategyproofness theorem has a meaningful nonatomic, type-reporting analogue.
The strongest objection is that the proposed mirror is not actually a continuization of the paper’s housing market; it is a new multi-unit exchange model.
In the paper, \(N\) simultaneously indexes agents and houses. An arc \((a,b)\) means that the particular agent \(a\) receives the particular house owned by \(b\). Preferences and forbidden arcs may therefore depend on those identities. With a fixed finite type space, however, many copies of a type must have identical preferences, endowments, acceptability relations, and restrictions. The only way to achieve that is to make houses within a type interchangeable. The resulting object has masses of house-types and a transportation matrix \(x\), rather than the paper’s one-to-one market over named houses.
There is a sharp dichotomy. If house identities and compatibility relations are retained, then a type must encode an agent’s complete incidence pattern to all houses. In kidney exchange, that includes the pair-specific compatibility and logistical restrictions that generate the directed exchange graph. Such signatures can be essentially unique, so the number of types grows with the number of agents and the claimed high-multiplicity compression disappears. If those identities are quotiented out, then every patient of type \(t\) can exchange with every donor of type \(u\), and every forbidden type-arc applies uniformly to all copies. That is a plausible typed exchange problem, but it is not the arbitrary \(\textsc{SCFA}\) problem solved by Theorem 4.4.
The proponent’s blocking condition also exposes the semantic gap. The paper blocks an integral allocation by a cycle of distinct named agents. The proposed \(z_{t,u,v}\) is instead a circulation among types whose members may be split across several current house-types. Such a circulation need not automatically correspond to the paper’s peak-set decomposition: peak sets are subsets of named vertices, while a positive-mass type may be partly inside and partly outside a proposed peak set. Replacing perfect matching by flow is therefore not the algorithmic substitution claimed; it requires a new weighted peak-set theorem and a proof that aggregate blocking is equivalent to blocking in every finite realization.
One can repair this by forbidding type-splitting, but then the continuous model loses the very mass-level flexibility that motivates it. Or one can allow splitting and obtain a genuine fractional multi-unit market, but then the result is a new theorem about that model rather than a mirror of Theorem 4.4. The issue is not whether the eventual answer is polynomial; it is whether the same computational object has survived.
This is the best negative case, but it is not decisive. A deliberately clone-symmetric kidney-exchange pool is a coherent high-multiplicity regime, and rational mass instances can plausibly be related to replicated finite markets. Replicating the paper’s four-agent examples by type would preserve their structural phenomena. Thus I cannot honestly sustain the universal claim that no worthwhile mirror exists. The fair negative conclusion is narrower: the proposed mirror has not yet shown that it preserves the paper’s identity-dependent housing problem; it currently looks like a promising, but distinct, typed exchange programme.
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.