| paper | Tight Approximations for Graphical House Allocation |
| authors | — |
| venue | AAMAS 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.10
Given a bounded-degree tree \(F=(V,E)\), rational house values \(h_1,\ldots,h_q\), and rational masses \(\nu_1,\ldots,\nu_q\) with \(\sum_j\nu_j=1\), consider a continuum of exchangeable copies of \(F\) with pooled house supply \(n\nu_j\) per copy on average, where \(n=|V|\). Choose a distribution \(p\) over configurations \(a:V\to\{1,\ldots,q\}\) satisfying \(\sum_a p_a=1\) and \(\sum_a p_a|\{v:a(v)=j\}|=n\nu_j\), minimizing \(\sum_a p_a\sum_{\{u,v\}\in E}|h_{a(u)}-h_{a(v)}|\).
A population of identical bounded-degree tree communities, with role types \(v\in V(F)\), configuration masses \(p_a\), pooled house-value masses \(\nu_j\), and objective equal to expected local envy \(\mathbb{E}_p[\sum_{\{u,v\}\in E}|h_{a(u)}-h_{a(v)}|]\).
The mirror requires an explicit graph-template coupling and pooled supply, so its finite lifts are forests rather than the connected trees appearing in Theorem 4.10.
fatal: False
The mirror covers the exact-allocation hardness result for bounded-degree trees, while leaving the paper's approximation bounds, random-graph result, complete-binary-tree result, and other graph classes untreated.
The strongest honest case is a narrow, topology-preserving extension of the paper’s bounded-degree-tree result. My lead anchor is Theorem 4.10, proved in this paper: “Graphical House Allocation is NP-hard on bounded-degree trees.” I would not claim that the paper’s other approximation theorems automatically transfer.
Consider \(\mathrm{CGHA}^{\mathrm{tree}}_\infty\), Configuration Graphical House Allocation on a repeated tree population. An instance contains a bounded-degree tree \(F=(V,E)\), with \(|V|=n\), distinct rational house values \(h_1,\ldots,h_q\), and rational house masses \(\nu_1,\ldots,\nu_q\) satisfying \(\sum_j\nu_j=1\). The population consists of a continuum of exchangeable copies of \(F\). Thus the agent type is a role \(v\in V\), with mass \(\mu_v=1/n\); agents with the same role in different copies have the same local position, valuation environment, and feasibility conditions. The graph template \(F\) is retained as part of the instance: type marginals alone would erase the adjacency information on which local envy depends.
A configuration is a complete local allocation \(a:V\to\{1,\ldots,q\}\): every role receives one indivisible house value. Write \(k_j(a)=|\{v:a(v)=j\}|\) and \(c_F(a)=\sum_{\{u,v\}\in E}|h_{a(u)}-h_{a(v)}|\). The decision variable is \(p_a\), the mass of population copies using configuration \(a\). The continuous problem is
\[ \min_{p\ge 0}\ \sum_a p_a c_F(a) \]
subject to
\[ \sum_a p_a=1 \qquad\text{and}\qquad \sum_a p_a k_j(a)=n\nu_j \quad\text{for every }j. \]
A solution is therefore a distribution over whole, integral local allocations; it is not fractional cake allocation inside a community. The objective is the average local envy. The masses \(\nu_j\) scale with the population, so houses are not held fixed while the number of agents grows.
This is a genuine high-multiplicity interpretation. Clearing denominators gives \(D\) finite copies of \(F\), \(D n\nu_j\) houses of value \(h_j\), and \(D p_a\) copies using configuration \(a\). Conversely, every such finite replicated instance induces a feasible \(p\). The finite lift is exactly Graphical House Allocation on a disjoint union of identical tree communities, with the same absolute-difference edge objective. Many identical hospital wards, campuses, or organizational branches with the same local interaction structure are a plausible regime for this model.
I expect \(\mathrm{CGHA}^{\mathrm{tree}}_\infty\) to be Class A. Its configuration LP has exponentially many columns, but its pricing problem is polynomial on a tree. Given dual prices \(\beta_j\), pricing asks for
\[ \min_{a:V\to[q]} \left( \sum_{\{u,v\}\in E}|h_{a(u)}-h_{a(v)}| -\sum_j\beta_j k_j(a) \right). \]
This is a standard tree-labeling dynamic program: root \(F\), and for each vertex \(v\) and label \(j\), compute the best cost conditional on \(a(v)=j\). The recurrence examines
\[ D_v(j)= -\beta_j+ \sum_{u\text{ child of }v} \min_{\ell\in[q]} \bigl(D_u(\ell)+|h_j-h_\ell|\bigr), \]
in \(O(nq^2)\) time. Standard separation-based LP machinery should therefore solve the continuous problem in polynomial time in \(n\), \(q\), and the input bit length.
The reason this can be easier than Theorem 4.10 is exactly the high-multiplicity relaxation. Its Unary 3-Partition reduction requires integral groups of flower gadgets to fit into individual bins. In \(\mathrm{CGHA}^{\mathrm{tree}}_\infty\), population mass can be distributed over different whole configurations, so the bin-packing integrality can disappear while every individual tree configuration still preserves the paper’s graph topology and local-envy calculation.
The weakest point is that this is an extension, not a literal single connected-tree instance: the continuum is a population of repeated tree components, and global house supply may be pooled across them. If a referee insists that every component must receive the same house multiset, then the relaxation largely vanishes and Theorem 4.10’s hardness should transfer instead, giving Class B. That boundary is itself a useful ChoCo question.
This case deliberately covers only Theorem 4.10. Natural follow-ups are the complexity of pricing on bounded-treewidth graphs, the finite-copy rounding rate, and the precise transition between pooled supplies (the Class-A configuration LP) and per-community supplies (where hardness may survive).
The only anchor raised is Theorem 4.10, and the proponent’s pricing argument is not where the case against should attack. The tree-labeling dynamic program appears sound. The deeper problem is that \(\mathrm{CGHA}^{\mathrm{tree}}_\infty\) does not continuize the population of the paper’s problem while preserving its defining object.
The finite lift of the proposed model is \(D\) disjoint copies of \(F\), with one globally pooled supply of houses. That is a forest, not a bounded-degree tree. Theorem 4.10 concerns one connected tree with one bijection between its vertices and houses. This distinction is structural: the paper repeatedly identifies disconnectedness and pooled assignment as sources of radically different behaviour. The proposed LP becomes meaningful precisely because houses may be redistributed between independent copies and configurations may be mixed. If every copy receives its own copy of the house multiset, the copies decouple and the continuum adds nothing to the original optimization. If supply is pooled, the model is a new resource-pooling problem on a disjoint union, rather than the high-multiplicity version of the connected-tree problem proved NP-hard in Theorem 4.10.
There is also a more fundamental population issue. A marginal distribution over role types \(v\in V(F)\) does not specify the local-envy objective. The same role masses \(\mu_v=1/|V(F)|\) can be coupled into copies with different adjacency relations, producing different total envy. In an ordinary nonatomic population, finite-degree edges have measure zero under the product measure, so an edge objective requires an additional graphing or coupling structure. The proposed \(p_a\) is exactly such additional structure, but it is a distribution over complete finite communities and their allocations—not merely a continuous society of agent types. The continuous object has moved from the population to a lottery or empirical distribution over whole allocations.
The natural alternatives do not repair this without changing the problem. Assigning house-value distributions directly to vertex masses loses the correlation between neighboring vertices’ assignments; independently sampling endpoints produces a different envy objective, while choosing couplings restores a configuration-level model. A graphon or graphing can preserve adjacency, but then the type space must retain a copy or location coordinate, and finite role marginals no longer determine the instance. Connecting the repeated copies likewise introduces connector roles and a new topology. Preserving per-copy feasibility removes the relaxation; pooling across copies creates a different allocation model.
Thus the strongest negative claim is that the paper offers no canonical population continuization that retains both essential ingredients of Theorem 4.10: connected sparse topology and indivisible one-to-one allocation. The proposed construction is a coherent high-multiplicity model, but its interesting feature is community-level supply pooling and convexification, not a continuous version of the paper’s connected-tree problem.
The honest weakness is substantial: repeated identical branches with a centrally pooled resource supply are a plausible high-multiplicity regime, and the resulting configuration LP is computationally nontrivial. If ChoCo accepts such community-template models as genuine population continuizations, then Theorem 4.10 is a real surviving anchor. The case against can therefore reject the proposed mirror as a faithful ChoCo mirror, but it cannot honestly establish the universal “no worthwhile scenario” claim.
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.