The Core of Housing Markets from an Agent's Perspective: Is It Worth Sprucing Up Your Home? (d4-conf-wine-2021-0031)

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 society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational. Here agent and house types share a set \(T\), \(m=|T|=\tau\), and \(\sum_{t\in T}\mu_t=1\); every type-\(t\) agent initially owns a type-\(t\) house.
Each type has an explicitly represented strict partial preference order \(\prec_t\) over \(T\), where \(h\prec_t k\) means that \(k\) is strictly preferred to \(h\). Define acceptable houses by \(A(t)=\{h\in T:\neg(h\prec_t t)\}\).
An assignment is a real matrix \(x\ge0\) with \(\sum_h x_{th}=\mu_t\), \(\sum_t x_{th}=\mu_h\), and \(x_{th}=0\) whenever \(h\notin A(t)\). Its entries describe masses receiving individual houses, rather than lotteries evaluated by agents.
A blocking flow is a nonzero real tensor \(z_{thk}\ge0\): it selects type-\(t\) agents currently receiving \(h\) and gives them \(k\), subject to \(\sum_k z_{thk}\le x_{th}\), with \(z_{thk}=0\) unless \(k\in A(t)\) and \(h\prec_t k\). For every \(k\in T\), require \(\sum_{t,h}z_{thk}=\sum_{h,j}z_{khj}\), so the coalition uses exactly its members’ original endowments. Every participating agent must strictly improve; arbitrary positive submasses may participate.
The input also specifies \(a,b\in T\) with \(b\in A(a)\), and a binary rational \(0<\eta\le\mu_a\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).

Is deciding whether an assignment with no blocking flow and \(x_{ab}\ge\eta\) exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite agents and indivisible houses, requiring a designated agent to receive a designated acceptable house in a core allocation is NP-complete, even with strict linear preferences ([Schlotter–Biró–Fleiner](https://real.mtak.hu/204566/1/core-mor.pdf)).
For fractional endowments, weak-core nonemptiness is known under stochastic-dominance blocking, a different model ([The core in the housing market model with fractional endowments](https://arxiv.org/html/2508.11151v1)). No complexity classification for the exact mass problem defined above was located.

Result

The decision problem is \(\mathrm{NP}\)-complete, even when every preference order is strict linear, all masses are equal dyadic rationals, and \(\eta=\mu_a\).

The crucial point is that blocking depends only on the support of the assignment. With equal masses, a stable fractional assignment can be rounded to a stable permutation while preserving a specified positive entry.

1. Blocking flows are equivalent to directed cycles

For a feasible assignment \(x\), define a directed graph \(G_x\) on \(T\) by
\[ t\to k \quad\Longleftrightarrow\quad k\in A(t)\ \text{and there exists }h\in T \text{ with }x_{th}>0\text{ and }h\prec_t k. \]

Lemma 1. An assignment \(x\) admits a blocking flow if and only if \(G_x\) contains a directed cycle.

Proof. Suppose \(z\) is a blocking flow. Set \(f_{tk}=\sum_h z_{thk}\). If \(f_{tk}>0\), some \(z_{thk}>0\); the capacity constraint implies \(x_{th}>0\), and the preference constraint implies \(k\in A(t)\) and \(h\prec_t k\). Thus \(f\) is supported on the arcs of \(G_x\).

The coalition balance equations give, for every \(k\in T\),
\[ \sum_t f_{tk}=\sum_j f_{kj}. \]
Consequently, \(f\) is a nonzero nonnegative circulation. Its positive support contains a directed cycle: start with a positive arc and continue along positive outgoing arcs, which exist by conservation whenever a vertex has positive incoming flow. Finiteness eventually forces a repeated vertex.

Conversely, suppose \(t_1\to t_2\to\cdots\to t_r\to t_1\) is a directed cycle with distinct vertices. Use cyclic indices. For each \(i\), choose \(h_i\) witnessing its arc, so that \(x_{t_i h_i}>0\), \(t_{i+1}\in A(t_i)\), and \(h_i\prec_{t_i}t_{i+1}\).

Let \(\varepsilon=\min_i x_{t_i h_i}>0\), and set
\[ z_{t_i h_i t_{i+1}}=\varepsilon \]
with all other entries zero. Each selected cell contributes at most its assigned mass. Every participating agent strictly improves. Each cycle type contributes \(\varepsilon\) of its original endowment and receives total demand \(\varepsilon\); other types contribute and receive zero. This is a nonzero blocking flow. \(\square\)

Corollary 2 (support monotonicity). If \(x\) has no blocking flow and \(y\) is another feasible assignment with \(\operatorname{supp}(y)\subseteq\operatorname{supp}(x)\), then \(y\) has no blocking flow.

Indeed, \(G_y\) is a subgraph of \(G_x\), so acyclicity is preserved.

2. Equal masses permit rounding that preserves a positive entry

Lemma 3. Suppose \(|T|=n\), every mass is \(1/n\), and \(x\) has no blocking flow. If \(x_{ab}>0\), there exists a permutation \(\sigma:T\to T\) such that:

• \(\sigma(a)=b\);
• \(x_{t,\sigma(t)}>0\) for every \(t\);
• the finite allocation \(\sigma\) is individually acceptable and belongs to the core defined by strict improvement for every coalition member.

Proof. Let \(P=nx\). Every row and column of \(P\) sums to \(1\).

Construct the bipartite support graph of \(P\), with agent types on the left, house types on the right, and edge \(th\) whenever \(P_{th}>0\). We show that it has a perfect matching containing \(ab\).

Delete left vertex \(a\) and right vertex \(b\). For any subset \(S\) of the remaining left vertices, let \(N(S)\) be its neighbors among the remaining right vertices. Every positive entry in rows \(S\) belongs to a column in \(N(S)\cup\{b\}\). Since row \(a\), which is outside \(S\), contributes \(P_{ab}>0\) to column \(b\),
\[ |S| =\sum_{t\in S,h}P_{th} \le |N(S)|+1-P_{ab}. \]
If \(|N(S)|<|S|\), their integer cardinalities imply
\[ |N(S)|+1-P_{ab}<|S|, \]
a contradiction. Hence Hall’s condition holds. Hall’s marriage theorem supplies a perfect matching after the deletion; adding \(ab\) gives the required permutation \(\sigma\).

Define \(y_{t,\sigma(t)}=1/n\), with all other entries zero. This is feasible because \(\sigma\) is a permutation and every chosen cell belongs to the acceptable support of \(x\). Corollary 2 shows that \(y\) has no blocking flow.

Finally, its improvement graph has arc \(t\to k\) exactly when \(k\in A(t)\) and \(\sigma(t)\prec_t k\). A finite blocking coalition reallocates its members’ original houses by a permutation. That permutation decomposes into directed cycles, each consisting entirely of strict improvements. Conversely, any directed cycle in the improvement graph gives a finite blocking coalition. Thus acyclicity means precisely that \(\sigma\) is in the finite core. \(\square\)

In particular, for equal masses and any threshold \(0<\eta\le 1/n\), the mass instance is a yes-instance exactly when the corresponding finite market has a core permutation assigning \(b\) to \(a\). The forward implication follows from Lemma 3; the reverse implication follows by scaling that permutation by \(1/n\).

3. Polynomial reduction proving hardness

We use the following established theorem: Arc in Core is \(\mathrm{NP}\)-complete even with strict linear preferences. Its input is a finite housing market and an acceptable arc \(ab\); it asks whether some core allocation assigns \(b\)’s house to \(a\). The source uses the same acceptability convention and defines core membership by absence of cycles that strictly improve every participant. These statements are verified in Section 2.2 and Theorem 1 of [Schlotter–Biró–Fleiner](https://real.mtak.hu/204566/1/core-mor.pdf).

Take such an instance with original type set \(U\), where \(|U|=n\). To ensure that all constructed masses are dyadic, let \(N\) be the least power of two at least \(n\), and add \(N-n\) dummy types.

Extend preferences as follows:

• Each original type retains its ordering over \(U\) and ranks every dummy house below every original house.
• Each dummy type ranks its own house first and orders all other houses arbitrarily below it.

These are strict linear orders. Every original type finds dummy houses unacceptable, and every dummy type finds only its own house acceptable.

Set \(T\) equal to the enlarged type set, and define
\[ m=\tau=N,\qquad \mu_t=\frac1N\quad(t\in T),\qquad \eta=\frac1N. \]
Keep the designated pair \(a,b\). The masses are positive dyadic rationals summing to \(1\), and \(\eta=\mu_a\).

Forward direction. Suppose the original finite market has a core permutation \(\sigma\) with \(\sigma(a)=b\). Extend it by fixing every dummy type, then scale its permutation matrix by \(1/N\).

The resulting assignment is feasible and has \(x_{ab}=\eta\). Its improvement graph on original types is the original finite improvement graph. Dummy types have no outgoing improvement arcs, and original types have no arcs to unacceptable dummy houses. Therefore the graph is acyclic, and Lemma 1 excludes blocking flows.

Reverse direction. Suppose the constructed mass instance has a feasible assignment \(x\) with no blocking flow and \(x_{ab}\ge\eta\). A dummy row can receive only its own house, so \(x_{dd}=1/N\). Its column is thereby exhausted.

Restrict \(x\) to original rows and columns and multiply by \(N\). This gives an \(n\times n\) doubly stochastic matrix with positive \(ab\) entry. The matching argument in Lemma 3 yields an original permutation \(\sigma\) containing \(ab\) and supported on these entries.

Every improvement arc of \(\sigma\) is an arc of \(G_x\). Hence its improvement graph is acyclic, and \(\sigma\) is an original finite core allocation.

This proves equivalence of the two instances.

Since \(N<2n\), the construction is polynomial. If the source input has bit length \(S\), even explicitly listing every comparison in every constructed order gives output length \(L=O(S+n^3\log(n+1))\) and polynomial construction time. Therefore the mass problem is \(\mathrm{NP}\)-hard under the stated restrictions.

4. Membership in \(\mathrm{NP}\) and running times

Real-valued assignments do not obstruct membership in \(\mathrm{NP}\): a certificate can consist solely of an ordering of the types.

Guess a bijection \(\pi:T\to\{1,\ldots,m\}\). Define the permitted cells
\[ B_\pi= \left\{ (t,h): h\in A(t),\ \pi(t)<\pi(k) \text{ for every }k\in A(t)\text{ with }h\prec_t k \right\}. \]

A feasible assignment supported on \(B_\pi\) has every improvement arc directed forward in \(\pi\), so Lemma 1 guarantees that it has no blocking flow. Conversely, if an assignment has no blocking flow, any topological ordering of \(G_x\) places all its positive cells in the corresponding \(B_\pi\).

It remains to test transportation feasibility on \(B_\pi\) with \(x_{ab}\ge\eta\). Reject if \(ab\notin B_\pi\) or \(\eta>\mu_b\). Otherwise reserve \(\eta\) in cell \(ab\), leaving row supplies
\[ r_t=\mu_t-\eta\,\mathbf1_{\{t=a\}} \]
and column demands
\[ c_h=\mu_h-\eta\,\mathbf1_{\{h=b\}}. \]
Both totals equal \(1-\eta\). A standard bipartite flow network tests whether these residual supplies and demands can be met using permitted cells; adding the reserved mass reconstructs the required assignment.

For explicit running times:

• Preference preprocessing and construction of \(B_\pi\) require \(O(m^3)\) relation operations.
• The flow network has \(O(m)\) vertices and \(O(m^2)\) edges. Edmonds–Karp uses \(O(m^5)\) arithmetic operations.
• Multiply capacities by the product of all input denominators. This common denominator has \(O(L)\) bits, so all flow arithmetic has polynomial bit complexity. A conservative total verifier bound is \(O((m^5+L)L^2)\) bit operations.

The certificate has \(O(\tau\log(\tau+1))\) bits, with \(m=\tau\). Thus the problem belongs to \(\mathrm{NP}\). Enumerating all orders also gives an exact deterministic algorithm taking \(O(\tau!\,(m^5+L)L^2)\) bit operations.

Together with the reduction, this proves \(\mathrm{NP}\)-completeness. In particular, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct: the argument establishes NP-completeness for the exact mass problem, including the stated restrictions. I found no major or minor mathematical issues.

• Lemma 1: blocking flows and directed cycles.

The aggregation \(f_{tk}=\sum_h z_{thk}\) is valid. A positive entry \(f_{tk}\) implies a positive witness \(z_{thk}\), hence \(x_{th}>0\) by the capacity constraint. The remaining constraints give precisely the conditions defining an arc of \(G_x\).

The coalition balance equation becomes incoming flow equals outgoing flow at every type. Nonzero, nonnegative flow therefore yields a directed cycle by the finite traversal argument given.

Conversely, the construction along a cycle satisfies every constraint. Distinct cycle vertices ensure that the selected assignment cells have distinct row indices, so no cell is charged more than once. The minimum defining \(\varepsilon\) is positive. Each cycle type supplies and demands exactly \(\varepsilon\), and every selected agent strictly improves.

There is no omitted self-loop case: an arc \(t\to t\) would require an assigned acceptable house \(h\) with \(h\prec_t t\), contradicting acceptability.

• Corollary 2: support monotonicity.

Correct. Reducing assignment support can only remove improvement arcs. A subgraph of an acyclic graph remains acyclic, and feasibility of the new assignment is explicitly required.

• Lemma 3: rounding while preserving the designated entry.

Scaling by \(n\) correctly produces a doubly stochastic matrix.

The Hall inequality is sound: columns in \(N(S)\) contribute at most \(|N(S)|\), while column \(b\) contributes at most \(1-P_{ab}\) to rows in \(S\), because row \(a\) lies outside \(S\). Positivity of \(P_{ab}\), together with integer cardinalities, excludes \(|N(S)|<|S|\).

Thus the written argument verifies Hall’s condition for the remaining balanced bipartite graph and obtains a perfect matching containing \(ab\). Scaling this matching produces a feasible assignment with support contained in that of \(x\), so Corollary 2 applies.

The finite-core identification is also correct. A coalition’s reallocation of its original houses is a permutation on its members; if everyone strictly improves, its cycles are improvement cycles. Conversely, an improvement cycle gives such a coalition. Consequently, the threshold equivalence holds for every \(0<\eta\le 1/n\).

• External hardness theorem and model compatibility.

The cited theorem applies as stated. Section 2.2 of the source defines the same preference orientation and acceptability convention, and defines core membership by acyclicity of the strict-improvement graph. Section 3 defines Arc in Core using a designated acceptable arc. Theorem 1 establishes NP-completeness even with strict preferences; its construction explicitly uses ordered preference lists. [Schlotter–Biró–Fleiner, Sections 2.2–3 and Theorem 1](https://real.mtak.hu/204566/1/core-mor.pdf).

Thus the reduction uses the appropriate core notion and does not substitute strict-core membership or stochastic-dominance blocking.

• Padding and reduction.

The dummy preferences enforce exactly the claimed acceptability restrictions. Original agents cannot receive dummy houses, and each dummy can receive only its own house.

In the forward direction, fixing dummies introduces no improvement arcs involving them. Stability of the original permutation therefore implies stability of the scaled assignment.

In the reverse direction, each dummy exhausts its own column. The original submatrix, multiplied by \(N\), consequently has every row and column sum equal to one. The designated entry is positive, and the matching argument applies. Every improvement arc of the resulting original permutation appears in \(G_x\), establishing its core membership.

The masses are positive dyadic rationals and sum to one. The threshold equals \(\mu_a\). Since \(N<2n\), both the construction and the stated output-length bound are polynomial.

• NP membership.

The ordering certificate is sufficient even though assignments may be real-valued. For any positive permitted cell, the universal condition defining \(B_\pi\) forces every corresponding improvement arc forward in the ordering. Conversely, a topological ordering of a stable assignment’s graph satisfies that condition for every positive cell.

Reserving \(\eta\) in cell \(ab\) is equivalent to imposing its lower bound. The preliminary rejection conditions are necessary, and the residual supplies and demands are nonnegative with equal totals. Transportation feasibility on the permitted cells therefore verifies exactly the required condition.

This establishes both certificate soundness and completeness without assuming a rational representation of the original witness.

• Running times and edge cases.

The stated bounds are valid conservative bounds. The permitted-cell construction uses \(O(m^3)\) relation operations. With \(O(m)\) vertices and \(O(m^2)\) edges, Edmonds–Karp uses \(O(m^5)\) arithmetic operations. The product of input denominators has \(O(L)\) bits, so scaling permits exact arithmetic within the claimed polynomial bit bound.

The certificate size and factorial enumeration bound correctly use \(m=\tau\). Cases such as \(a=b\), a single type, or zero residual total when \(\eta=1\) do not invalidate the argument.

No repair or additional mathematical clarification is needed. The proof resolves the requested complexity classification.

⟨structured verdict parsed — rendered above⟩