Answer: Polynomial-time solvable in $m,\tau,L$ by an exact reduction to maximum flow.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a number k, checking if cP ≥k can be done in polynomial time if the value of each item belongs to the domain {0, 1}. PROOF. We follow a linear-programming-based approach. Let I be a problem instance with n agents and m items, each having a utility of 0 or 1 for every agent. For each agent i, let si be the number of items that have utility 1 for agent i.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), \(q\) indivisible good categories with rational per-capita supplies \(b_g\), binary values \(v_{tg}\), and a rational threshold \(c\), decide whether there is a nonnegative allocation measure \(\lambda_{t,z}\) over integral bundles \(z \in \mathbb{Z}_{\ge 0}^{q}\) such that \(\sum_z \lambda_{t,z}=\mu_t\), \(\sum_{t,z}\lambda_{t,z}z_g\le b_g\) for each category \(g\), and every bundle assigned positive mass to type \(t\) satisfies \(\sum_g v_{tg}z_g \ge c\sum_g v_{tg}b_g\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
There are \(m=q\ge1\) good categories, nonnegative binary-rational per-capita supplies \(b_g\), additive binary values \(v_{tg}\in\{0,1\}\), and a nonnegative binary-rational threshold \(c\). Let \(L\) be the total input bit length.
An allocation measure consists of real masses \(\lambda_{t,z}\ge0\), indexed by \(t\in T\) and integral bundles \(z\in\mathbb Z_{\ge0}^{m}\), satisfying \(\sum_z\lambda_{t,z}=\mu_t\) and \(\sum_{t,z}\lambda_{t,z}z_g\le b_g\) for every category \(g\). Unused supply is permitted; integral bundles have no additional coordinate bounds.
Define the proportional share \(p_t=\sum_g v_{tg}b_g\). Assume \(p_t>0\) for every type and promise that some allocation measure gives strictly positive utility to every bundle assigned positive mass.
The decision problem asks whether an allocation measure exists such that \(\lambda_{t,z}>0\) implies \(\sum_g v_{tg}z_g\ge c p_t\), for every \(t,z\).
Is this decision problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finitely many agents and explicitly listed indivisible goods with additive binary values, deciding whether every agent can receive at least a specified multiple of her proportional share is polynomial-time solvable ([Nguyen, Nguyen, and Rothe](https://ifaamas.org/Proceedings/aamas2017/pdfs/p262.pdf)). No result settling exactly the allocation-measure problem above was identified in the literature search.
The decision problem is polynomial-time solvable in $m,\tau,L$. It reduces exactly to a maximum-flow problem with rational capacities. Moreover, every feasible instance admits a rational allocation measure supported on at most $m\tau$ type–bundle pairs.
The essential fact is that bundles may contain arbitrarily many copies of a category, while supply constraints apply to aggregate consumption.
Write $G=\{1,\ldots,m\}$ and define
$$
A_t=\{g\in G:v_{tg}=1\},\qquad
k_t=\left\lceil c p_t\right\rceil,\qquad
d_t=\mu_t k_t.
$$
For every integral bundle $z$, its utility to type $t$ is the nonnegative integer
$$
u_t(z)=\sum_{g\in A_t}z_g.
$$
Consequently,
$$
u_t(z)\ge c p_t
\quad\Longleftrightarrow\quad
u_t(z)\ge k_t.
$$
Consider the following finite system, with a real variable $x_{tg}$ for each pair satisfying $g\in A_t$:
$$
x_{tg}\ge0,\qquad
\sum_{g\in A_t}x_{tg}=d_t\quad(t\in T),\qquad
\sum_{t:g\in A_t}x_{tg}\le b_g\quad(g\in G).
$$
Here $x_{tg}$ represents aggregate consumption of category $g$ by type $t$.
We prove that this system is feasible exactly when the requested allocation measure exists.
Suppose $\lambda$ is a feasible allocation measure satisfying the thresholds. For each valued pair, define
$$
y_{tg}=\sum_{z\in\mathbb Z_{\ge0}^{m}}\lambda_{t,z}z_g.
$$
These sums are finite: nonnegativity and the supply constraint imply $y_{tg}\le b_g$. Also,
$$
\sum_{t:g\in A_t}y_{tg}\le b_g.
$$
For each type, let
$$
r_t=\sum_{g\in A_t}y_{tg}
=\sum_z\lambda_{t,z}u_t(z).
$$
The equality follows by interchanging a finite sum with a series of nonnegative terms. Every bundle of positive mass has utility at least $k_t$, so
$$
r_t\ge k_t\sum_z\lambda_{t,z}
=k_t\mu_t=d_t.
$$
If $d_t>0$, then $r_t>0$, and we set
$$
x_{tg}=\frac{d_t}{r_t}y_{tg}.
$$
If $d_t=0$, set $x_{tg}=0$. In both cases, the row sum is $d_t$ and $0\le x_{tg}\le y_{tg}$. Thus every column sum remains at most $b_g$, proving feasibility of the finite system.
Conversely, suppose $x$ satisfies the finite system. Let $e_g$ denote the $g$th unit vector.
For each type with $k_t>0$, assign masses
$$
\lambda_{t,k_t e_g}=\frac{x_{tg}}{k_t}
\qquad(g\in A_t),
$$
and assign zero mass to every other bundle. Then
$$
\sum_z\lambda_{t,z}
=\frac{1}{k_t}\sum_{g\in A_t}x_{tg}
=\frac{d_t}{k_t}
=\mu_t.
$$
Every assigned bundle consists of $k_t$ copies of a valued category, so its utility is exactly $k_t$, which is at least $c p_t$.
For each type with $k_t=0$, assign its entire mass $\mu_t$ to the zero bundle. Since $c p_t$ is nonnegative and has ceiling zero, this bundle satisfies the threshold.
For every category $g$, aggregate consumption is
$$
\sum_{t,z}\lambda_{t,z}z_g
=\sum_{t:g\in A_t}x_{tg}
\le b_g.
$$
The equality also covers types with $k_t=0$: their consumption is zero, and their nonnegative row variables all vanish.
This proves the equivalence. Each type uses at most $m$ bundles, since a type with zero threshold uses one bundle and $m\ge1$.
Let
$$
D=\sum_{t\in T}d_t.
$$
If $D=0$, the zero-bundle allocation is feasible, so return YES.
Otherwise, construct a directed network with source $s$, sink $h$, one vertex for each type, and one vertex for each category. Its edges and capacities are:
| Edge | Condition | Capacity |
|---|---|---|
| $s\to t$ | $t\in T$ | $d_t$ |
| $t\to g$ | $g\in A_t$ | $D$ |
| $g\to h$ | $g\in G$ | $b_g$ |
A feasible $x$ yields a flow of value $D$: send $d_t$ into each type vertex, $x_{tg}$ along each type–category edge, and the corresponding column sum into the sink. The middle-edge capacities suffice because
$$
x_{tg}\le d_t\le D.
$$
Conversely, a flow of value $D$ saturates every source edge, since their capacities sum to $D$. Conservation at each type vertex therefore gives
$$
\sum_{g\in A_t}x_{tg}=d_t,
$$
where $x_{tg}$ is the flow along $t\to g$. Conservation and capacity constraints at the category vertices give the required column inequalities.
Hence the algorithm returns YES exactly when the maximum-flow value equals $D$.
The network has
$$
V=m+\tau+2,\qquad E\le m\tau+m+\tau.
$$
The quantities $p_t$, $c p_t$, $k_t$, $d_t$, and $D$ can all be computed exactly with polynomially many bit operations. Indeed, the denominator of a sum of input rationals divides the product of their denominators; that product has bit length bounded by the sum of the input denominator lengths. Multiplication by $c$ and taking the ceiling preserve polynomial bit length. In particular, a numerically large $k_t$ is stored in binary and is never expanded into individual units.
For an explicit integer-capacity implementation, write the input masses and supplies as
$$
\mu_t=\frac{a_t}{r_t},\qquad b_g=\frac{u_g}{s_g},
$$
and set
$$
Q=\prod_{t\in T}r_t\prod_{g\in G}s_g.
$$
This integer has polynomial bit length. Multiplying every network capacity by $Q$ produces integer capacities, because $d_t=k_t\mu_t$ and $D=\sum_t d_t$. All scaled capacities have polynomial bit length.
The standard Edmonds–Karp theorem gives a maximum-flow algorithm using $O(VE^2)$ arithmetic operations, independently of the numerical capacity magnitudes. Its hypotheses hold here: the network is finite and all capacities are nonnegative integers after scaling. Every flow and residual-capacity value has polynomial bit length, so this is a polynomial-time algorithm in the bit model. Dividing the resulting flow by $Q$, and then using the construction in Section 3, also produces a rational allocation measure of polynomial encoding length.
The cited finite-agent tractability result concerns explicitly listed goods; the equivalence proved above directly settles the allocation-measure formulation. [Nguyen, Nguyen, and Rothe](https://ifaamas.org/Proceedings/aamas2017/pdfs/p262.pdf) establish the stated binary-utility tractability result for their finite-agent model.
Thus the requested decision problem belongs to $\mathrm P$. The proof also works without the promise that a positive-utility allocation already exists.
⟨structured verdict parsed — rendered above⟩
The proof correctly establishes polynomial-time solvability of the allocation-measure decision problem. Both directions of the reduction are valid, the maximum-flow formulation is exact, and the bit-complexity argument handles binary-encoded supplies and thresholds. No major or minor issues were found.
Because $v_{tg}\in\{0,1\}$ and $z_g\in\mathbb Z_{\ge0}$, the utility
$$
u_t(z)=\sum_{g\in A_t}z_g
$$
is a nonnegative integer. Therefore the equivalence
$$
u_t(z)\ge cp_t
\quad\Longleftrightarrow\quad
u_t(z)\ge\lceil cp_t\rceil
$$
is exact, including when $cp_t$ is integral or zero.
The quantities $k_t$ and $d_t=\mu_tk_t$ are nonnegative. The finite system uses variables only for categories valued by the corresponding type, consistently with its intended interpretation.
The assumption $p_t>0$ ensures $A_t$ is nonempty. The proof does not impose any additional restriction on bundle coordinates.
For each valued pair, the series defining $y_{tg}$ converges to a finite value: it is a subseries of the nonnegative aggregate consumption bounded by $b_g$.
The column inequalities follow directly from the original supply constraints. The identity
$$
\sum_{g\in A_t}y_{tg}
=\sum_z\lambda_{t,z}u_t(z)
$$
is justified because the category sum is finite and all summands are nonnegative.
The threshold condition applies to every positive-mass bundle, so the lower bound
$$
r_t\ge k_t\mu_t=d_t
$$
is valid even when the allocation has infinite support.
When $d_t>0$, the scaling factor $d_t/r_t$ is well-defined and belongs to $(0,1]$. It produces the required row sum while weakly decreasing every coordinate. When $d_t=0$, setting the row to zero also satisfies its equality. Consequently, all column constraints remain satisfied.
This direction is rigorous.
For $k_t>0$, the bundles $k_te_g$ are integral and distinct as $g$ varies. Their assigned masses are nonnegative and sum to
$$
\frac{d_t}{k_t}=\mu_t.
$$
Each positive-mass bundle has utility exactly $k_t$, so it satisfies the threshold.
The construction relies on permission to assign arbitrarily many copies of one category to a bundle. That permission is explicit in the task.
For $k_t=0$, nonnegativity of $cp_t$ implies $cp_t=0$, so the zero bundle is admissible. Moreover, the finite-system row has nonnegative entries summing to zero; every entry therefore vanishes.
The displayed aggregate-consumption equality is correct for both cases. Thus the construction satisfies the mass and supply constraints exactly as required.
The support bound is also correct: a positive-threshold type uses at most $|A_t|\le m$ bundles, and a zero-threshold type uses one bundle. Since $m\ge1$, the total is at most $m\tau$ type–bundle pairs.
This direction and the support bound are rigorous.
The case $D=0$ is handled correctly. Since all $d_t$ are nonnegative and all $\mu_t$ are positive, this case entails $k_t=0$ for every type; the zero-bundle allocation is feasible.
For $D>0$, a feasible finite-system solution induces a flow of value $D$. Each middle-edge capacity suffices because
$$
0\le x_{tg}\le d_t\le D.
$$
Conversely, a flow of value $D$ must saturate every source edge: their capacities sum to $D$, so any unsaturated source edge would force a smaller total flow. Flow conservation then supplies the row equalities, and the category-to-sink capacities supply the column inequalities.
The maximum-flow decision criterion is exact.
The stated vertex and edge counts are correct.
The rational-arithmetic argument establishes polynomial encoding length for $p_t$, $cp_t$, $k_t$, $d_t$, and $D$. A ceiling may produce a numerically large integer, but its binary encoding remains polynomial in the input length.
The proposed scaling factor $Q$ clears every network-capacity denominator. Including the denominator of $c$ is unnecessary: its effect has already been incorporated into the integer $k_t$. The product defining $Q$ has polynomial bit length, as do all scaled capacities.
The cited Edmonds–Karp bound gives a polynomial number of arithmetic operations independently of capacity magnitudes. Its stated hypotheses hold for the scaled network. Flow and residual-capacity values have polynomial bit length, making these operations polynomial-time in the bit model.
Dividing by $Q$ yields rational flow entries. Dividing the relevant entries by the binary-encoded integers $k_t$ preserves polynomial encoding length. Together with the support bound, this validates the claimed rational allocation certificate.
The complexity conclusion is justified.
The promise concerns the existence of some positive-utility allocation; it does not require every allocation satisfying the decision threshold to have positive utility. Thus using zero bundles when $c=0$ is legitimate. The proof correctly establishes feasibility equivalence without using the promise.
The ancillary attribution to the finite-agent result is supported by the [cited paper](https://ifaamas.org/Proceedings/aamas2017/pdfs/p262.pdf), which states polynomial-time threshold testing for additive binary utilities. The allocation-measure argument is independently established in the submitted proof.
No additional clarification, missing lemma, or mathematical repair is required.
⟨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.