Online Housing Market

There is an important qualification first: this paper contains no numbered result stating NP-hardness, membership in \( \mathrm{P} \), W[1]-hardness, FPT, approximation complexity, or a comparable complexity classification. Under a strictly complexity-only reading of ChoCo’s anchor rule, it has no eligible anchor. The strongest positive case therefore rests on its named algorithmic mechanism results, especially Proposition 3, rather than pretending that the paper already studies complexity.

My lead anchor is Proposition 3 (marked \( \star \); proved by the authors in the supplementary material): Algorithm 1 with the ascending-departure permutation \( \delta \) returns an \(M(I)\)-Pareto-optimal allocation for every instance \(I\). Proposition 4, proved in the main text, is a useful companion: this is the only online exchange algorithm that always returns an \(M(I)\)-Pareto-optimal allocation.

The mirror I would propose is \( \mathrm{OnlineHousing\text{-}PO}_{\infty} \). Consider a large institutional housing exchange with finitely many standardized house classes \(H\): for example, room categories in a university or dwelling categories in a social-housing transfer system. An agent type is a complete tuple \( \theta=(e_\theta,\succ_\theta,a_\theta,d_\theta) \), where \(e_\theta\in H\) is the agent’s endowed house class, \( \succ_\theta \) is a strict ranking of house classes, and \(a_\theta,d_\theta\) are arrival and departure windows. A society is a rational distribution \( \mu \) over the finite type set \( \Theta \). Thus \( \mu_\theta\) is the fraction of residents of type \( \theta \), and the supply of house units initially owned by type \( \phi \) is \( \mu_\phi\).

A mass allocation is a matrix \(x_{\theta\phi}\), where \(x_{\theta\phi}\) is the mass of agents of type \( \theta \) receiving a house initially owned by type \( \phi \). It must satisfy

\[ \sum_{\phi}x_{\theta\phi}=\mu_\theta,\qquad \sum_{\theta}x_{\theta\phi}=\mu_\phi, \]

and \(x_{\theta\phi}=0\) whenever \(a_\phi\ge d_\theta\). The latter is exactly the paper’s online availability condition: an agent cannot receive a house whose owner has not yet arrived.

The continuous lift of Algorithm 1 with \( \delta \) processes departure windows in increasing order. When a type departs, its remaining mass receives the most-preferred currently available house-class mass, consuming that supply irrevocably. If several types depart simultaneously, the instance includes a fixed within-window order; alternatively, one can batch types with identical preferences, in which case the order is immaterial.

Pareto dominance must be defined at the mass level without pretending that an individual receives a fractional house. An allocation \(y\) dominates \(x\) if the old and new assignments can be coupled within every type so that each mass unit receives a weakly preferred house under \(y\), with a positive mass receiving a strictly preferred one. The question \( \mathrm{OnlineHousing\text{-}PO}_{\infty} \) is:

Given \(H\), \( \Theta \), rational \( \mu \), the arrival and departure schedule, and the rankings, output the mass allocation \(x^\delta\) generated by the ascending-departure procedure and either certify that no feasible mass allocation dominates it or provide a dominating allocation and coupling.

I would expect this problem to be Class A. The greedy allocation itself is polynomial in \( |\Theta| \), \( |H| \), and the encoding length of \( \mu \). Pareto-improvement search can naturally be expressed as a capacitated flow or rational LP over type–house pairs, with the departure constraints represented by time layers. The important point is that the running time depends on the number of distinct complete types, not on the number of cloned residents. The structural proof of Proposition 3 should transfer directly: if a mass improvement existed, clearing denominators would produce a finite improvement for a sufficiently large cloned instance.

This is a genuine high-multiplicity regime. Imagine \(10^5\) residents but only a few hundred standardized endowment classes, preference templates, and exchange windows. The type must include every relevant feature—preference order, endowed class, arrival window, and departure window—so the model does not hide idiosyncratic information. The continuous object is not a probability about an uncertain market; it is the population composition of a deterministic exchange market.

The rational-clone bridge is especially clean. If \( \mu_\theta=p_\theta/Q \), create \(p_\theta\) clones of type \( \theta \) and \(p_\phi\) house copies owned by type \( \phi \). Applying the discrete ascending-departure procedure and aggregating its assignments gives \(x^\delta\). Conversely, any rational mass allocation can be realized by sufficiently many clones. The houses remain indivisible at the individual level; \(x_{\theta\phi}\) records only the aggregate assignment of whole houses.

The mirror is an extension rather than a literal restatement. The paper has individually named goods and assumes no simultaneous arrival or departure times. A high-multiplicity version needs repeated house classes and cohort-style event windows. Those changes are necessary to obtain \( |\Theta|\ll n \), but they preserve the paper’s central objects: initial endowments, ordinal preferences, irrevocable online assignment, arrival-based availability, and Pareto efficiency. An author of the paper should recognize this as the replicated-market version of their problem, not as an unrelated fractional-allocation problem.

Proposition 4 suggests a second question, \( \mathrm{UniversalOnlineHousing\text{-}PO}_{\infty} \): does there exist an anonymous causal mass mechanism that is Pareto-optimal for every rational society over the given type domain? The expected answer is that the ascending-departure rule is the unique such mechanism, modulo irrelevant choices among identical house copies. That would be a structural Class-A result about computing the unique rule, together with a uniqueness theorem inherited from Proposition 4.

I would not use the paper’s incentive results as a direct anchor. Propositions 1, 7, 11, 13, and 14 are named and proved here—Proposition 14, for example, states that the earliest-departure partition \( \zeta \) yields strong incentive compatibility—but individual deviations become problematic in an atomless population. A single agent has zero mass and cannot alter the aggregate state. Replacing individual deviations by positive-mass cohort deviations would be an interesting extension, but it is not a direct mirror. The same warning applies to Corollary 5: its impossibility of combining Pareto optimality with individual rationality or stronger timing incentives should survive rational cloning, but the incentive part requires a new strategic interpretation.

So the case covers Proposition 3 emphatically, with Proposition 4 as supporting evidence. Its weakest point is that the high-multiplicity scenario is much more convincing for standardized housing cohorts than for the paper’s original marketplace of individually distinctive goods. If the authors insist on unique named houses and strictly distinct event times, the type count grows with the population and the continuous advantage largely disappears. If repeated house classes and institutional exchange windows are accepted, however, this is a credible population continuization whose natural computational question is a compact, likely tractable mass version of their Pareto-optimal online exchange problem.