| paper | Local Envy-Freeness in House Allocation Problems |
| authors | A. Beynier, Y. Chevaleyre, L. Gourvès, Ararat Harutyunyan, Julien Lesca, N. Maudet et al. |
| venue | ATAL 2018 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\); every valid input admits a locally envy-free allocation. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given finite type sets \(\Theta\) and \(H\), rational masses \(\mu_\theta\), rational supplies \(\sigma_h\) with \(\sum_h \sigma_h=1\), strict rankings \(\succ_\theta\), and a symmetric matching kernel \(\eta_{\theta,\theta'}\) satisfying \(\sum_{\theta'}\eta_{\theta,\theta'}=\mu_\theta\), does there exist nonnegative \(y_{\theta,\theta',h,h'}\) satisfying \(y_{\theta,\theta',h,h'}=y_{\theta',\theta,h',h}\), \(\sum_{h,h'}y_{\theta,\theta',h,h'}=\eta_{\theta,\theta'}\), \(\sum_{\theta,\theta',h'}y_{\theta,\theta',h,h'}=\sigma_h\), and \(y_{\theta,\theta',h,h'}=0\) whenever \(h'\succ_\theta h\) or \(h\succ_{\theta'}h'\)?
A finite-type, high-multiplicity house-allocation LP: agent mass \(\mu\) is paired by \(\eta\), each unit receives one integral house type from supply \(\sigma\), and \(y\) records mass by endpoint types and house types; forbidden \(y\)-cells encode local non-envy.
The mirror covers the fixed-matching decision problem of Theorem 3.1. It leaves the location problem of Theorem 5.1, the \(\textsc{max\text{-}LEF}\) and \(\textsc{max\text{-}NE}\) optimization results, parameterized results, and experiments unmirrored.
My lead is a continuous version of the paper’s fixed-network problem, anchored in Theorem 3.1, which is proved in the paper:
\(\textsc{dec-LEF}\) is NP-complete even when the social network \(G\) is a matching.
Here \(\textsc{dec-LEF}\) asks, given agents with strict preferences over objects and a fixed graph \(G\), whether there is a bijective allocation \(A\) such that no agent prefers a neighbor’s object to her own. The theorem is proved by a reduction from \(3\textsc{SAT}\). Its important feature is that hardness survives when every agent has only one neighbor.
The continuous mirror I would propose is Matching-LEF\(_\infty\). An instance contains:
A type includes everything relevant to the problem: preferences and the agent’s local social role. The kernel is the type-level representation of a large collection of repeated two-person teams, paired shifts, or handoff relationships.
The question is whether one can allocate one integral house type to almost every unit of agent mass, respecting the supplies, so that almost every matched pair is locally envy-free. Equivalently, use variables \(y_{\theta,\theta',h,h'}\) for the mass of matched pairs whose endpoints have types \(\theta,\theta'\) and receive \(h,h'\). They must satisfy the matching marginals, the house-supply constraints, and
\[ y_{\theta,\theta',h,h'}>0 \quad\Longrightarrow\quad \neg(h'\succ_\theta h) \ \text{ and }\ \neg(h\succ_{\theta'}h'). \]
This is a linear-programming feasibility problem with polynomially many variables in \(|\Theta|\) and \(|H|\). The fractional variables do not mean that an individual receives a lottery or a fraction of a house: each unit of mass receives one integral house type. They record only how a large population of interchangeable agents is divided among those integral choices.
This is a plausible high-multiplicity regime. Imagine a large organisation with many repeated pairs of workers taking adjacent shifts. Workers in the same cohort have the same ranking of a finite collection of job categories, and the authority cares about envy within the paired handoff relation. The population may contain \(R\) copies of every type, with \(R\) very large while \(|\Theta|\) remains moderate. The paper’s shift example and its discussion of “similar” agents make this interpretation especially natural. Its future-work question about fixing the number of different rankings points in the same direction.
I would therefore expect Matching-LEF\(_\infty\) to be Class A: tractable by the LP above. The discrete hardness in Theorem 3.1 is driven by individually arranged gadget agents and objects. Once those agents become exchangeable masses and the network is a matching, the local constraints decompose by pair type and the Boolean gadget can be mixed at the mass level. A useful follow-up would be to establish a rounding theorem: how much local envy is introduced when a rational continuous solution is rounded to a finite population, and whether exact feasibility returns when all masses have a sufficiently large common denominator.
The weakest point is that the mirror replaces uniquely named objects by repeatedly available house types, or else requires a compressed description of many micro-houses. If the authors regard the identity of every object as essential, they may reject this as too substantial a change. I think the modification is defensible: one item per agent remains, preferences remain strict over house types, and only the population—not an individual outcome—is continuized. But this is where the positive case is most vulnerable.
A second, harder mirror is anchored in Theorem 5.1, also proved in the paper:
\(\textsc{dec-location-LEF}\) is NP-complete.
In this problem, the input is a graph \(G=(V,E)\), agents with strict preferences over objects, and the question is whether there are both an allocation \(A\) and a placement \(L\) of agents on vertices such that adjacent locations contain no envy. The proof reduces from \(\textsc{Independent Set}\): with \(s\) vertices and target size \(k\), it uses \(s-k\) agents \(X_i\), \(k\) agents \(L_j\), objects \(q_i\) and \(t_j\), with each \(X_i\) ranking \(q_i\) first and every \(L_j\) ranking the \(t\)-objects above the \(q\)-objects.
The corresponding Location-LEF\(_\infty\) instance has vertex capacities \(\rho_v\), masses of preference types \(\mu_\theta\), and a discrete supply of houses. A solution is a mass assignment \(z_{\theta,v,h}\): mass of type \(\theta\) placed at \(v\) and receiving \(h\). It must satisfy
\[ \sum_{v,h}z_{\theta,v,h}=\mu_\theta,\qquad \sum_{\theta,h}z_{\theta,v,h}=\rho_v,\qquad \sum_{\theta,v}z_{\theta,v,h}=\sigma_h. \]
For every edge \(\{v,w\}\in E\), every positive-mass choice at \(v\) and every positive-mass choice at \(w\) must satisfy mutual non-envy. Thus each unit of mass still occupies one location and receives one indivisible object; only the aggregate placement is fractional.
This has a natural regime of repeated cohorts occupying a fixed workplace, campus, or shift graph. Take \(R\) copies of every \(X_i\)-type and \(R\) copies of the common \(L\)-type, with \(R\) much larger than the number of distinct preference types. Give each graph vertex capacity \(R\), and use \(R\) copies of the relevant \(q\)- and \(t\)-objects, keeping them individually ordered so the \(L\)-agents have a strict common ranking.
The Independent Set argument survives. If positive \(L\)-mass occupied two adjacent vertices, two \(L\)-agents at those vertices would receive distinct objects, and because their rankings are identical and strict, one would envy the other. Hence the support of \(L\)-mass must be an independent set. Since each vertex has capacity \(R\) and the total \(L\)-mass is \(kR\), its support contains at least \(k\) vertices. Conversely, an independent set of size \(k\) supports the obvious placement of all \(L\)-mass, with the \(X_i\)-cohorts receiving their top \(q_i\)-objects. Thus this mirror should be Class B: the discrete hardness transfers, because the combinatorics live in the graph topology and the placement decision, not in the number of named agents.
This second mirror is less elegant than the first because it preserves individually distinguishable micro-houses. It is nevertheless useful: it shows that continuization need not make every problem easy. The paper’s hardness landscape can survive in a genuinely high-multiplicity population, while Theorem 3.1 suggests that another part of the landscape may collapse to LP feasibility. I would not claim to mirror the paper’s optimization and approximation results without separate definitions of mass-weighted LEF and non-envy; these two decision problems are enough for a strong case.
I cannot honestly make the universal negative case. The first anchor survives the strongest objections.
The proposed Matching-LEF\(_\infty\) does change distinct houses into repeatable house types, and therefore changes strict preferences over individual objects into strict preferences over categories. But that modification is forced by a genuine high-multiplicity interpretation: repeated cohorts receive one integral job category each, with per-capita supplies scaling with population. The matching kernel preserves the relational information that local envy needs. The resulting feasibility problem is a legitimate population-continuized computational problem, not merely fractional allocation. Its LP structure is precisely the sort of tractability gain the programme seeks. Calling it “a different problem” would be too weak: it is a sensible high-multiplicity version of the paper’s matching-network setting.
The Location-LEF\(_\infty\) construction is substantially weaker. Its claimed independent-set argument fails with repeatable house types. If adjacent positive mass at two locations receives the same type \(t\), identical \(L\)-types do not envy one another, since neither prefers \(t\) to \(t\). Thus positive \(L\)-mass need not have independent support.
Moreover, the displayed variables \(z_{\theta,v,h}\) do not themselves impose local envy-freeness. A forbidden combination across an edge requires a disjunctive constraint: at least one of the two masses must be zero. This is not an ordinary LP constraint. Retaining the reduction requires every copy of every house to remain individually ordered. But then the house labels, and hence the preference descriptions, grow with the replication factor; the construction no longer has a fixed finite house-type space. It has preserved object identity rather than continuized only the population.
That second anchor could perhaps be repaired into a meaningful capacitated graph-placement problem, but it would need to be presented as a new model and reproved from scratch. It does not currently establish the proposed mirror. It also cannot rescue the universal negative, because Matching-LEF\(_\infty\) already supplies one credible mirror.
The cited Cato work is not a collision: it studies local envy-freeness in large economies and gives an economic characterization, rather than the computational high-multiplicity question at issue. [Cato’s abstract](https://www.sciencedirect.com/science/article/abs/pii/S016548961000003X)
So the strongest honest verdict is: reject the location anchor as stated, but do not reject the paper. The fixed-matching result remains a worthwhile continuous mirror.
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.