| paper | Housing Market on Networks |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Bit (a) fails: none of the paper's numbered results asserts computational hardness, tractability, approximation, or parameterized complexity. The proposed Mass-CTC and Mass-WCC questions are plausible extensions, but they cannot supply the missing computational anchor. The opponent's concerns about identity-dependent houses and networks further weaken the claim that these are direct continuous mirrors.
fails bit a — no named computational result to mirror
The attempted mirror covers the structural CTC guarantee in Theorem 5.7 and the optimal-wcc impossibility in Theorem 4.8, while leaving the other boundary theorems and the SWN and LS guarantees without a developed continuous formulation.
On the strict ChoCo criterion, this paper has no qualifying computational-complexity anchor. It contains no named theorem proving NP-hardness, polynomial-time solvability, parameterized hardness, or an approximation result. The named results—Theorems 4.1, 4.2, 4.8, 4.10, 4.11, 4.12, and 5.7—are all structural mechanism-design theorems proved in this paper. Thus, this is not a complexity-landscape paper in the programme’s narrow sense.
The strongest positive case is nevertheless a mechanism-design mirror centred on Theorem 5.7, proved here: “For any order \(O\), CTC is optimal-cc.” I would treat this as an algorithmic anchor, but not pretend that it is a complexity theorem.
The natural regime is a large housing platform with many repeated communities, standardized housing classes, and only a small number of complete agent types. A type contains an agent’s strict ranking over house classes, endowed house class, initial-participant status, and network role. The network role must be part of the type: two agents with different invitation paths are not the same type. A society is a rational distribution \(\mu\) over these types, with \(n\gg\tau\). This could describe many apartment communities with recurring social-network patterns, rather than one seven-person exchange.
My lead question would be:
Mass-CTC-Optimal-cc. Given finite type set \(T\), house classes \(H\), rational masses \(\mu_t\), endowment map \(e(t)\), strict preferences \(\succ_t\), an initial-type set, a finite reported network relation, and an order \(O\), compute a mass allocation \(x=(x_{t,h})\). Here \(x_{t,h}\) is the mass of type \(t\) receiving house class \(h\), subject to
\[ \sum_{h\in H}x_{t,h}=\mu_t \]
and the corresponding house-supply constraints. Unqualified mass must retain its endowment. The allocation is mass-optimal-cc if there is no alternative transport plan \(y\) that weakly improves every affected type, strictly improves a positive mass, and changes allocations only inside a complete component of the reported network. The requested output is the allocation generated by a mass version of CTC: follow favourite-house pointers between types, settle a cycle by its bottleneck mass, and repeat, using the paper’s exclusive-path test and order \(O\).
I would expect the finite-type version to be Class A-like. Cycle detection and path tests operate on the finite network-role graph, while the remaining allocation is a finite transportation problem. For rational \(\mu\), the result has a direct downward bridge: multiply by a common denominator and decompose the transport plan into an ordinary finite matching. The interesting follow-up is whether a more general graphon or column-generation representation remains tractable when the house catalogue or network-role system is large.
The mirror is recognisable as the authors’ problem because it preserves their essential objects: invitation reports, qualification by directed paths, endowed houses, favourite pointing, connectedness, complete components, and trading cycles. Fractional \(x\) is only the aggregate representation of many repeated deterministic exchanges; the continuous object is the population, not merely a divisible outcome space.
A useful supporting anchor is Theorem 4.8, also proved here: “No IC and IR diffusion one-sided matching mechanism is optimal-wcc.” Its continuous counterpart is:
Mass-WCC Feasibility. Given the same typed society, does there exist a measurable diffusion mechanism mapping every admissible report profile to a mass allocation that is individually rational, incentive compatible, and has no positive-mass Pareto improvement whose changed agents form a weakly complete component, meaning that at most one directed connection is missing?
On a continuum of repeated copies of the four-agent gadget in Figure 2, the theorem’s obstruction transfers pointwise. The correct conclusion here is not continuum-specific hardness but impossibility transfer: continuity does not rescue optimal-wcc. This is a boundary question rather than a member of ChoCo’s A/B/C complexity trichotomy. Theorem 4.2 would give a similar mass-stability question, but I would not count it as a third anchor; it adds no new computational content.
The weakest point is that the paper’s strategic difficulty is fundamentally graph-theoretic and local. If one replaces the network by a simple distribution over preferences, the problem is no longer the authors’ problem. If one retains exact sparse invitation structure by repeating finite motifs, the continuum can look like a mixture of small markets and may offer little computational gain. The positive case is therefore strongest for repeated housing communities or cohort-level network structures, and weak for a single enormous sparse network with idiosyncratic edges.
So my honest verdict is: there is a credible continuous population mirror of the paper’s CTC and boundary theorems, with Mass-CTC-Optimal-cc as the lead question, but the paper itself supplies no qualifying ChoCo complexity result.
The negative case starts before the modelling details: this paper has no qualifying computational anchor. Theorems 4.1, 4.2, 4.8, 4.10, 4.11, 4.12, and 5.7 are axiomatic or structural mechanism-design results. None gives a complexity classification, algorithmic guarantee, approximation result, or parameterized result. Thus the proposed mirrors are not continuizations of a computational result in the ChoCo sense; they are new mechanism-design questions.
The proposed Mass-CTC mirror also fails to preserve the paper’s central object. Each agent owns a distinct house \(h_i\) and has a strict ranking over those individually identified houses. An agent’s type therefore includes her endowment identity and a preference order over an \(n\)-dependent set of objects. With arbitrary preferences, repeated complete types disappear as \(n\) grows: the type space is not a fixed finite \(\tau\), but grows with the market and effectively records individual identity. The network role has the same problem. Qualification, shortest-path order, complete components, and CTC’s exclusive-path test all depend on the particular labelled graph, not on the marginal frequency of preference types.
Replacing houses by classes does not repair this while retaining the paper’s result. It creates a capacity-constrained matching problem with duplicate goods. CTC’s favourite pointers, ownership-based trading cycles, and individual endowments are no longer the same objects. Conversely, retaining exact houses and exact networks means that a mass vector \(x_{t,h}\) has forgotten precisely the information on which CTC operates.
The proponent’s suggested “network role” type does not solve the problem either. A distribution of roles does not determine the edges between agents, while the paper’s definitions depend on those edges jointly. One can add a graphon, a distribution over rooted networks, or a full coupling between types and neighbourhoods, but then the input is no longer the paper’s finite-type society \(\mu\). If one instead repeats a fixed finite network motif, the copies are independent finite housing markets. The resulting aggregate is bookkeeping over many copies, not a population-level CTC problem.
This also breaks the claimed high-multiplicity bridge. Multiplying a fractional transport plan by a common denominator can produce an assignment of houses, but it does not produce the common invitation graph, qualification set, shortest-path order, or exclusive-path certificates required by CTC. Decomposing within repeated motifs preserves those structures only by treating each motif separately; decomposing across motifs can create an allocation with no corresponding instance of the paper’s problem.
The incentive issue is even more fundamental. In the paper, one named agent can withhold an invitation and thereby disqualify another named agent. In a nonatomic population, an individual has measure zero. If her report changes only zero mass, the invitation incentive that drives Theorems 4.1, 4.2, and 5.7 vanishes in the aggregate model. If a single agent must retain positive influence over a positive-mass group, that agent is a distinguished bridge or block, not an interchangeable member of a finite type. Giving every bridge positive mass produces a different block-network mechanism.
Theorem 4.8 does not provide an escape. Repeating its four-agent gadget yields either independent finite gadgets, in which case the impossibility transfers pointwise but no continuous computational question appears, or a continuum of copies, in which case each particular gadget has measure zero. To preserve the gadget’s identity one must retain the copy label as part of the type, producing an unbounded or continuum type space. Pooling agents with the same local preference and role across different copies destroys the weakly complete-component condition, because agents from different copies may then be incorrectly treated as one exchangeable group. Theorem 4.2 has exactly the same defect.
The strongest possible rescue is therefore a new model of recurring housing classes, block-level social relations, and mass trading cycles. It may be mathematically coherent, but its complete components, endowments, strategic agents, and cycles are all block-level replacements for the paper’s individual networked housing market. It is not a continuous mirror of CTC or of the paper’s impossibility results. The alternatives form an unhelpful trilemma: preserve individual houses and networks, and high multiplicity disappears; quotient them into classes and blocks, and the problem changes; retain the full network as a graphon, and the model leaves the programme’s finite-type computational setting.
So the proponent has identified a possible new fractional/block matching model, but not a worthwhile ChoCo mirror of this paper. Under the programme’s strict scope, the absence of any computational result is decisive, and the paper’s identity-sensitive network structure prevents the proposed axiomatic mirrors from becoming genuine continuous-population complexity questions.
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.