Answer: Polynomial-time solvable; every instance is feasible.
Theorem 14 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor given $N$, let $n = \lceil \frac{N + 4}{2} \rceil$. Then for every $N \ge 4$, there is an allocation instance with $N$ agents and at most $N + 4n - 7$ items (which gives $3N+1$ when $N$ is even and $3N + 3$ when $N$ is odd) for which in every allocation, at least one of the agents does not get more than a $1 - \frac{1}{f(n)}$ fraction of her MMS. Here, the function $f(n)$ has value $f(n) = n^2(n-2)^2 +n$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For each \(N\ge4\), let \(n=\lceil(N+4)/2\rceil\) and use the Theorem 14 valuation types \(R,C\), masses \(\mu_R=\lfloor N/2\rfloor/N\) and \(\mu_C=1-\mu_R\), and per-capita supply \(\rho_g=1/N\) for every item class; decide whether masses \(x_{\theta,B}\) can be assigned to integral bundles \(B\) with \(\sum_Bx_{\theta,B}=\mu_\theta\), \(\sum_{\theta,B:g\in B}x_{\theta,B}=\rho_g\), and \(v_\theta(B)\ge W_\theta\) whenever \(x_{\theta,B}>0\), where \(W_\theta\) is the type's continuum MMS threshold.
For \(N\ge4\), set \(n=\lceil(N+4)/2\rceil\) and \(t=n^2(n-2)^2+n\). There are two additive types \(R,C\), of masses \(\mu_R=\lfloor N/2\rfloor/N\) and \(\mu_C=1-\mu_R\), and every item class has supply \(1/N\).
The core classes are the seven indicated groups of positions \(g_{ij}\), for \(2\le j\le n-1\), with base values \(b_{1j}=n(n-2)\), \(b_{1n}=1\), \(b_{j1}=(n-2)(n-1)\), \(b_{jj}=(n-2)(n^2-4n+2)\), \(b_{jn}=(n-2)(n-1)+1\), \(b_{n1}=b_{nj}=(n-2)^2+1\), and \(b_{nn}=(n-2)(n-3)\). Add \(N-n\) auxiliary classes, each valued \(t\) by both types.
For a core class \(g\), let \(v_R(g)=nb_g-\mathbf 1[g=g_{nj}\text{ for some }j<n]+(n-1)\mathbf 1[g=g_{nn}]\), and let \(v_C(g)=nb_g-\mathbf 1[g=g_{jn}\text{ for some }j<n]+(n-1)\mathbf 1[g=g_{nn}]\). An integral bundle is a subset of the item classes.
For \(\theta\in\{R,C\}\), define \(W_\theta\) as the largest \(w\) for which supplies can be assigned as masses \(y_B\ge0\) of integral bundles with \(\sum_B y_B=1\), \(\sum_{B\ni g}y_B=1/N\) for every class \(g\), and \(v_\theta(B)\ge w\) whenever \(y_B>0\).
The decision problem asks whether there are masses \(x_{\theta,B}\ge0\) with \(\sum_Bx_{\theta,B}=\mu_\theta\), \(\sum_{\theta,B\ni g}x_{\theta,B}=1/N\), and \(v_\theta(B)\ge W_\theta\) whenever \(x_{\theta,B}>0\).
Is this continuous MMS-feasibility problem solvable in polynomial time, or is it NP-hard?
For the corresponding discrete instance with \(N\) individual agents of these two types, every agent has MMS \(t\), yet every allocation gives some agent value at most \(t-1\).
No result for the exact distribution-over-types formulation above was verified.
The problem is polynomial-time solvable: every instance in the question is feasible. The key is that each type’s benchmark already permits a distribution over bundles. Those distributions can be scaled by the type masses and combined.
Here is the general argument. Let \(\mathcal G\) be a finite set of classes with supplies \(s_g\), and let the type masses satisfy \(\mu_\theta\ge 0\) and \(\sum_\theta\mu_\theta=1\). Suppose that, for every type \(\theta\), a distribution \(y^\theta_B\) attains its benchmark \(W_\theta\), so that
\( \displaystyle \sum_B y^\theta_B=1,\qquad \sum_{B\ni g}y^\theta_B=s_g,\qquad y^\theta_B>0\Longrightarrow v_\theta(B)\ge W_\theta. \)
Set \(x_{\theta,B}=\mu_\theta y^\theta_B\). Then the required type masses are
\( \displaystyle \sum_Bx_{\theta,B}=\mu_\theta\sum_By^\theta_B=\mu_\theta. \)
For every class \(g\), the combined consumption is
\( \displaystyle \sum_{\theta,B\ni g}x_{\theta,B}=\sum_\theta\mu_\theta\sum_{B\ni g}y^\theta_B=\sum_\theta\mu_\theta s_g=s_g. \)
Finally, \(x_{\theta,B}>0\) implies \(y^\theta_B>0\), hence \(v_\theta(B)\ge W_\theta\). This proves feasibility whenever the benchmark distributions exist.
For completeness, the benchmarks in the stated instance are attained and equal to \(t\), and an explicit feasible allocation follows.
Write \(A=n(n-2)^2+1\), so \(t=nA\). Let \(P_i\) consist of all core classes in row \(i\), and let \(Q_j\) consist of all core classes in column \(j\). Each row and column has total base value \(A\). Indeed, the three possible row sums are
\( \displaystyle \sum_{g\in P_i}b_g=(n-2)\bigl(2(n-1)+n^2-4n+2\bigr)+1=A. \)
The three possible column sums are
\( \displaystyle \sum_{g\in Q_j}b_g=(n-2)\bigl(n+n^2-4n+2+n-2\bigr)+1=A. \)
For type \(R\), the perturbations vanish on every row other than the last. On the last row, the \(n-1\) negative perturbations cancel the positive perturbation \(n-1\). Thus \(v_R(P_i)=t\) for every \(i\). The corresponding column argument gives \(v_C(Q_j)=t\) for every \(j\).
Since \(n\le N\), adjoining the \(N-n\) auxiliary singleton bundles gives a partition into exactly \(N\) bundles of value \(t\) for each respective type. Giving every bundle in either partition mass \(1/N\) proves \(W_R\ge t\) and \(W_C\ge t\).
Conversely, either partition shows that the total value of all classes is \(Nt\) for its type. For any distribution satisfying the benchmark supply constraints, additivity therefore gives
\( \displaystyle \sum_B y_Bv_\theta(B)=\sum_{g\in\mathcal G}v_\theta(g)\sum_{B\ni g}y_B=\frac1N\sum_{g\in\mathcal G}v_\theta(g)=t. \)
If every positive-mass bundle has value at least \(w\), this expectation is at least \(w\), because \(\sum_By_B=1\). Consequently \(W_\theta\le t\), proving \(W_R=W_C=t\).
An explicit allocation now assigns mass \(\mu_R/N\) to each row bundle for type \(R\), mass \(\mu_C/N\) to each column bundle for type \(C\), and mass \(\mu_\theta/N\) to each auxiliary singleton for each type \(\theta\). Each type receives its prescribed total mass. Every class is consumed with total mass \((\mu_R+\mu_C)/N=1/N\), and every used bundle has value \(t\) for its recipient type.
Thus the decision algorithm returns YES on every valid input. The discrete impossibility does not obstruct this construction: continuous masses permit combining the two types’ different benchmark partitions.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct. The argument establishes feasibility for every valid instance of the stated decision problem, computes both benchmarks exactly, and supplies an explicit feasible allocation. No mathematical gaps or incorrect steps were found.
The general argument uses precisely the constraints in the task: every benchmark distribution has total mass \(1\) and the same class marginals \(s_g\), while the type masses sum to \(1\).
Setting \(x_{\theta,B}=\mu_\theta y^\theta_B\) preserves nonnegativity and gives total mass \(\mu_\theta\) to each type. The displayed marginal calculation correctly gives total consumption \(s_g\) for every class. If \(x_{\theta,B}>0\), then \(y^\theta_B>0\), so the recipient’s benchmark condition holds. This implication also handles zero type masses correctly.
The initial argument is conditional on benchmark attainment. The subsequent construction establishes attainment for the instances under consideration, so there is no unresolved existence assumption.
From \(N\ge4\) and \(n=\lceil(N+4)/2\rceil\), one has \(4\le n\le N\). Thus the indicated interior rows and columns exist, and the auxiliary count \(N-n\) is nonnegative.
With \(A=n(n-2)^2+1\), the identity \(t=nA\) agrees exactly with the task’s definition. When \(N-n=0\), the construction simply has no auxiliary singletons; none of its calculations require any.
The first and interior row formulas count the specified classes correctly. In the interior-row formula, the parenthesized expression simplifies to \(n(n-2)\), giving \(A\). The last-row expression also expands to \(A\).
The first-column formula simplifies to \(n(n-2)^2+1\). In the interior-column formula, the parenthesized expression again simplifies to \(n(n-2)\), giving \(A\). The last-column expression likewise equals \(A\).
Consequently, every row and every column has base-value sum \(A\), as claimed.
For type \(R\), only the last row is perturbed. It contains exactly \(n-1\) classes receiving a decrement of \(1\), including \(g_{n1}\), and the class \(g_{nn}\) receiving an increment of \(n-1\). Its net perturbation is therefore zero. Every row has type-\(R\) value \(nA=t\).
For type \(C\), the same count applies to the last column, including \(g_{1n}\). Every column consequently has type-\(C\) value \(t\).
The proof uses each partition only for its corresponding type; it does not assume that rows and columns have value \(t\) for both types.
The \(n\) row bundles partition the core classes, as do the \(n\) column bundles. Adding the \(N-n\) auxiliary singleton bundles produces exactly \(N\) bundles in each partition.
Assigning mass \(1/N\) to each partition bundle gives total mass \(1\) and marginal \(1/N\) for every class. Each supported bundle has value \(t\) for the corresponding type. Thus both benchmark lower bounds are established by admissible distributions.
Each corresponding partition shows that the total value of all classes for its type is \(Nt\). The expectation calculation is valid by additivity and rearrangement of finite sums.
Every admissible benchmark distribution therefore has expected value \(t\). If all its supported bundles have value at least \(w\), its expectation is at least \(w\), implying \(w\le t\). Combined with the exhibited distributions, this proves \(W_R=W_C=t\), including attainment.
Each type has exactly \(N\) partition bundles, each assigned mass \(\mu_\theta/N\), so its total mass is \(\mu_\theta\).
Every core class occurs in exactly one row and exactly one column. Every auxiliary class occurs in its singleton bundle for each type. Hence every class has combined consumption \((\mu_R+\mu_C)/N=1/N\). All supported bundles meet the recipient’s benchmark.
Since every valid instance is feasible, always returning YES correctly solves the stated decision problem in constant time on valid inputs, hence in polynomial time. This conclusion does not require enumerating all integral bundles or constructing an allocation when the input encodes \(N\) compactly.
The discrete impossibility statement is not contradicted: the displayed masses satisfy the continuous constraints, which impose no discrete-agent allocation requirement.
No corrective feedback or additional clarification is necessary.
⟨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.