Strategy-Proof House Allocation with Existing Tenants over Social Networks

The strongest honest case is narrow but real: this paper supports a Class A continuous mirror of the computation performed by YRMH-IGYT for tree-structured social networks. It does not provide an NP-hardness or parameterized-hardness anchor. Its impossibility results are mechanism-design impossibilities, not computational complexity results. The one clear computational anchor is Theorem 6, proved in this paper: for given \(A,H,\triangleright,\theta'\), the YRMH-IGYT mechanism for tree-structured social networks runs in \(O(n\cdot n')\) time.

I would therefore lead with the following problem.

Call it Continuous YRMH-IGYT Evaluation on Typed Referral Trees, or \(\mathrm{CYRMH}_{\infty}\).

An instance consists of a finite set \(Q\) of population-role types and a finite set \(K\) of house classes. A type \(q\in Q\) specifies whether its agents are existing tenants or newcomers, a strict ranking \(\succ_q\) over \(K\), an initial endowment class \(e(q)\in K\) if the type consists of existing tenants, its distance from the moderator, and its parent–child role in a rooted tree template. The instance also contains rational masses \(\mu_q\ge 0\), with \(\sum_{q\in Q}\mu_q=1\), and rational masses \(\nu_h\ge0\) of available house copies in each class \(h\in K\). The type tree and the masses must be consistent: each positive-mass child role has one parent role, and the occupied-house mass agrees with the mass of existing-tenant roles.

The intended regime is a large housing programme consisting of many repeated local referral trees: for example, many housing estates or relocation cohorts with the same referral structure, tenant/newcomer roles, house categories, and preference patterns. A type is a complete local role description, including its preference order, endowment class, distance, and referral position. If a fixed tree template has \(q_0\) roles and is repeated \(N\) times, then \(n=Nq_0\) while \(\tau=|Q|=O(q_0)\); more generally, \(N\gg\tau\). This is genuine high multiplicity rather than a claim that arbitrary named social networks can be compressed.

The decision variable is a mass allocation \(x=(x_{q,h})\), where \(x_{q,h}\) is the mass of type \(q\) assigned a house of class \(h\). But \(x\) is not allowed to be any feasible fractional matching. It must be the output of a mass version of Mechanism 1. The mechanism maintains residual type masses, residual house masses, and the distance-based priority queue. When the first active type \(q\) is selected, it chooses its most-preferred currently available house among vacant houses, houses of active ancestors, its own endowment class, and houses of its children. A vacant-house step transfers the largest possible batch of \(q\)-mass to that house class. A child step activates the corresponding child mass; an ancestor step executes the corresponding tree cycle on the largest batch supported by all participating residual masses. The process ends when all positive population mass has received a house or \(\varnothing\).

The question is: given \((Q,K,\mu,\nu,\mathcal G,\triangleright)\), compute the exact rational mass allocation \(x\), the residual vacant-house masses, and a finite batch-execution trace. A solution is valid only if the trace satisfies the mechanism’s transitions and all mass-conservation constraints. This is the continuous analogue of evaluating YRMH-IGYT for TSSNs, not a new welfare maximization problem.

The expected classification is Class A. Theorem 6 gives the uncompressed algorithmic template: each agent is selected at most \(1+|r_i|\) times, and each selection scans the houses. In the typed setting, identical agents are processed in batches. The expected running time is polynomial in \(\tau\), \(|K|\), the number of type-tree edges, and the encoding length \(L\) of \(\mu\) and \(\nu\), plausibly something like \(O((\tau+|E_Q|)|K|)\) rational-arithmetic steps. A rational instance with denominator \(D\) has a finite lift with \(D\) copies of every type and house class; conversely, every repeated finite instance produces rational masses. Thus the mirror has the desired high-multiplicity bridge.

This should be recognisable to the authors as their problem. It retains existing tenants, newcomers, indivisible house copies, strict rankings, partial neighbour revelation, the rooted-tree restriction, distance-based priority, and exactly the dynamically restricted choice set of YRMH-IGYT for TSSNs. The continuous object is only the population summary: \(\mu_q\) records how much society occupies each complete role type, while \(\nu_h\) records the normalized number of corresponding house copies. It is not outcome-space continuity in the sense of turning one physical house into a divisible good.

Theorem 4, also proved here, gives useful structural support: the finite mechanism is strategy-proof on every tree. Theorem 5 gives the accompanying IR, weak non-wastefulness, and SC4N guarantees. In the mass model these suggest natural population versions: no positive-mass tenant type is assigned below its endowment class, no type prefers a house class that remains vacant, and no positive-mass parent–child pattern can profitably exchange endowment classes. These are expected continuations of the paper’s guarantees, not results proved by the paper and not additional complexity anchors.

The main weakness is that the paper’s computational content is thin. Theorem 6 is a polynomial evaluation theorem, not a discrete hardness result whose difficulty might dissolve under continuization. Consequently this mirror cannot support a strong Class A versus Class B comparison of the kind sought for bribery or control. A second weakness is strategic: individual strategy-proofness becomes partly vacuous for a nonatomic agent of zero mass. The meaningful continuous notion is therefore type-block or positive-mass strategy-proofness, while the exact individual property should be stated through finite lifts and limiting guarantees. Finally, if one insists on arbitrary globally pooled named houses and strict rankings over every individual house, repeated house classes may fail to be genuine types; the repeated-tree housing-programme regime is the defensible scope.

So I would cover only Theorem 6 emphatically, with Theorems 4 and 5 as supporting fidelity evidence. I would not claim that this paper supplies a hardness anchor, nor that it establishes the compressed continuous algorithm. Its contribution to ChoCo is a credible, precisely stated Class A research question: whether the paper’s tree-based mechanism and its \(O(n n')\) execution can be lifted to exact mass-flow computation polynomial in the number of role types rather than the number of households.