Answer: Polynomial-time solvable: every valid instance is feasible.
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists an algorithm which in polyno- mial time outputs an allocation that gives 1 2-MMS to each agent. Remark 4.2. The values µi defined in Equation 7 are upper bounds on APS also. From Claim 2.3, single good reduction also holds for APS with symmetric agents.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite valuation types \(\Theta\) with rational masses \(\mu_\theta\), rational per-capita supplies \(\sigma_j\), and a compact encoding of SPLC marginal schedules, define \(\mathrm{MMS}^\infty_\theta(\sigma)\) as the supremum \(z\) for which a finite-support distribution over integral bundles \(B\) has expected bundle vector \(\sigma\) and \(v_\theta(B) \ge z\) almost surely. Decide whether finite-support masses \(y_{\theta B}\) exist with \(\sum_B y_{\theta B}=\mu_\theta\), \(\sum_{\theta,B} y_{\theta B} B_j=\sigma_j\), and \(y_{\theta B}>0\) only when \(v_\theta(B) \ge \mathrm{MMS}^\infty_\theta(\sigma)/2\); equivalently, maximize the guaranteed MMS factor.
A society is given by its support: a list \(\Theta\) of \(\tau\geq1\) valuation types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types; masses represent equally entitled individuals.
There are \(m\geq1\) good categories with nonnegative binary-rational per-capita supplies \(\sigma_j\). An integral bundle is \(B\in\mathbb Z_{\geq0}^m\), including the empty bundle, without an individual upper bound on its coordinates.
Each type has normalized SPLC valuation \(v_\theta(B)=\sum_{j=1}^m\sum_{k=1}^{B_j}a_{\theta jk}\). Marginals are nonnegative, nonincreasing binary rationals, encoded by finitely many constant runs with binary-integer lengths and a final infinite constant run. Let \(L\) be the total input bit length.
Define \(\operatorname{MMS}^{\infty}_\theta(\sigma)=\sup\{z\geq0:\exists\text{ finitely supported probability distribution }p\text{ on integral bundles},\ \sum_Bp_BB=\sigma,\ p_B>0\Rightarrow v_\theta(B)\geq z\}\).
A feasible half-share allocation consists of nonnegative masses \(y_{\theta B}\), with finite support, satisfying \(\sum_By_{\theta B}=\mu_\theta\), \(\sum_{\theta,B}y_{\theta B}B_j=\sigma_j\) for every category, and \(y_{\theta B}>0\Rightarrow v_\theta(B)\geq\operatorname{MMS}^{\infty}_\theta(\sigma)/2\).
Is deciding feasibility of a half-share allocation polynomial-time in \(m,\tau,L\), or is it NP-hard?
For finite societies with equally entitled agents and SPLC valuations, a half-MMS allocation always exists and can be computed in polynomial time; the guarantee also holds for symmetric APS ([Chekuri et al.](https://arxiv.org/html/2312.08504)). No result settling this precise distribution-over-types formulation was located in the search.
Every valid instance admits a feasible half-share allocation. Consequently, deciding feasibility is polynomial-time: on the specified input domain, the answer is always YES.
The proof transfers the finite-agent existence theorem exactly, by showing that the benchmarks have rational finite-support witnesses and then clearing denominators.
Fix a type \(\theta\), and write \(M_\theta=\operatorname{MMS}^{\infty}_\theta(\sigma)\).
There exists a finitely supported distribution on integral bundles with expectation \(\sigma\): independently round each coordinate \(\sigma_j\) to its floor or ceiling, with probabilities giving expectation \(\sigma_j\). Thus the set of distributions in the benchmark definition is nonempty.
Because the encoding contains only finitely many distinct rational marginal values, there is a positive integer \(D_\theta\) such that every marginal is an integer multiple of \(1/D_\theta\). Hence every integral-bundle value belongs to \((1/D_\theta)\mathbb Z_{\geq0}\).
Nonincreasing marginals imply, for every bundle \(B\),
\[ v_\theta(B)\leq\sum_{j=1}^{m}a_{\theta j1}B_j. \]
Therefore, for any finitely supported distribution \(p\) with expectation \(\sigma\),
\[ \min_{B:p_B>0}v_\theta(B) \leq \sum_Bp_Bv_\theta(B) \leq U_\theta, \qquad U_\theta:=\sum_{j=1}^{m}a_{\theta j1}\sigma_j<\infty. \]
Consider the set of all support minima attained by such distributions:
\[ S_\theta:= \left\{ \min_{B:p_B>0}v_\theta(B): p\text{ has finite support and }\sum_Bp_BB=\sigma \right\}. \]
This set is nonempty and lies in the finite set
\((1/D_\theta)\mathbb Z_{\geq0}\cap[0,U_\theta]\).
It consequently has an attained maximum.
For any fixed distribution, the admissible thresholds are precisely those between zero and its support minimum. Thus
\[ M_\theta=\max S_\theta. \]
In particular, some finitely supported distribution witnesses the threshold \(M_\theta\) itself.
Let \(F_\theta\) be the finite support of an attaining distribution. Consider the system
\[ \sum_{B\in F_\theta}q_B=1, \qquad \sum_{B\in F_\theta}q_BB=\sigma, \qquad q_B\geq0. \]
It is feasible. Choose a feasible solution \(q\) with the smallest possible number of positive coordinates, and denote its positive support by \(G_\theta\).
The integer columns \((1,B)\), for \(B\in G_\theta\), are linearly independent. Indeed, a dependence would give nonzero real coefficients \(d_B\) satisfying
\[ \sum_{B\in G_\theta}d_B=0, \qquad \sum_{B\in G_\theta}d_BB=0. \]
The coefficients have both signs. Setting
\[ t=\min_{B:d_B>0}\frac{q_B}{d_B}, \qquad q'_B=q_B-td_B \]
preserves all equalities and nonnegativity, while eliminating at least one positive coordinate. This contradicts minimality.
There are therefore at most \(m+1\) positive coordinates. Moreover, selecting a nonsingular square row submatrix of these independent integer columns expresses their probabilities as the solution of an invertible rational linear system. All probabilities are consequently rational.
Every retained bundle belongs to \(F_\theta\), so its value remains at least \(M_\theta\). We have proved that each type has a rational finite-support witness \(q^\theta\) satisfying
\[ \sum_Bq^\theta_B=1, \qquad \sum_Bq^\theta_BB=\sigma, \qquad q^\theta_B>0\Longrightarrow v_\theta(B)\geq M_\theta. \]
Choose a positive integer \(N\) divisible by the denominators of all masses \(\mu_\theta\), supplies \(\sigma_j\), and positive witness probabilities \(q^\theta_B\). This is possible because there are finitely many such rational numbers.
Construct a finite society with:
All these counts are nonnegative integers, and the agent counts sum to \(N\).
For each type \(\theta\), take \(Nq^\theta_B\) copies of bundle \(B\). They form exactly \(N\) bundles and use exactly the available inventory, because
\[ \sum_BNq^\theta_B=N, \qquad \sum_BNq^\theta_BB_j=K_j. \]
Thus they define a partition of the finite inventory into \(N\) bundles, all valued at least \(M_\theta\) by type \(\theta\). The finite-agent MMS of that type is therefore at least \(M_\theta\).
Conversely, any partition of this inventory into \(N\) bundles induces a finitely supported distribution by selecting a part uniformly. Its expected bundle is \(K/N=\sigma\). Its minimum value cannot exceed \(M_\theta\), by the benchmark definition.
Consequently, in this finite society,
\[ \operatorname{MMS}^{N}_\theta(K)=M_\theta \]
for every type \(\theta\).
Each of these partitions is a separate benchmark witness; they need not be mutually compatible.
The finite-agent theorem of Chekuri et al. states that every finite instance with equally entitled agents and nonnegative SPLC valuations admits an integral allocation giving each agent at least half her MMS. [Theorem 4.1](https://arxiv.org/html/2312.08504)
Its hypotheses hold here: the agents have equal entitlement, the inventory is finite, and restricting each input valuation to the available copies preserves nonnegative, nonincreasing marginals and separability. If the inventory is empty, all benchmarks are zero and assigning the empty bundle to everyone already suffices.
Apply the theorem to obtain bundles \(A_1,\ldots,A_N\), with agent \(i\) of type \(\theta(i)\) satisfying
\[ v_{\theta(i)}(A_i)\geq \frac{\operatorname{MMS}^{N}_{\theta(i)}(K)}{2} =\frac{M_{\theta(i)}}{2}. \]
The bundles partition the inventory. If the theorem is formulated with unallocated leftovers, assign those leftovers arbitrarily; nonnegative marginals preserve the guarantees.
Define
\[ y_{\theta B}:= \frac{\left|\{i:\theta(i)=\theta,\ A_i=B\}\right|}{N}. \]
This allocation has finite support and satisfies
\[ \sum_By_{\theta B}=\frac{N\mu_\theta}{N}=\mu_\theta, \]
and, for every category \(j\),
\[ \sum_{\theta,B}y_{\theta B}B_j =\frac{K_j}{N} =\sigma_j. \]
Whenever \(y_{\theta B}>0\), the finite-agent guarantee gives
\(v_\theta(B)\geq M_\theta/2\).
These are exactly the required half-share allocation conditions.
The proof establishes feasibility for all valid inputs, including binary-encoded masses, supplies, and run lengths. Therefore the decision algorithm simply returns YES; input validation, if required, takes polynomial time.
The denominator-clearing construction may produce a very large finite society. It proves existence but does not establish polynomial-time construction of an allocation in the compressed input size. That distinction does not affect the requested feasibility decision.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes that every valid instance admits a feasible half-share allocation, so feasibility decision is polynomial-time. No major or minor mathematical issues were found. The proof does not establish polynomial-time construction in the compressed representation, and it correctly acknowledges that limitation.
Coordinatewise randomized rounding produces a distribution supported on at most \(2^m\) integral bundles with expectation \(\sigma\). Integer and zero coordinates cause no difficulty: their rounding is deterministic. Thus the family of admissible distributions is nonempty.
The finite run encoding, including the final constant run, supplies only finitely many rational marginal values. A common denominator \(D_\theta\) therefore exists, and every integral-bundle value is a nonnegative integer multiple of \(1/D_\theta\). This remains valid for arbitrarily large bundles because each bundle contains only finitely many units.
Nonincreasing marginals give the stated pointwise bound
\(v_\theta(B)\leq\sum_j a_{\theta j1}B_j\).
Taking expectations and comparing the support minimum with the average yields the finite upper bound \(U_\theta\).
Consequently, the set \(S_\theta\) of attained support minima is nonempty and contained in a finite lattice interval. Its maximum exists and, by the definition of \(S_\theta\), is witnessed by a finite-support distribution. The identification \(M_\theta=\max S_\theta\) follows from the threshold definition. No compactness assumption or limiting distribution is needed.
The probability system on the fixed finite support \(F_\theta\) is feasible. A solution minimizing the number of positive coordinates exists because the possible support sizes form a nonempty finite set of integers.
The linear-dependence argument is valid. A nonzero dependence among the columns \((1,B)\) has coefficients summing to zero, so it has both positive and negative coefficients. The specified positive value of \(t\) preserves nonnegativity, keeps both equality constraints, and eliminates at least one positive coordinate without introducing coordinates outside the previous support. This contradicts minimality.
The resulting columns are independent, so there are at most \(m+1\) of them. Selecting an invertible square row submatrix is justified by full column rank. Its coefficients are integers and its right-hand side is rational; hence its unique solution, consisting of the retained probabilities, is rational.
Restricting to bundles in \(F_\theta\) preserves the value threshold. Thus the claimed rational finite-support witnesses are established for every type.
There are finitely many masses, supplies, and witness probabilities, all rational. A common positive denominator multiple \(N\) therefore exists.
The counts \(N\mu_\theta\), \(N\sigma_j\), and \(Nq^\theta_B\) are integers. The agent counts sum to \(N\), and each positive type mass gives a positive agent count.
For each fixed type, the repeated witness bundles number exactly \(N\) and consume exactly the inventory \(K=N\sigma\). Thus they constitute a finite MMS partition witness. In particular, no bundle demands more copies of a category than the inventory contains: the bundle counts are nonnegative and their total demand is exactly \(K_j\).
Conversely, uniformly sampling one of the \(N\) parts of any inventory partition gives an admissible finite-support distribution with expectation \(\sigma\). Its minimum value is therefore at most \(M_\theta\).
These two directions establish the stated exact equality
\(\operatorname{MMS}^{N}_\theta(K)=M_\theta\).
The partitions may differ between types, as the prover explicitly notes; simultaneous compatibility is not required for benchmark witnesses.
The cited Theorem 4.1 guarantees an allocation giving every agent at least half her finite MMS for a symmetric finite SPLC instance. The paper’s model allows empty parts and defines SPLC valuations by nonincreasing marginal values within categories and additivity across categories. These are the hypotheses used here. [Chekuri et al., Sections 2.1–2.2 and Theorem 4.1](https://arxiv.org/html/2312.08504)
The constructed society has equal individual entitlements and finite inventory. Restricting the original valuations to that inventory preserves normalization, nonnegativity, monotonicity, separability, and decreasing marginals. The theorem therefore applies.
The completely empty inventory is explicitly handled. Zero-supply categories do not affect the finite valuation model. Assigning any leftovers preserves all guarantees because the marginals are nonnegative.
Each \(y_{\theta B}\) is a nonnegative integer count divided by \(N\), and only finitely many bundles occur.
Summing these counts within a type gives exactly \(\mu_\theta\). Summing category quantities across agents gives exactly \(\sigma_j\), since the finite allocation exhausts the inventory.
Whenever \(y_{\theta B}>0\), at least one agent of that type received \(B\). The finite-agent guarantee and the established benchmark equality yield
\(v_\theta(B)\geq M_\theta/2\).
This verifies every condition in the requested allocation definition.
The proof covers every valid input under the specified rational encoding. Therefore returning YES decides feasibility on that input domain without computing the benchmarks, their witnesses, or the expanded society.
The potentially large value of \(N\) does not undermine this decision conclusion. The prover correctly distinguishes its existence argument from a polynomial-time allocation-construction algorithm in \(m,\tau,L\).
Repair feedback: None required. The argument resolves the assigned feasibility decision question as written.
⟨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.