| paper | Graphical House Allocation |
| authors | — |
| venue | AAMAS 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 5.16
statement extracted from the paper’s text layer
Given a finite catalogue \(S\) of clique sizes, rational component masses \(\rho_s\), and rational masses \(\nu_j\) of house values \(v_1<\cdots<v_q\) satisfying \(\sum_{s\in S}s\rho_s=\sum_{j=1}^q\nu_j\), choose masses \(\lambda_{s,b}\) over nondecreasing bundles \(b\in\{v_1,\ldots,v_q\}^s\) such that \(\sum_b\lambda_{s,b}=\rho_s\) and \(\sum_{s,b}\mathrm{mult}_{v_j}(b)\lambda_{s,b}=\nu_j\); minimize \(\sum_{s,b}\lambda_{s,b}\sum_{1\le p<\ell\le s}(b_\ell-b_p)\), or decide whether the optimum is at most a given rational threshold.
A component-type configuration LP whose types are clique sizes \(s\) and whose decision variables \(\lambda_{s,b}\) give mass to whole \(K_s\) components receiving integral house bundles \(b\). Component mass and house-value mass are conserved, and the objective is total edgewise \(L_1\)-envy.
The mirror is not a plain distribution over individual agent types, and no standard atomless graph limit preserves the sparse component-local objective, so accepting structured component measures is essential.
fatal: False
The mirror directly covers disjoint unions of cliques, including equal and unequal clique sizes, and the broader configuration formulation covers repeated paths, cycles, and stars. It leaves arbitrary connected graphs, general trees, non-identical valuations, and the general minimum-bisection setting untreated.
The strongest positive case is for the paper’s disconnected-clique results. I would not claim that every result in the paper survives continuization, but the clique results have exactly the kind of repeated local structure that makes a high-multiplicity mirror credible.
My lead anchor is Theorem 5.15 and its algorithmic Corollary 5.16, both proved in this paper, with Theorem 5.13 and Corollary 5.14 as the equal-size special case. Theorem 5.15 proves that a disjoint union of cliques of sizes \(n_1\ge\cdots\ge n_r\) is separable, and Corollary 5.16 gives an \(O(n^{r+2})\) XP algorithm. For equal-sized cliques, Theorem 5.13 and Corollary 5.14 give strong separability and a linear-time algorithm.
A natural regime is a housing market consisting of many independent social groups—student houses, workplace teams, apartment associations, or dormitory floors—where every group is a clique and group sizes come from a small fixed catalogue. All agents have the common valuation function assumed in the paper. There may be millions of residents but only, say, \(k\) distinct clique sizes and \(q\) distinct house-value types. A clique member’s complete type includes the size of their clique and the fact that they belong to that clique; the component structure cannot be discarded because adjacency is part of the problem.
Here is the precise mirror I would propose, called Clique-Component House Allocation\(_\infty\). The input consists of:
\[ \sum_{s\in S}s\rho_s=\sum_{j=1}^q\nu_j. \]
A solution is a family \(\lambda_{s,b}\), where \(b=(b_1,\ldots,b_s)\) is a nondecreasing \(s\)-tuple of house values. The quantity \(\lambda_{s,b}\) is the mass of \(K_s\)-components receiving exactly the multiset \(b\). It must satisfy
\[ \sum_b\lambda_{s,b}=\rho_s \]
for each \(s\), and
\[ \sum_{s,b} \#_j(b)\lambda_{s,b}=\nu_j \]
for every house value \(v_j\), where \(\#_j(b)\) counts occurrences of \(v_j\) in \(b\). The objective is
\[ \min_\lambda \sum_{s,b}\lambda_{s,b} \sum_{1\le p<q\le s}(b_q-b_p). \]
The output is an optimal rational configuration measure \(\lambda\), or a decision whether the optimum is at most a given rational threshold.
This is not fractional allocation inside a clique. Each unit represented by \(\lambda_{s,b}\) is a whole clique receiving a whole integral bundle of houses. Only the population of repeated clique copies is aggregated. Clearing denominators converts a rational instance into a finite instance with many cloned cliques and cloned houses, preserving the objective exactly after normalization. Conversely, any finite high-multiplicity instance produces such a \(\lambda\).
The paper’s structural results make this recognizably its own problem. Theorem 5.15 says that larger cliques can be arranged contiguously relative to smaller ones in an optimum. Thus the continuum problem becomes a mass version of the paper’s ordered clique allocation, not an unrelated fractional welfare problem. In the equal-size case it reduces directly to the contiguous-block structure of Theorem 5.13 and the linear-time algorithm of Corollary 5.14.
I would expect Clique-Component House Allocation\(_\infty\) to be Class A, at least when the number of clique sizes and the maximum clique size are bounded or treated as parameters. The natural route is a configuration LP or a dynamic program over the ordered house-value axis. The original \(r\)-clique enumeration is replaced by masses of the \(k\) clique types, and the pricing problem has a particularly simple complete-graph cost. The interesting questions are whether polynomial dependence on the largest clique size is possible, whether a compact separation oracle exists for unrestricted \(S\), and whether the paper’s conjectured W[1]-hardness for arbitrary clique unions survives when the number of distinct clique types is the parameter.
A second, independent anchor is Theorem 3.3, “Hardness of Disjoint Unions,” and its Corollary 3.4, both proved here. They show NP-completeness for disjoint unions of arbitrary paths, cycles, stars, and cliques. The reduction is from Unary Bin Packing: graph components act as items, and separated clusters of house values act as bins.
The corresponding mirror is Clustered Component Envy\(_\infty\). Let \(\mathcal A\) be a finite catalogue of connected graph components, with \(\rho_g\) mass of copies of \(g\), and let \(z_1<\cdots<z_k\) be house-value bands with house masses \(\beta_1,\ldots,\beta_k\). A solution assigns whole component copies to value-band configurations. Formally, if \(a_g=|V(g)|\), let \(\Lambda_{g,\mathbf j}\) be the mass of copies of \(g\) whose vertices receive band values \((z_{j_1},\ldots,z_{j_{a_g}})\). The constraints are
\[ \sum_{\mathbf j}\Lambda_{g,\mathbf j}=\rho_g \]
and
\[ \sum_{g,\mathbf j} \Lambda_{g,\mathbf j} \#_b(\mathbf j)=\beta_b \]
for every band \(b\). The objective is
\[ \min_\Lambda \sum_{g,\mathbf j}\Lambda_{g,\mathbf j} \sum_{\{u,v\}\in E(g)} |z_{j_u}-z_{j_v}|. \]
The zero-cost specialization asks whether all component mass can be assigned wholly within bands. Writing \(x_{g,b}\) for the mass of \(g\)-components assigned to band \(b\), this becomes
\[ \sum_b x_{g,b}=\rho_g, \qquad \sum_g |V(g)|x_{g,b}=\beta_b. \]
That is the fractional high-multiplicity counterpart of the bin-packing core of Theorem 3.3. I would expect this specialization to be Class A: it is a linear mass-flow or configuration problem. The discrete NP-hardness is plausibly caused by having to place individual component copies integrally into bins. In the repeated-component regime, rational \(x_{g,b}\) can be realized by sufficiently many cloned components, while no individual component is split.
I would not claim that Theorem 3.3’s NP-hardness transfers. That would be an overstatement: allowing component mass to divide among destinations is precisely what can dissolve the bin-packing obstruction. But this is a meaningful positive result for the programme: it identifies a paper whose hardness is plausibly population-integrality-driven and asks whether the continuous mirror removes it.
The weakest point is that a bare distribution over individual agent types is insufficient. In a disjoint union of cliques or paths, one must retain the component-copy structure; otherwise the model forgets which agents are adjacent. I am therefore proposing an author-recognizable extension with a finite catalogue of repeated graph components and configuration masses, rather than pretending that ordinary type marginals alone suffice. That is a real modelling assumption, but it is exactly the repeated social-block regime studied by the paper, and it preserves whole components, indivisible house assignments, the common valuation function, and the aggregate edgewise envy objective.
This case covers the paper’s disjoint-union results—especially Theorem 5.15/Corollary 5.16 and Theorem 3.3/Corollary 3.4. It does not claim a mirror for arbitrary graphs, trees, non-identical valuations, or the minimum-bisection reduction of Theorem 3.2.
The strongest negative objection is that the paper’s real object is not a population of interchangeable agents. It is a collection of finite graph components, and the envy objective depends on which houses are grouped inside the same component.
A plain distribution over agent types therefore fails immediately. Take two \(K_2\) components and house values \(0,1,2,3\). The same individual value marginal can produce components \((0,1),(2,3)\), with total envy \(2\), or \((0,3),(1,2)\), with total envy \(4\). Agent-type masses do not record this grouping. Including the identity of every clique in the type restores the information, but then the number of types grows with the number of components and the high-multiplicity gain disappears.
There is also a genuine limit problem. A population consisting of \(M\) copies of fixed-size cliques has only \(O(M)\) edges. Under the usual dense graphon normalization, its edge contribution vanishes as \(M\to\infty\); replacing it by a positive-measure complete block instead produces \(O(M^2)\) edges and a different problem. A graphon or ordinary atomless-agent model therefore does not preserve the paper’s sparse, component-local objective.
This is a serious objection to the direct mirror, but it does not defeat the proponent’s stronger component-level construction. The configuration variable \(\lambda_{s,b}\) explicitly retains the missing correlation: it is a distribution over whole clique copies and whole house bundles. Rational denominator clearing gives a finite instance with many cloned cliques, so this is genuinely a high-multiplicity regime rather than fractional allocation inside a clique. The same applies to the full \(\Lambda_{g,\mathbf j}\) formulation for paths, stars, or arbitrary repeated components.
Theorem 5.15 is therefore difficult to dismiss. Its literal “larger clique splits smaller clique” statement is not itself a property of an anonymous mass measure, but the associated continuous optimization problem remains author-recognizable, and its finite-clone correspondence is exact. The equal-size case of Theorem 5.13 is even harder to attack: repeated equal-sized clique blocks and repeated house-value types are a perfectly sensible housing-market regime.
The second anchor, Theorem 3.3, has a sharper limitation. Its Unary Bin Packing reduction relies on integral placement of individual components into individual bins. In the proposed continuous version, \(x_{g,b}\) may distribute the mass of identical components among bands. After denominator clearing, this becomes packing many cloned copies with scaled capacities, where the bin-packing obstruction can disappear. If one forbids that distribution and insists that each bin retain its discrete integral component pattern, one has simply retained the original finite bin-packing problem; the population has not been continuized in the relevant sense.
But this cannot serve as a decisive negative argument under the programme’s rules. The disappearance of bin-packing hardness is precisely the kind of population-integrality effect that continuization is meant to test. It is not a defect that the continuous answer may be easier. The zero-cost mass-flow version is still a well-posed computational question, and the full configuration version preserves indivisible component assignments.
So the negative case successfully rejects a naive agent-marginal mirror and exposes a real modelling burden: the graph must be continuized at the component or configuration level, not by forgetting adjacency. It does not, however, defeat the best version of the clique anchor. Under the programme’s allowance for author-recognizable high-multiplicity re-modelling, I cannot honestly sustain the universal claim that no worthwhile continuous mirror exists. The negative case is weak precisely because the first anchor survives the strongest objections.
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.