Answer: \(\mathrm{NP}\)-hard
Theorem 3.16 — class: algorithmic
Given a star \(S_m\), a finite set of additive valuation types \(T\), a distribution \(\mu\) over \(T\), and per-location capacities \(q_v\), find the maximum \(\alpha\) for which there is a mass allocation \(x_{t,B}\ge 0\) over connected integral bundles \(B\subseteq V(S_m)\), satisfying \(\sum_B x_{t,B}=\mu_t\), \(\sum_{t,B\ni v}x_{t,B}=q_v\), and \(u_t(B)\ge \alpha\,\operatorname{MMS}^{\infty}_t(q)\) whenever \(x_{t,B}>0\).
Let \(S_m\) be a star on \(m\ge2\) vertices, with center \(c\). A society is given by its support: the list of \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Each type has nonnegative binary-rational additive vertex values \(u_t(v)\). Capacities \(q_v\in[0,1]\) are binary rationals.
Define the unconstrained mass maximin share by
\(\operatorname{MMS}^{\infty}_t(q)=\max\{z\ge0:\exists(y_B)_{B\subseteq V},\ y_B\ge0,\ \sum_B y_B=1,\ \sum_{B\ni v}y_B=q_v\ \forall v,\ y_B>0\Rightarrow u_t(B)\ge z\}\).
Allowed allocation bundles form \(\mathcal C=\{\varnothing\}\cup\{\{v\}:v\in V\}\cup\{B\subseteq V:c\in B\}\); thus empty bundles are permitted and all nonempty bundles are connected and integral.
For \(\alpha\ge0\), an admissible mass allocation satisfies \(x_{t,B}\ge0\), \(\sum_{B\in\mathcal C}x_{t,B}=\mu_t\), \(\sum_{t,B\in\mathcal C:v\in B}x_{t,B}=q_v\), and \(x_{t,B}>0\Rightarrow u_t(B)\ge\alpha\operatorname{MMS}^{\infty}_t(q)\). The optimization problem asks for the largest feasible \(\alpha\), allowing infeasibility or an unbounded value; zero benchmarks impose no positive utility requirement.
Is deciding whether an admissible mass allocation exists for a given binary-rational \(\alpha\ge0\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\), where \(L\) is the total input bit length, including \(\alpha\).
For discrete stars with \(m\ge n\ge2\), a polynomial-time algorithm guarantees each agent \(1/(m-n+1)\) of her unconstrained MMS, and this universal factor is tight ([source](https://arxiv.org/pdf/1908.05433v3)).
The related AnyPrice share uses distributions over integral bundles with uniform marginal upper bounds; computing it is NP-hard even for additive values and entitlement \(1/2\) ([source](https://arxiv.org/pdf/2103.04304)). This concerns a benchmark, not the connected mass-allocation decision problem above; no result settling that exact problem was located.
The decision problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, already with support size \(\tau=2\) and fixed \(\alpha=2\). Both benchmarks in the reduction are explicitly known and positive.
For general inputs, an exact algorithm runs in \(2^{O(m)}\operatorname{poly}(\tau,L)\) time. Thus the problem is polynomial-time solvable for fixed \(m\), but a polynomial-time algorithm for unrestricted \(m\) would imply \(\mathrm P=\mathrm{NP}\).
We use the standard \(\mathrm{NP}\)-complete problem PARTITION: given positive binary integers \(a_1,\ldots,a_k\), decide whether some subset has half their total sum. See [these university notes](https://ktiml.mff.cuni.cz/~fink/teaching/computability_2017_18/tutorial_5.pdf). We may assume the total is even: multiplying every input integer by two preserves the answer and ensures this condition.
Write \(\sum_{i=1}^k a_i=2T\), where \(T>0\). Define
\(r=\lceil\log_2(k+2)\rceil,\qquad p=2^{-r},\qquad D=2T+1,\qquad K=2D-T=3T+2.\)
In particular, \(0<p\le 1/(k+2)\).
Construct a star with center \(c\), one distinguished leaf \(h\), and leaves \(\ell_1,\ldots,\ell_k\). Hence \(m=k+2\). Set
\(q_c=p,\qquad q_h=1-p,\qquad q_{\ell_i}=p/2.\)
There are exactly two types, denoted \(A\) and \(B\), with masses
\(\mu_A=p,\qquad \mu_B=1-p.\)
Their additive vertex values are:
| Vertex | Type \(A\) | Type \(B\) |
|---|---:|---:|
| \(c\) | \(K\) | \(1/2\) |
| \(h\) | \(D\) | \(1\) |
| \(\ell_i\) | \(a_i\) | \(0\) |
Finally, set \(\alpha=2\). All values, masses, and capacities satisfy the required hypotheses; indeed, all rational numbers used are dyadic.
We prove
\(\operatorname{MMS}^{\infty}_A(q)=D,\qquad \operatorname{MMS}^{\infty}_B(q)=1/2.\)
Let \(I=\{\ell_1,\ldots,\ell_k\}\). Consider the distribution
\(y_{\{h\}}=1-p,\qquad y_{\{c\}}=p/2,\qquad y_{\{c\}\cup I}=p/2,\)
with all other masses zero.
Its masses sum to one. Its center marginal is \(p\), its distinguished-leaf marginal is \(1-p\), and every original-leaf marginal is \(p/2\). Thus it has exactly the required marginals.
For type \(A\), its three supported bundles have utilities \(D\), \(K\), and \(K+2T\). Since \(K-D=T+1>0\), all have utility at least \(D\). Therefore
\(\operatorname{MMS}^{\infty}_A(q)\ge D.\)
For type \(B\), the same bundles have utilities \(1\), \(1/2\), and \(1/2\). Consequently,
\(\operatorname{MMS}^{\infty}_B(q)\ge 1/2.\)
Consider any distribution over integral bundles having marginals \(q\), and let \(F\) be a random bundle drawn from it. The union bound gives
\(\Pr(F\cap(\{c\}\cup I)\ne\varnothing)\le q_c+\sum_{i=1}^k q_{\ell_i}=p(1+k/2)\le 1/2.\)
Thus with positive probability, \(F\) contains neither the center nor any original leaf. Such a bundle is either \(\varnothing\) or \(\{h\}\), and its type-\(A\) utility is at most \(D\).
Every distribution with the required marginals therefore has a positive-mass bundle of utility at most \(D\). No benchmark strictly greater than \(D\) is feasible. This proves
\(\operatorname{MMS}^{\infty}_A(q)=D.\)
In any distribution with the required marginals, the probability of omitting \(h\) is \(1-q_h=p>0\). Every bundle omitting \(h\) has type-\(B\) utility at most \(1/2\), because only the center can contribute positive utility.
Hence no benchmark strictly greater than \(1/2\) is feasible, proving
\(\operatorname{MMS}^{\infty}_B(q)=1/2.\)
Suppose an admissible allocation exists at \(\alpha=2\). Its required utilities are therefore \(2D\) for type \(A\) and \(1\) for type \(B\).
Every allowed bundle omitting the center is empty or a singleton leaf. None meets type \(A\)'s requirement:
\(u_A(\varnothing)=0<2D,\qquad u_A(\{h\})=D<2D,\qquad a_i\le 2T<2D.\)
Thus every positive-mass type-\(A\) bundle contains \(c\). Its total mass is \(p\), exactly the center capacity. Therefore no positive-mass type-\(B\) bundle contains \(c\).
Every bundle omitting \(h\) has type-\(B\) utility at most \(1/2<1\). Hence every positive-mass type-\(B\) bundle contains \(h\).
The type-\(B\) mass is \(1-p\), exactly \(q_h\). Consequently, no positive-mass type-\(A\) bundle contains \(h\).
Moreover, a type-\(B\) bundle contains \(h\) and omits \(c\). Connectivity then forces it to be precisely \(\{h\}\). In particular, type \(B\) receives no original leaves.
For an allocation bundle \(F\), write
\(s(F)=\sum_{\{i:\ell_i\in F\}}a_i.\)
Every positive-mass type-\(A\) bundle contains \(c\) and omits \(h\), so its utility requirement implies
\(K+s(F)\ge 2D,\qquad\text{hence}\qquad s(F)\ge 2D-K=T.\)
All original-leaf capacity goes to type \(A\). Therefore
\(\sum_{F\in\mathcal C}x_{A,F}s(F)=\sum_{i=1}^k a_iq_{\ell_i}=(p/2)(2T)=pT.\)
Since \(\sum_{F\in\mathcal C}x_{A,F}=p\), subtraction gives
\(\sum_{F\in\mathcal C}x_{A,F}(s(F)-T)=0.\)
Every summand is nonnegative. Thus every positive-mass type-\(A\) bundle satisfies \(s(F)=T\). At least one such bundle exists because \(\mu_A=p>0\). Its original leaves give a subset of the input integers summing to \(T\), and hence a solution to PARTITION.
Conversely, suppose \(J\subseteq\{1,\ldots,k\}\) satisfies \(\sum_{i\in J}a_i=T\). Its complement also has sum \(T\).
Set
\(x_{A,\{c\}\cup\{\ell_i:i\in J\}}=p/2,\)
\(x_{A,\{c\}\cup\{\ell_i:i\notin J\}}=p/2,\)
\(x_{B,\{h\}}=1-p,\)
and set all other allocation masses to zero.
All three bundles are allowed. The type masses are correct; the center has marginal \(p\), the distinguished leaf has marginal \(1-p\), and each original leaf occurs in exactly one of the two type-\(A\) bundles, giving marginal \(p/2\).
Each type-\(A\) bundle has utility \(K+T=2D\), and the type-\(B\) bundle has utility \(1\). These are exactly the required utilities at \(\alpha=2\).
Thus the allocation instance is feasible if and only if the PARTITION instance is a yes-instance.
If the PARTITION input has bit length \(\ell\), the construction has \(m=k+2\), \(\tau=2\), and output bit length \(O(\ell+k\log k)\). The numbers \(T,D,K\) are obtained by polynomial-time integer arithmetic, and \(p\) uses \(O(\log k)\) bits. The reduction is therefore polynomial-time.
This proves hardness of the allocation decision itself, even on instances whose benchmarks are explicitly computable by the preceding elementary arguments. The reduction establishes hardness at \(\alpha=2\); it does not establish hardness for the narrower restriction \(0\le\alpha\le1\).
For each listed type \(t\), enumerate the \(2^m\) subsets and their utilities. For a candidate value \(z\), benchmark feasibility is the rational linear program with variables \(y_F\) for subsets satisfying \(u_t(F)\ge z\), subject to
\(\sum_F y_F=1,\qquad \sum_{F\ni v}y_F=q_v\quad(v\in V),\qquad y_F\ge0.\)
The benchmark is the largest feasible subset-utility value. Indeed, every distribution has finite nonempty support, and its minimum supported utility is one of these values. Conversely, a feasible linear program supplies the required distribution.
Feasibility is monotone in \(z\), so sorting the candidate values and binary-searching them requires \(O(m)\) linear-program feasibility calls per type. Value zero is always feasible: independent vertex inclusion with probabilities \(q_v\) supplies a distribution with the required marginals.
Once the benchmarks are known, retain exactly the pairs \((t,F)\) with \(F\in\mathcal C\) and \(u_t(F)\ge\alpha\operatorname{MMS}^{\infty}_t(q)\). Solve the linear program expressing the type-mass and vertex-capacity equalities over these pairs.
There are \(|\mathcal C|=2^{m-1}+m\) allowed bundles, at most \(\tau(2^{m-1}+m)\) allocation variables, and \(\tau+m\) equality constraints. The constructed rational coefficients have bit length polynomial in \(L\). Polynomial-time rational linear programming therefore gives total running time
\(2^{O(m)}\operatorname{poly}(\tau,L).\)
The same bound handles exact optimization. First test feasibility at \(\alpha=0\); failure means infeasibility for every \(\alpha\). If all benchmarks vanish and this test succeeds, the value is unbounded. Otherwise, the finite optimum is among zero and the ratios \(u_t(F)/\operatorname{MMS}^{\infty}_t(q)\) for positive-benchmark types and allowed bundles. Between consecutive ratios, the eligible pairs are unchanged, so sorting these ratios and binary-searching feasibility finds the exact optimum within the same running-time bound.
⟨structured verdict parsed — rendered above⟩
The output proves the requested \(\mathrm{NP}\)-hardness result. The reduction, benchmark calculations, and exact algorithm are correct. I found no major or minor mathematical issues.
The reduction addresses the decision problem in USER_TASK: feasibility of an admissible connected mass allocation at a supplied binary-rational \(\alpha\). The restriction \(\alpha=2\) is permitted because the task allows every \(\alpha\ge0\).
The stated source problem is the standard binary-encoded PARTITION problem with positive integers. Its formulation agrees with the [cited university notes](https://ktiml.mff.cuni.cz/~fink/teaching/computability_2017_18/tutorial_5.pdf).
Multiplying every input integer by two preserves the existence of an equal-sum partition and makes the total even. This preprocessing increases the encoding length only polynomially. Thus writing the resulting total as \(2T\), with \(T>0\), is legitimate.
All constructed data satisfy the task’s requirements:
The definitions give
\[
p\le\frac1{k+2},\qquad
D=2T+1,\qquad
K=3T+2,
\]
and consequently
\[
K-D=T+1>0,\qquad 2D-K=T.
\]
These identities and inequalities are correct and are used consistently.
Common lower-bound distribution. The three specified probabilities sum to one. Their marginals are exactly \(q_c=p\), \(q_h=1-p\), and \(q_{\ell_i}=p/2\).
The supported type-\(A\) utilities are \(D\), \(K\), and \(K+2T\), all at least \(D\). The supported type-\(B\) utilities are \(1\), \(1/2\), and \(1/2\). Thus both claimed lower bounds follow directly from the benchmark definition.
Type-\(A\) upper bound. The union-bound calculation is correct:
\[
p(1+k/2)=\frac{p(k+2)}2\le\frac12.
\]
Therefore every distribution with the prescribed marginals assigns positive probability to bundles containing neither the center nor an original leaf. Each such bundle is either empty or \(\{h\}\), with utility at most \(D\).
This argument applies to arbitrary integral bundles, as required for the unconstrained benchmark. It establishes the upper bound without imposing connectivity.
Type-\(B\) upper bound. Every admissible benchmark distribution omits \(h\) with probability \(p>0\). A bundle omitting \(h\) has type-\(B\) utility at most \(1/2\). Hence the claimed upper bound follows.
Both exact benchmark values are established:
\[
\operatorname{MMS}^{\infty}_A(q)=D,\qquad
\operatorname{MMS}^{\infty}_B(q)=\frac12.
\]
At \(\alpha=2\), the required utilities are \(2D\) and \(1\).
Center saturation. Every allowed bundle omitting \(c\) is empty or a singleton leaf. None meets type \(A\)’s threshold, since each \(a_i\le2T<2D\). Therefore all type-\(A\) mass contains \(c\). Its mass equals the entire center capacity, so nonnegativity excludes positive type-\(B\) mass on any center-containing bundle.
Distinguished-leaf saturation. Every bundle omitting \(h\) has type-\(B\) utility at most \(1/2<1\). Thus all type-\(B\) mass contains \(h\), exhausting its capacity. No positive type-\(A\) mass can contain \(h\).
Since a type-\(B\) bundle contains \(h\) and omits \(c\), the allowed-bundle definition forces it to be \(\{h\}\). Hence type \(A\) receives all original-leaf capacity.
Exact subset value. Every positive-mass type-\(A\) bundle satisfies
\[
s(F)\ge2D-K=T.
\]
The marginal equalities give the stated weighted sum \(pT\), while the total type-\(A\) mass is \(p\). Consequently,
\[
\sum_{F\in\mathcal C}x_{A,F}(s(F)-T)=0.
\]
Every term is nonnegative: positive-mass terms have \(s(F)\ge T\), and zero-mass terms vanish. Therefore every positive-mass type-\(A\) bundle has \(s(F)=T\).
Such a bundle exists because \(p>0\), and its original leaves give the required partition. No integrality assumption on allocation masses is used.
The two complementary subsets each have value \(T\). Their center-containing bundles are allowed and have utility \(K+T=2D\).
The assigned masses satisfy every type-mass and capacity equality. Each original leaf appears in exactly one of the two type-\(A\) bundles. The type-\(B\) singleton has utility \(1\).
Because \(T>0\), both partition sides are nonempty and distinct; the two assignments do not accidentally specify the same allocation variable twice.
The converse is therefore valid, establishing the claimed equivalence.
The claimed output-length bound \(O(\ell+k\log k)\) is valid. The denominator of \(p\) needs \(O(\log k)\) bits, and the integer arithmetic and repeated input values require polynomial encoding length.
Thus the construction is a polynomial-time many-one reduction. It proves \(\mathrm{NP}\)-hardness with \(\tau=2\), fixed \(\alpha=2\), and explicitly established positive benchmarks.
The output correctly limits its conclusion: it does not establish hardness under the additional restriction \(0\le\alpha\le1\), nor does it claim \(\mathrm{NP}\)-completeness.
Benchmark enumeration. There are \(2^m\) subset utilities. Every benchmark-feasible distribution has finite nonempty support, so its minimum supported utility is a candidate value. The largest feasible candidate therefore equals the benchmark.
The feasibility predicate is monotone. Binary search requires \(O(m)\) calls per type, and zero is feasible by the stated independent-inclusion distribution.
Allocation linear program. After computing benchmarks, filtering pairs by their utility thresholds exactly implements the support restriction. The remaining equalities and nonnegativity constraints exactly implement allocation feasibility.
The allowed-bundle count is correct:
\[
|\mathcal C|=2^{m-1}+m.
\]
All subset utilities, thresholds, and linear-program coefficients have bit length polynomial in \(L\). The invoked polynomial-time rational linear-program feasibility theorem applies to these explicitly represented rational systems.
Enumeration, sorting, and all feasibility calls consequently fit within
\[
2^{O(m)}\operatorname{poly}(\tau,L).
\]
The fixed-\(m\) polynomial-time conclusion follows.
Exact optimization. The initial zero-threshold test, all-zero-benchmark case, and finite candidate-ratio search cover the stated infeasible, unbounded, and finite cases. The weak utility inequalities include the ratio endpoints themselves, so the finite candidate search correctly finds an attained optimum. Its running-time claim is valid.
The output resolves the assigned complexity question and supplies a valid exact exponential-time upper bound. No additional lemma, clarification, or 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.