Answer: \(\mathrm{NP}\)-complete, even with \(\tau=1\), a connected block graph, and strictly positive supplies.
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a locally envy-free allocation iff formula φ = φalloc ∧φlef is satisfiable. Note that the structural allocation clauses in φalloc are sufficient to impose that exactly one object is assigned to every agent, because there are exactly as many objects as agents.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many block types \(b\), each a graph \(H_b=(P_b,E_b)\) with strict rankings over \(K\) item classes at its positions, rational block masses \(\lambda_b\) with \(\sum_b |P_b|\lambda_b=1\), and rational per-capita item supplies \(s_k\) with \(\sum_k s_k=1\), decide whether there are nonnegative rational masses \(z_{b,a}\) such that \(\sum_{a\in\mathcal A_b} z_{b,a}=\lambda_b\) for each \(b\), and \(\sum_b\sum_{a\in\mathcal A_b} z_{b,a}|\{p\in P_b:a(p)=k\}|=s_k\) for each \(k\). Here \(\mathcal A_b\) contains the assignments giving each position one indivisible item and satisfying local envy-freeness on every edge of \(H_b\); item-class copies are interchangeable, and distinct blocks have no edges between them.
A society is given by its support: a list of \(\tau\) block types with positive masses, each encoded as a binary rational; \(\tau\) counts listed types, not possible types.
There are \(m\geq1\) interchangeable item classes. Each block type \(b\) has an explicitly given finite nonempty simple undirected graph \(H_b=(P_b,E_b)\), and each position \(p\) has a strict linear order \(\succ_{b,p}\) over the classes. Distinct blocks have no edges between them.
Block masses \(\lambda_b>0\) and nonnegative rational per-capita supplies \(s_k\) satisfy \(\sum_b|P_b|\lambda_b=1\) and \(\sum_{k=1}^{m}s_k=1\); all rationals are binary encoded.
Let \(\mathcal A_b\) consist of maps \(a:P_b\to\{1,\ldots,m\}\) satisfying \(a(p)\succ_{b,p}a(q)\) and \(a(q)\succ_{b,q}a(p)\) on every edge \(\{p,q\}\in E_b\). Each position receives one indivisible copy; classes may repeat within a block, but equal classes at adjacent positions violate this strict condition. The sets \(\mathcal A_b\) are defined implicitly, not listed in the input.
Feasibility means existence of \(z_{b,a}\in\mathbb Q_{\geq0}\) with \(\sum_{a\in\mathcal A_b}z_{b,a}=\lambda_b\) for every \(b\), and \(\sum_b\sum_{a\in\mathcal A_b}z_{b,a}|\{p\in P_b:a(p)=k\}|=s_k\) for every \(k\).
Write running times in \(m\), \(\tau\), \(B=\sum_b|P_b|\), and the total input bit length \(L\).
Is this block-mass feasibility problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finitely many agents and equally many distinct objects, locally envy-free allocation existence is equivalent to satisfiability of a polynomial-size CNF encoding ([SAT equivalence](https://ebooks.iospress.nl/pdf/doi/10.3233/FAIA240900)).
That discrete existence problem is \(\mathrm{NP}\)-complete even when the social graph is a matching ([discrete complexity](https://www.lamsade.dauphine.fr/~aharutyunyan/house.pdf)). No result settling this precise block-mass problem was located in the search.
The block-mass feasibility problem is \(\mathrm{NP}\)-complete. Hardness holds even with \(\tau=1\), a connected block graph, and strictly positive supplies for every class.
The reduction explicitly handles fractional mixtures: in a no-instance, every admissible allocation consumes too few copies of one distinguished class, so averaging cannot meet its prescribed supply.
We use the \(\mathrm{NP}\)-complete problem Independent Set: given a finite simple graph \(G=(V,E)\), with \(n=|V|\), and an integer \(1\leq K\leq n\), decide whether \(G\) has an independent set of size at least \(K\). Its hardness follows equivalently from Vertex Cover, since \(S\subseteq V\) is independent exactly when \(V\setminus S\) is a vertex cover. Vertex Cover is one of [Karp’s classical completeness results](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Introduce the following \(m=n+3\) classes:
There is exactly one block type. Its positions are:
Thus \(\tau=1\) and \(B=n+K+2\).
The block graph has precisely these edges:
In particular, \(u\) is adjacent to every other position, so the block graph is connected.
Fix a strict order \(R\) of all classes other than \(g,h\). The guard preferences are
\(g\succ_u h\succ_u R,\qquad h\succ_w g\succ_w R.\)
The same order \(R\) appears at both guards.
For every core position, set
\(t_v\succ_{p_v} f\succ_{p_v} g\succ_{p_v}\text{all remaining classes}.\)
The remaining classes are ordered arbitrarily but strictly.
For every filler position, put every private class above \(g\), and both \(f,h\) below \(g\):
\(t_{v_1}\succ_{r_i}\cdots\succ_{r_i}t_{v_n}\succ_{r_i}g\succ_{r_i}f\succ_{r_i}h,\)
where \(v_1,\ldots,v_n\) is a fixed enumeration of \(V\). Every preference is therefore an explicitly specified strict linear order over all \(m\) classes.
Give the sole block mass
\(\lambda=1/B.\)
Set supplies
\(s_{t_v}=1/B\quad(v\in V),\qquad s_f=K/B,\qquad s_g=s_h=1/B.\)
These satisfy both required normalizations:
\(|P|\lambda=B/B=1,\qquad \sum_k s_k=(n+K+2)/B=1.\)
All supplies are positive, and every rational has binary encoding length \(O(\log(B+1))\).
Let \(a\) be any admissible allocation of the constructed block.
We claim that \(a(u)=g\) and \(a(w)=h\).
First suppose exactly one guard receives a class outside \(\{g,h\}\). That guard ranks its neighbor’s class above its own, violating admissibility on \(\{u,w\}\).
If both guards receive classes outside \(\{g,h\}\), equal classes violate strictness. For distinct classes, the guards’ identical order \(R\) means the guard receiving the less-preferred class envies the other.
Consequently both guards receive classes in \(\{g,h\}\). They must receive different classes. The assignment \(a(u)=h,\ a(w)=g\) violates \(u\)’s strict comparison. Thus the only possibility is
\(a(u)=g,\qquad a(w)=h.\)
Each core position is adjacent to \(u\), which receives \(g\). It must therefore receive a class strictly above \(g\) in its own ranking. Exactly two classes qualify:
\(a(p_v)\in\{t_v,f\}.\)
Likewise, each filler position must receive a private class:
\(a(r_i)\in\{t_v:v\in V\}.\)
The comparison in the opposite direction is automatically satisfied: \(u\) ranks \(g\) above every other class.
Define
\(S(a)=\{v\in V:a(p_v)=f\}.\)
If \(\{v,v'\}\in E\), both corresponding core positions cannot receive \(f\), because equal classes violate the strict edge condition. Hence \(S(a)\) is independent.
Conversely, for adjacent core positions, every other combination of their allowed classes satisfies both comparisons:
Therefore every independent set \(S\subseteq V\) determines admissible core assignments by giving \(f\) to its vertices and \(t_v\) to the others. Any private-class assignments to the fillers then complete an admissible allocation.
Since neither guards nor fillers can receive \(f\), the number of copies of \(f\) in any admissible allocation is exactly
\(c_f(a)=|S(a)|\leq\alpha(G),\)
where \(\alpha(G)\) is the maximum independent-set size.
Suppose \(\alpha(G)\geq K\). Taking a subset if necessary, choose an independent set \(S\) of size exactly \(K\).
Assign:
Section 2 proves admissibility. This allocation uses each private class exactly once, class \(f\) exactly \(K\) times, and each guard class exactly once.
Setting \(z_a=\lambda=1/B\), with all other allocation weights zero, meets every prescribed supply.
Conversely, suppose nonnegative rational weights \(z_a\) satisfy the block-mass and supply equations. In particular,
\(\sum_a z_a=1/B,\qquad \sum_a z_a c_f(a)=K/B.\)
The bound proved in Section 2 gives
\(K/B=\sum_a z_a c_f(a)\leq\alpha(G)\sum_a z_a=\alpha(G)/B.\)
Thus \(K\leq\alpha(G)\).
This proves the exact equivalence
\(\text{constructed society is feasible}\quad\Longleftrightarrow\quad\alpha(G)\geq K.\)
The inequality applies to every fractional mixture, so the reduction does not assume integrality of the allocation weights.
Here \(m=n+3\), \(\tau=1\), and \(B=n+K+2\leq2n+2\). The construction writes \(B\) preference lists of length \(m\), at most \(O(B^2)\) edges, and \(m+1\) rationals.
Using an explicit encoding, its bit length and construction time are \(O(n^2\log(n+1))\). Equivalently, the construction is polynomial in \(m,\tau,B,L\). Hence this is a polynomial-time many-one reduction proving \(\mathrm{NP}\)-hardness.
The implicit allocation sets require a certificate argument: listing all admissible allocations could take exponential space.
Put \(q=\tau+m\). For every admissible pair \((b,a)\), form an integer column \(v_{b,a}\in\mathbb Z^q\). Its first \(\tau\) coordinates identify the block type:
\((v_{b,a})_j=1\) if \(j=b\), and \(0\) otherwise.
Its remaining coordinates are the class counts:
\((v_{b,a})_{\tau+k}=|\{p\in P_b:a(p)=k\}|.\)
Every entry lies between \(0\) and \(B\). Feasibility is precisely
\(\sum_{b,a}z_{b,a}v_{b,a}=d,\qquad z_{b,a}\geq0,\)
where \(d=(\lambda_1,\ldots,\lambda_\tau,s_1,\ldots,s_m)\).
Assume feasibility, and choose a rational feasible solution with the smallest number \(r\) of positive weights. Such a choice exists because the collection of columns is finite.
Its supported columns must be linearly independent. Otherwise, their integer entries give a nonzero rational dependence
\(\sum_{i=1}^r c_i v_i=0.\)
Summing the first \(\tau\) coordinates yields \(\sum_i c_i=0\), because every column has exactly one \(1\) among those coordinates. Thus the coefficients \(c_i\) include both positive and negative values.
Set
\(t=\min_{i:c_i>0}z_i/c_i>0,\qquad z'_i=z_i-tc_i.\)
Every new weight is nonnegative, at least one becomes zero, and the represented vector remains \(d\). This contradicts minimality. Therefore \(r\leq q\).
Choose \(r\) rows on which the supported columns form a nonsingular integer matrix \(C\).
Let \(D\) be the product of the denominators of the coordinates of \(d\). Since those rationals occur in the input, \(\log D=O(L)\). Also every coordinate of \(d\) lies in \([0,1]\), by the normalization assumptions.
The supported weights solve \(Cz=d_I\). By Cramer’s rule,
\(z_i=\det(C_i')/(D\det C),\)
where \(C_i'\) replaces column \(i\) of \(C\) by the integer vector \(Dd_I\).
The determinant expansion gives
\(|\det C|\leq r!B^r,\qquad |\det C_i'|\leq r!DB^{r-1}.\)
Consequently every weight has numerator and denominator encoding length
\(O\!\left(L+q\log(q(B+1))\right).\)
A certificate therefore lists at most \(q\) block indices, their explicit allocations, and their rational weights. Its total length is bounded by
\(O\!\left(q\left[\log(\tau+1)+B\log(m+1)+L+q\log(q(B+1))\right]\right).\)
A verifier checks all edge comparisons and all mass and supply equalities using exact rational arithmetic. There are at most \(q\) allocations to check, each on at most \(B\) positions and \(O(B^2)\) edges. The certificate bounds ensure a verification running time of \(\operatorname{poly}(m,\tau,B,L)\).
Thus the problem belongs to \(\mathrm{NP}\).
The reduction proves \(\mathrm{NP}\)-hardness for the precise block-mass model, and the sparse rational certificate proves membership in \(\mathrm{NP}\). Therefore the problem is \(\mathrm{NP}\)-complete, already with one connected block type and positive supplies throughout. A polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem. The reduction establishes \(\mathrm{NP}\)-hardness for the precise fractional block-mass model, and the certificate argument establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical issues.
The source problem is stated precisely: Independent Set on a finite simple graph, with \(1\leq K\leq n\). The stated equivalence with Vertex Cover is correct, including the threshold correspondence between an independent set of size at least \(K\) and a vertex cover of size at most \(n-K\). The cited classical source is [Karp’s completeness paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
The restriction excludes only trivial threshold cases and does not invalidate the hardness premise. In particular, \(n\geq1\), so the construction always has private classes and its filler preferences are well-defined.
The construction has \(m=n+3\) classes, one listed block type, and \(B=n+K+2\) positions. Its graph is finite, nonempty, simple, undirected, and connected: \(u\) is adjacent to every other position.
Each preference description specifies a strict linear order over all classes. At a core position, “all remaining classes” excludes the three classes already specified; consequently its only classes above \(g\) are \(t_v\) and \(f\).
The positive mass and supplies satisfy
\(\lvert P\rvert\lambda=1\) and
\(\sum_k s_k=(n+K+2)/B=1\).
Every supply is strictly positive because \(K\geq1\). The rational encoding bounds are correct.
The argument considers every possibility on the edge \(\{u,w\}\).
The remaining assignment is therefore necessarily \(a(u)=g\), \(a(w)=h\). It satisfies both comparisons on their edge.
With \(a(u)=g\), admissibility forces each adjacent position to receive a class it ranks above \(g\). The specified orders therefore yield exactly
\(a(p_v)\in\{t_v,f\}\) and
\(a(r_i)\in\{t_v:v\in V\}\).
The opposite comparison at \(u\) is satisfied for every class in these domains, since \(u\) ranks \(g\) first. Thus the argument does not overlook the second condition on an edge.
Adjacent core positions cannot both receive \(f\), so \(S(a)\) is independent.
The converse checks all other allowed combinations on a core edge. Distinct vertices have distinct private classes; each core ranks its own private class first and ranks \(f\) above every other vertex’s private class. These facts justify each comparison listed in the proof.
Fillers have no edges to cores or to other fillers. Consequently arbitrary private-class assignments to fillers introduce no further constraints. Repeated classes at nonadjacent positions are permitted by the task.
Neither guards nor fillers can receive \(f\). Hence the asserted identity and bound
\(c_f(a)=|S(a)|\leq\alpha(G)\)
hold for every admissible allocation.
An independent set of size at least \(K\) contains one of size exactly \(K\). The allocation described in the output is admissible by the preceding characterization.
For a vertex outside \(S\), its private class appears at its core. For a vertex inside \(S\), its private class appears at exactly one filler. Thus every private class appears once; \(f\) appears exactly \(K\) times; and \(g,h\) each appear once.
Giving this allocation weight \(1/B\) satisfies the block-mass equation and every supply equation with rational nonnegative weights.
Every admissible allocation satisfies the same upper bound on its consumption of \(f\). Nonnegative weights preserve that bound under summation:
\(K/B=\sum_a z_a c_f(a)\leq\alpha(G)\sum_a z_a=\alpha(G)/B\).
Since \(B>0\), this implies \(K\leq\alpha(G)\). No integrality assumption about the mixture is used. This establishes the claimed many-one equivalence for the actual feasibility definition.
The inequality \(B\leq2n+2\) follows from \(K\leq n\). There are \(B\) preference lists of length \(m\), at most quadratically many edges, and \(m+1\) rationals.
Under the explicit encoding stated in the output, the bound \(O(n^2\log(n+1))\) for construction time and output length is valid. The construction therefore supplies a polynomial-time reduction, with \(\tau=1\), a connected graph, and positive supplies throughout.
The integer columns encode exactly the block-mass and class-supply equations. There are finitely many columns, despite their implicit representation. Since feasibility already requires rational weights, selecting a rational feasible solution with minimum support is legitimate.
If its supported columns were dependent, their integer entries would give a nonzero rational dependence. Summing the block coordinates gives \(\sum_i c_i=0\), so the dependence has both positive and negative coefficients.
The specified value of \(t\) is positive and rational. Subtracting \(tc_i\) preserves every equation and nonnegativity, while eliminating at least one supported weight. This contradicts minimality. Thus the supported columns are independent and their number satisfies \(r\leq q=\tau+m\).
Independent supported columns admit an invertible \(r\)-row submatrix \(C\). The normalization assumptions imply that every coordinate of \(d\) lies in \([0,1]\), including each block mass because its block is nonempty.
The denominator product satisfies \(\log D=O(L)\). Cramer’s rule has the stated scaling:
\(z_i=\det(C_i')/(D\det C)\).
Each term in the determinant expansion for \(C\) has magnitude at most \(B^r\). Each term for \(C_i'\) contains one entry bounded by \(D\) and \(r-1\) entries bounded by \(B\). Hence both stated determinant bounds are correct, and they imply the claimed polynomial encoding length for every weight.
Listing at most \(q\) explicit allocations and their weights therefore gives a polynomial-size certificate. Admissibility, nonnegativity, and all mass and supply equations can be checked using exact rational arithmetic in \(\operatorname{poly}(m,\tau,B,L)\) time. The explicit input representation also bounds these structural parameters polynomially in the input length.
The claimed \(\mathrm{NP}\)-completeness and the stated restrictions are established. No additional clarification or repair is needed.
⟨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.