Envy-Free Allocations Respecting Social Networks (d4-conf-atal-2018-0376)

Given finitely many positive-mass role types \(T\) with population distribution \(\mu\), a directed role graph \(H=(T,F)\), common \(0/1\) utilities over a finite resource catalogue \(R\), and per-capita supplies \(\rho_r\), find a mass allocation \(\lambda_{t,B}\) over integral bundles \(B\subseteq R\) such that each type receives mass \(\mu_t\), every resource supply is met, and for every role edge \(t\to t'\), every supported bundle of type \(t\) is at least as valuable to type \(t\) as every supported bundle of type \(t'\); otherwise report infeasibility.

A society is given by its support: a list \(T\) of \(\tau\geq1\) role types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains a loopless directed role graph \(H=(T,F)\), a resource catalogue \(R\) with \(m=|R|\), a common additive utility specified by \(u(r)\in\{0,1\}\), and binary-rational per-capita supplies \(\rho_r\in[0,1]\).
An allocation assigns nonnegative real mass \(\lambda_{t,B}\) to each type \(t\) and integral bundle \(B\subseteq R\); empty bundles are allowed, and each bundle contains at most one unit of each catalogue resource.
Completeness requires \(\sum_{B\subseteq R}\lambda_{t,B}=\mu_t\) for every \(t\), and \(\sum_{t\in T}\sum_{B\ni r}\lambda_{t,B}=\rho_r\) for every \(r\).
Graph envy-freeness requires \(u(B)\geq u(C)\) whenever \((t,t')\in F\), \(\lambda_{t,B}>0\), and \(\lambda_{t',C}>0\); thus comparisons concern every pair of supported bundles.
Is feasibility of a complete graph-envy-free mass allocation solvable in polynomial time in \(m\), \(\tau\), and the total input bit length \(L\), or is it \(\mathrm{NP}\)-hard?
For finite agents and indivisible resources, complete graph-envy-free allocation with identical binary utilities is \(\mathrm{NP}\)-hard even with maximum outdegree two; strongly connected comparison graphs admit a linear-time algorithm. [Source](https://arxiv.org/html/2011.11596)
No complexity result for exactly this support-wise mass-allocation problem was located in the literature search.

Result

The feasibility problem is \(\mathrm{NP}\)-complete. Hardness holds even when \(m=1\), the single resource has utility one, all masses and supplies are dyadic rationals, and the role graph is a disjoint union of directed cycles of length two. In particular, every vertex has indegree and outdegree one.

The supplied [finite-agent paper](https://arxiv.org/html/2011.11596) also uses equality of utilities within strongly connected components. The proof below establishes the necessary rigidity directly for supported mass allocations and gives a reduction for this precise model.

1. Mutual comparisons force a common utility

Lemma. Suppose two positive-mass types \(p,q\) satisfy \((p,q),(q,p)\in F\). Then every supported bundle of either type has the same utility.

Proof. By positive masses and type completeness, each type has at least one supported bundle. If \(B\) is supported by \(p\) and \(C\) by \(q\), the two arcs require both \(u(B)\geq u(C)\) and \(u(C)\geq u(B)\). Hence \(u(B)=u(C)\).

Fixing one supported bundle of \(q\) shows that all supported bundles of \(p\) have that same utility; fixing one of \(p\) gives the corresponding conclusion for \(q\). \(\square\)

For a catalogue consisting of one resource \(r\), with \(u(r)=1\), the only bundles are \(\varnothing\) and \(\{r\}\), with distinct utilities. Consequently, a mutually comparing pair must allocate its entire combined mass either to \(\varnothing\) or to \(\{r\}\). Mixing these bundles is impossible.

2. Polynomial-time reduction from Subset Sum

We use the standard \(\mathrm{NP}\)-complete Subset Sum problem: given positive integers \(a_1,\ldots,a_n\) and a positive integer \(b\), decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=b\). We may restrict to \(1\leq b\leq S\), where \(S=\sum_{i=1}^{n}a_i\), since targets outside this range are immediately decidable.

Choose a power of two \(D\) such that \(D>S+b\), and introduce the additional integer

\(a_0=D-S.\)

Thus \(a_0>b\), and \(\sum_{i=0}^{n}a_i=D\).

Construction

Use one resource \(r\), with

\(R=\{r\},\qquad u(r)=1,\qquad \rho_r=b/D.\)

For every \(i\in\{0,\ldots,n\}\), introduce two distinct types \(p_i,q_i\), with masses

\(\mu_{p_i}=\mu_{q_i}=a_i/(2D).\)

The graph has exactly the arcs \((p_i,q_i)\) and \((q_i,p_i)\) for each \(i\).

All masses are positive, and their sum is

\(\displaystyle \sum_{i=0}^{n}\bigl(\mu_{p_i}+\mu_{q_i}\bigr)=\frac{\sum_{i=0}^{n}a_i}{D}=1.\)

Also \(0<\rho_r<1\). Since \(D\) is a power of two, every mass and the supply are dyadic rationals.

The graph is loopless and consists of disjoint directed cycles of length two. Its support size is \(\tau=2(n+1)\).

Forward implication

Suppose \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=b\).

For each \(i\in I\), allocate the entire mass of both \(p_i\) and \(q_i\) to \(\{r\}\). Allocate every other type entirely to \(\varnothing\).

Each type receives its prescribed mass. The total mass receiving \(r\) is

\(\displaystyle \sum_{i\in I}\bigl(\mu_{p_i}+\mu_{q_i}\bigr)=\frac{\sum_{i\in I}a_i}{D}=\frac bD=\rho_r.\)

Within each comparison pair, both types receive bundles of equal utility. There are no other comparisons. The allocation is therefore complete and graph-envy-free.

Reverse implication

Suppose the constructed instance admits a complete graph-envy-free mass allocation.

By the lemma, each pair \(p_i,q_i\) allocates all its mass to a common bundle. Let \(x_i=1\) if that bundle is \(\{r\}\), and \(x_i=0\) if it is \(\varnothing\). Resource completeness gives

\(\displaystyle \frac bD=\sum_{i=0}^{n}\frac{a_i}{D}x_i,\)

and hence

\(\displaystyle b=\sum_{i=0}^{n}a_i x_i.\)

Because \(a_0>b\) and all summands are nonnegative, necessarily \(x_0=0\). Therefore the indices \(i\in\{1,\ldots,n\}\) with \(x_i=1\) form a subset summing to \(b\).

Encoding size

Take \(D\) to be the smallest power of two strictly exceeding \(S+b\). Then \(D\leq 2(S+b)\), so its binary length is polynomial in the Subset Sum input length.

There are \(2(n+1)\) types and arcs, and every constructed rational has binary encoding length \(O(\log D)\). Thus the construction is a polynomial-time many-one reduction.

This proves \(\mathrm{NP}\)-hardness under all the restrictions stated above.

3. Polynomial-size certificates

We next prove membership in \(\mathrm{NP}\), despite the exponentially many possible bundles and the permission to use real allocation masses.

Suppose a feasible allocation exists. Let \(J\) be its set of supported pairs \((t,B)\). Retain only these pairs as permitted variables and impose the completeness equations. Write this system as

\(Ax=c,\qquad x\geq 0,\)

where \(A\) has \(N=\tau+m\) rows. A column for \((t,B)\) has a one in the row for type \(t\), and a one in each resource row corresponding to a resource in \(B\). All other entries are zero.

Every feasible solution using only these columns remains graph-envy-free: its support is a subset of the original feasible support.

A sparse feasible solution exists

Choose a feasible solution with the smallest number \(k\) of positive coordinates. Its corresponding columns must be linearly independent.

Indeed, otherwise there is a nonzero vector \(z\) on those coordinates with \(Az=0\). Summing the type rows gives \(\sum_j z_j=0\), because every column has exactly one nonzero type entry. Thus \(z\) has both positive and negative coordinates.

Set

\(\displaystyle \theta=\min_{j:z_j>0}\frac{x_j}{z_j}>0.\)

Then \(x-\theta z\) remains nonnegative, satisfies the same equations, and has fewer positive coordinates, a contradiction.

Consequently \(k\leq N=\tau+m\).

The positive masses have polynomial bit length

Select \(k\) rows on which these independent columns form a nonsingular square matrix \(M\). Let \(c'\) be the corresponding right-hand side.

Let \(Q\) be the product of the denominators of all input masses and supplies. Its binary length is \(O(L)\), and \(Qc'\) is integral. Every entry of \(Qc'\) lies between zero and \(Q\).

Cramer’s rule expresses each positive coordinate as

\(\displaystyle x_j=\frac{\det M_j(Qc')}{Q\det M},\)

where \(M_j(Qc')\) replaces column \(j\) of \(M\) by \(Qc'\).

Since \(M\) has entries in \(\{0,1\}\), the determinant expansion gives \(|\det M|\leq k!\). The same expansion gives \(|\det M_j(Qc')|\leq Qk!\). Therefore each mass has a rational representation of bit length \(O(L+k\log k)\).

A certificate can thus list at most \(\tau+m\) supported pairs, encoding each bundle by \(m\) bits and each positive mass by polynomially many bits.

The verifier checks all completeness equations using exact rational arithmetic. It then checks the utility inequality for every pair of listed bundles whose types are connected by an arc. These checks take polynomial time.

Hence the problem belongs to \(\mathrm{NP}\).

Conclusion

Feasibility is \(\mathrm{NP}\)-complete. The decisive obstruction is that mutual support-wise comparisons prohibit mixing utility values, allowing binary-encoded component masses to encode Subset Sum. A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict

The prover establishes that the specified mass-allocation feasibility problem is \(\mathrm{NP}\)-complete, including the claimed restriction to one valued resource, dyadic input data, and disjoint directed cycles of length two.

The reduction and the polynomial-certificate argument are correct. No major or minor mathematical issues were found.

1. Mutual-comparison lemma

Verified.

Positive type mass and type completeness ensure that each type has at least one supported bundle: there are finitely many bundles, their allocation masses are nonnegative, and their sum is positive.

For any supported bundle \(B\) of \(p\) and any supported bundle \(C\) of \(q\), the two directed comparisons impose
\[ u(B)\geq u(C) \quad\text{and}\quad u(C)\geq u(B). \]
Thus their utilities agree. Fixing a supported bundle of either type correctly establishes constancy across the other type’s entire support.

With one resource of utility one, the only possible bundles have distinct utilities. Therefore each mutually comparing pair must use precisely one common bundle, and type completeness forces each type’s entire mass onto that bundle. This conclusion uses the task’s comparisons between every pair of supported bundles, exactly as required.

The contextual claim about equal utilities within strongly connected components is also supported by Observation 5(1) of the [cited finite-agent paper](https://arxiv.org/html/2011.11596). The mass-allocation proof does not depend on transferring that paper’s result to this model.

2. Subset Sum source problem and normalization

Verified.

The prover states the standard positive-integer, binary-encoded Subset Sum decision problem precisely.

Restricting to \(1\leq b\leq S\), where \(S=\sum_{i=1}^{n}a_i\), is legitimate: the source problem already assumes a positive target, and targets exceeding the sum of all positive items are immediate no-instances. This restriction does not remove the hard part of the source problem.

The chosen power of two satisfies \(D>S+b\). Consequently,
\[ a_0=D-S>b>0, \]
and
\[ \sum_{i=0}^{n}a_i=D. \]
Both properties used later are correct.

3. Validity of the constructed instance

Verified.

The construction satisfies every relevant input restriction:

• There is exactly one catalogue resource, with utility one.
• All type masses \(a_i/(2D)\) are positive.
• Summing the two masses in each pair and then all pairs gives total mass one.
• The supply \(b/D\) lies strictly between zero and one.
• Since \(D\) is a power of two, the masses and supply are dyadic rationals.
• Every graph arc joins distinct types, so the graph is loopless.
• Every vertex belongs to exactly one directed cycle of length two and has indegree and outdegree one.
• The support size is \(\tau=2(n+1)\).

The construction uses integral bundles while allowing real allocation masses, precisely matching the target model.

4. Forward implication

Verified.

Given a subset summing to \(b\), the proposed allocation places each type’s entire prescribed mass on one bundle. Hence type completeness holds.

The resource receives total mass
\[ \sum_{i\in I}\frac{a_i}{D}=\frac{b}{D}, \]
so resource completeness holds exactly.

Both endpoints of every comparison pair receive bundles of equal utility. Since these are all the graph’s arcs, every required envy inequality holds. Empty bundles are explicitly allowed by the task.

5. Reverse implication

Verified.

The lemma makes each pair’s choice binary: its full combined mass \(a_i/D\) either receives the resource or does not. Thus the variables \(x_i\) used by the prover belong to \(\{0,1\}\).

Resource completeness gives exactly
\[ b=\sum_{i=0}^{n}a_i x_i. \]
Since \(a_0>b\) and every summand is nonnegative, \(x_0=1\) is impossible. The remaining selected indices therefore constitute a subset of the original items summing to \(b\).

There is no residual possibility of fractional mixing within a pair. The mutual-comparison lemma rules it out before the binary variables are introduced.

6. Reduction size and running time

Verified.

For the smallest power of two strictly greater than \(S+b\), the bound
\[ D\leq 2(S+b) \]
is correct, including when \(S+b\) itself is a power of two.

The binary length of \(S+b\), and hence of \(D\), is polynomial in the source input length. All constructed numerators and denominators have the stated polynomial encoding size. There are \(2(n+1)\) vertices and the same number of arcs.

Computing the sums, the next power of two, and the rational data requires polynomial time. The reduction proves hardness for binary-encoded data; it makes no unsupported claim of strong \(\mathrm{NP}\)-hardness.

7. Restricting to an existing feasible support

Verified.

There are finitely many possible pairs \((t,B)\), even though their number may be exponential. Consequently, the original support \(J\) is finite, and the restricted completeness system is well-defined.

Every solution using only columns from \(J\) has support contained in the original feasible support. Removing supported bundles cannot introduce a new violating comparison. Thus preserving completeness within this restricted system also preserves graph envy-freeness.

This is an existence argument for certificates; it does not require constructing or enumerating \(J\) in polynomial time.

8. Sparse feasible solution

Verified.

A feasible solution minimizing the number of positive coordinates exists because the possible support sizes form a finite set of integers.

If its positive-coordinate columns are dependent, the stated nonzero vector \(z\) satisfies \(Az=0\). Summing the type rows yields
\[ \sum_j z_j=0, \]
because each column contains exactly one type-row entry equal to one. Therefore \(z\) has both positive and negative coordinates.

The specified positive value of \(\theta\) ensures that \(x-\theta z\) remains nonnegative, preserves all equations, and makes at least one previously positive coordinate zero. No new coordinates are introduced. This contradicts minimality.

Hence the positive columns are independent and their number satisfies \(k\leq\tau+m\).

9. Rational masses and certificate length

Verified.

Independent columns admit a nonsingular square submatrix formed by selecting \(k\) rows. Its equations uniquely determine the selected positive masses.

The product \(Q\) of input denominators has bit length \(O(L)\). Every selected right-hand-side entry lies in \([0,1]\), so \(Qc'\) is integral with entries in \([0,Q]\).

The application of Cramer’s rule is correct. The determinant expansion gives
\[ |\det M|\leq k!, \qquad |\det M_j(Qc')|\leq Qk!. \]
Each numerator term in the second determinant contains exactly one entry from the replaced column, which justifies its single factor of \(Q\).

These bounds establish polynomial bit length for every positive mass. They also establish that real feasibility admits a rational certificate of polynomial size.

10. Certificate verification and conclusion

Verified.

At most \(\tau+m\) listed pairs suffice. Bundles require \(m\) bits each, and their masses have polynomial bit length.

Exact rational arithmetic verifies type and resource completeness in polynomial time. Checking all relevant pairs of listed bundles also requires only polynomially many comparisons, and additive binary utilities are polynomial-time computable.

Thus membership in \(\mathrm{NP}\) is established for the full problem, including zero-valued resources and zero supplies. Combined with the reduction, this proves the claimed \(\mathrm{NP}\)-completeness. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩