Answer: The exact optimization problem is polynomial-time solvable. Every valid instance is feasible, and the welfare-threshold decision problem belongs to \(\mathrm{P}\).
Lemma 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any 𝛽≤−2 𝑛, ALG-M(𝛽) returns an MMS allocation in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(N\), \(m\), a finite type set \(T\), rational disutility vectors \(a_t\in\mathbb{Q}_{\le 0}^m\) with \(\sum_j a_t(j)=-1\), and a rational society distribution \(\mu\in\Delta(T)\), let \(\mathcal{K}_{\mathrm{MMS}}\) be the typed contiguous allocations of one \(m\)-chore path among \(N\) slots in which every type-\(t\) slot receives value at least \(M_t=\max_{(I_1,\ldots,I_N)\in\Pi_N([m])}\min_\ell a_t(I_\ell)\). Over masses \(z_\kappa\ge 0\) of repeated paths using configuration \(\kappa\), find a \(z\) satisfying \(\sum_\kappa z_\kappa=1\) and \(\sum_\kappa z_\kappa r_t(\kappa)=N\mu_t\) for every \(t\), maximizing \(\sum_\kappa z_\kappa\sum_{(t,I)\in\kappa}a_t(I)\), without splitting any chore within a path.
Given integers \(N\ge 3\) and \(m\ge 1\), with \(N\) encoded in unary, the chores form the path \([m]=\{1,\ldots,m\}\).
A society is given by its support: the list \(T\) of its \(\tau\) types with positive masses \(\mu_t\) encoded as binary rationals, where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type has an additive valuation \(a_t\in\mathbb Q_{\le 0}^m\), with \(\sum_{j=1}^m a_t(j)=-1\); write \(a_t(I)=\sum_{j\in I}a_t(j)\).
Let \(\Pi_N([m])\) contain all partitions into \(N\) contiguous bundles, allowing empty bundles, and define \(M_t=\max_{(I_1,\ldots,I_N)\in\Pi_N([m])}\min_{\ell\in[N]}a_t(I_\ell)\).
A configuration \(\kappa=((t_\ell,I_\ell))_{\ell=1}^N\) assigns a type to each bundle of such a partition and satisfies \(a_{t_\ell}(I_\ell)\ge M_{t_\ell}\) for every slot. Types may repeat, their order is unrestricted, and empty slots count toward type multiplicities.
Let \(\mathcal K_{\mathrm{MMS}}\) be all such configurations, \(r_t(\kappa)=|\{\ell:t_\ell=t\}|\), and \(w(\kappa)=\sum_{\ell=1}^N a_{t_\ell}(I_\ell)\).
The optimization problem is to detect infeasibility or maximize \(\sum_{\kappa\in\mathcal K_{\mathrm{MMS}}}z_\kappa w(\kappa)\) over nonnegative masses satisfying \(\sum_\kappa z_\kappa=1\) and \(\sum_\kappa z_\kappa r_t(\kappa)=N\mu_t\) for every type. Chores remain indivisible within each configuration.
Is this exact optimization problem solvable in polynomial time in \(m,\tau,N,L\), or is its decision version with an input binary-rational welfare threshold NP-hard?
For a finite list of agents, a contiguous MMS allocation can be found in polynomial time, and each agent’s contiguous MMS value is polynomial-time computable. [Sun and Li](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p1800.pdf)
No result settling this exact distribution-over-configurations optimization problem was located.
The exact optimization problem is solvable in polynomial time in \(m,\tau,N,L\). Every valid instance is feasible, and an optimal distribution can be returned with polynomially many configurations in its support. The welfare-threshold decision problem therefore belongs to \(\mathrm{P}\).
The key is that configurations admit a polynomial-size representation as paths in a directed acyclic graph. Distributions over these paths are represented exactly by flows, while the expected type multiplicities become linear constraints.
For each \(t\in T\), choose a partition attaining \(M_t\). Such a partition exists because there are finitely many contiguous partitions, including those with empty bundles.
Assign type \(t\) to all \(N\) bundles of this partition, obtaining a configuration \(\kappa_t\). Every bundle meets its assigned type’s MMS requirement, and
\(r_u(\kappa_t)=N\) if \(u=t\), while \(r_u(\kappa_t)=0\) otherwise.
Give \(\kappa_t\) probability \(\mu_t\). These probabilities sum to one, and for every \(u\in T\),
\(\displaystyle \sum_{t\in T}\mu_t r_u(\kappa_t)=N\mu_u.\)
Thus the requested distribution is always feasible. This observation settles feasibility; optimizing welfare still requires the construction below.
Here is a direct dynamic program, also establishing the computability stated in Lemma 4 of [Sun and Li](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p1800.pdf).
Set \(c_t(j)=-a_t(j)\), so all costs are nonnegative. For \(0\le p\le q\le m\), define
\(\displaystyle C_t(p,q)=\sum_{j=p+1}^{q}c_t(j),\)
with \(C_t(p,p)=0\).
Let \(D_t(s,q)\) be the minimum possible maximum bundle cost in a partition of the prefix \(\{1,\ldots,q\}\) into \(s\) contiguous bundles, allowing empties. Initialize
\(D_t(0,0)=0,\qquad D_t(0,q)=+\infty\quad\text{for }q>0.\)
For \(1\le s\le N\), use
\(\displaystyle D_t(s,q)=\min_{0\le p\le q}\max\{D_t(s-1,p),C_t(p,q)\}.\)
To justify this recurrence, take the last bundle to be \(\{p+1,\ldots,q\}\). The preceding bundles partition the prefix ending at \(p\); their best possible maximum cost is \(D_t(s-1,p)\). Conversely, an optimal partition of that prefix followed by the last bundle realizes the corresponding maximum. Minimizing over \(p\) considers every possible last bundle, including an empty one.
Negating costs reverses the max–min objective, giving
\(\displaystyle M_t=-D_t(N,m).\)
The dynamic program uses \(O(Nm^2)\) rational comparisons per type, after computing interval costs. Backtracking produces an MMS-defining partition.
Every finite table entry is zero or an interval cost, because the recurrence only takes minima and maxima of such values. Interval sums have polynomial binary encoding length: a common denominator can be formed by multiplying the input denominators, whose total bit length is bounded by \(L\). Hence these computations take polynomial bit complexity.
We may arrange bundles in path order. If a configuration lists bundles in another order, reorder the type–bundle pairs together. This preserves all MMS conditions, multiplicities, and welfare. Empty pairs can be placed anywhere between bundles.
Construct a directed multigraph with vertices
\(\displaystyle V=\{(s,p):0\le s\le N,\ 0\le p\le m\}.\)
The vertex \((s,p)\) records that \(s\) slots have been assigned and the first \(p\) chores have been covered. Let the source be \(\sigma=(0,0)\) and the sink be \(\omega=(N,m)\).
For every \(1\le s\le N\), \(0\le p\le q\le m\), and \(t\in T\), include an arc
\(\displaystyle e:(s-1,p)\longrightarrow(s,q)\)
precisely when
\(\displaystyle a_t(\{p+1,\ldots,q\})\ge M_t.\)
Label this arc by \(t(e)=t\), and give it weight
\(\displaystyle u_e=a_t(\{p+1,\ldots,q\}).\)
When \(p=q\), the arc represents an empty bundle. Its weight is zero, and its type still counts toward multiplicity. Such an arc satisfies the MMS condition because \(M_t\le 0\).
Every arc increases the slot coordinate by one, so the graph is acyclic. It has
\(\displaystyle |V|=(N+1)(m+1),\qquad |E|\le N\tau\frac{(m+1)(m+2)}2.\)
A source-to-sink path has exactly \(N\) arcs. Its successive endpoints define a partition covering every chore exactly once, and its labels assign types satisfying all MMS constraints. Conversely, every configuration, after ordering its bundles as above, gives such a path.
For the configuration associated with a path \(P\),
\(\displaystyle r_t(P)=\sum_{e\in P}\mathbf 1_{\{t(e)=t\}},\qquad w(P)=\sum_{e\in P}u_e.\)
Introduce a nonnegative variable \(x_e\) for each arc. Write \(\delta^+(v)\) and \(\delta^-(v)\) for the outgoing and incoming arcs of \(v\). Define \(b_\sigma=1\), \(b_\omega=-1\), and \(b_v=0\) at every other vertex.
Solve the following rational linear program:
\(\displaystyle \max \sum_{e\in E}u_e x_e\)
subject to
\(\displaystyle \sum_{e\in\delta^+(v)}x_e-\sum_{e\in\delta^-(v)}x_e=b_v\qquad(v\in V),\)
\(\displaystyle \sum_{\substack{e\in E\\t(e)=t}}x_e=N\mu_t\qquad(t\in T),\)
and \(x_e\ge 0\) for all \(e\in E\).
The first equations impose a unit source-to-sink flow. The second equations impose the expected type multiplicities.
Given any feasible distribution, represent each configuration by its path and set
\(\displaystyle x_e=\sum_P z_P\mathbf 1_{\{e\in P\}}.\)
Each path carries a unit source-to-sink flow, so averaging their incidence vectors gives the required flow equations. Moreover,
\(\displaystyle \sum_{e:t(e)=t}x_e=\sum_P z_P r_t(P)=N\mu_t,\)
and
\(\displaystyle \sum_e u_e x_e=\sum_P z_P w(P).\)
Thus every original feasible solution gives a feasible flow with identical welfare.
We prove the converse explicitly. Start with any feasible flow. As long as positive flow leaves the source, follow positive-flow arcs. At every intermediate vertex reached, conservation guarantees a positive outgoing arc. Acyclicity prevents revisiting vertices. The walk must therefore reach the sink: termination at another vertex with positive incoming flow would contradict conservation.
Let \(P\) be this path and let
\(\displaystyle \lambda=\min_{e\in P}x_e>0.\)
Subtract \(\lambda\) from every arc of \(P\), and record \(P\) with mass \(\lambda\). The residual flow remains nonnegative and satisfies conservation, with its source-to-sink value reduced by \(\lambda\). At least one positive arc disappears.
Consequently, at most \(|E|\) extractions occur. No nonzero residual flow can remain once the source flow is zero. Indeed, if one remained, choose a vertex with positive outgoing flow in the earliest layer containing such a vertex. It has no positive incoming flow, contradicting conservation and zero residual source flow.
We therefore obtain paths \(P_1,\ldots,P_k\) and positive masses \(\lambda_1,\ldots,\lambda_k\), where \(k\le |E|\), such that
\(\displaystyle x_e=\sum_{i=1}^k\lambda_i\mathbf 1_{\{e\in P_i\}},\qquad \sum_{i=1}^k\lambda_i=1.\)
Each path is an MMS configuration. Its resulting distribution satisfies
\(\displaystyle \sum_{i=1}^k\lambda_i r_t(P_i)=\sum_{e:t(e)=t}x_e=N\mu_t,\)
and has welfare
\(\displaystyle \sum_{i=1}^k\lambda_i w(P_i)=\sum_e u_e x_e.\)
Thus the two optimization problems have exactly the same feasible welfare values. Fractional flows represent randomization over configurations; every constituent configuration still allocates indivisible chores.
The graph has polynomially many vertices and arcs. Its MMS eligibility tests, objective coefficients, and right-hand sides are exactly computable rationals of polynomial bit length. Therefore the entire linear program has encoding length polynomial in \(m,\tau,N,L\). The unary encoding of \(N\) ensures that constructing its \(N\) layers is polynomial in the input length.
The program is feasible by Section 1. The path decomposition shows that every feasible \(x_e\) lies between zero and one, so its feasible region is bounded.
We apply the standard rational linear programming theorem: feasibility and optimization are computable in time polynomial in the binary encoding length; when a finite optimum exists, an exact rational optimal solution and value can be returned. All hypotheses hold here. Decomposing the resulting flow takes polynomially many rational operations and produces an optimal distribution supported on at most \(|E|\) configurations.
Finally, compare the exact optimal welfare with the input rational threshold. This decides the threshold problem in polynomial time, including its threshold encoding length. In particular, the problem can be NP-hard only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated problem correctly. The argument establishes an exact polynomial-time algorithm, universal feasibility for valid instances, and an optimal distribution with polynomial support. No major or minor mathematical issues were found.
The construction is valid.
For each type \(t\), the maximum defining \(M_t\) is attained because the set of permitted partitions is finite and nonempty. In an attaining partition, every bundle has value at least \(M_t\). Assigning type \(t\) to all \(N\) slots therefore gives a valid configuration, including any empty slots.
Mixing these configurations with masses \(\mu_t\) gives total mass one and expected multiplicity \(N\mu_u\) for every type \(u\). The construction uses exactly the task’s permission to repeat types within a configuration. It does not require an unstated integrality condition on \(N\mu_u\).
Finding: Correct.
The sign conversion and recurrence are correct.
With nonnegative costs \(c_t(j)=-a_t(j)\), maximizing the minimum bundle valuation is equivalent to negating the minimum achievable maximum bundle cost. Thus \(M_t=-D_t(N,m)\).
The initialization correctly handles the empty prefix and excludes a nonempty prefix with zero bundles. For every state with at least one bundle, selecting the final cut \(p\) exhausts all possibilities. The choice \(p=q\) includes an empty final bundle. The recurrence’s use of the best preceding maximum is justified because taking the maximum with a fixed final-bundle cost is monotone.
The claimed rational bit complexity also holds: finite entries are selected from zero and interval costs, so the recurrence does not introduce growing arithmetic expressions. The input-denominator product has polynomial bit length.
The attribution to Lemma 4 is accurate: [Sun and Li](https://aamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p1800.pdf) state polynomial-time computability of contiguous MMS values. The submitted argument independently supplies the required computation.
Finding: Correct, including empty bundles, zero-cost chores, and \(N>m\).
The graph represents all relevant configurations.
Ordering nonempty bundles along the path and carrying their assigned types with them preserves eligibility, multiplicities, and welfare. Empty slots can be inserted at cut positions because their location changes none of those quantities.
Each arc covers precisely the next interval, and each layer accounts for one slot. Consequently, a source-to-sink path covers all chores exactly once using exactly \(N\) slots. Conversely, every permitted configuration has such a representation after ordering.
Empty arcs correctly contribute zero welfare while contributing one occurrence of their type. Their eligibility follows from \(M_t\le 0\).
The vertex and arc counts are correct. Parallel arcs distinguish different type assignments.
Finding: Correct. A bijection with originally ordered configurations is unnecessary; preservation of feasible welfare and multiplicities suffices.
Both directions of the equivalence are established.
A distribution over paths yields a nonnegative unit flow. Summing arcs by type gives exactly the expected type multiplicities, and summing weighted arcs gives exactly expected welfare.
For the converse, conservation ensures that a positive-flow walk starting at the source can continue at every reached vertex other than the sink. Acyclicity ensures termination. Subtracting the minimum path flow preserves nonnegativity and internal conservation while reducing the flow value.
Every extraction removes at least one positive arc, so at most \(|E|\) extractions occur. The earliest-layer argument correctly excludes residual positive flow after the source flow reaches zero. This also excludes extraneous flow in graph components disconnected from the source.
The decomposition preserves arc totals, hence preserves both the additional type constraints and the objective. Individual extracted paths remain valid configurations of indivisible chores.
Finding: Correct. The additional linear constraints need not survive intermediate extraction; they hold for the final distribution by the stated arc-total identities.
The rational linear-programming theorem is stated sufficiently precisely, and its hypotheses are verified.
The LP has polynomially many variables and constraints, with rational coefficients of polynomial encoding length. Unary encoding of \(N\) makes the layered construction polynomial in input size.
Feasibility follows from Section 1. The path decomposition implies \(0\le x_e\le 1\), so the feasible region is bounded. A finite optimum therefore exists, and exact rational LP optimization applies.
The subsequent decomposition has polynomial bit complexity as well as polynomial operation count: minimum selection and subtraction on the polynomial-size rational solution do not cause uncontrolled denominator growth. Its support bound \(|E|\) gives a polynomial-size explicit output.
Comparing the exact optimum with a binary-rational threshold takes polynomial time in the combined instance and threshold lengths. The final qualification concerning NP-hardness and \(\mathrm{P}=\mathrm{NP}\) is correct.
Finding: Correct.
No additional lemma, clarification, or correction is needed. The prover’s claimed resolution is supported by the submitted argument.
⟨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.