Answer: \(\mathrm{NP}\text{-hard}\)
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen n = 2, an allocation satisfying EF and SO always exists, but computing such an allocation is NP-HARD. Moreover, an allocation satisfying EF and TS always exists and can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), positive rational type masses \(\mu_t\) summing to \(1\), and rational type-pair interaction masses \(q_{tu}\), choose fractions \(p_t\in[0,1]\) of each type for Team 1, with \(0<\sum_t\mu_t p_t<1\), to maximize \(K(p)=\sum_{t<u}q_{tu}\bigl(p_t(1-p_u)+(1-p_t)p_u\bigr)+\sum_t q_{tt}p_t(1-p_t)\). What is the complexity of computing a maximizing split, which gives an EF+SO two-team allocation?
A society is given by its support: an ordered list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; each type consists of divisible, atomless mass.
For each unordered type pair, including equal types, the input specifies a nonnegative binary-rational interaction coefficient \(q_{tu}\). Interactions are homogeneous within each type pair. For distinct types, \(q_{tu}\) is their total interaction mass; \(q_{tt}\) is twice the total unordered interaction mass within type \(t\). These coefficients need not sum to \(1\). Require \(q_{tt}+\sum_{u\ne t}q_{\min(t,u),\max(t,u)}>0\) for every type.
A complete two-team allocation chooses real fractions \(p_t\in[0,1]\), assigning fraction \(p_t\) of type \(t\) to Team 1 and the remainder to Team 2, with \(0<\sum_t\mu_t p_t<1\).
Both teams have the identical cut valuation, so each team's utility is
\(K(p)=\sum_{t<u}q_{tu}\bigl(p_t(1-p_u)+(1-p_t)p_u\bigr)+\sum_tq_{tt}p_t(1-p_t)\).
Every feasible allocation is envy-free (EF); social optimality (SO) means maximizing total utility \(2K(p)\). Any maximizing split is acceptable.
Measure running time in \(\tau\) and total binary input length \(L\); the number of teams is fixed at two, and there is no finite item-count parameter \(m\).
Is computing an exact maximizing split for this continuous two-team cut problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite simple graphs, computing a two-agent EF+SO allocation is NP-hard, whereas an EF allocation satisfying transfer stability can be computed in polynomial time. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/38754/42716)
No result settling this exact continuous problem was identified in the literature search.
Computing an exact maximizing split is \(\mathrm{NP}\)-hard, already when every within-type coefficient is zero and every other coefficient belongs to \(\{0,1\}\). Divisibility does not increase the optimal value on these instances.
The proof below reduces unweighted Simple Max-Cut to the stated continuous problem and handles the possibility that the algorithm returns a fractional maximizer.
Because all masses are positive and sum to \(1\), the condition
\(0<\sum_t\mu_t p_t<1\) excludes exactly the two vectors \(\mathbf 0\) and \(\mathbf 1\) from the cube \([0,1]^\tau\).
The polynomial \(K\) is continuous, so it attains a maximum on this compact cube. Moreover,
\[ K(\mathbf 0)=K(\mathbf 1)=0, \qquad K\!\left(\tfrac12\mathbf 1\right) =\tfrac12\sum_{t<u}q_{tu}+\tfrac14\sum_tq_{tt}>0. \]
The strict inequality follows from nonnegativity and the required positive interaction incidence at every type. Consequently, every cube maximizer is feasible. Maximizing \(2K\) is equivalent to maximizing \(K\).
We use the established theorem that Simple Max-Cut is \(\mathrm{NP}\)-complete: given a finite simple graph and an integer threshold, decide whether some cut contains at least that many edges. See [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://www.sciencedirect.com/science/article/pii/0304397576900591).
We may restrict to graphs with at least one edge and no isolated vertices. Indeed, deleting isolated vertices preserves every achievable cut size, while edgeless instances are decidable immediately. Thus a polynomial algorithm for the restricted problem would solve the unrestricted problem.
Let \(G=(V,E)\) be such a graph, with ordered vertices \(V=\{1,\ldots,n\}\). Construct a society with \(\tau=n\), one type per vertex. Set
\[ q_{tt}=0, \qquad q_{tu}= \begin{cases} 1,&\{t,u\}\in E,\\ 0,&\{t,u\}\notin E \end{cases} \quad(t<u). \]
Choose \(h=\lceil\log_2 n\rceil\), and set
\[ \mu_t=2^{-h}\quad(1\le t<n), \qquad \mu_n=1-(n-1)2^{-h}. \]
These masses are positive dyadic rationals summing to \(1\): since \(n\le 2^h\), the last mass is at least \(2^{-h}\). Each mass has binary encoding length \(O(\log n)\).
Every type has positive interaction incidence because its corresponding vertex has positive degree. Thus all input requirements hold. The entire construction has polynomial binary length, with \(\tau=n\); no individual-item parameter is introduced.
Its objective is
\[ K_G(p)=\sum_{\{t,u\}\in E} \bigl(p_t(1-p_u)+(1-p_t)p_u\bigr). \]
For a binary vector \(x\in\{0,1\}^n\), define its cut size by
\[ c_G(x)=\bigl|\{\{t,u\}\in E:x_t\ne x_u\}\bigr|, \qquad M(G)=\max_{x\in\{0,1\}^n}c_G(x). \]
Fix any \(p\in[0,1]^n\). Let \(X_1,\ldots,X_n\) be independent Bernoulli random variables satisfying \(\Pr(X_t=1)=p_t\). Independence gives, for each edge,
\[ \Pr(X_t\ne X_u) =p_t(1-p_u)+(1-p_t)p_u. \]
By linearity of expectation,
\[ K_G(p)=\mathbb E[c_G(X)]\le M(G), \]
because every realization of \(X\) defines a graph cut whose size is at most \(M(G)\).
Conversely, if \(x\) describes a maximum cut, substituting its binary coordinates into the objective gives \(K_G(x)=M(G)\). Since \(G\) has an edge, \(M(G)\ge1\). Hence this cut has vertices on both sides and, because every type mass is positive, its allocation is feasible.
Therefore,
\[ \max_{\substack{p\in[0,1]^n\\0<\sum_t\mu_t p_t<1}}K_G(p)=M(G). \]
This establishes equality of the continuous and discrete optimal values.
To prove hardness of computing a split, we must also handle algorithms that return fractional maximizers.
Let \(p^\star\) be any exact maximizer. Define
\[ x_t= \begin{cases} 1,&p^\star_t\ge\tfrac12,\\ 0,&p^\star_t<\tfrac12. \end{cases} \]
Apply the independent Bernoulli construction to \(p^\star\). The probability of the particular outcome \(x\) is
\[ r=\Pr(X=x) =\prod_{t:x_t=1}p^\star_t \prod_{t:x_t=0}(1-p^\star_t) \ge 2^{-n}>0. \]
Suppose that \(c_G(x)<M(G)\). Every other outcome still has cut size at most \(M(G)\), so
\[ K_G(p^\star) =\mathbb E[c_G(X)] \le r\,c_G(x)+(1-r)M(G) <M(G). \]
This contradicts optimality and the equality proved above. Consequently, \(c_G(x)=M(G)\).
Under the usual binary encoding of exact rational coordinates, this rounding requires only \(n\) comparisons with \(\tfrac12\), and therefore takes polynomial time. The constructed instances always have binary, and hence rational, optimal outputs.
Thus a polynomial-time algorithm returning any exact maximizing split would yield a polynomial-time algorithm for Simple Max-Cut: construct the society, compute the split, round it as above, and count the cut edges.
The exact continuous two-team cut problem is \(\mathrm{NP}\)-hard. Since every feasible allocation is EF by the premises, the same conclusion applies to computing an exact EF+SO allocation. A polynomial-time exact algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the task: computing an exact maximizing split is \(\mathrm{NP}\)-hard under the explicitly stated, conventional binary encoding of rational outputs. The reduction is valid, and the argument extracting a maximum cut from any returned fractional maximizer is correct. No major or minor mathematical issues were found.
Since every \(\mu_t>0\) and their sum is \(1\), the weighted sum \(\sum_t\mu_t p_t\) equals \(0\) only at \(\mathbf 0\), and equals \(1\) only at \(\mathbf 1\). Thus the feasibility condition excludes exactly those two cube points.
Continuity guarantees a cube maximizer. The displayed midpoint calculation is correct: each distinct-type term contributes \(q_{tu}/2\), and each within-type term contributes \(q_{tt}/4\). The incidence requirement ensures at least one positive coefficient, so this value is strictly positive. Both excluded points have value zero; consequently, every cube maximizer is feasible.
Maximizing \(2K\) and maximizing \(K\) are equivalent. This step has no gap.
The prover states the required decision theorem precisely: given a finite simple unweighted graph and an integer threshold, deciding whether a cut meets that threshold is \(\mathrm{NP}\)-complete. The cited paper explicitly establishes completeness of Simple Max-Cut with unit edge weights. [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
Removing isolated vertices preserves achievable cut sizes: restriction preserves a cut’s size, and removed vertices can be assigned arbitrarily when extending a cut. Edgeless instances are immediately decidable by comparing the threshold with zero. Hence an algorithm for graphs with at least one edge and no isolated vertices would solve the unrestricted decision problem.
The restriction is justified.
The graph restriction implies \(n\ge2\), so the mass construction has no undefined small-instance case.
For \(h=\lceil\log_2 n\rceil\), all first \(n-1\) masses are positive. Also,
\[
\mu_n=\frac{2^h-n+1}{2^h}\ge 2^{-h}>0.
\]
Their sum is exactly \(1\). Numerators and denominators have \(O(\log n)\) bits, as claimed.
All coefficients are nonnegative binary rationals. Because each graph vertex has positive degree, every type satisfies the positive-incidence requirement. The explicit pair table has \(O(n^2)\) entries, and the masses use \(O(n\log n)\) bits. Thus the construction is polynomial in the graph input size.
Setting all diagonal coefficients to zero produces exactly the displayed graph objective. There is no missing factor arising from the convention for within-type interactions.
For distinct vertices, independence gives exactly
\[
\Pr(X_t\ne X_u)=p_t(1-p_u)+(1-p_t)p_u.
\]
Summing edge indicators therefore yields \(K_G(p)=\mathbb E[c_G(X)]\). Every outcome is a binary cut with size at most \(M(G)\), so \(K_G(p)\le M(G)\) for every cube point.
Conversely, substitution of a maximum-cut vector gives \(K_G(x)=M(G)\). Since the graph has an edge, \(M(G)\ge1\); such a cut has vertices on both sides. Positive type masses then ensure that its allocation is feasible.
Both directions of the asserted equality are established. Divisibility cannot improve the optimal value on these instances.
The rounding rule handles equality at \(1/2\) explicitly. Every selected coordinate outcome has probability at least \(1/2\), including coordinates at the endpoints \(0\) and \(1\). Independence therefore gives the stated bound \(r\ge2^{-n}>0\).
If the selected cut were suboptimal, its positive probability together with the upper bound \(M(G)\) on all other outcomes would imply
\[
\mathbb E[c_G(X)]
\le r\,c_G(x)+(1-r)M(G)<M(G).
\]
This contradicts the established value of an exact maximizer.
Thus the rounding recovers a maximum cut from every maximizing split. The proof does not rely on the optimizer choosing a binary solution.
The prover explicitly assumes the usual binary encoding of exact rational coordinates. In that model, comparison with \(1/2\) takes polynomial time in the coordinate’s encoding length. A polynomial-time algorithm can output only polynomially many bits, so the entire rounding procedure is polynomial in the original input length.
The assertion that the constructed instances have binary optimal outputs establishes the existence of succinct exact solutions; it need not assert that every optimizer is rational. The preceding extraction argument already covers every rational maximizer that an algorithm might return.
The task leaves exact-real output representation unspecified. The prover’s explicitly stated conventional representation is a natural interpretation, and no further representation assumption is needed for the claimed hardness in that model.
Construction, exact optimization, rounding, and edge counting would decide Simple Max-Cut in polynomial time. This establishes the claimed optimization hardness.
Because EF is automatic under the task’s premises, an exact social optimizer is also an exact EF+SO allocation. That concluding implication is valid.
The proof establishes hardness, not membership in \(\mathrm{NP}\) or \(\mathrm{NP}\)-completeness of a general continuous decision formulation; it makes neither additional claim. No repair or missing lemma 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.