Answer: —
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateEvery fair division instance with additive valuations admits a $1/2$-approximate groupwise maximin share allocation. Furthermore, such an allocation can be found in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), additive valuations \(v_t\), an integral bundle catalogue \(2^G\), and per-capita supplies \(b_g\), find masses \(x_{t,B}\geq 0\) satisfying \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=b_g\), such that for every subpopulation \(H\) with \(0\leq h_{t,B}\leq x_{t,B}\), every type \(t\) and bundle \(B\) with \(h_{t,B}>0\) satisfy \(v_t(B)\geq \frac12\MMS_t^\infty(H)\), where \(\MMS_t^\infty(H)\) is the maximum minimum \(v_t\)-value attainable by redistributing \(H\)'s pooled goods among its mass while each individual receives an integral bundle.
Let \(T\) be a finite set of types with rational masses \(\mu_t\) summing to \(1\), and let \(G\) be a finite set of goods. Each type has a nonnegative additive valuation \(v_t\); each individual receives an integral bundle \(B\subseteq G\). Rational \(b_g\) is the mass of individuals who must receive good \(g\).
An allocation consists of masses \(x_{t,B}\geq 0\) with \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=b_g\). A subpopulation has masses \(0\leq h_{t,B}\leq x_{t,B}\). Define \(\operatorname{MMS}^{\infty}_t(H)\) as the greatest \(q\) for which its pooled goods can be redistributed into integral bundles, preserving its total mass and each good’s mass, while every bundle assigned positive mass has \(v_t\)-value at least \(q\).
Is finding an allocation satisfying \(v_t(B)\geq \tfrac12\operatorname{MMS}^{\infty}_t(H)\) for every subpopulation \(H\) and every \((t,B)\) with \(h_{t,B}>0\) solvable in polynomial time in the binary input length, or is it NP-hard?
For finite agent lists, a \(\tfrac12\)-approximate groupwise maximin share allocation always exists and is computable in polynomial time. A later discrete result improves the polynomial-time guarantee to \((\sqrt5-1)/2\). Neither result addresses this exact mass model.
I do not settle the polynomial-time versus hardness question. The following results give a finite support characterization, polynomial-size witnesses, and an obstruction to directly transferring a familiar discrete argument.
1. Definitions and assumptions
For the complexity statements, assume that the item values \(v_t(g)\) are rational and binary encoded. Write \(m=|G|\) and \(n=|T|\). Assume \(\mu_t\geq 0\) and \(0\leq b_g\leq 1\); these conditions are necessary for feasibility.
For a nonzero subpopulation \(h\), put
\(M(h)=\sum_{t,B}h_{t,B}\), and \(c_g(h)=\sum_{t,B:g\in B}h_{t,B}\).
A redistribution is a nonnegative vector \(y=(y_C)_{C\subseteq G}\) satisfying
\(\displaystyle \sum_C y_C=M(h),\qquad \sum_{C:g\in C}y_C=c_g(h)\quad(g\in G).\)
Only bundles receiving positive mass enter its minimum value. Consequently, the benchmark is attained: every possible minimum belongs to the finite set \(\{v_t(C):C\subseteq G\}\), and at least one redistribution exists.
Scaling a subpopulation and its redistributions gives
\(\displaystyle \operatorname{MMS}^{\infty}_t(\lambda h)=\operatorname{MMS}^{\infty}_t(h)\qquad(\lambda>0).\)
Call an allocation *fair* if it satisfies the requested factor \(\tfrac12\) guarantee.
2. Proven: fairness depends only on support
Define \(\operatorname{supp}(x)=\{(t,B):x_{t,B}>0\}\).
Proposition. If \(x\) is fair and \(x'\) is feasible with \(\operatorname{supp}(x')\subseteq\operatorname{supp}(x)\), then \(x'\) is fair.
Proof. Suppose \(h'\leq x'\) violates fairness at \((t,B)\), so that
\(\displaystyle h'_{t,B}>0,\qquad \operatorname{MMS}^{\infty}_t(h')>2v_t(B).\)
All positive coordinates of \(h'\) correspond to positive coordinates of \(x\). Since there are finitely many coordinates, a sufficiently small \(\lambda>0\) satisfies \(\lambda h'\leq x\). Homogeneity then gives the same violation within \(x\), a contradiction. \(\square\)
In particular, two feasible allocations with identical supports are either both fair or both unfair.
Corollary. If a fair allocation exists, one exists with at most \(n+m\) positive coordinates and with polynomial-length rational masses.
Proof. Fix a fair allocation and restrict the allocation equations to its support. Their matrix has \(n+m\) rows and entries in \(\{0,1\}\): one row per type and one per good.
This restricted feasible polytope is nonempty and bounded, because all allocation masses sum to one. Choose a vertex \(z\). Its positive columns must be linearly independent. Otherwise, a nonzero dependence supported on the positive coordinates would allow sufficiently small perturbations in both directions, contradicting extremality. Hence \(z\) has at most \(n+m\) positive coordinates.
Its support is contained in the original fair support, so the proposition makes \(z\) fair.
For the bit bound, let \(r\leq n+m\) be its support size, and select an invertible \(r\times r\) submatrix determining its positive coordinates. Let \(D\) be the product of the input denominators of the masses. Its binary length is at most their total input length. Cramer’s rule and Hadamard’s determinant bound give numerators and denominators of bit length
\(\displaystyle O\bigl(\log D+r\log(r+1)\bigr).\)
Thus the resulting support list and masses have polynomial encoding length. \(\square\)
This rules out a possible representation obstruction: whenever a solution exists, exponentially many output bundles or exponentially long mass encodings are unnecessary.
3. Proven: violations have polynomial-size certificates
Fix a feasible allocation \(x\), its support \(S\), and a distinguished pair \(i=(t,B)\in S\). Define
\(\displaystyle \mathcal Q_i=\{C\subseteq G:v_t(C)>2v_t(B)\}.\)
Consider nonnegative variables \(a_j\) for \(j\in S\), and \(y_C\) for \(C\in\mathcal Q_i\), satisfying
\(\displaystyle \sum_{j\in S}a_j=\sum_{C\in\mathcal Q_i}y_C,\)
\(\displaystyle \sum_{j=(s,D)\in S:g\in D}a_j=\sum_{C\in\mathcal Q_i:g\in C}y_C\quad(g\in G),\)
and \(a_i=1\).
Proposition. Fairness fails at \(i\) if and only if this system is feasible.
Proof. A violating subpopulation and a redistribution attaining its benchmark use only bundles in \(\mathcal Q_i\). Divide all their masses by the positive distinguished mass to obtain the displayed system.
Conversely, suppose the system is feasible. Choose \(\lambda>0\) small enough that \(\lambda a_j\leq x_j\) for every positive \(a_j\). Then \(\lambda a\) is a subpopulation containing \(i\), and \(\lambda y\) is its redistribution. Every positive redistribution bundle has value strictly greater than \(2v_t(B)\). There are finitely many such bundles, so their minimum also strictly exceeds \(2v_t(B)\). This is a violation. \(\square\)
The system has \(m+2\) equations, coefficients in \(\{-1,0,1\}\), and a right-hand side with a single nonzero entry, equal to one.
If it is feasible, it has a feasible solution with linearly independent positive columns: starting from any feasible solution, a dependence among its positive columns permits a feasible movement until a positive coordinate becomes zero; repeat. Thus at most \(m+2\) variables need be positive.
Selecting a nonsingular square submatrix and applying Cramer’s rule shows that their rational values have bit length \(O((m+2)\log(m+2))\). Each selected bundle needs only \(m\) bits to describe.
Therefore a violation has a polynomial-size certificate consisting of the distinguished pair, the selected original and redistribution bundles, and their normalized masses. Its equations and strict valuation inequalities can all be checked in polynomial time.
Two consequences follow:
These are upper bounds, not hardness results or a polynomial-time construction.
4. Proven: a sufficient condition, and why it cannot always be imposed
The discrete EFL approach underlying the original finite-agent result motivates a useful sufficient condition. The finite-agent result is established by [Barman, Biswas, Krishnamurthy, and Narahari](https://arxiv.org/abs/1711.07621). The implication below is proved directly for the mass model.
Suppose that, for every two supported pairs \((t,B)\) and \((s,C)\), at least one of the following holds:
Proposition. Every allocation satisfying this condition is fair.
Proof. Fix a subpopulation \(h\) containing \((t,B)\), and put \(a=v_t(B)\). Let
\(\displaystyle L=\{g\in G:v_t(g)>2a\}.\)
Every original supported bundle containing a good in \(L\) has exactly one positively valued good. Indeed, its value exceeds \(2a\), so the first alternative must hold. Let \(s\) be the mass of such bundles within \(h\), and put \(r=M(h)-s\).
The distinguished bundle \(B\) contains no good in \(L\), since \(v_t(B)=a\). Hence \(r>0\).
Bundles containing \(L\) contribute no value from goods outside \(L\). Every remaining original bundle has value at most \(2a\): this follows either from the second alternative or from having at most one positive good, whose value is at most \(2a\). Thus the total pooled value from goods outside \(L\) is at most \(2ar\).
The total mass of goods in \(L\) is exactly \(s\). In any redistribution, the mass of individuals receiving at least one such good is therefore at most \(s\). At least \(r\) individuals receive only goods outside \(L\).
If every redistribution bundle had value at least some \(q>2a\), those individuals alone would require value at least \(qr>2ar\), a contradiction. Thus the benchmark is at most \(2a\). \(\square\)
However, this condition is not always achievable in the mass model.
Take one type and two goods with
\(\displaystyle v(g)=3,\qquad v(h)=1,\qquad b_g=\tfrac12,\qquad b_h=1.\)
Every individual must receive \(h\). Consequently, the unique allocation is
\(\displaystyle x_{\{h\}}=\tfrac12,\qquad x_{\{g,h\}}=\tfrac12.\)
It fails the sufficient condition: the second bundle contains two positive goods and has value \(4>2v(\{h\})\).
Nevertheless, it satisfies exact groupwise fairness. If a subpopulation contains positive mass of \(\{h\}\), its mass of \(g\) is smaller than its population mass. Every redistribution must give \(h\) to everyone, and some positive mass must remain without \(g\). Its benchmark is therefore exactly one. A subpopulation containing only \(\{g,h\}\) has benchmark four.
Thus even a universally present good can obstruct an EFL-style support requirement without obstructing the desired fairness guarantee.
5. Proven: exact existence for one type, but exact computation is hard
For one type, an allocation satisfying the stronger factor-one guarantee always exists.
Proof. Let \(a_1<\cdots<a_k\) be the distinct bundle values. For a feasible allocation \(x\), define
\(\displaystyle z_j(x)=\sum_{B:v(B)=a_j}x_B.\)
Lexicographically minimize \((z_1(x),\ldots,z_k(x))\), starting with the lowest value. A minimizer exists: minimize each coordinate successively over the compact feasible set left by the previous minimizations.
Suppose a subpopulation \(h\) containing \(B\) admits a redistribution \(y\) in which every positive bundle has value at least \(q>v(B)\). Let \(a_j\) be the smallest value of a bundle appearing positively in \(h\). Then \(a_j\leq v(B)<q\).
The allocation \(x'=x-h+y\) is feasible. Its coordinates \(z_\ell\) with \(\ell<j\) are unchanged, while \(z_j\) strictly decreases: positive mass at value \(a_j\) is removed and none is added. This contradicts lexicographic minimality. \(\square\)
This is an existence proof, not a polynomial-time algorithm. In fact, computing an exact fair allocation is already \(\mathrm{NP}\)-hard for one type under explicit support-list output.
To prove this, take a PARTITION instance with positive integers \(a_1,\ldots,a_m\) summing to \(2A\). Introduce one good per integer, with
\(\displaystyle v(g_j)=a_j,\qquad b_{g_j}=\tfrac12.\)
For the grand population, a redistribution attaining minimum value at least \(A\) exists if and only if the integers have an equal partition:
\(\sum_j b_{g_j}v(g_j)=A\).
If all positive bundles have value at least \(A\), they must all have value exactly \(A\). Any positive bundle yields a partition.
In a yes-instance, exact groupwise fairness forces every positive output bundle to have value at least \(A\), by applying the guarantee to the grand population. In a no-instance, no feasible allocation can have that property. Therefore a polynomial-time exact-fairness algorithm would decide PARTITION by inspecting its output.
The same reduction proves hardness of evaluating the exact grand-population benchmark. It does not prove hardness for the requested factor \(\tfrac12\).
6. Remaining question
The target classification remains unsettled by these arguments. The support characterization eliminates irrationality and output-size concerns, and provides small certificates of failure. What is still missing is either a polynomial-time method for constructing a fair support in the general heterogeneous instance or a hardness reduction for finding such a support at the specified approximation factor. General existence in this precise mass model is also not established here.
⟨structured verdict parsed — rendered above⟩
The output is correct partial progress, but it does not resolve the assigned complexity question. The support characterization, certificate bounds, sufficient condition, and exact-fairness hardness reduction withstand scrutiny. The principal missing result is precisely the requested classification for the factor \(\tfrac12\).
I found no false central step. There is one minor omission in the one-type existence argument: nonemptiness of the feasible allocation set is assumed rather than justified.
The redistribution equations correctly preserve population mass and each good’s mass. They impose no additional type constraints, consistently with the benchmark being evaluated entirely using the distinguished type’s valuation.
For a nonzero subpopulation, every redistribution has at least one positive coordinate. Its minimum assigned value therefore belongs to the finite set of bundle values. The existing subpopulation supplies a feasible redistribution after aggregating over types. Thus the set of attainable minimum values is finite and nonempty, and its maximum is attained.
The homogeneity assertion is correct: scaling by a positive number preserves feasible redistribution supports and their minimum values. Its use with normalized vectors that need not themselves lie beneath the original allocation is legitimate because the redistribution definition depends only on their masses.
The zero subpopulation causes no difficulty: it contains no distinguished pair of positive mass, so it imposes no fairness requirement.
Encoding scope: The complexity results are explicitly conditional on rational, binary-encoded item values. The task specifies rational population and good masses but does not explicitly specify valuation encoding. This assumption must accompany the reported complexity upper bounds; they are not claims about arbitrary real-valued input representations.
The downward-support proposition is correct.
A violation has a strictly positive distinguished coordinate and satisfies
\(\operatorname{MMS}^{\infty}_t(h')>2v_t(B)\).
Every positive coordinate of the violating subpopulation corresponds to a positive coordinate of the original allocation. Finiteness therefore permits a common positive scaling factor placing the whole subpopulation beneath that allocation. Homogeneity preserves the strict violation and the positive distinguished coordinate.
Both directions of the identical-support consequence follow by applying the proposition with the allocations interchanged.
No rationality assumption on the allocation masses is needed for this argument.
The corollary is correct, conditional on existence of a fair allocation.
The bit bound is also valid. A nonsingular square subsystem determines the positive coordinates. Clearing the input mass denominators and applying Cramer’s rule gives rational coordinates whose denominator and numerator lengths are bounded by the stated
\(O(\log D+r\log(r+1))\).
The right-hand-side masses lie between zero and one, as required for the stated numerator estimate.
Type identifiers and bundle incidence vectors also have polynomial encoding length. Thus the conclusion covers the entire output representation, not just its numerical coordinates.
This proves the absence of an output-size obstruction. It does not provide a method for finding the support.
The normalized feasibility system correctly characterizes failure at the distinguished pair.
In the forward direction, attainment of the benchmark justifies choosing a redistribution supported entirely on bundles whose values strictly exceed \(2v_t(B)\). Dividing by the positive distinguished mass makes \(a_i=1\).
In the reverse direction, a sufficiently small common scaling places the selected original masses beneath the allocation. The normalization ensures positive distinguished mass. Because the positive redistribution support is finite, strict inequalities for its individual bundle values imply a strictly larger minimum value, as required for a violation.
The sparsity argument is valid even though this polyhedron need not be bounded. A dependence supported on positive coordinates allows a movement toward a finite boundary in a suitable direction; at least one coordinate disappears, and the equality constraints remain satisfied. Repetition terminates because there are finitely many variables.
There are \(m+2\) equations. Hence an independent positive support has at most \(m+2\) variables. The coefficient and right-hand-side bounds justify the stated rational bit bound by a nonsingular subsystem and Cramer’s rule.
Verification must include checking that every selected original pair belongs to the given positive support. That is routine for an explicitly listed allocation and is consistent with the proposed certificate.
The resulting conclusions are correct:
The second conclusion correctly combines an existentially guessed feasible allocation of polynomial size with universal exclusion of polynomial-size violation certificates. Neither membership statement establishes polynomial-time solvability or hardness.
The proof is correct, including the case \(a=0\).
Relative to the fixed distinguished pair, a supported bundle containing a good valued above \(2a\) cannot satisfy the second alternative. It therefore has exactly one positively valued good. In particular, it contains exactly one good from \(L\), and its other goods contribute zero value.
This justifies both critical counting statements:
The distinguished bundle cannot contain a good from \(L\), by nonnegativity and additivity. Its positive participation implies \(r>0\).
In any redistribution, the mass receiving at least one good from \(L\) is at most the sum of those goods’ masses, hence at most \(s\). A mass of at least \(r\) consequently receives only goods outside \(L\). A minimum value \(q>2a\) would require more outside-\(L\) value than is available. This proves the claimed benchmark bound.
The cited paper supports the contextual attribution to the finite-agent GMMS literature. No theorem from that paper is used as an unverified premise of this mass-model proof. [Barman, Biswas, Krishnamurthy, and Narahari](https://arxiv.org/abs/1711.07621)
The example is correct.
The full mass of the second good forces it into every positive bundle. The first good’s mass then fixes the two listed bundle masses uniquely.
The sufficient condition fails because the larger bundle has two positive goods and value \(4>2\).
For any subpopulation containing positive mass of the smaller bundle, the first good’s mass is strictly below population mass. Some positive mass must therefore receive only the second good in every redistribution, while everyone receives that second good. The benchmark is exactly \(1\).
A subpopulation consisting only of the larger bundle has both goods at full population mass and benchmark \(4\).
This establishes the claimed obstruction to imposing this sufficient condition. It does not obstruct the requested fairness property.
The lexicographic argument is sound once the feasible set is known to be nonempty.
There are finitely many distinct bundle values. Successive minimization of continuous linear coordinates over nonempty compact minimizer sets produces a lexicographic minimizer.
In a purported violation, the smallest value represented positively in the subpopulation is below every value represented in its improving redistribution. Thus replacing the subpopulation preserves all earlier value-class masses and strictly reduces the first affected class. This contradicts lexicographic minimality.
Minor omission: The proof invokes a compact feasible set without establishing its nonemptiness for every permitted marginal vector. Boundedness and closedness alone do not establish this. The minimum clarification needed is a brief justification that the stated admissible good masses admit a feasible allocation. This is a routine feasibility point, not a defect in the lexicographic argument.
The reduction is correct for the stronger, factor-one search problem under explicit support-list output.
Every feasible allocation in the constructed instance has average value \(A\). An equal partition supplies the stated two-bundle redistribution. Conversely, if every positive bundle has value at least \(A\), the fixed average forces every positive bundle to have value exactly \(A\), supplying an equal partition.
On a yes-instance, the grand-population benchmark is \(A\), so exact fairness forces the output property inspected by the reduction. On a no-instance, no feasible output has that property.
The restriction to even-total PARTITION instances and the use of positive integers are standard and do not invalidate the reduction. Its weak numerical hardness still excludes a polynomial-time algorithm in binary input length unless \(\mathrm{P}=\mathrm{NP}\).
The same threshold equivalence supports the benchmark-evaluation hardness claim.
Crucially, no corresponding implication is established for a factor-\(\tfrac12\) output. The prover correctly acknowledges this limitation.
Major unresolved requirement: The assigned question remains unanswered. The output gives neither a polynomial-time construction nor a hardness reduction for finding a factor-\(\tfrac12\)-fair allocation in the heterogeneous mass model. It also does not establish general existence.
Further work must address that exact approximation factor and model. Merely strengthening the exact-fairness hardness discussion or restating the certificate upper bounds would not complete the assignment.
⟨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.