Answer: polynomial-time solvable; exact optimization is possible
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven two agents with known valuations which are MAX-SUM-ALL read-once functions, it is NP- hard to find an allocation whose welfare is more than 1 2 of the welfare of the optimal allocation. The proof is in Appendix D. Notice that achieving welfare of at least half the optimal is easy because we can simply give all the items to the agent who values the total the most. This shows that it is NP-hard to do any better. 5.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) item categories, \(\tau\) types with known MAX-SUM-ALL read-once valuations \(v_t\), rational masses \(\mu_t\) summing to \(1\), and rational per-person supplies \(b_i\), compute the exact maximum welfare and a maximizing allocation. Each person receives an integral bundle \(S\subseteq[n]\); the allocation assigns mass \(x_{t,S}\ge 0\) of type \(t\) to bundle \(S\), with \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:i\in S}x_{t,S}\le b_i\). The objective is to maximize \(\sum_{t,S}x_{t,S}v_t(S)\), with complexity measured in \(n\), \(\tau\), the formula sizes, and input bit length \(L\).
There are \(m\ge1\) item categories. A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not all possible types.
Each type has an explicitly given read-once valuation tree: each category labels at most one leaf, which returns its positive binary-rational weight when present in a bundle and zero otherwise. Internal gates have at least two children: SUM adds their outputs, MAX takes their maximum, and ALL adds their outputs if every output is positive and returns zero otherwise. The root defines \(v_t(S)\) for \(S\subseteq\{1,\ldots,m\}\), including the empty bundle.
Supplies \(b_i\ge0\) are binary rationals. A feasible allocation assigns masses \(x_{t,S}\ge0\) with \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:i\in S}x_{t,S}\le b_i\). Each person receives an integral bundle; supplies may remain unused. Write \(W(x)=\sum_{t,S}x_{t,S}v_t(S)\) and \(\mathrm{OPT}=\max_x W(x)\). Let \(F\) be the total formula size and \(L\) the total input bit length.
Is finding a feasible allocation with \(W(x)>\mathrm{OPT}/2\) whenever \(\mathrm{OPT}>0\) solvable in time polynomial in \(m,\tau,F,L\), or is it NP-hard?
For two discrete agents with these valuations, obtaining welfare strictly greater than \(\mathrm{OPT}/2\) is NP-hard, while welfare at least \(\mathrm{OPT}/2\) is attainable in polynomial time. [Zinkevich, Blum, and Sandholm](https://www.cs.cmu.edu/~sandholm/www/polytime_preference_elicitation.acmec03.pdf)
No result settling this precise mass-allocation approximation question was identified in the literature search.
The problem is polynomial-time solvable. In fact, an exactly optimal allocation can be computed, with polynomially many supported bundles and rational masses of polynomial encoding length.
The proof constructs a polynomial-size linear program and explicitly converts any feasible solution into an allocation of integral bundles.
Fix a type and its valuation tree. For a node \(u\), let \(v_u\) be the valuation defined by the subtree rooted at \(u\).
Lemma 1. Every bundle \(S\) has a subbundle \(S'\subseteq S\) with the same root valuation and the following structure:
Here, “active” means that the retained subtree valuation is positive.
Proof. Proceed recursively. If \(v_u(S)=0\), discard every item below \(u\). Otherwise:
Children have disjoint category sets because the tree is read-once. Consequently, these operations preserve the value at \(u\) and retain only items originally present. Applying the construction at the root proves the claim. \(\square\)
Call the resulting bundles pruned bundles. For such a bundle, its value equals the sum of the weights of its retained leaves: SUM and active ALL nodes add their children’s values, while an active MAX node has only one active child.
Replacing every allocated bundle by its pruned subbundle preserves welfare and weakly decreases every category’s consumption. Thus an optimal allocation can be assumed to use pruned bundles.
For each type \(t\) and each node \(u\) of its tree, introduce a variable \(z_{t,u}\), representing the mass for which that node is active. Let \(r_t\) denote the root, \(C(u)\) the children of \(u\), and \(w_{t,\ell}\) the weight of leaf \(\ell\).
Impose nonnegativity \(z_{t,u}\ge 0\), root bounds \(z_{t,r_t}\le\mu_t\), and these gate constraints:
| Gate at \(u\) | Constraints |
|---|---|
| SUM | \(z_{t,c}\le z_{t,u}\) for every \(c\in C(u)\), and \(z_{t,u}\le\sum_{c\in C(u)}z_{t,c}\) |
| MAX | \(\sum_{c\in C(u)}z_{t,c}=z_{t,u}\) |
| ALL | \(z_{t,c}=z_{t,u}\) for every \(c\in C(u)\) |
For category \(i\), impose the supply constraint
\(\sum_{t,\ell:\,\ell\text{ labels }i}z_{t,\ell}\le b_i\).
Maximize the linear objective
\(Q(z)=\sum_{t,\ell\text{ a leaf}}w_{t,\ell}z_{t,\ell}\).
The program has \(O(F)\) variables and \(O(F+m+\tau)\) constraints, with polynomial input encoding length. It is feasible at \(z=0\). Every child variable is at most its parent variable, so every variable for type \(t\) is at most \(\mu_t\); hence the feasible region is bounded.
Every allocation of pruned bundles induces a feasible LP solution by taking activation masses. In particular, the SUM lower bound follows because every active SUM node has at least one active child. Its objective equals the allocation’s welfare. Therefore the LP optimum is at least \(\mathrm{OPT}\).
It remains to prove the converse, including efficient reconstruction.
Lemma 2. Every rational feasible LP solution \(z\) can be converted, in polynomial time, into an allocation with welfare \(Q(z)\).
Proof. Treat each type separately and suppress the type subscript. Represent its mass by the interval \(I=[0,\mu)\). We construct, for every node \(u\), a set \(A_u\subseteq I\) of measure \(z_u\). These sets will specify which people activate that node.
Set \(A_r=[0,z_r)\). Construct children’s sets from their parent’s set, proceeding from the root downward.
Suppose \(A_u\) has measure \(a=z_u\). If \(a=0\), every child variable is zero, and we assign empty sets to all children. Assume henceforth that \(a>0\).
Because \(A_u\) is a finite union of half-open intervals, traversing those intervals from left to right gives a measure-preserving bijection \(\phi_u:[0,a)\to A_u\). We specify child sets in this measure coordinate and then apply \(\phi_u\).
ALL. Set \(A_c=A_u\) for every child. The equalities \(z_c=a\) give the required measures.
MAX. Order the children as \(c_1,\ldots,c_k\), and put \(s_0=0\) and \(s_j=\sum_{h=1}^jz_{c_h}\). Since \(s_k=a\), the intervals \([s_{j-1},s_j)\) partition \([0,a)\). Define
\(A_{c_j}=\phi_u([s_{j-1},s_j))\).
Thus the children partition the parent’s active mass, and each has its prescribed measure.
SUM. Use the same cumulative sums \(s_j\). Here \(0\le z_{c_j}\le a\) and \(s_k\ge a\). Let \(B_j\subseteq[0,a)\) be the image of \([s_{j-1},s_j)\) under reduction modulo \(a\), and define \(A_{c_j}=\phi_u(B_j)\).
An interval of length \(z_{c_j}\le a\) has modulo-\(a\) image of measure exactly \(z_{c_j}\). Moreover, the consecutive intervals together form \([0,s_k)\), which contains \([0,a)\). Their modulo-\(a\) images therefore cover \([0,a)\). Consequently, the children have their prescribed measures and cover \(A_u\).
This construction gives the following pointwise properties:
For a person at position \(q\in I\), assign precisely the categories of leaves \(\ell\) satisfying \(q\in A_\ell\).
An inactive node has no active descendant, so its subtree value is zero. An active leaf has positive weight. Induction upward now shows that every active internal node has positive value and that its value equals the sum of the weights of its active descendant leaves. In particular, each person receives an integral pruned bundle with its intended value.
Leaf \(\ell\) is assigned to mass exactly \(z_\ell\). Thus, after performing this construction for every type, category consumption is exactly the left-hand side of its LP supply constraint, and total welfare is \(Q(z)\). The entire interval of each type is allocated, including the people receiving the empty bundle.
Each constructed set is a finite union of intervals. At a MAX or SUM gate, a child’s set in the parent’s measure coordinate has at most two interior boundary points. Pulling it back through \(\phi_u\) introduces at most two new endpoints in the original person interval; all other endpoints are inherited from the parent’s set.
Thus a tree with \(N\) nodes introduces only \(O(N)\) distinct endpoints. Partitioning \(I\) at all these endpoints produces \(O(N)\) intervals on each of which every leaf’s activity is constant. Output one bundle and its interval length for each nonempty interval. This gives \(O(N)\) supported bundles for that type.
For bit complexity, let \(D\) be the product of the denominators of \(\mu\) and the values \(z_u\). Its bit length is at most the sum of their encoding lengths. Every endpoint constructed above is an integer multiple of \(1/D\): the operations use sums, differences, and reduction modulo a quantity that is itself such a multiple. Pullback through \(\phi_u\) uses only translations of interval coordinates.
All endpoints lie in \([0,\mu]\subseteq[0,1]\), so endpoints and output masses have encoding length polynomial in that of \(z\). Interval manipulation and extraction of the bundles therefore take polynomial time. \(\square\)
Lemma 1 shows that the LP optimum is at least \(\mathrm{OPT}\). Lemma 2 converts an optimal LP solution into a feasible allocation with the same objective, proving that the LP optimum is also at most \(\mathrm{OPT}\). Hence they are equal.
Polynomial-time rational linear programming applies because the program is explicitly given, feasible, bounded, and has polynomial encoding length. It produces an optimal rational solution of polynomial encoding length. Lemma 2 then produces an explicit optimal allocation in time polynomial in \(m,\tau,F,L\).
Therefore the returned allocation satisfies \(W(x)=\mathrm{OPT}\), and whenever \(\mathrm{OPT}>0\), it satisfies \(W(x)>\mathrm{OPT}/2\).
The [cited discrete-agent result](https://www.cs.cmu.edu/~sandholm/www/polytime_preference_elicitation.acmec03.pdf) requires choosing a single bundle for each agent. Here each supported type may split its mass among multiple bundles, and supply constraints restrict their aggregate consumption. The reconstruction above uses precisely this permitted splitting while keeping every person’s bundle integral.
The number of supported types enters only through the explicitly supplied trees and root bounds. No enumeration of unsupported types is needed.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The LP captures the attainable activation masses exactly, and the reconstruction produces a feasible allocation with polynomial output size and polynomial bit complexity. No major or minor mathematical issues were found.
Lemma 1 is correct.
Read-once labeling ensures that changes within one child’s category set do not affect another child. The construction retains only originally present categories. Categories absent from the tree need not be retained.
For a pruned bundle, the claimed equality between root value and the sum of retained leaf weights follows from the specified gate behavior: SUM and active ALL add, and active MAX has exactly one active child.
Replacing bundles with pruned subbundles consequently preserves welfare and weakly decreases consumption. This establishes that restricting to pruned bundles does not change the optimum.
Each gate constraint correctly describes necessary activation-mass relations.
A retained leaf corresponds exactly to consuming its category. Therefore the supply constraints and objective correctly represent consumption and welfare.
The size bounds are correct: there is one variable per node and only a constant number of constraints per tree edge, besides root and supply constraints. All coefficients have polynomial total encoding length.
Boundedness also follows as written. Every child variable is bounded by its parent variable, including at MAX nodes by nonnegativity and the sum equality. Root bounds therefore bound all variables. The zero solution establishes feasibility.
Thus the allocation-to-LP direction correctly gives LP optimum at least \(\mathrm{OPT}\).
The construction in Lemma 2 is valid for every rational feasible LP solution.
Zero mass. When a parent has zero mass, the constraints force every child mass to be zero. Assigning empty sets is consistent.
Measure coordinates. Traversing the finitely many half-open component intervals defines the stated measure-preserving bijection. The half-open convention makes boundary membership unambiguous.
ALL. Copying the parent set gives each child its required measure and the required simultaneous activation.
MAX. The cumulative intervals partition the parent’s measure coordinate because their lengths sum to its mass. Mapping these intervals into the parent set gives exactly one active child at every active position.
SUM. Both critical assertions hold:
Hence the SUM children have the prescribed measures and cover the parent set. Overlap is permitted and matches SUM behavior.
The pointwise induction is sound. Child sets lie inside parent sets, so an inactive node has no active descendant leaves. Positive leaf weights and the constructed child-activation rules ensure that an active internal node has positive value.
The same rules make each active node’s value equal to the sum of its active descendant leaf weights. This verifies the objective equality for the actual valuation functions, including ALL gates.
Read-once labeling ensures that assigning active leaves defines an integral bundle without repeated-category counting. Leaf measures give exactly the LP’s category consumption. Allocating the entire type interval also accounts for the required mass, including recipients of the empty bundle.
Therefore every reconstructed allocation is feasible and has welfare \(\mathrm{Q}(z)\).
The endpoint argument is correct and avoids exponential fragmentation.
A MAX child occupies one coordinate interval. A SUM child occupies at most two coordinate intervals, with at most two boundary points strictly inside the parent coordinate domain. Under the piecewise-translation bijection, these points introduce at most two new endpoints in the original interval. Other boundaries occur at endpoints already belonging to the parent set.
Since the tree has linearly many parent-child edges, the global collection of endpoints has size linear in its number of nodes. Partitioning at those endpoints makes every leaf’s membership constant on each resulting interval. Thus the stated linear bound on output bundle entries follows. Repeated bundles can be represented by their combined masses without increasing output size.
The denominator argument is also valid. The product \(\mathrm{D}\) has bit length bounded by the sum of input denominator lengths. Sums, differences, modulo operations, and coordinate translations preserve the grid of multiples of \(1/\mathrm{D}\). Original-coordinate endpoints remain between zero and the type mass, so their numerators have polynomial bit length.
Consequently, the interval representations, arithmetic, and explicit bundle extraction all require polynomial time in the encoding length of the rational LP solution and the original input.
The rational linear-programming theorem is invoked with the needed hypotheses: an explicitly encoded rational LP, polynomial encoding length, a nonempty feasible region, and boundedness. Its stated conclusion—polynomial-time production of an optimal rational solution with polynomial encoding length—is applicable.
Combining the two established directions gives equality between the LP optimum and \(\mathrm{OPT}\). Reconstruction therefore yields an exactly optimal feasible allocation in time polynomial in the specified input parameters.
The strict approximation guarantee follows immediately when \(\mathrm{OPT}>0\). The construction also handles zero optimum, zero supplies, leaf-only trees, unused categories, and unused supplies.
The explanation of why the discrete hardness result does not invalidate this construction is correct. The mass-allocation model permits each supported type to distribute its mass among several bundles; discrete agents must each receive a single bundle. The cited paper’s Theorem 6 concerns the latter setting. [Zinkevich, Blum, and Sandholm, Theorem 6](https://www.cs.cmu.edu/~sandholm/www/polytime_preference_elicitation.acmec03.pdf).
The argument uses only explicitly supported types and their trees. It therefore addresses the precise representation and complexity requirement in the task.
Repair feedback: None required.
⟨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.