Answer: \(\mathrm{P}\). A finite-support allocation with at most \(\tau(m+1)\) positive-mass assignments can be constructed in time polynomial in \(m,\tau,L\). Every valid instance is feasible for binary-encoded rational assignment masses; for dyadic assignment masses, feasibility is equivalent to all supplies being dyadic.
Theorem 19 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any number of agents with additive cost functions and arbitrary positive real weights, there exists an algorithm that computes a 1WEF complete allocation in polynomial time. The crux of this theorem relies on the carefully con- structed picking-sequence of Algorithm 3 so that each agent receives at least one item of higher cost (in the final loop) and the remaining items are allocated based on a weight- adjusted picking frequency for each agent. We claim that every agent is 1WEF up to the chore selected in the final for loop at every iteration of the while loop.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses of agent types, each with a positive entitlement and additive costs for finitely many recurring indivisible chore classes, and rational per-capita supplies of those classes, decide whether and constructively output a finite-support mass allocation over integral chore bundles such that every positive-mass agent assignment satisfies 1WEF against every other assignment, with complexity polynomial in the type count, chore-class count, and binary input length.
A society is given by its support: a list of \(\tau\geq 1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq 1\) recurring chore classes with per-capita supplies \(s_k\in\mathbb{Q}_{\geq 0}\). Type \(t\) has entitlement \(w_t\in\mathbb{Q}_{>0}\) and additive class costs \(c_{tk}\in\mathbb{Q}_{\geq 0}\); write \(c_t(b)=\sum_{k=1}^m c_{tk}b_k\). Entitlements need not sum to \(1\).
A mass allocation consists of finitely many pairs \((t,b)\), with integral bundles \(b\in\mathbb{Z}_{\geq 0}^m\), and positive binary-rational assignment masses \(x_{t,b}\), satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_k=s_k\) for every class \(k\).
It is 1WEF if every ordered pair of positive-mass assignments \((t,b),(u,d)\), including assignments of the same type, satisfies \(\frac{c_t(b)-\max_{k:b_k>0}c_{tk}}{w_t}\leq\frac{c_t(d)}{w_u}\); the maximum is \(0\) for an empty bundle. Thus one may remove one chore from the comparing agent’s own bundle.
Let \(L\) be the total binary input length; bundle multiplicities are encoded in binary.
Is feasibility of a 1WEF mass allocation in \(\mathrm{P}\), or is it NP-hard? In the polynomial-time case, can a finite-support allocation also be constructed in time polynomial in \(m,\tau,L\)?
For explicitly listed agents and indivisible chores, arbitrary positive entitlements and additive nonnegative costs admit a complete 1WEF allocation computable in polynomial time ([Springer, Hajiaghayi and Yami](https://arxiv.org/html/2305.16081)).
An independent efficient picking-sequence result uses a continuous interpretation of discrete picks ([Wu, Zhang and Zhou](https://arxiv.org/abs/2301.08090)); no result settling the exact mass-allocation problem above was located.
Feasibility is in \(\mathrm{P}\). Under the interpretation that “binary-rational” means a rational encoded by binary numerator and denominator, every valid instance is feasible, and a finite-support allocation can be constructed in time polynomial in \(\m,\tau,L\), with at most \(\tau(m+1)\) positive-mass assignments.
If “binary-rational” instead means *dyadic rational*, feasibility holds exactly when all supplies are dyadic; the construction below also runs in polynomial time in that case.
The construction compresses the [reversed weighted picking sequence of Wu, Zhang and Zhou](https://arxiv.org/html/2301.08090). Both its fairness and the compressed implementation are proved below.
First interpret assignment masses as arbitrary rationals encoded in binary.
Choose a positive integer \(\N\) divisible by every denominator occurring in the masses \(\mu_t\) and supplies \(\s_k\). Their product suffices and has binary length at most \(\L\). Define
\[ N_t=N\mu_t,\qquad S_k=Ns_k,\qquad M=\sum_{k=1}^m S_k. \]
These are nonnegative integers, with \(\N_t\geq1\) and \(\sum_tN_t=N\).
Consider a finite instance containing \(\N_t\) identical agents of each type \(\t\), and \(\S_k\) individual chores of class \(\k\). Give every type-\(\t\) agent weight \(\w_t\) and class costs \(\c_{tk}\). Order agents lexicographically by type and then by an index \(\j\in\{1,\ldots,N_t\}\).
A complete 1WEF allocation in this finite instance induces a mass allocation: if exactly \(\ell\) type-\(\t\) agents receive bundle \(\b\), assign
\[ x_{t,b}=\frac{\ell}{N}. \]
The type-mass and supply equations then hold. Every ordered pair of positive-mass assignments has corresponding agents, so finite-agent 1WEF implies the required mass-allocation condition, including comparisons within one type.
The difficulty is that \(\N\) and \(\M\) can be exponentially large. We therefore construct their allocation implicitly.
This section concerns an arbitrary finite collection of agents with positive weights and additive nonnegative chore costs.
Generate a forward sequence of length \(\M\). Starting with counters \(\a_i=0\), repeatedly select an agent minimizing \(\a_i/w_i\), break ties by the fixed agent order, and increase that agent’s counter by one.
Then process this sequence in reverse, letting each selected agent take a minimum-cost remaining chore.
Let \(\a_i(K)\) be agent \(\i\)’s number of occurrences in the first \(\K\) positions of the forward sequence. For every prefix and every ordered pair of agents,
\[ \frac{a_i(K)-1}{w_i}\leq\frac{a_j(K)}{w_j}. \tag{1} \]
At \(\K=0\), this follows from positivity of the weights. Suppose it holds before the next selected agent \(\h\) increments its counter. For the new inequalities with \(\i=h\) and \(\j\neq h\), the selection rule gives
\[ \frac{a_h(K+1)-1}{w_h} =\frac{a_h(K)}{w_h} \leq\frac{a_j(K)}{w_j}. \]
The inequality with \(\i=j=h\) is immediate. All other inequalities are preserved because their left sides stay fixed and their right sides either stay fixed or increase. This proves (1).
Consequently, every suffix of the reversed sequence satisfies
\[ \frac{\text{number of occurrences of }i-1}{w_i} \leq \frac{\text{number of occurrences of }j}{w_j}. \tag{2} \]
Indeed, such a suffix consists precisely of an original forward prefix.
Write \(\B_i\) for the final bundle of agent \(\i\). Fix agents \(\i,j\) and a real threshold \(\z\geq0\). Let \(\n_i(z)\) count chores in \(\B_i\) whose cost to \(\i\) exceeds \(\z\), and let \(\n_j(z)\) count chores in \(\B_j\) whose cost to \(\i\) exceeds \(\z\).
Suppose \(\n_i(z)>0\). Consider the suffix of the reversed picking sequence beginning when \(\i\) takes its first chore costing more than \(\z\). At that pick, every remaining chore costs more than \(\z\) to \(\i\): otherwise the selected chore would not have minimum cost.
Thus that suffix contains all \(\n_i(z)\) costly picks of \(\i\), and every pick of \(\j\) in the suffix contributes to \(\n_j(z)\). Applying (2) gives
\[ \frac{n_i(z)-1}{w_i}\leq\frac{n_j(z)}{w_j}. \]
When \(\n_i(z)=0\), nonnegativity gives the corresponding inequality with zero on the left. Therefore, for every threshold,
\[ \frac{\max\{n_i(z)-1,0\}}{w_i}\leq\frac{n_j(z)}{w_j}. \tag{3} \]
For a finite bundle of nonnegative-cost chores, integrating its threshold counts gives its total cost. Removing a maximum-cost chore changes the threshold count from \(\n_i(z)\) to \(\max\{n_i(z)-1,0\}\). Integrating (3) therefore yields
\[ \frac{c_i(B_i)-\max_{e\in B_i}c_i(e)}{w_i} \leq\frac{c_i(B_j)}{w_j}, \]
with maximum zero for an empty bundle. Hence the procedure produces a complete 1WEF allocation. This proof requires neither normalized weights nor strictly positive costs.
Write each type weight in reduced form as \(\w_t=p_t/q_t\), with positive integers \(\p_t,q_t\). Set
\[ D=\prod_{t=1}^{\tau}p_t,\qquad A_t=\frac{Dq_t}{p_t}. \]
Each \(\A_t\) is a positive integer of polynomial binary length.
For every type-\(\t\) agent, introduce events at integer times
\[ 0,A_t,2A_t,\ldots. \]
Order all events by time and then by agent order. This is exactly the forward sequence: an agent that has already appeared \(\r\) times has its next event at time \(\r A_t=D r/w_t\).
For integer \(\T\geq0\), the number of events through time \(\T\) is
\[ F(T)=\sum_{t=1}^{\tau}N_t \left(\left\lfloor\frac{T}{A_t}\right\rfloor+1\right). \tag{4} \]
Given a positive prefix length \(\K\leq M\), find the smallest integer \(\T\) satisfying \(\F(T)\geq K\). Binary search on \(\{0,\ldots,K A_{\max}\}\), where \(\A_{\max}=\max_tA_t\), finds it in polynomial time.
Each type-\(\t\) agent has exactly
\[ u_t(K)=\left\lceil\frac{T}{A_t}\right\rceil \]
events strictly before \(\T\). The prefix then takes
\[ J=K-\sum_tN_tu_t(K) \]
events at time \(\T\). Only types with \(\A_t\mid T\) have events there. Visiting those types in order, give each type the first \(\z_t(K)\) of its \(\N_t\) events until these \(\J\) events are exhausted.
Thus the number of occurrences of agent \(t,j)\) in the prefix is
\[ v_{t,j}(K)=u_t(K)+\mathbf 1_{\{j\leq z_t(K)\}}, \tag{5} \]
and the aggregate number for type \(\t\) is
\[ P_t(K)=N_tu_t(K)+z_t(K). \tag{6} \]
For \(\K=0\), set all these quantities to zero. Equations (4)–(6) give a polynomial-time prefix oracle using only polynomial-length integers.
Maintain remaining supplies \(\R_k\), initially \(\S_k\), and a cursor \(\K\), initially \(\M\). The unprocessed reversed sequence consists of forward positions \(\K,K-1,\ldots,1\).
When \(\K>0\), let \(\f_t\) be type \(\t\)’s minimum-cost class among those with \(\R_k>0\), breaking cost ties by class index.
Temporarily suppose each type always picks its class \(\f_t\). Processing the next \(\H\) reversed positions would use
\[ d_k(H)= \sum_{\{t:f_t=k\}} \bigl(P_t(K)-P_t(K-H)\bigr) \tag{7} \]
chores of class \(\k\).
Every \(\d_k(H)\) is nondecreasing in \(\H\). Use binary search to find the largest \(\H\in\{0,\ldots,K\}\) satisfying
\[ d_k(H)\leq R_k\qquad\text{for every }k. \tag{8} \]
The next hypothetical pick uses a positive-supply class, so \(\H\geq1\).
Throughout these \(\H\) hypothetical picks, no class is overused, by monotonicity and (8). Therefore, at every pick, the selected class \(\f_t\) is still available.
It was type \(\t\)’s preferred class at the phase’s start. Removing other chores cannot make an available \(\f_t\) less preferred. Hence every hypothetical pick agrees with actual minimum-cost picking.
We may therefore process the entire phase at once and update
\[ R_k\leftarrow R_k-d_k(H),\qquad K\leftarrow K-H. \]
If \(\H<K\) before this update, maximality implies that the next hypothetical pick would exceed one class supply. Since quantities are integral, that class is exhausted exactly by the chosen phase.
If \(\H=K\), all remaining picks are processed. The invariant \(\sum_kR_k=K\) implies that all remaining supplies are exhausted.
Thus every phase exhausts at least one previously positive-supply class. There are at most \(\m\) phases.
Suppose the phase endpoints are
\[ M=K_0>K_1>\cdots>K_h=0,\qquad h\leq m, \]
and type \(\t\)’s selected class in phase \(\ell\) is \(\f_{t,\ell}\).
Agent \(t,j)\)’s number of picks during that phase is
\[ v_{t,j}(K_{\ell-1})-v_{t,j}(K_\ell). \tag{9} \]
These are nonnegative integers, because they count occurrences in nested prefixes. Its bundle is therefore given by
\[ b_{t,j,k} = \sum_{\{\ell:f_{t,\ell}=k\}} \bigl(v_{t,j}(K_{\ell-1})-v_{t,j}(K_\ell)\bigr). \tag{10} \]
By (5), the bundle depends on \(\j\) only through comparisons with the phase-endpoint values \(\z_t(K_\ell)\). The terminal value \(\z_t(0)\) is zero, so there are at most \(\h\) relevant internal cuts in the ordered indices \(\{1,\ldots,N_t\}\).
Partition those indices at these cuts. There are at most \(\h+1\leq m+1\) nonempty intervals per type, and every agent in an interval receives the same bundle.
For an interval containing \(\ell\) indices and receiving bundle \(\b\), output
\[ (t,b),\qquad x_{t,b}=\frac{\ell}{N}. \]
Identical bundles of the same type may be merged. Hence the output has at most \(\tau(m+1)\) positive-mass assignments.
Because this construction reproduces the finite-agent allocation exactly, Section 2 proves its 1WEF property. The interval lengths sum to \(\N_t\), and the allocation uses exactly \(\S_k\) chores of each class. Consequently,
\[ \sum_bx_{t,b}=\frac{N_t}{N}=\mu_t, \qquad \sum_{t,b}x_{t,b}b_k=\frac{S_k}{N}=s_k. \]
The integers \(\N,N_t,S_k,M,D,A_t\) have binary lengths polynomial in \(\m,\tau,L\). The prefix oracle searches times bounded by \(\M A_{\max}\), also of polynomial binary length.
Each phase uses a binary search over \(\H\leq M\). Each trial evaluates (7) using the prefix oracle and polynomially many arithmetic operations. There are at most \(\m\) phases.
The final partition has at most \(\tau(m+1)\) intervals. Formula (10) computes their bundles in polynomial time. Every bundle coordinate is at most \(\M\), and each output mass has numerator at most \(\N\) and denominator \(\N\). Thus the entire output has polynomial encoding length.
When \(\M=0\), simply assign the empty bundle to each type with mass \(\mu_t\).
This proves both polynomial-time feasibility and polynomial-time construction.
A finite sum of integer multiples of dyadic rationals is dyadic. Therefore, dyadic assignment masses necessarily make every \(\s_k\) dyadic.
Conversely, if the given masses and all supplies are dyadic, choose \(\N\) to be a power of two clearing their denominators. The entire construction above then applies, and every output mass \(\ell/N\) is dyadic.
Testing whether a reduced rational denominator is a power of two takes polynomial time. Thus this interpretation also has a complete polynomial-time feasibility and construction algorithm.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time feasibility and polynomial-time construction, with at most \(\tau(m+1)\) positive-mass assignments. I found no substantive mathematical gap or false step. The only issue is malformed mathematical notation, which requires an editorial correction.
Both interpretations of “binary-rational” are addressed: arbitrary binary-encoded rational assignment masses give feasibility for every valid instance; dyadic assignment masses give feasibility exactly when all supplies are dyadic. Both interpretations yield polynomial-time algorithms.
Correct. A common denominator \(N\) for the input masses and supplies makes \(N_t=N\mu_t\) and \(S_k=Ns_k\) integers. Positivity of \(\mu_t\) implies \(N_t\geq1\), and normalization gives \(\sum_tN_t=N\).
Taking the product of input denominators has polynomial binary length. Thus the potentially exponential population and chore count do not themselves invalidate the proposed complexity bound.
The conversion from a finite-agent allocation to assignment masses \(\ell/N\) preserves both conservation equations. Every positive-mass bundle has a representative agent. Comparisons between different bundles of the same type are therefore covered. Comparing an assignment with itself also satisfies the required inequality by nonnegativity of the removed maximum cost.
Correct. The base case holds because all weights are positive.
In the induction step, inequalities whose left-hand counter increases are justified by the minimizing selection rule. All other left-hand sides remain fixed, while right-hand sides either remain fixed or increase. The self-comparison is immediate.
Reversing the sequence converts each forward prefix into a suffix of the reversed sequence, with exactly the same occurrence counts. Consequently, equation (2) follows from equation (1).
Correct. Fixing the evaluating agent \(i\), both threshold counts use costs measured by \(i\), as required.
When \(i\) first selects a chore costing more than \(z\), minimum-cost picking implies that every chore then remaining costs more than \(z\) to \(i\). Consequently:
The suffix invariant therefore yields the asserted threshold inequality. When \(n_i(z)=0\), equation (3) follows from nonnegative costs and positive weights.
The integration step is valid for finite bundles of nonnegative-cost chores. Removing a maximum-cost chore changes the threshold count to \(\max\{n_i(z)-1,0\}\), including at thresholds equal to an item cost. Thus integrating gives precisely the required weighted inequality.
Empty bundles, zero costs, arbitrary positive weights, and self-comparisons are all covered.
The attribution to the reversed weighted picking sequence is accurate: the cited paper’s Algorithm 1 generates the sequence by minimizing weighted occurrence counts and then reverses it for minimum-cost picking. The submitted proof establishes fairness independently, rather than relying on an unstated theorem application. [Wu, Zhang and Zhou, Section 3.1](https://arxiv.org/html/2301.08090)
Correct. With \(w_t=p_t/q_t\), the event spacing satisfies \(A_t=D/w_t\). Hence an agent’s next event after \(r\) occurrences has time \(Dr/w_t\), matching the selection rule. Ordering equal-time events by the fixed agent order also matches its tie-breaking.
Equation (4) correctly counts events through time \(T\), including the event at time zero.
For positive \(K\), the binary-search range is sufficient: even one agent with spacing at most \(A_{\max}\) has at least \(K\) events through time \(KA_{\max}\). The search is over integer times, and all event times are integers.
The number of events strictly before \(T\) is correctly given by \(\lceil T/A_t\rceil\), including when \(T=0\) or \(A_t\) divides \(T\). Minimality of \(T\) ensures that the remaining \(J\) events can be selected among events occurring exactly at \(T\). Within each participating type, agent order makes these the first \(z_t(K)\) indices.
Equations (5) and (6), together with the separately defined zero prefix, therefore give the claimed exact oracle.
Correct. Equation (7) counts precisely the type occurrences in the next \(H\) reversed positions. Each class demand is nondecreasing in \(H\), so the feasibility predicate supports binary search.
For \(K>0\), the remaining-supply invariant guarantees a positive-supply class. Every type’s chosen class has positive integer supply, so the first hypothetical pick is feasible and \(H\geq1\).
The availability argument is sound: if a selected class were unavailable before a hypothetical pick, that pick would make its cumulative demand exceed its initial remaining supply, contradicting equation (8). Removing chores cannot introduce a more preferred class, so the fixed class choices reproduce actual greedy picking throughout the phase.
If \(H<K\), failure at \(H+1\) identifies a class whose supply was exhausted by the first \(H\) picks. If \(H=K\), conservation forces every remaining supply to be exhausted. Thus each phase eliminates at least one previously positive class, giving at most \(m\) phases.
Correct. Equation (9) counts occurrences between nested prefixes and is nonnegative. Summing these counts by the phase’s chosen class gives the actual bundle in equation (10).
For a fixed type, dependence on the agent index occurs only through the endpoint cut values \(z_t(K_\ell)\). There are \(h\) potentially relevant endpoint values because the terminal value is zero. Duplicate cuts and cuts at the population boundary cannot increase the number of nonempty intervals.
Consequently, at most \(h+1\leq m+1\) bundles are needed per type. Each interval has a positive integer length, so its assignment mass is positive. Merging identical bundles preserves conservation and fairness.
The stated type-mass and class-supply equations follow from the exact finite-agent simulation.
Correct. All initial constructed integers have polynomial binary length. Prefix searches use bounds with polynomial binary length, and phase searches likewise depend on the binary length of \(M\), rather than on its numerical magnitude.
There are at most \(m\) phases, polynomially many oracle calls per phase, and polynomially many arithmetic operations per call. Rational cost comparisons can also be performed exactly in polynomial time from the supplied encodings.
The output has polynomially many assignments. Bundle coordinates are bounded by \(M\), and assignment masses have numerator and denominator bounded by \(N\), so their encodings have polynomial length.
The \(M=0\) case is explicitly handled and satisfies fairness and conservation.
Correct. A finite sum of integer multiples of dyadic assignment masses is dyadic, proving necessity for every supply.
Under the dyadic interpretation, the input type masses are themselves dyadic. When supplies are also dyadic, a power-of-two common denominator makes all output masses dyadic. Its binary length remains polynomial in the input length.
Testing reduced denominators for being powers of two is polynomial-time. This interpretation therefore also receives a complete feasibility and construction algorithm.
Minor — malformed notation throughout. The output uses undefined commands such as \N, \M, \m, \t, and \c, and malformed agent-index expressions such as \(t,j)\). Their intended meanings are recoverable from context, so this does not affect the mathematical conclusion.
Required correction: replace undefined commands with ordinary variable notation and correct the agent-index delimiters. No additional mathematical lemma or justification is needed.
⟨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.