Answer: polynomial-time solvable
Theorem 3 (Additive scenarios) — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIn additive scenarios, any sequence of individually rational 1-deals will eventually result in an allocation with maximal utilitarian social welfare.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete agent types \(T\), rational type masses \(\mu_t\), resource kinds \(R\) with rational per-capita supplies \(\rho_r\), additive values \(v_{t,r}\), and an initial feasible mass allocation \(y^0\), compute a feasible \(y^\star\) maximizing \(W(y)=\sum_{t,S}y_{t,S}\sum_{r\in S}v_{t,r}\), where \(y_{t,S}\ge0\), \(\sum_S y_{t,S}=\mu_t\), and \(\sum_{t,S:r\in S}y_{t,S}=\rho_r\), together with a finite sequence of strictly welfare-increasing mass \(1\)-deals from \(y^0\) to a maximizing allocation.
A society is nonatomic and given by its support: the list of \(\tau=|T|\) complete types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=|R|\) resource kinds, binary-rational supplies \(\rho_r\in[0,1]\), and signed rational additive values \(v_{t,r}\). Each individual holds a bundle \(S\subseteq R\), hence at most one unit of each kind; empty bundles are allowed.
A feasible allocation satisfies \(y_{t,S}\geq0\), \(\sum_{S\subseteq R}y_{t,S}=\mu_t\), and \(\sum_{t,S:r\in S}y_{t,S}=\rho_r\). Its welfare is \(W(y)=\sum_{t,S}y_{t,S}\sum_{r\in S}v_{t,r}\).
The input includes a feasible rational allocation \(y^0\), listed by its positive entries; let \(k\) be their number and \(L\) the total input bit length.
A mass \(1\)-deal selects \(t,u\in T\), bundles \(S,B\subseteq R\), a kind \(r\in S\setminus B\), and rational \(0<\varepsilon\leq\min\{y_{t,S},y_{u,B}\}\). It subtracts \(\varepsilon\) from each selected entry and adds \(\varepsilon\) to each of \(y_{t,S\setminus\{r\}}\) and \(y_{u,B\cup\{r\}}\), combining coincident entries.
The two participating cohorts are disjoint, even if \(t=u\); every other individual's bundle is unchanged. A deal is admissible precisely when \(W\) strictly increases. Unrestricted balanced monetary side payments are available, with no budget constraints.
The computational problem is to compute a rational welfare-maximizing allocation \(y^\star\), represented by its positive entries, together with a finite sequence of admissible mass \(1\)-deals from \(y^0\) to \(y^\star\); the sequence may be empty.
Is this allocation-and-negotiation problem solvable in time polynomial in \(m,\tau,k,L\), or is it NP-hard?
For finite agents with additive utilities and unrestricted side payments, every maximal sequence of individually rational \(1\)-deals terminates at a utilitarian optimum ([Endriss et al.](https://www.doc.ic.ac.uk/~fs/Papers/Multi-agent%20systems/EndrissEtAlJAIR2006.pdf)).
No result settling exactly the continuous problem specified here was identified in the literature search.
The problem is solvable in polynomial time in \(m,\tau,k,L\).
More precisely, one can construct an optimal allocation with at most \(k(m+1)\) positive entries and a sequence of at most \(mk(m+1)\) admissible mass \(1\)-deals. Every rational mass appearing in the construction has bit length \(O(L)\).
The key is to partition the initial cohorts once, before negotiating. Each resource is then processed completely before proceeding to the next, so partial transfers do not cause repeated fragmentation.
For any feasible allocation \(y\), define its resource marginals by
\[ x_{t,r}(y)=\sum_{S:r\in S}y_{t,S}. \]
They satisfy \(0\leq x_{t,r}(y)\leq\mu_t\) and \(\sum_t x_{t,r}(y)=\rho_r\). Additivity gives
\[ W(y)=\sum_{r\in R}\sum_{t\in T}v_{t,r}x_{t,r}(y). \]
Write \(x^0_{t,r}=x_{t,r}(y^0)\).
Fix a resource \(r\). Sorting types by decreasing \(v_{t,r}\), choose a value \(\lambda_r\) such that
\[ \sum_{t:v_{t,r}>\lambda_r}\mu_t \leq \rho_r \leq \sum_{t:v_{t,r}\geq\lambda_r}\mu_t. \]
Such a value exists: for positive supply, take the value at which the sorted cumulative mass first reaches the supply; for zero supply, take the maximum value.
Partition the types into
\[ H_r=\{t:v_{t,r}>\lambda_r\},\qquad E_r=\{t:v_{t,r}=\lambda_r\},\qquad F_r=\{t:v_{t,r}<\lambda_r\}. \]
Set target marginals \(z_{t,r}=\mu_t\) on \(H_r\) and \(z_{t,r}=0\) on \(F_r\). The required total marginal on \(E_r\) is
\[ h_r=\rho_r-\sum_{t\in H_r}\mu_t. \]
Let \(e_r=\sum_{t\in E_r}x^0_{t,r}\). Choose the tied types’ targets as follows:
This is possible because \(0\leq h_r\leq\sum_{t\in E_r}\mu_t\). It uses only additions, subtractions, and minima.
Call \(t\) a donor for \(r\) if \(z_{t,r}<x^0_{t,r}\), and a recipient if \(z_{t,r}>x^0_{t,r}\).
Every donor has value at most \(\lambda_r\), and every recipient has value at least \(\lambda_r\). Moreover, tied types cannot include both donors and recipients: all their changes have the same direction. Consequently,
\[ v_{u,r}>v_{t,r} \quad\text{whenever $t$ is a donor and $u$ is a recipient for $r$.} \]
Thus every donor–recipient pairing strictly improves welfare.
The targets are optimal for this resource. Indeed, for any vector \(w_t\) satisfying \(0\leq w_t\leq\mu_t\) and \(\sum_t w_t=\rho_r\),
\[ \sum_t v_{t,r}(w_t-z_{t,r}) = \sum_t (v_{t,r}-\lambda_r)(w_t-z_{t,r}) \leq 0. \]
The equality uses equal total supply. Each summand is nonpositive: on \(H_r\), \(z_{t,r}=\mu_t\); on \(F_r\), \(z_{t,r}=0\); and on \(E_r\), the coefficient vanishes. This argument also covers signed values.
Index the positive entries of \(y^0\) by \(p\), writing them as
\[ (t_p,S_p,q_p),\qquad p\in\{1,\ldots,k\}. \]
For every \(p,r\), choose a mass \(a_{p,r}\in[0,q_p]\) whose possession of \(r\) will be toggled.
For a donor type \(t\), distribute its required removal \(x^0_{t,r}-z_{t,r}\) among its initial entries containing \(r\), greedily taking up to each entry’s mass. This is possible because their total mass is \(x^0_{t,r}\).
For a recipient type \(t\), similarly distribute its required addition \(z_{t,r}-x^0_{t,r}\) among its initial entries lacking \(r\). Their total mass is \(\mu_t-x^0_{t,r}\), which is sufficient.
All other \(a_{p,r}\) are zero. Therefore, whenever \(a_{p,r}>0\), it specifies a removal from a donor or an addition to a recipient.
Represent entry \(p\), solely for bookkeeping, by an interval of length \(q_p\). For resource \(r\), designate its prefix of length \(a_{p,r}\) for toggling. Cut this interval at every distinct point among
\[ 0,\quad q_p,\quad a_{p,r}\ \text{for }r\in R. \]
There are at most \(m+1\) resulting positive-length intervals. Each resulting labelled cohort has a rational mass, its original type and bundle, and a fixed set of resources to toggle.
Let \(N\) be the total number of labelled cohorts. Then
\[ N\leq k(m+1). \]
This refinement changes no individual’s bundle. It is bookkeeping, not a deal. Nonatomicity permits the finite subdivisions of the specified masses.
Each designated prefix is a union of whole labelled cohorts. Hence, for every resource, the labelled donor cohorts have exactly the required total removal mass, and the labelled recipient cohorts have exactly the required total addition mass.
Process resources in a fixed order.
At the beginning of each resource’s processing, maintain this invariant:
Every labelled cohort has one uniform bundle. Previously processed resources have their prescribed final possession status; unprocessed resources retain their initial status.
The invariant holds initially.
Fix the current resource \(r\). Form two lists:
Their total masses agree, since
\[ \sum_{t:z_{t,r}<x^0_{t,r}}(x^0_{t,r}-z_{t,r}) = \sum_{t:z_{t,r}>x^0_{t,r}}(z_{t,r}-x^0_{t,r}). \]
Match these lists greedily. Take a donor cohort with remaining untransferred mass \(d>0\) and a recipient cohort with remaining untransferred mass \(b>0\), and set
\[ \varepsilon=\min\{d,b\}. \]
Let their remaining individuals’ bundles be \(S\) and \(B\), and their types be \(t\) and \(u\). Because \(r\) is unprocessed, \(r\in S\setminus B\). Perform the specified mass \(1\)-deal with mass \(\varepsilon\), and reduce both remaining masses accordingly.
This deal is valid for three reasons.
First, the aggregate allocation entries satisfy
\[ y_{t,S}\geq d\geq\varepsilon,\qquad y_{u,B}\geq b\geq\varepsilon. \]
Labels merely identify subcohorts within those entries. Combining coincident entries does not invalidate these inequalities.
Second, the two selected cohorts are disjoint. In fact, the strict value inequality proved earlier implies \(t\neq u\).
Third, its welfare change is
\[ W(y_{\mathrm{after}})-W(y_{\mathrm{before}}) = \varepsilon(v_{u,r}-v_{t,r})>0. \]
Thus every emitted deal is admissible. Each deal preserves type masses, all supplies, and nonnegativity: it changes only the possession of \(r\), removing and adding equal mass.
Transferred individuals are not selected again while processing \(r\). A partially processed labelled cohort therefore has only two bundle states: its bundle before toggling \(r\), and that bundle with \(r\) toggled.
Every deal exhausts at least one remaining cohort. Equal total masses ensure that both lists finish together. At completion, every designated cohort has been entirely toggled, so every labelled cohort is uniform again. Other resources have remained unchanged. This proves the invariant for the next resource.
If the two lists contain \(n_D\) and \(n_A\) cohorts, a nonempty processing phase uses at most \(n_D+n_A-1\) deals: every deal exhausts at least one cohort, and the final deal exhausts both remaining cohorts. Since the lists are disjoint subsets of the \(N\) cohorts, the total number of deals is at most
\[ mN\leq mk(m+1). \]
At any intermediate point, each labelled cohort occupies at most two bundles, so the allocation has at most \(2N\) positive entries.
After all resources have been processed, aggregate labelled cohorts with identical type and bundle to obtain \(y^\star\). It has at most \(N\) positive entries.
For every \(t,r\), precisely the designated removal or addition mass has changed possession. Therefore,
\[ x_{t,r}(y^\star)=z_{t,r}. \]
For any feasible allocation \(y\), the marginal optimality established in Section 1 gives
\[ W(y) = \sum_r\sum_t v_{t,r}x_{t,r}(y) \leq \sum_r\sum_t v_{t,r}z_{t,r} = W(y^\star). \]
Thus \(y^\star\) is globally welfare-maximizing, and the constructed sequence reaches it using only admissible deals. If no transfers are needed, the sequence is empty.
If \(m=0\), simply return \(y^0\) and the empty sequence; every feasible allocation has welfare zero.
Let \(D\) be the product of the denominators of all input masses, supplies, and positive entries of \(y^0\), in their binary rational representations. Its binary length is \(O(L)\).
Every mass computed above is obtained using additions, subtractions, minima, or comparisons. Consequently, every such mass is an integer multiple of \(1/D\). All cohort masses, allocation entries, and deal masses lie in \([0,1]\), so they admit rational representations of bit length \(O(L)\).
The construction requires:
These involve polynomially many arithmetic operations and comparisons on polynomial-length numbers. Each bundle is represented by \(m\) bits, and both requested outputs have polynomial length. Hence the full algorithm runs in time polynomial in \(m,\tau,k,L\).
The [finite-agent result of Endriss et al., Theorem 3](https://www.doc.ic.ac.uk/~fs/Papers/Multi-agent%20systems/EndrissEtAlJAIR2006.pdf) establishes convergence for additive utilities. The proof here independently supplies the bounded constructive sequence required by the continuous problem.
Arbitrary improving continuous schedules can be infinite: with two types of mass \(1/2\), one resource initially held entirely by the lower-valued type, repeatedly transferring half the remaining misplaced mass gives infinitely many strictly improving deals. The polynomial guarantee concerns the explicitly constructed schedule.
⟨structured verdict parsed — rendered above⟩
Result: proved. The output resolves both parts of the task: it constructs a rational welfare-maximizing allocation and a polynomial-length sequence of admissible mass \(1\)-deals reaching it. The support, deal-count, and bit-length bounds are justified. No major or minor mathematical issues were found.
The marginal constraints follow directly from feasibility: each type’s possession mass lies between zero and its total mass, and summing possession masses over types gives the prescribed supply. The welfare decomposition follows from additive values and finite summation.
The threshold \(\lambda_r\) exists as stated. Normalization and positive type masses ensure that the support is nonempty and that cumulative mass reaches every supply in \([0,1]\). The zero-supply choice satisfies the threshold inequalities; supply one is also covered.
The tied-type adjustment is feasible. Increasing tied marginals has total available capacity equal to their total type mass minus \(e_r\); decreasing them has total available mass \(e_r\). The stated bounds on \(h_r\) ensure that the required adjustment fits these capacities.
The strict donor–recipient ordering is valid:
Therefore, a donor and recipient cannot both have threshold value. Together with their respective weak value bounds, this establishes the asserted strict inequality. Equal-valued transfers are never required.
The resource-optimality calculation is correct. Equal total supply justifies subtracting the threshold term. The signs of the remaining summands follow from the upper bound on high-valued types and the lower bound on low-valued types. The argument applies to signed values.
Assessment: Correct and complete.
For each donor, the requested removal does not exceed its initial possession mass. For each recipient, the requested addition does not exceed its initially unpossessed mass. Thus both greedy distributions are feasible.
Every selected prefix length belongs to its initial entry’s interval. At most \(m\) internal cut points yield at most \(m+1\) positive-length pieces per entry, establishing
\[
N\leq k(m+1).
\]
Cutting at every designated prefix endpoint ensures that each resource designation is a union of whole labelled cohorts. Consequently, the refinement preserves the exact required transfer totals.
This is legitimate bookkeeping under nonatomicity. It neither changes the allocation nor introduces an unrecorded negotiation step.
Assessment: Correct and complete.
The resource-processing invariant is sufficient for the construction. At the start of a phase, every labelled cohort is uniform. During that phase, an untransferred remainder retains its pre-transfer bundle because transferred individuals are excluded from further matching.
For the current resource, donor remainders possess it and recipient remainders lack it. Therefore the condition \(r\in S\setminus B\) holds whenever a deal is emitted.
The aggregate-entry inequalities are justified: each selected remainder is contained within the corresponding current allocation entry. Aggregating coincident entries preserves this containment and the required mass bounds.
The strict value ordering ensures that donor and recipient types differ, so their selected cohorts are disjoint. This also avoids any issue involving subtracting twice from a common selected entry.
The welfare-change formula is correct. Each participating bundle changes by exactly the current resource, giving
\[
W(y_{\mathrm{after}})-W(y_{\mathrm{before}})
=\varepsilon(v_{u,r}-v_{t,r})>0.
\]
This is precisely the task’s admissibility criterion. No separate side-payment construction is required by the requested output.
The updates preserve nonnegativity, type masses, and supplies.
Assessment: Every emitted operation is a valid admissible mass \(1\)-deal.
Equal donor and recipient totals follow from equality of initial and target supplies.
Every greedy match exhausts at least one remainder. The two lists finish together, and the final match exhausts both participating remainders. Hence the bound of \(n_D+n_A-1\) deals for a nonempty phase is correct.
The lists are disjoint subsets of the fixed labelled cohorts, so summing over resources gives the stated bound
\[
mN\leq mk(m+1).
\]
Temporary splitting does not accumulate across resource phases. During a phase, a labelled cohort has at most its untoggled and toggled bundle states. At completion, every designated cohort has been fully toggled and becomes uniform again. This establishes both the intermediate support bound of \(2N\) and the final support bound of \(N\).
Assessment: The finite sequence and all stated support bounds are justified.
The final resource marginals equal the targets because exactly the designated removal and addition masses have been transferred.
The resourcewise optimality inequalities apply to the marginals of every feasible allocation. Summing them proves global welfare optimality of the constructed feasible allocation. The construction itself establishes simultaneous realizability of the target marginals.
The stated edge cases are covered:
Assessment: The claimed final allocation satisfies the complete task.
The product \(D\) has binary length bounded by the sum of the input denominator lengths, hence \(O(L)\).
All mass computations use additions, subtractions, and selection by minima or comparisons. They therefore preserve the common denominator grid. The relevant masses lie in \([0,1]\), so their numerators and denominators admit \(O(L)\)-bit representations.
Value comparisons also have polynomial bit complexity because the rational values are part of the input.
The listed sorting, distribution, refinement, matching, and aggregation procedures require polynomially many operations. Bundles have \(m\)-bit representations, and the established support and deal-count bounds give polynomial output length.
Assessment: The claimed polynomial running time is justified in the binary input model.
The cited finite-agent theorem does concern convergence of individually rational \(1\)-deals in additive scenarios. Its finite setting and monetary-payment context agree with the comparison made in Section 6. The continuous construction does not invoke that theorem to establish any essential step. See [Endriss et al., Theorem 3](https://www.doc.ic.ac.uk/~fs/Papers/Multi-agent%20systems/EndrissEtAlJAIR2006.pdf).
The example of an infinite improving continuous schedule is also valid: each transfer leaves a positive misplaced remainder, and each finite step strictly improves welfare. It does not contradict the polynomial bound for the explicitly constructed schedule.
No mathematical repairs or additional clarifications are 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.