Answer: \(\mathrm{NP\text{-}hard}\)
Theorem 4.10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume that an instance is (𝛾𝑛+ 𝑖−1, 𝛽)-robust with respect to agent 𝑖(who has a 𝑝𝑖-system constraint). If 𝑖 chooses greedily in the Round-Robin protocol, they build a solution 𝑆𝑖 such that 𝑓𝑖(𝑆𝑖) ≥OPT𝑖/𝛽(𝑝𝑖+ 1 + 1/𝛾).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given agent types \(a\in[\tau]\) with rational masses \(\mu_a\), resource types \(q\in Q\) with rational supplies \(\sigma_q\), per-type monotone submodular objectives \(f_a\), \(p_a\)-system constraints \(\mathcal I_a\), a canonical deterministic Round-Robin schedule with greedy tie-breaking, and an \((\gamma,\beta)\)-robustness certificate, compute the induced mass \(x_{a,B}\) of agents receiving each feasible integral whole-copy bundle \(B\), satisfying \(\sum_B x_{a,B}=\mu_a\) and \(\sum_{a,B}B_qx_{a,B}\le\sigma_q\), and decide whether \(g_a(x):=\inf\{f_a(B):x_{a,B}>0\}\ge\rho_a\) for each requested type.
Let \(T\) be finite, with rational masses \(\mu_t>0\), resource classes \(R\), and per-capita supplies \(b_r\); total supply is \(B_r=b_r\sum_{t\in T}\mu_t\). An individual bundle is \(x\in\mathbb Z_{\ge0}^{R}\); type \(t\) may hold exactly bundles in \(\mathcal I_t\) and values one by \(f_t(x)\), a normalized nonnegative diminishing-returns submodular utility.
A fixed fluid round-robin schedule prescribes successive turns for type-mass. On a turn, a mass element receives one feasible unit \(e_r\), or nothing; other types select a feasible \(r\) maximizing \(f_t(x+e_r)-f_t(x)\), with fixed tie-breaking.
A legal history is a schedule trajectory whose partial bundles are feasible. A mass-flow assigns nonnegative rational mass to legal histories, conserves each type's mass \(\mu_t\), and uses at most \(B_r\) units of every resource class; hence every mass element ends with an integral bundle.
For a target policy, let \(V\) be the target type's final value per unit mass under its flow, and let \(V_G\) be the corresponding value when the target also uses the fixed greedy policy.
For every fixed \(\varepsilon\in(0,0.3)\), is deciding whether a feasible target policy and mass-flow attain \(V\ge(1+\varepsilon)V_G\), and producing such a flow, solvable in polynomial time or NP-hard?
In the discrete round-robin model, for \(n\ge2\), consistently improving a fixed target agent's greedy outcome by a factor \(1+\varepsilon\) is NP-hard unless \(P=NP\), even when every other agent has an additive objective and follows greedy.
For every fixed \(\varepsilon\in(0,0.3)\), deciding whether there exists a feasible target policy and mass-flow satisfying \(V\geq(1+\varepsilon)V_G\) is \(\mathrm{NP\text{-}hard}\). Consequently, deciding and producing such a flow cannot be done in polynomial time unless \(\mathrm{P}=\mathrm{NP}\).
The hardness already holds with two types, unit masses, modular utilities, unit total supplies, and a graph-represented feasibility family whose membership problem is polynomial-time solvable.
We use the following standard consequence of the hardness of approximating Maximum Independent Set.
Gap Independent Set. It is \(\mathrm{NP\text{-}hard}\) to distinguish instances \((G,K)\) satisfying one of the following promises:
where \(\alpha(G)\) denotes the maximum size of an independent set in \(G\).
This follows, for example, from the stronger \(n^{1-\delta}\)-inapproximability of Maximum Clique proved by [Zuckerman](https://www.theoryofcomputing.org/articles/v003a006/v003a006.pdf), together with the identity \(\alpha(G)=\omega(\overline G)\).
Fix an instance \((G,K)\) of Gap Independent Set. Let \(C\) be a new set of \(K\) vertices. Construct a graph \(H\) as follows:
Thus an independent set of \(H\) is contained entirely in \(C\) or entirely in \(V(G)\). Hence
\[ \alpha(H)=\max\{K,\alpha(G)\}. \]
Create two types: the target type \(\star\) and a dummy type \(d\), with masses
\[ \mu_\star=\mu_d=1. \]
There is one resource class for every vertex of \(H\). For every resource \(r\), set \(b_r=1/2\). Since the total mass is \(2\), its total supply is
\[ B_r=b_r(\mu_\star+\mu_d)=1. \]
The target feasibility family is
\[ \mathcal I_\star = \left\{ x\in\{0,1\}^{V(H)}: \operatorname{supp}(x)\text{ is an independent set of }H \right\}. \]
Membership in \(\mathcal I_\star\) is checkable in polynomial time from the graph \(H\).
The target utility is the modular function
\[ f_\star(x)=\sum_{r\in V(H)}x_r. \]
It is normalized and nonnegative. It is diminishing-returns submodular because, for every \(x\leq y\) and every coordinate \(r\),
\[ f_\star(x+e_r)-f_\star(x) = 1 = f_\star(y+e_r)-f_\star(y). \]
The dummy type has \(\mathcal I_d=\{0\}\) and \(f_d=0\). Prescribe sufficiently many turns for the target, for example \(|V(H)|\) turns, interleaved arbitrarily with dummy turns.
Arrange the fixed resource tie-breaking so that every resource in \(C\) precedes every resource in \(V(G)\).
Initially every feasible resource has target marginal value \(1\). Therefore the target’s greedy policy first selects a vertex of \(C\).
After this first selection, every vertex of \(G\) becomes infeasible because every vertex of \(C\) is adjacent to every vertex of \(G\). The remaining vertices of \(C\) remain feasible because \(C\) is independent. Greedy consequently selects all \(K\) vertices of \(C\) and nothing else.
Thus
\[ V_G=K. \]
Because the tie-breaking is fixed, the greedy history is unique up to the irrelevant ordering within \(C\).
Let a feasible target mass-flow assign coefficient \(y_h\) to each target history \(h\). Since \(\mu_\star=1\),
\[ \sum_h y_h=1. \]
Let \(S_h\) be the terminal support of history \(h\). Legality and the definition of \(\mathcal I_\star\) imply that \(S_h\) is an independent set of \(H\). Therefore
\[ f_\star(S_h)=|S_h|\leq\alpha(H). \]
Consequently every mass-flow satisfies
\[ V=\sum_h y_h f_\star(S_h) \leq \sum_h y_h\alpha(H) = \alpha(H). \]
Conversely, let \(S\) be a maximum independent set of \(H\). A target history can select the elements of \(S\) in any order and then select nothing. Every partial support is a subset of \(S\), hence remains feasible. Putting the entire target mass on this single history consumes at most one unit of each resource and is therefore a feasible mass-flow. It attains value \(|S|=\alpha(H)\).
Hence the optimal fluid value is exactly
\[ V^\star=\alpha(H)=\max\{K,\alpha(G)\}. \]
This equality also shows why fractional mass-splitting cannot help in the construction: \(V\) is an average of cardinalities of independent sets and therefore cannot exceed their maximum cardinality.
Suppose first that \((G,K)\) is a YES instance. Then
\[ V^\star \geq \alpha(G) \geq 2K. \]
Since \(\varepsilon<0.3<1\),
\[ 2K>(1+\varepsilon)K=(1+\varepsilon)V_G. \]
Thus the constructed fluid instance admits the required policy and flow.
Suppose instead that \((G,K)\) is a NO instance. Then \(\alpha(G)\leq K\), and therefore
\[ V^\star=\max\{K,\alpha(G)\}=K=V_G. \]
Because \(\varepsilon>0\),
\[ V^\star=K<(1+\varepsilon)K=(1+\varepsilon)V_G. \]
Thus no required policy or mass-flow exists.
The construction is polynomial in \(|V(G)|+|E(G)|+K\), and it maps YES instances to YES instances and NO instances to NO instances. This proves \(\mathrm{NP\text{-}hardness}\).
This proof settles the problem exactly as stated. It does not establish the stronger restriction in which every \(\mathcal I_t\) is unconstrained or merely a cardinality constraint. The supplied discrete hardness theorem cannot by itself justify that stronger fluid claim, because allowing type mass to split convexifies the set of trajectories. The construction above avoids that gap by proving that the fluid optimum is exactly an integral graph parameter.
⟨structured verdict parsed — rendered above⟩
The combinatorial reduction is sound under the additional assumption that the target problem admits graph-encoded independent-set feasibility families. In that encoding, the proof correctly establishes that the optimal fluid value is \( \alpha(H) \), while the greedy benchmark is \( K \), so fractional mass splitting does not invalidate the gap.
However, the user task specifies no representation of \( \mathcal I_t \), utilities, policies, schedules, or flows. Consequently, it does not define a formal computational problem to which a polynomial-time reduction can be given. The prover introduces a graph representation without establishing that it belongs to the input model. Thus the unconditional claim that the problem “exactly as stated” is NP-hard is not formally established.
The asserted promise gap
is consistent with the cited strong inapproximability result. Zuckerman’s proof is explicitly gap-based and provides much larger completeness-to-soundness ratios than \( 2 \), so complementing the graph yields the corresponding independent-set gap. See [Zuckerman, Theorem 1.1 and its gap proof](https://www.theoryofcomputing.org/articles/v003a006/v003a006.pdf).
There are nevertheless two omitted domain conditions:
These are routine restrictions or cases, but they must be stated.
The claim
\( \alpha(H)=\max\{K,\alpha(G)\} \)
is correct. Complete adjacency between \( C \) and \( V(G) \) prevents an independent set from meeting both parts, while \( C \) itself is an independent set of size \( K \).
With two unit masses and \( b_r=1/2 \), the computation \( B_r=1 \) is correct.
The target feasibility family consists exactly of incidence vectors of independent sets of \( H \). It is downward closed, contains zero, and membership can be checked in polynomial time from an explicitly supplied graph.
The utility \( f_\star(x)=\sum_r x_r \) is normalized, nonnegative, modular, and satisfies diminishing returns on the full nonnegative integer lattice. The dummy utility and feasibility family are also valid.
The unresolved point is representational: polynomial-time membership does not itself specify how \( \mathcal I_\star \) is represented in the target problem. The prover must identify a formal input encoding under which a graph and the stated interpretation of its independent sets constitute a legal instance. Without that, “polynomial construction” and “NP-hard” are undefined relative to the user task.
Having at least \( |V(H)| \) target turns is sufficient. Since the dummy cannot receive any resource, its placement does not affect the argument.
The phrase “interleaved arbitrarily” does not give an exact schedule encoding. This is a minor specification omission: the reduction should output a concrete polynomial-size schedule and state whether the schedule is part of the instance or fixed externally by the model.
All initially feasible resources have marginal value \( 1 \). Given tie-breaking that ranks every element of \( C \) before every element of \( V(G) \), the first greedy choice lies in \( C \).
After that choice:
Thus \( V_G=K \) is correct.
The statement that the history is “unique up to the irrelevant ordering within \( C \)” is imprecise: a fully fixed tie-breaking rule determines the order inside \( C \) as well. This does not affect the value.
For each legal target history, its terminal support is an independent set of \( H \), hence has utility at most \( \alpha(H) \). Since the target mass is \( 1 \), averaging over histories gives
\( V\leq\alpha(H) \).
This correctly handles arbitrary fractional splitting. It does not rely on an unstated integrality assertion beyond the definitions.
Putting all target mass on one history that chooses a maximum independent set is feasible:
A target policy realizing this one history exists. Therefore \( V^\star=\alpha(H) \) is correct.
No policy-consistency problem arises because the attaining flow has only one target history.
For YES instances,
\( V^\star\geq2K>(1+\varepsilon)K \)
is correct because \( \varepsilon<0.3<1 \), assuming \( K>0 \).
For NO instances,
\( V^\star=K<(1+\varepsilon)K \)
is correct because \( \varepsilon>0 \), again assuming \( K>0 \).
Thus the reduction separates the two promise cases under the stated encoding assumption.
The reduction gives genuine evidence of NP-hardness for a particular formalization in which graph-encoded independent-set feasibility families are admissible inputs. It does not, as written, settle the representation-independent user task because that task never defines such an encoding.
The production conclusion is acceptable only in the combined sense of an algorithm that decides existence and produces a flow on YES instances. Decision hardness rules out such a combined polynomial-time procedure unless \( P=NP \).
The prover must specify the formal input model and establish that it includes:
Once that clarification is supplied, the substantive reduction appears valid; no new combinatorial lemma 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.