Answer: Polynomial-time solvable.
Theorem 4.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor n ≥5 groups of three agents, PROP1 allocations need not exist, even when utilities are binary and the groups are all identical. Moreover, deciding whether a PROP1 (or EF1) allocation exists is NP-complete for groups of three agents, even for binary utilities.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite category set \(A\), supported types \(T\) with \(t=(S_{t1},S_{t2},S_{t3})\), rational masses \(\mu_t\ge 0\) summing to \(1\), and rational per-household supplies \(q_a\in[0,1]\), decide whether nonnegative masses \(x_{tB}\) exist for \(t\in T\) and \(B\subseteq A\) such that \(\sum_{B\subseteq A}x_{tB}=\mu_t\) for every \(t\), \(\sum_{t\in T}\sum_{B\ni a}x_{tB}=q_a\) for every \(a\), and every \(B\) with \(x_{tB}>0\) satisfies binary PROP1 for all three members of \(t\). Specifically, with \(p_{ti}=\sum_{a\in A}q_a\mathbf{1}[a\in S_{ti}]\), require \(|B\cap S_{ti}|+\max(\{0\}\cup\{1:a\in S_{ti}\setminus B,\ q_a>0\})\ge p_{ti}\) for each \(i\in\{1,2,3\}\).
Let \(A\) be a finite category set, with \(m=|A|\). Each household has exactly three members and type \(t=(S_{t1},S_{t2},S_{t3})\), where \(S_{ti}\subseteq A\); member \(i\)'s binary additive utility for bundle \(B\subseteq A\) is \(|B\cap S_{ti}|\). All members fully enjoy the household's bundle, which contains at most one item per category.
A society is given by its support: the list \(T\) of its \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types. Supplies \(q_a\in[0,1]\) are binary rationals per unit household mass; let \(L\) be the total input bit length.
Define \(p_{ti}=\sum_{a\in S_{ti}}q_a\). Bundle \(B\) satisfies binary PROP1 for type \(t\) if, for every \(i\in\{1,2,3\}\), \(|B\cap S_{ti}|+\mathbf{1}[\exists a\in S_{ti}\setminus B:\ q_a>0]\ge p_{ti}\); thus one may hypothetically add at most one available item outside the bundle.
Feasibility means that real masses \(x_{tB}\ge0\) exist with \(\sum_{B\subseteq A}x_{tB}=\mu_t\) for every \(t\), \(\sum_{t\in T}\sum_{B\subseteq A:\ a\in B}x_{tB}=q_a\) for every \(a\), and every bundle with \(x_{tB}>0\) satisfies PROP1 for all three members. Types may split their mass among bundles; empty bundles and empty approval sets are permitted.
Is this feasibility problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite households, deciding whether a complete PROP1 allocation exists is NP-complete even with exactly three members per household and binary utilities ([Gölz–Yaghoubizade](https://paulgoelz.de/papers/couples.pdf)).
No result settling this exact mass-allocation feasibility problem was located in the literature search.
The feasibility problem is solvable in time polynomial in \(m,\tau,L\). We prove this by constructing a polynomial-size rational linear program whose feasible solutions correspond exactly to the permitted mass allocations.
Let \(A^+=\{a\in A:q_a>0\}\), and write \(r=|A^+|\).
Every bundle receiving positive mass in a feasible allocation lies in \(A^+\). Indeed, if \(q_a=0\), the supply equation gives
\[
\sum_{t\in T}\sum_{B\ni a}x_{tB}=0.
\]
All summands are nonnegative, so every bundle containing \(a\) has zero mass. We can therefore restrict attention to bundles contained in \(A^+\).
For each type \(t\) and member \(i\), define
\[
R_{ti}=S_{ti}\cap A^+,
\qquad
k_{ti}=\max\{0,\lceil p_{ti}\rceil-1\}.
\]
Since every supply is at most one,
\[
0\le p_{ti}=\sum_{a\in R_{ti}}q_a\le |R_{ti}|\le r.
\]
Lemma. For every \(B\subseteq A^+\), member \(i\)'s PROP1 condition is equivalent to
\[
|B\cap R_{ti}|\ge k_{ti}.
\]
Proof. Put \(c=|B\cap R_{ti}|\).
If PROP1 holds, its hypothetical addition contributes at most one, so \(c+1\ge p_{ti}\). Since \(c\) is a nonnegative integer, this implies \(c\ge\max\{0,\lceil p_{ti}\rceil-1\}=k_{ti}\).
Conversely, suppose \(c\ge k_{ti}\). If \(p_{ti}=0\), PROP1 holds automatically. Suppose \(p_{ti}>0\). If \(R_{ti}\setminus B\) is nonempty, an available approved category can be added, and
\[
c+1\ge k_{ti}+1=\lceil p_{ti}\rceil\ge p_{ti}.
\]
If \(R_{ti}\setminus B\) is empty, then \(c=|R_{ti}|\ge p_{ti}\), so no addition is necessary. This proves the equivalence. \(\square\)
Thus a bundle is valid for type \(t\) precisely when it meets three integer lower bounds.
Order the positive-supply categories as \(A^+=\{a_1,\ldots,a_r\}\). For each type \(t\), put
\[
K_t=(k_{t1},k_{t2},k_{t3}).
\]
Construct a directed layered graph \(D_t\). At each layer \(j\in\{0,\ldots,r\}\), its states are
\[
(j,c_1,c_2,c_3),
\qquad
0\le c_i\le k_{ti}.
\]
The source is \(s_t=(0,0,0,0)\). Add a distinct sink \(z_t\).
For each state \((j-1,c)\), add two labeled arcs to layer \(j\):
\[ c'_i=\min\{k_{ti},\,c_i+\mathbf{1}[a_j\in R_{ti}]\} \qquad(i\in\{1,2,3\}). \]
Keep these as distinct arcs even when they have the same endpoints. Finally, add one arc from \((r,K_t)\) to \(z_t\), and no other arcs to \(z_t\).
A sequence of take and skip decisions selects a unique bundle. By induction over the layers, after processing the first \(j\) categories its state satisfies
\[
c_i=\min\{k_{ti},\,|B\cap R_{ti}\cap\{a_1,\ldots,a_j\}|\}.
\]
Consequently, it reaches \((r,K_t)\) exactly when all three thresholds hold.
Therefore, source-to-sink paths in \(D_t\) correspond bijectively to the valid bundles for type \(t\).
This construction includes the degenerate cases. If all thresholds are zero, all take/skip sequences are accepted. If \(r=0\), the source has a direct arc to the sink, representing the empty bundle.
The number of states per layer is
\[
H_t=\prod_{i=1}^3(k_{ti}+1)\le(r+1)^3.
\]
Hence \(D_t\) has \((r+1)H_t+1\) vertices and \(2rH_t+1\) arcs.
For each arc \(e\) of \(D_t\), introduce a nonnegative real variable \(f_{te}\).
Require a flow of value \(\mu_t\) from \(s_t\) to \(z_t\). Explicitly, for every vertex \(v\),
\[
\sum_{e\in\delta^+(v)}f_{te}
-
\sum_{e\in\delta^-(v)}f_{te}
=
\begin{cases}
\mu_t,&v=s_t,\\
-\mu_t,&v=z_t,\\
0,&\text{otherwise}.
\end{cases}
\]
Let \(E^{\mathrm{take}}_{tj}\) be the take arcs processing category \(a_j\). Impose the supply equations
\[
\sum_{t\in T}\sum_{e\in E^{\mathrm{take}}_{tj}}f_{te}=q_{a_j}
\qquad(j\in\{1,\ldots,r\}).
\]
These are all the constraints. Categories outside \(A^+\) are absent from every represented bundle and therefore satisfy their zero-supply equations automatically.
Suppose the original instance is feasible. Its positive-mass bundles lie in \(A^+\), and the lemma shows that each is valid in the corresponding graph.
For every such bundle \(B\), send \(x_{tB}\) units along its associated path in \(D_t\), and sum these path flows.
Each path contributes its mass to the source-to-sink flow value, giving total value \(\mu_t\). It uses a take arc for category \(a_j\) exactly when \(a_j\in B\). Thus the graph supply equations are precisely the original supply equations. The linear program is feasible.
Conversely, suppose the linear program is feasible. Each \(D_t\) is acyclic because its arcs advance through successive layers and then enter the sink.
We first justify decomposition into source-to-sink path flows. While the residual source outflow is positive, choose a positive-flow arc from the source and continue along positive-flow arcs. At every reached vertex other than the sink, flow conservation guarantees a positive outgoing arc. Acyclicity prevents revisiting a vertex, so this process reaches the sink.
Subtract the minimum flow on the resulting path. This amount is positive, conservation is preserved, and at least one positive arc becomes zero. Repeating therefore extracts at most \(|E(D_t)|\) paths.
Once the residual source outflow is zero, no positive residual arc can remain. Otherwise, choose a vertex earliest in a topological ordering among those with positive outgoing flow. It has no positive incoming flow. It is neither the source nor the sink, contradicting conservation.
We have therefore expressed \(f_t\) as a finite sum of nonnegative source-to-sink path flows, whose weights sum to \(\mu_t\).
Assign each path's weight to its corresponding bundle, combining weights if necessary. Every resulting bundle satisfies all three thresholds and hence PROP1. Moreover, its membership in category \(a_j\) is recorded exactly by the path's take arc at layer \(j\). The graph supply equations consequently give
\[
\sum_{t\in T}\sum_{B\ni a_j}x_{tB}=q_{a_j}.
\]
This is a feasible original mass allocation.
Thus the constructed linear program is feasible if and only if the original instance is feasible.
Across all types, the linear program has
\[
O\bigl(\tau(m+1)^4\bigr)
\]
variables and
\[
O\bigl(\tau(m+1)^4+m\bigr)
\]
constraints.
Its matrix coefficients belong to \(\{-1,0,1\}\), and its right-hand sides are the input rationals \(\mu_t\) and \(q_a\). Computing the rational sums \(p_{ti}\), their ceilings, and the integer thresholds takes polynomial time in the input length: products of the input denominators have bit lengths bounded by the sum of their bit lengths.
We apply the standard polynomial-time theorem for rational linear programming: feasibility of an explicitly represented rational system can be decided in time polynomial in its encoding length, with a rational feasible solution produced when one exists. The polynomial-time LP principle is also recalled in [Gölz–Yaghoubizade, Proposition 2.1](https://paulgoelz.de/papers/couples.pdf). All hypotheses hold here: the system is explicit, rational, and has polynomial encoding length.
Therefore the required decision algorithm runs in time polynomial in \(m,\tau,L\). A feasible allocation can also be recovered through the path decomposition above.
The cited [finite-household hardness theorem](https://paulgoelz.de/papers/couples.pdf) requires indivisible assignments to individual households. Here each type may divide its mass among bundles, and the graph variables may be arbitrary nonnegative real flows. The proof establishes an exact linear formulation for this splitting model; it does not impose integrality on those flows.
The fixed number of members and binary utilities are essential to the polynomial size of this construction: only three counters, each bounded by \(m\), are needed to recognize a valid bundle.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time solvability of the exact mass-allocation feasibility problem in USER_TASK. The threshold reduction, graph representation, and linear-program equivalence are correct, including the permitted degenerate cases. No major or minor mathematical issues were found.
The restriction to bundles contained in \(A^+\) is justified.
For any category \(a\) with \(q_a=0\), its supply equation is a finite sum of nonnegative masses equal to zero. Every summand must therefore vanish. Consequently, every positive-mass bundle excludes \(a\).
This restriction also preserves the PROP1 condition: zero-supply categories contribute neither to \(p_{ti}\) nor to the indicator for an available approved category outside the bundle.
Both directions of the lemma are valid.
For necessity, PROP1 implies \(c+1\ge p_{ti}\), because the hypothetical addition contributes at most one. Since \(c\) is a nonnegative integer, this gives precisely \(c\ge\max\{0,\lceil p_{ti}\rceil-1\}\).
For sufficiency, the proof correctly distinguishes three cases:
This covers empty approval sets, integer and noninteger values of \(p_{ti}\), and approval sets fully contained in the bundle. No availability condition is lost in the reduction.
The capped-counter construction correctly recognizes every bundle satisfying the three thresholds.
The claimed invariant follows from the update rule: skipping leaves the counts unchanged, while taking a category increments exactly the counters of members approving it, with each counter capped at its threshold. Thus the terminal state equals \(K_t\) exactly when all thresholds have been reached.
The claimed bijection is also correct. Every bundle determines one take/skip decision at each layer, and those decisions determine its path uniquely. Retaining parallel take and skip arcs as distinct labeled arcs is necessary and sufficient to preserve this distinction when their endpoints coincide.
The edge cases are handled correctly:
The exact counts \((r+1)H_t+1\) vertices and \(2rH_t+1\) arcs are correct. Since \(k_{ti}\le r\), the bound \(H_t\le(r+1)^3\) is valid.
The constraints encode the intended quantities exactly.
A flow of value \(\mu_t\) represents the entire mass of type \(t\). A source-to-sink path uses exactly one processing arc at each category layer, and that arc is a take arc precisely when the represented bundle contains that category. Therefore the take-arc supply equations measure category inclusion mass without duplication.
Zero-supply categories need no additional equations because every represented bundle excludes them. The formulation imposes no integrality restriction, consistently with the task’s permission to split type masses.
Sending each bundle’s mass along its associated path preserves both the type-mass equations and the category-supply equations. Every positive-mass bundle has an accepted path by the threshold lemma. This direction is complete.
The supplied decomposition argument is valid for these graphs.
A positive-flow path can be continued from the source: at each reached intermediate vertex, positive incoming flow and conservation imply positive outgoing flow. Acyclicity prevents indefinite continuation, and the path must terminate at the sink.
Subtracting the minimum arc flow along the path preserves internal conservation and nonnegativity, while removing at least one positive arc. Consequently, at most \(|E(D_t)|\) paths are extracted.
The argument excluding leftover positive flow is correct. Once source outflow is zero, an earliest vertex with positive outgoing residual flow has no positive incoming residual flow. It cannot be the source, and the sink has no outgoing arcs, so internal conservation gives a contradiction.
The resulting path weights sum to \(\mu_t\). Assigning those weights to the represented bundles preserves category totals and gives PROP1-valid bundles. Hence both directions of the equivalence are established.
The graph-size bounds yield polynomially many variables and constraints in \(m\) and \(\tau\). Nonnegativity constraints do not change these asymptotic bounds.
The numerical encoding argument is sound. Exact sums of input rationals have polynomial bit length: a common denominator formed from their denominators has bit length bounded by the sum of the denominator bit lengths. Computing the ceilings and thresholds therefore takes polynomial time.
The invoked rational-LP theorem is stated sufficiently precisely, and its hypotheses are verified: the system is explicit, rational, and has polynomial encoding length. Real feasibility is appropriately decided by rational linear programming; no assumption that the original masses are rational is needed.
The supplementary [Proposition 2.1 citation](https://paulgoelz.de/papers/couples.pdf) concerns polynomial-time optimization over a nonempty polytope. It is consistent with the invocation, although the independently stated rational-feasibility theorem carries the decision claim.
The constructive recovery claim is also supported: decomposition extracts polynomially many paths, each of polynomial length.
The proof addresses the exact model in USER_TASK, including complete supply use, support-size dependence, empty bundles, and empty approval sets.
The distinction from finite-household hardness is valid: splitting a type’s mass permits fractional path weights, whereas assigning one bundle to each individual household requires discrete choices. The cited finite-household result therefore does not contradict this formulation.
Required clarification or repair: none.
⟨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.