Answer: —
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any p < 0, there does not exist an online al- gorithm with competitive ratio strictly less than 2−(2+2/|p|) · n |p| 2|p|+1 for the p-mean welfare maximization problem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(p<0\), given a finite type set \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), total population \(N\) with \(M_\theta=N\mu_\theta\ge1\), and an online sequence of \(T\) divisible goods, where arrival \(t\) reveals \(v_t(\theta)\) but not future vectors and \(\sum_t v_t(\theta)=1\), choose irrevocable masses \(y_{t,\theta}\) with \(0\le y_{t,\theta}\le M_\theta\) and \(\sum_\theta y_{t,\theta}\le1\). Determine the best worst-case competitive ratio and an online policy computable in time polynomial in \(\tau\), \(T\), and the encoding length, for \(W_p(y)=\left(\sum_\theta\mu_\theta u_\theta^p\right)^{1/p}\), where \(u_\theta=\sum_t v_t(\theta)y_{t,\theta}/M_\theta\), against the offline optimum for the same sequence, including adaptive adversaries.
Definitions. Fix \(p<0\). An instance has a finite type set \(\Theta\), rational masses \(\mu_\theta\) with \(\sum_\theta\mu_\theta=1\), and population \(N\), where \(M_\theta=N\mu_\theta\ge1\). At round \(t\), a divisible good of supply \(1\) arrives and reveals nonnegative values \(v_t(\theta)\), with \(\sum_{t=1}^T v_t(\theta)=1\) for every \(\theta\).
An online policy irrevocably chooses \(y_{t,\theta}\) with \(0\le y_{t,\theta}\le M_\theta\) and \(\sum_\theta y_{t,\theta}\le1\). Type \(\theta\)'s per-agent utility is \(u_\theta=\sum_t v_t(\theta)y_{t,\theta}/M_\theta\), and welfare is \(W_p(y)=\left(\sum_\theta\mu_\theta u_\theta^p\right)^{1/p}\). The competitive ratio compares the offline optimum for the realized sequence with the policy's welfare; the adversary may choose each next value vector after observing earlier allocations, while satisfying the normalization above.
Target.
For fixed \(p<0\), is determining the optimal worst-case competitive ratio and computing a polynomial-time online policy for this type-mass model in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Nearest known results.
For the discrete normalized model with \(n\) individual agents, every online algorithm has competitive ratio at least \(2^{-(2+2/|p|)}n^{|p|/(2|p|+1)}\) for every \(p<0\).
This lower bound concerns online performance, rather than the computational complexity of the type-mass model above.
As stated, the target does not yet define a decision or function problem to which the labels \(\mathrm P\) or \(\mathrm{NP}\)-hard can rigorously be applied. In particular, the horizon, numerical encoding of revealed values, required precision, representation of an online policy, and deterministic-versus-randomized convention are unspecified.
Nevertheless, several structural and algorithmic facts can be proved. They isolate the genuinely open part of the question.
Throughout, write \(K=|\Theta|\), let
\[ X_\theta=\sum_{t=1}^T v_t(\theta)y_{t,\theta}, \]
and use the competitive-ratio convention
\[ \operatorname{CR}(A)=\sup_v\frac{\operatorname{OPT}(v)}{W_p(A(v))}. \]
If some type receives zero utility, \(W_p\) is understood as \(0\), consistently with the limit definition for \(p<0\).
For every feasible allocation,
\[ W_p(y)=\frac1N\left(\sum_{\theta\in\Theta}\mu_\theta^{\,1-p}X_\theta^p\right)^{1/p}. \]
Consequently, if the mass vector \(\mu\) is fixed, changing \(N\) does not change any competitive ratio.
Since \(M_\theta=N\mu_\theta\),
\[ u_\theta=\frac{X_\theta}{N\mu_\theta}. \]
Therefore
\[ \sum_\theta\mu_\theta u_\theta^p =\sum_\theta\mu_\theta \left(\frac{X_\theta}{N\mu_\theta}\right)^p =N^{-p}\sum_\theta\mu_\theta^{\,1-p}X_\theta^p. \]
Taking the \(1/p\)-power gives the claimed formula.
Moreover, \(M_\theta\geq1\), while feasibility already implies \(y_{t,\theta}\leq1\). Thus the constraint \(y_{t,\theta}\leq M_\theta\) is redundant, and the feasible set is independent of \(N\). Both online and offline welfare are multiplied by \(1/N\), so their ratio is independent of \(N\). ∎
In particular, binary encoding of a very large population cannot by itself be the source of hardness.
Expand each type \(\theta\) into \(M_\theta\) individual agents with identical values \(v_t(\theta)\).
The type-mass offline optimum equals the offline optimum of the expanded individual instance. More strongly, the optimal worst-case competitive ratio over mathematical, not necessarily succinct, policies is the same in the two formulations.
Given a type allocation \(y\), allocate \(y_{t,\theta}/M_\theta\) to every clone of \(\theta\). This is feasible and gives every clone utility \(u_\theta\), so it preserves welfare exactly.
Conversely, consider any expanded allocation and let \(U_{\theta,j}\) be the utilities of the clones of type \(\theta\). Define
\[ y_{t,\theta}=\sum_{j=1}^{M_\theta}x_{t,\theta,j}. \]
The induced type utility is their average:
\[ u_\theta=\frac1{M_\theta}\sum_{j=1}^{M_\theta}U_{\theta,j}. \]
Since \(p<0\), the function \(s\mapsto s^p\) is convex on the positive reals. Jensen's inequality gives
\[ \frac1{M_\theta}\sum_{j=1}^{M_\theta}U_{\theta,j}^p \geq \left(\frac1{M_\theta}\sum_{j=1}^{M_\theta}U_{\theta,j}\right)^p =u_\theta^p. \]
After weighting by \(M_\theta/N=\mu_\theta\) and summing over types, the inner power sum of the expanded allocation is at least that of the type allocation. Because \(1/p<0\), taking the \(1/p\)-power reverses the inequality. Hence symmetrization weakly increases welfare. The same conclusion holds at zero utilities by continuity.
It follows in both directions that the offline optima are equal.
A type policy can be lifted symmetrically to the expanded instance. Conversely, an expanded online policy can be simulated and its allocations aggregated by type; the resulting type welfare is at least the expanded policy's welfare on every sequence. Thus the infima of the worst-case ratios coincide. This argument does not imply that a policy running in time polynomial in \(N\) can be compressed to time polynomial in \(\log N\). ∎
As a special case, setting \(M_\theta=1\), \(N=K\), and \(\mu_\theta=1/K\) recovers the normalized individual-agent model exactly. Hence every individual-agent online lower bound transfers immediately to the type-mass model when the number of types is allowed to grow.
For a fixed realized sequence, maximizing \(W_p\) is equivalent to the convex minimization problem
\[ \min_y F(y),\qquad F(y)=\sum_{\theta\in\Theta}\mu_\theta^{\,1-p} \left(\sum_t v_t(\theta)y_{t,\theta}\right)^p, \]
over the allocation polytope.
Proposition 1 gives \(W_p=N^{-1}F^{1/p}\). Since \(1/p<0\), maximizing \(W_p\) is equivalent to minimizing \(F\).
For \(x>0\),
\[ \frac{d^2}{dx^2}x^p=p(p-1)x^{p-2}>0, \]
because both \(p\) and \(p-1\) are negative. Thus every summand is convex, and composition with the linear map \(y\mapsto X_\theta\) preserves convexity.
There is a strictly positive feasible point: take \(y_{t,\theta}=\mu_\theta\). Then
\[ X_\theta=\mu_\theta\sum_t v_t(\theta)=\mu_\theta>0. \]
At this point,
\[ F=\sum_\theta\mu_\theta^{\,1-p}\mu_\theta^p =\sum_\theta\mu_\theta=1. \]
Hence an optimum satisfies \(F^\star\leq1\). Every optimal coordinate consequently obeys
\[ \mu_\theta^{\,1-p}(X_\theta^\star)^p\leq1, \]
which, because \(p<0\), implies
\[ X_\theta^\star\geq \mu_\theta^{(1-p)/(-p)}. \]
Thus the optimum stays a bit-complexity-controlled distance away from the singularity at zero. ∎
If \(p\) is a fixed rational number and all realized values are rational, standard weak convex optimization computes an \(\varepsilon\)-approximate offline optimum in time polynomial in \(K\), \(T\), the input bit length, and \(\log(1/\varepsilon)\). The objective and its gradient are efficiently evaluable on the bounded-away-from-zero region above.
Therefore, any hardness of the online target must come from optimizing over nonanticipatory strategies, not from evaluating the offline benchmark.
Define the proportional policy \(A_{\mathrm{prop}}\) by
\[ y_{t,\theta}=\mu_\theta \]
at every round, independently of the revealed values.
Let
\[ B_p(\mu)= \left(\sum_{\theta\in\Theta}\mu_\theta^{\,1-p}\right)^{1/p}. \]
Then \(A_{\mathrm{prop}}\) has competitive ratio at most \(B_p(\mu)\). If arbitrary horizons are allowed, or if \(T\geq K\), its worst-case competitive ratio is exactly \(B_p(\mu)\). Moreover,
\[ 1\leq B_p(\mu)\leq K. \]
The policy uses \(O(K)\) rational operations per round.
The policy is feasible because \(\sum_\theta\mu_\theta=1\). Its aggregate utility numerator is
\[ X_\theta=\sum_t v_t(\theta)\mu_\theta=\mu_\theta, \]
so every type has per-agent utility
\[ u_\theta=\frac{\mu_\theta}{N\mu_\theta}=\frac1N. \]
Consequently,
\[ W_p(A_{\mathrm{prop}})=\frac1N. \]
For an arbitrary feasible allocation, \(y_{t,\theta}\leq1\), and therefore
\[ X_\theta =\sum_t v_t(\theta)y_{t,\theta} \leq\sum_t v_t(\theta)=1. \]
Thus \(u_\theta\leq1/(N\mu_\theta)\). The \(p\)-mean is coordinatewise nondecreasing, including for \(p<0\), so
\[ \operatorname{OPT} \leq \frac1N \left(\sum_\theta\mu_\theta^{\,1-p}\right)^{1/p} =\frac{B_p(\mu)}N. \]
Hence \(\operatorname{OPT}/W_p(A_{\mathrm{prop}})\leq B_p(\mu)\).
For tightness, take one round for every type and let the round associated with \(\theta\) have value \(1\) for \(\theta\) and value \(0\) for every other type. The offline allocation gives that entire good to \(\theta\), attaining \(X_\theta=1\) simultaneously for every type. Its welfare is \(B_p(\mu)/N\), while the proportional policy still obtains \(1/N\).
Finally, put \(q=1-p>1\). Convexity gives
\[ K^{1-q}=K^p \leq \sum_\theta\mu_\theta^q \leq\sum_\theta\mu_\theta=1. \]
Raising to the negative power \(1/p\) reverses these inequalities and yields \(1\leq B_p(\mu)\leq K\). ∎
This proves the existence of a polynomial-time type-succinct policy, but not of an optimal one.
The optimal competitive ratio is \(1\) in either of the following cases:
If \(K=1\), allocating the whole good in every round gives utility \(1/N\), which is also the coordinatewise upper bound. Hence the allocation is offline optimal.
If \(T=1\), normalization forces \(v_1(\theta)=1\) for every type, so the complete sequence is known immediately.
If \(T=2\), after observing the first vector, normalization determines the second vector exactly:
\[ v_2(\theta)=1-v_1(\theta). \]
Thus at round \(1\) the policy already knows the entire sequence. It may choose an offline-optimal pair \((y_1^\star,y_2^\star)\), implement \(y_1^\star\), and then implement \(y_2^\star\) in the final round. Compactness and continuity ensure existence of an offline optimum. Therefore the ratio is \(1\). ∎
Any nontrivial hardness reduction must consequently use at least three rounds and at least two types.
Assume now that \(p=-a/b\), where \(a,b\) are fixed positive coprime integers. Fix an explicitly encoded finite horizon \(T\), restrict attention to deterministic policies, and ask whether there exists a policy with competitive ratio at most a rational threshold \(c\geq1\).
This repaired threshold problem is expressible in the first-order theory of real closed fields and is therefore decidable by real quantifier elimination.
Let \(V_t\) denote the value vector revealed at round \(t\), and \(Y_t\) the online allocation vector. Nonanticipativity is represented exactly by the alternating prefix
\[ \forall V_1\ \exists Y_1\ \forall V_2\ \exists Y_2\ \cdots\ \forall V_T\ \exists Y_T. \]
The validity conditions \(v_t(\theta)\geq0\) and \(\sum_t v_t(\theta)=1\), as well as all allocation constraints, are polynomial inequalities.
After the online allocations, universally quantify an offline allocation \(Z\). Let \(X_\theta^Y\) and \(X_\theta^Z\) be the corresponding aggregate utility numerators.
For each allocation introduce positive auxiliary variables \(q_\theta^Y,q_\theta^Z\) satisfying
\[ (q_\theta^Y)^b(X_\theta^Y)^a=M_\theta^a, \qquad (q_\theta^Z)^b(X_\theta^Z)^a=M_\theta^a. \]
These equations state precisely that
\[ q_\theta^Y=(u_\theta^Y)^{-a/b}=(u_\theta^Y)^p, \]
and analogously for \(Z\). Define
\[ S_Y=\sum_\theta\mu_\theta q_\theta^Y, \qquad S_Z=\sum_\theta\mu_\theta q_\theta^Z. \]
Because \(W_p(Y)^p=S_Y\), the inequality \(W_p(Z)\leq cW_p(Y)\) is equivalent to
\[ S_Y^b\leq c^aS_Z^b. \]
This is a polynomial inequality. Offline allocations with a zero-utility type may be omitted from the universal comparison, since they have welfare \(0\), while a strictly positive offline allocation always exists.
Thus the entire strategy-threshold statement is a quantified formula over rational polynomial equalities and inequalities. Quantifier elimination decides its truth. ∎
As a further consequence, for fixed finite \(T\) the set of feasible thresholds \(c\) is semialgebraic and upward closed. Its infimum is therefore a real algebraic number. This establishes decidability, not membership in \(\mathrm P\): the number of alternating quantifier blocks grows with \(T\), and known general quantifier-elimination procedures are not polynomial-time here.
The lower bound quoted in the question transfers by taking singleton types, but it remains an information-theoretic online lower bound.
There is also a more recent strengthening. Huang, Lee, Shu, and Wang obtain asymptotically matching competitive-ratio exponents in the normalized individual model: for fixed \(-1\leq p<0\), the exponent is \(|p|/(|p|+1)\), while for fixed \(p\leq-1\) it is \(1/2\), up to logarithmic or lower-order factors. Their algorithms use Nashian and egalitarian greedy components, while their lower bounds hold even for binary values. See [The Long Arm of Nashian Allocation in Online \(p\)-Mean Welfare Maximization](https://pure.mpg.de/rest/items/item_3648174/component/file_3648175/content).
These results transfer as lower bounds to the singleton-type subclass. They do not determine an exact optimal ratio, establish \(\mathrm{NP}\)-hardness, or automatically yield running time polynomial in the succinct type-mass encoding when \(N\) is binary encoded.
The requested \(\mathrm P\)-versus-\(\mathrm{NP}\)-hard classification is not presently justified.
What is proved is:
The remaining difficulty is the computational complexity of the alternating online-strategy problem for \(T\geq3\), together with a succinct representation of an optimal or near-optimal policy.
⟨structured verdict parsed — rendered above⟩
The prover correctly recognizes that the stated target is not yet a formal complexity problem: the role and encoding of \(T\), the numerical representation of values, approximation requirements, policy representation, and treatment of randomization are unspecified. It therefore does not establish either membership in \(\mathrm P\) or \(\mathrm{NP}\)-hardness.
The output nevertheless proves several genuine structural results. Propositions 1, 4, and 5 are correct. The allocation-level part of Proposition 2 is correct, while its policy-level formulation needs a convention clarification. Proposition 3 correctly identifies the convex objective but does not rigorously justify its polynomial-time optimization claim. Proposition 6 gives the right algebraic ingredients for a real-closed-field formulation, but it does not actually write the guarded quantified formula required to establish the claim exactly.
Accordingly, the proper status is partial.
The identity
\[ W_p(y)=\frac1N\left(\sum_\theta \mu_\theta^{1-p}X_\theta^p\right)^{1/p} \]
is correct whenever every \(X_\theta>0\), and it remains valid under the declared zero-welfare extension.
The redundancy of \(y_{t,\theta}\leq M_\theta\) is also correct: nonnegativity and \(\sum_\theta y_{t,\theta}\leq1\) imply \(y_{t,\theta}\leq1\), while \(M_\theta\geq1\). Thus, for fixed \(\mu\), the feasible allocation set is independent of \(N\), and both online and offline welfare scale by \(1/N\).
This proves independence of the mathematical competitive ratio from \(N\). It does not by itself settle computational dependence on the binary representation of \(N\), which the prover correctly notes.
For an expanded allocation, the aggregated type utility is indeed the arithmetic mean of the clone utilities. Jensen's inequality gives
\[ \frac1{M_\theta}\sum_j U_{\theta,j}^p \geq \left(\frac1{M_\theta}\sum_j U_{\theta,j}\right)^p \]
because \(x\mapsto x^p\) is convex for \(p<0\). Since \(1/p<0\), applying the outer power reverses the inequality, so equalizing clones weakly increases welfare. This establishes equality of the offline optima.
The zero-utility case is only described as holding “by continuity.” Since \(0^p\) is not finite for \(p<0\), Jensen cannot literally be applied there as written. A separate extended-real or limiting convention must be stated. This is a minor issue: the claimed inequality survives.
The online-policy equivalence is persuasive for deterministic policies: an expanded policy can be simulated, its allocations aggregated, and the type welfare is pointwise no smaller. However, Proposition 2 says “policies” without fixing the randomized-policy convention, even though the opening status explicitly says that convention is unspecified. If random policies are included, the performance criterion, adversary's observation model, and coupling of the random simulation must be stated. This is a scope ambiguity rather than a demonstrated counterexample.
The singleton-type specialization is correct.
The order reversal is correct: since
\[ W_p=N^{-1}F^{1/p} \]
and \(1/p<0\), maximizing \(W_p\) is equivalent to minimizing \(F\).
Convexity is also correct on \(X_\theta>0\), because
\[ \frac{d^2}{dx^2}x^p=p(p-1)x^{p-2}>0. \]
The feasible allocation \(y_{t,\theta}=\mu_\theta\) gives \(X_\theta=\mu_\theta\) and \(F=1\). Therefore \(F^\star\leq1\), and each positive summand satisfies
\[ \mu_\theta^{1-p}(X_\theta^\star)^p\leq1. \]
Reversing the inequality when solving for \(X_\theta^\star\) yields the displayed lower bound
\[ X_\theta^\star\geq\mu_\theta^{(1-p)/(-p)}. \]
That calculation is correct.
There are two gaps:
The claim is plausible, but under the requested verification standard it remains unverified. This is a major gap in the auxiliary assertion that the offline benchmark is polynomial-time computable.
The proportional policy is feasible and gives
\[ X_\theta=\mu_\theta,\qquad u_\theta=\frac1N,\qquad W_p(A_{\mathrm{prop}})=\frac1N. \]
For every allocation, \(y_{t,\theta}\leq1\) implies \(X_\theta\leq1\). The generalized \(p\)-mean is coordinatewise nondecreasing, including for \(p<0\), so the resulting upper bound on the offline welfare is correct.
The tight instance is valid: one dedicated unit-value round per type allows the offline allocation to attain \(X_\theta=1\) for all types simultaneously. If \(T>K\), the remaining rounds may have zero values. Thus the exact ratio claim is correct for \(T\geq K\), and also for a worst case over arbitrary horizons.
For \(q=1-p>1\),
\[ K^{1-q}\leq\sum_\theta\mu_\theta^q\leq1 \]
is correct, and raising to \(1/p<0\) gives \(1\leq B_p(\mu)\leq K\). The running-time claim is also correct in the stated rational-operation model.
For \(K=1\), allocating each good completely is offline optimal.
For \(T=1\), normalization reveals the entire sequence immediately. For \(T=2\), observing \(v_1\) determines
\[ v_2(\theta)=1-v_1(\theta). \]
Thus a mathematical online policy can select an offline-optimal allocation before making its first decision. The allocation polytope is compact, and the declared continuous extension of negative \(p\)-mean welfare attains a maximum. The ratio-one conclusion is correct.
This proposition establishes existence, not a polynomial-time exact representation of the chosen offline optimum. The prover does not explicitly claim the latter.
For \(p=-a/b\), the auxiliary equation
\[ (q_\theta)^b(X_\theta)^a=M_\theta^a \]
correctly expresses \(q_\theta=u_\theta^p\) when \(X_\theta>0\) and \(q_\theta>0\).
The conversion of
\[ W_p(Z)\leq cW_p(Y) \]
to
\[ S_Y^b\leq c^aS_Z^b \]
is correct.
The alternating prefix
\[ \forall V_1\,\exists Y_1\,\cdots\,\forall V_T\,\exists Y_T \]
has the correct dependency pattern for deterministic nonanticipatory strategies. Nevertheless, the proof does not present a complete first-order sentence:
These are routine logical details rather than evidence that the real-closed-field conclusion is false. Still, the claim that the displayed prefix represents nonanticipativity “exactly” is incomplete as written.
Once the intended finite formula is supplied, decidability by quantifier elimination and semialgebraicity of the feasible threshold set are standard consequences. The algebraicity claim additionally presupposes that the mass instance and finite horizon are fixed and that the feasible threshold set is nonempty; nonemptiness follows from the earlier proportional policy, although this dependency is not stated here.
The cited paper does report the stated exponents: for fixed negative \(p\) between \(0\) and \(-1\), the exponent is \(\lvert p\rvert/(\lvert p\rvert+1)\), while for \(p\leq-1\) it is \(1/2\), up to the described lower-order or logarithmic losses. It also states binary-valuation lower bounds in the relevant negative regime. The summary is consistent with the [cited paper](https://pure.mpg.de/rest/items/item_3648174/component/file_3648175/content).
These are competitive-ratio lower bounds, not computational \(\mathrm{NP}\)-hardness results. The prover distinguishes those notions correctly.
The output supplies no polynomial-time algorithm for determining the optimal worst-case ratio, no succinct representation of an optimal policy, and no hardness reduction. Therefore it does not answer the requested \(\mathrm P\)-versus-\(\mathrm{NP}\)-hard alternative. This is openly acknowledged rather than concealed.
The minimum clarification needed before that target can be verified is a formal decision or approximation problem specifying:
Even after those specifications, a complexity classification remains absent from the prover output.
⟨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.