| paper | Envy-Free House Allocation under Uncertain Preferences |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 4.2
statement extracted from the paper’s text layer
Given finite applicant types with rational masses, a fixed menu of recurring house classes with rational capacities summing to one, and an independent preference lottery for each type, compute a feasible mass matching \(x\) maximizing the per-capita log EF probability \(\sum_{t,h} x_{t,h} \log q_{t,h}\), where \(q_{t,h}\) is the probability that \(h\) is top among the menu for type \(t\).
High-multiplicity cohorts of indistinguishable applicants, recurring house classes with capacities, mass matching x, and objective equal to the per-capita logarithm of the paper's EF probability.
The mirror covers fixed-menu allocation and proposes a full-menu joint-probability analogue; it leaves the paper's uncertainty-model-specific existence results, approximation bounds, and pairwise model results aside.
My strongest case is that this paper has a credible continuous mirror once its “agents” are read as large cohorts rather than named individuals. This is not because preference uncertainty is itself continuization: the new object is the population distribution \(\mu\), while the paper’s probability model remains an uncertainty model on top of it.
A plausible setting is municipal housing. There are \(K\) applicants, but only a small number of cohort types: household size, accessibility needs, workplace region, income band, and so on. A type \(t\) includes the cohort’s complete state-contingent preference information. Thus \(K\mu_t\) applicants share type \(t\), with \(K\gg |T|\). Houses are recurring classes or blocks with capacities \(\nu_h\); an aggregate allocation is the limit of ordinary one-house-per-person matchings, not a fractional entitlement given to an individual.
My lead anchor is Theorem 7.2, proved in this paper. It states that, under the joint probability model, no polynomial-time algorithm achieves a \((6/5-\varepsilon)\)-approximation for MAX-PROBEF for any constant \(\varepsilon>0\), unless \(P=NP\).
The corresponding continuous problem is HM-Joint-MAX-PROBEF.
An instance consists of:
The planner chooses a menu \(S\subseteq H\) whose capacities sum to one and a mass matching \(x_{t,h}\). Every type’s mass is assigned, every selected house capacity is filled, and unselected houses receive no mass:
\[ \sum_h x_{t,h}=\mu_t,\qquad \sum_t x_{t,h}=\nu_h\ \text{for }h\in S. \]
The allocation is envy-free in state \(\ell\) if, for every \(x_{t,h}>0\), house \(h\) is ranked above every other selected house \(h'\in S\setminus\{h\}\) by \(R_{\ell,t}\). The objective is
\[ \max_x\ \Pr[\text{the mass allocation is EF}] = \max_x\sum_{\ell=1}^r p_\ell\mathbf 1[\text{x is EF in state \ell}]. \]
A solution is the selected menu \(S\) and a feasible mass matching \(x\) attaining the maximum.
This is recognisably the authors’ problem. The allocation is fixed before uncertainty resolves; EF is evaluated against the same selected houses; and the joint model is retained literally, except that “every agent” becomes “almost every member of every positive-mass cohort.” A natural application is a large housing market in which a common latent state—future transit links, school assignments, rents, or zoning—induces one of several correlated preference profiles. The authority must commit to one assignment before learning the state.
I expect the general problem to be Class B: the hard combinatorics in Theorem 7.2 live in the selected house agenda and the profile structure, not in the number of named applicants. Population mass should not automatically dissolve that hardness. A proof would need a gap-preserving lift of the paper’s reduction in which splitting a cohort across houses cannot evade the gadget penalties. That is plausible if house blocks are capacity-complete and EF depends on the support of the selected menu, but it is not automatic. The theorem from the paper does not itself establish the continuous lower bound.
My safer, algorithmic anchor is Proposition 4.2, proved in this paper. It says that, for any reasonable independent uncertainty model, once the set \(M'\) of assigned houses is fixed, an allocation maximizing EF probability can be found in polynomial time by maximum-weight matching.
Its continuous counterpart is HM-FixedMenu-LogMAX-PROBEF. The input is a mass distribution \(\mu\) over uncertainty types, a fixed house menu \(M'\) with capacities \(\nu_h\), and for every type \(t\) a lottery \(\Delta_t\) over rankings. Define
\[ q_{t,h}=\Pr_{R\sim\Delta_t} [h\text{ is the top house in }M']. \]
The decision variable is again a feasible mass matching \(x_{t,h}\). The objective is the per-capita log probability
\[ \max_x\ \Lambda(x)= \sum_{t\in T}\sum_{h\in M'}x_{t,h}\log q_{t,h}. \]
This normalization is forced by high multiplicity. If \(x\) has denominator \(K\), it describes \(K\) ordinary agents of each type-house pair, and independent uncertainty gives
\[ \Pr[\text{all K agents are EF}] =\exp(K\Lambda(x)). \]
Thus \(\Lambda\) is exactly the logarithmic rate of the paper’s MAX-PROBEF objective, not an unrelated welfare function.
For a fixed menu, the \(q_{t,h}\) are constants, so the continuous problem is a transportation LP, equivalently a maximum-cost flow problem with edge weights \(\log q_{t,h}\). I therefore expect this mirror to be Class A. It is a genuine continuous-optimization formulation of the paper’s structural result, and it exposes precisely what Proposition 4.2 exposes: once house selection disappears, the remaining allocation problem is easy.
The programme would then study the boundary between these two questions: fixed-menu HM-MAX-PROBEF is an LP, while choosing the menu may retain the paper’s NP-hard combinatorics. Further questions include whether the joint-model hardness survives fractional mass matching, whether finite-\(K\) allocations can be rounded from \(x\) with controlled loss, and whether the compact-indifference model admits an analogous large-deviation algorithm.
The weakest point is that repeated house classes and mass matchings are not literally the paper’s finite set of individually labelled houses. Also, under the independent lottery model, the raw probability that an entire continuum is envy-free collapses to zero; the per-capita logarithmic rate is necessary to obtain a nondegenerate limit. If the authors reject that normalization or insist that identical house copies must remain individually distinguishable under strict rankings, the mirror becomes substantially weaker. The joint-probability formulation avoids that problem most cleanly, which is why Theorem 7.2 is my lead anchor.
I cannot honestly make the requested universal negative case. Theorem 7.2 is weaker than the proponent suggests, but Proposition 4.2 supplies a genuine surviving mirror.
The joint-probability anchor does not automatically transfer its hardness. In the paper, a profile is an arbitrary vector of rankings for named agents. The reduction encodes the exact-cover incidence structure in those agent-specific rankings and in individually identified houses. A type-level version must either retain one type for each such incidence role—making the “continuum” mostly a weighted rewrite—or replace the model by finitely many common, state-contingent rankings \(R_{\ell,t}\). The latter is a sensible robust capacitated-allocation problem, but it is no longer the paper’s unrestricted joint-profile model, and Theorem 7.2 proves no hardness for it. The proposed Class-B prediction is therefore unsupported, although the resulting question remains legitimate.
The fixed-menu anchor is much harder to defeat. For \(K\) replicated agents, with \(Kx_{t,h}\) type–house assignments,
\[ \Pr[\mathrm{EF}]=\prod_{t,h}q_{t,h}^{Kx_{t,h}}, \qquad \frac1K\log\Pr[\mathrm{EF}] =\sum_{t,h}x_{t,h}\log q_{t,h}. \]
Thus the proponent’s log-rate is not an arbitrary replacement objective: it is exactly the high-multiplicity limit of the paper’s MAX-PROBEF objective. With a fixed menu it is a transportation/max-cost-flow problem. The raw probability does collapse to zero whenever some \(q_{t,h}<1\), but the per-capita log rate is the standard and mathematically faithful repair; the programme explicitly permits such natural mass variants.
There is a modelling caveat: because house allocation requires one house per agent, a nontrivial population limit must also use repeated house classes or scaled capacities. If that is rejected as outcome-space continuization, both proposed mirrors fail. But recurring housing blocks and cohort-level capacities are a plausible high-multiplicity interpretation, not an obviously illegitimate one.
So the strongest negative conclusion is narrow: the proponent overstates the joint-model hardness mirror and has not shown that the paper’s reduction survives type aggregation. It cannot support the universal claim that no worthwhile mirror exists. Proposition 4.2 is already a faithful, nontrivial continuous analogue, and Theorem 7.2 still leaves a credible open population-level question.
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.