Answer: Polynomial-time solvable in \(m,\tau,L\); every valid input admits a locally envy-free allocation.
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate, we can extend the previous hardness result to more general classes of graphs. It suffices to add, in the graph of the previous proof, dummy agents who are connected to three other agents. They have a dummy resource on top of their ranking, followed by the whole ranking of one of her neighbors. Each initial agent ranks last the dummy resources.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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'\)?
Let \(\Theta\) be a nonempty set of agent types and \(H\) a nonempty set of house types, with \(m=|H|\). A society is given by its support: the list of its \(\tau=|\Theta|\) types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Support size means the number of listed types, not the number of possible rankings.
Each type has a strict linear order \(\succ_\theta\) on \(H\). House supplies are binary rationals \(\sigma_h\geq0\) with \(\sum_h\sigma_h=1\). Each agent receives one house; different agents may receive distinct copies of the same house type.
The input also specifies a nonnegative binary-rational symmetric kernel \(\eta_{\theta,\theta'}\) with \(\sum_{\theta'}\eta_{\theta,\theta'}=\mu_\theta\). It describes a fixed pairing of the entire society, counted by ordered endpoints; diagonal entries describe pairs of distinct agents of the same type.
A feasible allocation is a nonnegative real array \(y_{\theta,\theta',h,h'}\), describing ordered paired-agent mass receiving house types \(h,h'\), satisfying, for every applicable index,
\(y_{\theta,\theta',h,h'}=y_{\theta',\theta,h',h}\), \(\sum_{h,h'}y_{\theta,\theta',h,h'}=\eta_{\theta,\theta'}\), and \(\sum_{\theta,\theta',h'}y_{\theta,\theta',h,h'}=\sigma_h\).
Local envy-freeness requires \(y_{\theta,\theta',h,h'}=0\) whenever \(h'\succ_\theta h\) or \(h\succ_{\theta'}h'\); receiving the same house type creates no envy.
Is deciding whether such a locally envy-free allocation exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard, where \(L\) is the total binary input length?
For finite agents with strict rankings and equally many distinct houses, deciding whether a bijective locally envy-free allocation exists is NP-complete even when the social network is a perfect matching. [Source](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p292.pdf)
No result settling the exact continuous formulation above was located in the literature search.
The exact continuous formulation is polynomial-time solvable. In fact, every valid input admits a locally envy-free allocation.
The permission for paired agents to receive the same house type gives a universal witness. Below I verify it and then address the substantive distinction from finite bijective allocation.
For every \(\theta,\theta'\in\Theta\) and \(h,h'\in H\), define
\[ y_{\theta,\theta',h,h'} = \begin{cases} \eta_{\theta,\theta'}\sigma_h,&h=h',\\ 0,&h\ne h'. \end{cases} \]
Thus each pairing class is split across house types according to their supplies, and both endpoints receive the same house type.
First, the kernel normalization implies
\[ \sum_{\theta,\theta'}\eta_{\theta,\theta'} = \sum_\theta\mu_\theta = 1. \]
We now check every allocation requirement.
Nonnegativity. Every entry is nonnegative because both the kernel and supplies are nonnegative.
Symmetry. If \(h\ne h'\), both entries in the required symmetry equation vanish. If \(h=h'\), kernel symmetry gives
\[ y_{\theta,\theta',h,h} = \eta_{\theta,\theta'}\sigma_h = \eta_{\theta',\theta}\sigma_h = y_{\theta',\theta,h,h}. \]
Preservation of the fixed pairing. For every ordered type pair,
\[ \sum_{h,h'}y_{\theta,\theta',h,h'} = \eta_{\theta,\theta'}\sum_h\sigma_h = \eta_{\theta,\theta'}. \]
In particular, the total first-endpoint mass of each type remains correct:
\[ \sum_{\theta',h,h'}y_{\theta,\theta',h,h'} = \sum_{\theta'}\eta_{\theta,\theta'} = \mu_\theta. \]
House supplies. For each house type \(h\),
\[ \sum_{\theta,\theta',h'}y_{\theta,\theta',h,h'} = \sigma_h\sum_{\theta,\theta'}\eta_{\theta,\theta'} = \sigma_h. \]
This calculation uses precisely the ordered-endpoint convention in the question.
Local envy-freeness. Every positive entry has \(h=h'\). A strict linear order is irreflexive, so neither endpoint strictly prefers its partner’s house type to its own. Every forbidden entry therefore vanishes.
The construction is a feasible locally envy-free allocation for arbitrary rankings, supplies, and admissible kernels.
On inputs promised to satisfy the hypotheses, the decision algorithm simply answers yes. If validity must also be checked, all stated input conditions can be checked using polynomially many exact rational operations.
An explicit witness has at most \(\tau^2m\) nonzero entries. Each is the product of two input rationals, whose binary encoding length is at most the sum of their encoding lengths, up to a constant. Consequently, the witness can also be constructed in time polynomial in \(m,\tau,L\).
The polynomial-time conclusion extends beyond the universal witness: even if specified assignments—including all same-house assignments—are forbidden, feasibility remains polynomial-time solvable, provided the forbidden set is explicitly listed or computable in polynomial time.
To prove this extension, retain one real variable for each ordered quadruple. There are \(N=\tau^2m^2\) variables. Impose:
This is a rational linear feasibility problem. It has at most \(N\) symmetry equations, \(\tau^2\) pairing equations, \(m\) supply equations, and \(N\) zero equations. All matrix coefficients belong to \(\{-1,0,1\}\); all right-hand sides are input rationals or zero. Its total encoding length is therefore polynomial in \(m,\tau,L\).
The standard polynomial-time theorem for rational linear programming decides feasibility over the reals in time polynomial in that encoding length. Its hypotheses hold here, and the constraints are exactly the allocation requirements. No integrality condition is present.
The cited paper defines allocations as bijections between finite agents and distinct objects and proves hardness even for a matching network. [Beynier et al., Section 2 and Theorem 3.1](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p292.pdf).
A minimal example demonstrates the difference. Take a single type \(\theta\), with
\[ \mu_\theta=\eta_{\theta,\theta}=1,\qquad H=\{a,b\},\qquad \sigma_a=\sigma_b=\frac12,\qquad a\succ_\theta b. \]
The continuous allocation
\[ y_{\theta,\theta,a,a} = y_{\theta,\theta,b,b} = \frac12 \]
satisfies every constraint.
In the corresponding finite instance, two paired agents both rank \(a\) above \(b\), and there is one distinct house of each type. Every bijection gives one agent \(b\) and its partner \(a\), creating envy.
Thus aggregate rational supplies do not impose finite indivisibility. The continuous formulation permits splitting a pairing class into submasses whose endpoints receive equal house types, while a finite bijection need not permit such an assignment.
⟨structured verdict parsed — rendered above⟩
The prover resolves the exact continuous problem correctly. Its explicit witness satisfies every required constraint for every valid input. No major or minor mathematical issues were found.
\(\sum_{\theta,\theta'}\eta_{\theta,\theta'}=\sum_\theta\mu_\theta=1\).
This identity is valid, including when some kernel entries vanish.
\(\sum_{h,h'}y_{\theta,\theta',h,h'}=\eta_{\theta,\theta'}\sum_h\sigma_h=\eta_{\theta,\theta'}\).
The subsequent calculation recovering each type’s mass is also correct.
\(\sum_{\theta,\theta',h'}y_{\theta,\theta',h,h'}=\sigma_h\sum_{\theta,\theta'}\eta_{\theta,\theta'}=\sigma_h\).
There is no missing factor of two: the specified supply constraint counts ordered endpoints, exactly as the calculation does.
No mathematical repair or additional clarification is needed. The universal witness alone establishes the requested conclusion; the linear-programming extension and finite comparison are consistent supporting material.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.