Answer: \(\mathrm{NP}\text{-hard}\), already for uniform positive rational masses.
Proposition 3 — class: hardness
Given a finite graph \(H=(T,F)\) and positive binary rational masses \(\mu_t\) summing to \(1\), compute the exact value and an optimal rate vector for \(\bar\alpha(H,\mu)=\min\{\max_{I\in\mathcal I(H)}\sum_{t\in I}\mu_t q_t:q_t\ge0,\ q_t+q_u\ge1\ \forall tu\in F\}\). Each type represents interchangeable players; a cross-type pair is a minimal winning coalition exactly when its types form an edge, and no within-type pair wins.
Input: a finite simple undirected graph \(H=(T,F)\) with \(F\ne\varnothing\), and a society given by its support: the list of \(\tau=|T|\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; put \(m=|F|\), and let \(L\) be the total binary input length.
Each type represents interchangeable players. A cross-type pair is a minimal winning coalition exactly when its types form an edge; no within-type pair wins. A coalition may contain any fraction of each type's mass and is losing exactly when its positive-mass support is independent in \(H\).
Let \(\mathcal I(H)\) denote all independent sets of \(H\). Rates are constant within types, with \(q\in\mathbb R_{\ge0}^{T}\); the winning-pair normalization is \(q_t+q_u\ge1\) for every \(tu\in F\), without a total-payoff constraint. Define
\(\bar\alpha(H,\mu)=\min\{\max_{I\in\mathcal I(H)}\sum_{t\in I}\mu_tq_t:q\in\mathbb R_{\ge0}^{T},\ q_t+q_u\ge1\text{ for every }tu\in F\}\).
Is computing the exact value \(\bar\alpha(H,\mu)\) and an optimal rate vector polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
For finite players, computing the analogous unweighted critical threshold is NP-hard on arbitrary graphs and polynomial-time solvable on bipartite graphs ([source](https://arxiv.org/html/1810.08841)).
No result addressing exactly the stated mass formulation was located in the literature search.
Computing the exact value \(\bar\alpha(H,\mu)\), and hence computing it together with an optimal rate vector, is \(\mathrm{NP}\)-hard. This already holds when all supported types have equal masses.
For a finite simple graph \(G=(V,E)\), define its unweighted critical threshold by
\(\alpha_G=\min\{\max_{I\in\mathcal I(G)}\sum_{v\in I}p_v:p\in\mathbb R_{\ge0}^{V},\ p_u+p_v\ge1\text{ for every }uv\in E\}\).
Proposition 2 of [Hof, Kern, Kurz, Pashkovich, and Paulusma](https://arxiv.org/html/1810.08841#S4) establishes that computing \(\alpha_G\) exactly is \(\mathrm{NP}\)-hard. The displayed formulation is the one used in their algorithmic results: there is no total-payoff constraint.
The hardness remains valid upon restricting to \(E\ne\varnothing\). Indeed, an edgeless graph has \(\alpha_G=0\), attained by \(p=0\). Consequently, an algorithm for all graphs with nonempty edge sets would extend to arbitrary graphs by checking whether the edge set is empty.
Take any such graph \(G=(V,E)\), put \(n=|V|\), and construct the mass instance
\(H=G\), \(T=V\), and \(\mu_v=1/n\) for every \(v\in V\).
Every mass is positive and \(\sum_{v\in V}\mu_v=1\). The feasible rate vectors in this instance are exactly the feasible vectors in the definition of \(\alpha_G\), because both require nonnegativity and the inequalities \(q_u+q_v\ge1\) on edges.
For every feasible \(q\), positivity of \(1/n\) gives
\(\max_{I\in\mathcal I(G)}\sum_{v\in I}\mu_vq_v=\frac1n\max_{I\in\mathcal I(G)}\sum_{v\in I}q_v\).
Minimizing over their common feasible set therefore yields the exact identity
\(\bar\alpha(G,\mu)=\alpha_G/n\).
Thus one exact evaluation of the mass problem recovers the unweighted value by
\(\alpha_G=n\bar\alpha(G,\mu)\).
The sets of optimal vectors also coincide, since multiplying an objective by a positive constant preserves its minimizers.
Each rational mass \(1/n\) has binary encoding length \(O(\log n)\). The construction preserves the graph and adds \(O(n\log n)\) bits, so its output length is polynomial in the original graph input length. It has \(\tau=n\) and \(m=|E|\).
Accordingly, an algorithm polynomial in \(m,\tau,L\) that returned the exact value and an optimal vector would compute \(\alpha_G\) in polynomial time. The cited hardness theorem excludes such an algorithm unless \(\mathrm P=\mathrm{NP}\).
This proves hardness of the requested joint computation through hardness of its value component.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the assigned task: exact value computation is \(\mathrm{NP}\)-hard, already for uniform positive rational masses. Consequently, computing the value together with an optimal rate vector is also \(\mathrm{NP}\)-hard. No major or minor mathematical issues were found.
Proposition 2 states that computing \(\alpha_G\) for arbitrary graphs is \(\mathrm{NP}\)-hard. The feasible-payoff definition and equation (2) in the same section use nonnegative coordinates, edge inequalities with right-hand side one, and an objective bounding every independent-set payoff. There is no total-payoff constraint. Thus the prover states the applicable theorem accurately and uses the correct optimization formulation. [Hof et al., Section 4](https://arxiv.org/html/1810.08841#S4)
For an edgeless graph, the zero vector is feasible and has objective value zero. Nonnegativity prevents any smaller value. Therefore the prover’s proposed check for an empty edge set correctly extends an algorithm on graphs with nonempty edge sets to all graphs. The restriction preserves hardness.
On every instance subsequently reduced, the nonempty edge set also guarantees \(|V|\geq 2\), so the denominator used in the masses is nonzero.
Setting \(H=G\), \(T=V\), and \(\mu_v=1/n\) preserves simplicity, undirectedness, and the nonempty edge set. Every listed type has positive rational mass, and the masses sum to one. The support size is exactly \(\tau=n\), including any isolated vertices.
Both problems impose precisely the same nonnegativity and edge constraints. Identifying the coordinates of \(p\) and \(q\) therefore identifies their entire feasible sets.
For each feasible vector, every independent-set payoff in the mass instance is its unweighted payoff multiplied by the same positive constant \(1/n\). Taking the maximum preserves this scaling. Taking the minimum over the common feasible set then gives
\(\bar\alpha(G,\mu)=\alpha_G/n\).
This establishes exact equality of values, rather than merely a bound. The claim that the sets of minimizers coincide also follows directly from this positive scaling.
Each mass has numerator one and denominator \(n\), requiring \(O(\log n)\) bits. Listing all masses adds \(O(n\log n)\) bits. Under the explicit graph representation used by the source problem, this is a polynomial-size, polynomial-time construction.
Multiplication of the returned exact rational value by the integer \(n\) recovers \(\alpha_G\), with polynomial overhead in the encoded output length. The reduction therefore respects the binary input model and the requested parameters \(m,\tau,L\).
A polynomial-time algorithm returning the requested value and optimal vector would, in particular, return the value needed by the reduction. Thus hardness of the value component establishes hardness of the joint computation.
The prover does not claim that returning an optimal vector alone is hard, or that the problem is \(\mathrm{NP}\)-complete; neither stronger claim is needed.
Actionable feedback: No additional mathematical 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.