Answer: Exactly polynomial-time solvable under the original supplies; therefore the requested scheme exists.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMulti-unit combinatorial auctions with multi- minded bidders and a constant number of distinct goods ad- mit a truthful FPTAS, that optimizes the social welfare fully, while violating the supplies of goods at most by a factor (1 + ϵ), for any fixed ϵ > 0. Computational Hardness Note that this problem is strongly NP-hard, when we do not allow violation of supply constraints and m ≥2 [Chekuri and Khanna, 2000]. It is well known that if a problem is strongly NP-hard, it does not admit an FPTAS, unless P=NP, see, e.g., [Vazirani, 2003]. Also the assumption that m is a fixed constant is necessary.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a constant number \(m\) of goods, a finite set \(T\) of bidder types with rational masses \(\mu_t\) summing to \(1\), explicitly listed integral bundles \(D_t\) with rational values \(v_t(d)\), and rational per-capita supplies \(b_\ell\), choose masses \(x_{t,d}\ge 0\) to maximize \(\sum_{t\in T}\sum_{d\in D_t}v_t(d)x_{t,d}\), subject to \(\sum_{d\in D_t}x_{t,d}\le\mu_t\) for each \(t\) and \(\sum_{t\in T}\sum_{d\in D_t}d_\ell x_{t,d}\le b_\ell\) for each good \(\ell\).
Fix a constant number \(m\ge 1\) of goods. A society is given by its support: an explicit list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Each type has an explicitly listed nonempty demand set \(D_t\subseteq\mathbb Z_{\ge0}^{m}\setminus\{0\}\) and positive binary-rational values \(v_t(d)\). Require \(v_t(d)\le v_t(e)\) whenever \(d\le e\) componentwise. The value of any integral bundle \(a\) is \(\max(\{v_t(d):d\in D_t,\ d\le a\}\cup\{0\})\).
Supplies \(b_\ell\) are positive binary rationals measured per capita; individual bundles need not satisfy \(d_\ell\le b_\ell\). Mass may be split among alternatives, with unassigned mass receiving nothing.
For \(x_{t,d}\ge0\), write \(W(x)=\sum_{t\in T}\sum_{d\in D_t}v_t(d)x_{t,d}\). Let \(\mathrm{OPT}(b)\) be the maximum of \(W(x)\) subject to \(\sum_{d\in D_t}x_{t,d}\le\mu_t\) and \(\sum_{t\in T}\sum_{d\in D_t}d_\ell x_{t,d}\le b_\ell\).
Let \(K=\sum_{t\in T}|D_t|\) and let \(L\) be the total binary encoding length of the instance.
Does this mass-allocation problem admit, for every rational \(0<\varepsilon<1\), an algorithm returning \(x\) with \(W(x)\ge\mathrm{OPT}(b)\), \(\sum_{d\in D_t}x_{t,d}\le\mu_t\), and \(\sum_{t\in T}\sum_{d\in D_t}d_\ell x_{t,d}\le(1+\varepsilon)b_\ell\), in time polynomial in \(\tau,K,L,1/\varepsilon\) for each fixed \(m\) (with polynomial degree allowed to depend on \(m\)); or can such a scheme be ruled out unless \(\mathrm P=\mathrm{NP}\)?
For indivisible bidders and constant \(m\), a truthful FPTAS attains at least the optimum welfare under the original supplies while exceeding each supply by at most \(1+\varepsilon\). [Krysta–Telelis–Ventre](https://ranger.uta.edu/~weems/NOTES6319/PAPERSTWO/Mechanisms_for_Multi-unit_Comb.pdf).
No result specifically addressing the stated mass model was located in the search.
Yes. The stated mass-allocation problem is exactly solvable in polynomial time, without any supply augmentation. This holds even when \(m\) is part of the input.
The decisive premise is that mass may be split: the allocation variables are continuous. Thus the linear program in the question describes the allocation problem itself.
Let \(I=\{(t,d):t\in T,\ d\in D_t\}\), so \(|I|=K\). Define a matrix \(A\) with \(K\) columns indexed by \(I\) and \(\tau+m\) rows as follows:
Let \(h\) consist of the masses followed by the supplies, and set \(c_{(t,d)}=v_t(d)\). The optimization problem is precisely
\( \displaystyle \max\{c^\top x:Ax\le h,\ x\ge0\}. \)
All coefficients are rational and explicitly available from the input. The program has \(K\) variables and \(\tau+m+K\) inequalities when nonnegativity is included.
Its encoding length is polynomial in \(\tau,K,m,L\). Indeed, even a dense representation introduces only \(K(\tau+m)\) matrix entries; the demand coordinates are copied from the input, and the additional entries are zeros and ones. In particular, no expansion of rational masses into individual bidders is required.
The feasible set is nonempty because \(x=0\) is feasible.
For every feasible point and every \((t,d)\in I\), nonnegativity and the type constraint imply
\( \displaystyle 0\le x_{t,d}\le\sum_{e\in D_t}x_{t,e}\le\mu_t\le1. \)
Consequently, the feasible set is bounded. It is also closed, being defined by finitely many non-strict linear inequalities. Therefore it is compact, and the continuous objective attains a finite maximum.
We apply the standard polynomial-time theorem for rational linear programming: an explicitly encoded rational linear program can be solved in time polynomial in its binary encoding length; when feasible with finite optimum, an exact rational optimal solution can be returned. The relevant complexity is bit complexity, including coefficient lengths. This classical result is recalled in [Adler–Beling, *Polynomial Algorithms for Linear Programming over the Algebraic Numbers*, Introduction](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).
Every hypothesis has now been checked: the program is explicit, rational, feasible, and bounded. Hence an exact rational optimizer \(x^\star\) is computable in time polynomial in \(\tau,K,m,L\).
There is also no obstruction from the size of the exact output. To see this, let \(S\) be the program’s binary encoding length. A bounded nonempty polyhedron has an optimal vertex. At a vertex, \(K\) linearly independent active constraints determine its coordinates. Clearing denominators in those equations produces an integer system whose coefficients and right-hand side have absolute values at most \(2^{2S}\). Cramer’s rule and the determinant expansion bound every coordinate’s numerator and denominator by \(K!2^{2SK}\). Their bit lengths are therefore \(O(K(S+\log K))\), which is polynomial. Output rationals can be represented by binary numerators and denominators.
Return the exact optimizer \(x^\star\) under the original supplies. By its optimality and feasibility,
\( \displaystyle W(x^\star)=\mathrm{OPT}(b), \)
\( \displaystyle \sum_{d\in D_t}x^\star_{t,d}\le\mu_t\qquad(t\in T), \)
and
\( \displaystyle \sum_{t\in T}\sum_{d\in D_t}d_\ell x^\star_{t,d}\le b_\ell\le(1+\varepsilon)b_\ell\qquad(\ell=1,\ldots,m). \)
These are stronger than the requested guarantees. The allocation algorithm does not use \(\varepsilon\), so its running time is certainly polynomial in \(\tau,K,L,1/\varepsilon\) for every fixed \(m\).
In the [Krysta–Telelis–Ventre setting](https://ranger.uta.edu/~weems/NOTES6319/PAPERSTWO/Mechanisms_for_Multi-unit_Comb.pdf), each bidder receives one alternative or nothing. Here, a type’s mass may be distributed among alternatives, so the continuous variables have their stipulated allocation meaning.
Integral demand coordinates do not impose integrality on allocated mass. For example, with \(m=1\), one type of mass \(1\), demand set \(\{(2)\}\), value \(1\), and supply \(1\), the mass allocation \(x_{t,(2)}=1/2\) is feasible and optimal.
Thus exact linear programming settles the intended mass model, including demands larger than per-capita supplies. No additional restriction or interpretation is needed.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated mass-allocation problem. Its exact polynomial-time algorithm satisfies stronger guarantees than requested. No major or minor mathematical issues were found.
The index set \(I\) contains precisely one variable for every explicitly listed type–demand pair, so its cardinality is \(K\). The type rows enforce the mass constraints, the good rows enforce the supply constraints, and the objective equals \(W(x)\).
Crucially, USER_TASK explicitly permits splitting mass and defines \(\mathrm{OPT}(b)\) using these continuous variables. Thus there is no omitted integrality constraint or unproved equivalence with a discrete allocation problem. The monotonicity assumption on values introduces no additional constraint on \(x\).
There are \(K\) variables and \(\tau+m+K\) inequalities, counting nonnegativity. The dense matrix has \(K(\tau+m)\) entries. Its nonconstant entries, the right-hand side, and the objective coefficients are already explicitly encoded in the instance.
Adding zeros, ones, and indexing information requires only polynomial space. Large demand coordinates remain binary encoded; neither demands nor rational masses are expanded into individual units or bidders. The asserted polynomial encoding bound is valid.
The zero vector is feasible because masses and supplies are positive. For each coordinate, nonnegativity and its type constraint give
\(0\le x_{t,d}\le\mu_t\le1\).
Consequently, the feasible region is bounded. It is closed because all constraints are non-strict linear inequalities. It is therefore compact and nonempty, and the linear objective attains a finite maximum. Every premise used here holds under USER_TASK.
The prover states the needed theorem with the relevant computational interpretation: an explicitly encoded rational LP admits polynomial-time solution in binary encoding length, including an exact rational optimizer when feasible with finite optimum. This is a valid standard theorem.
Its hypotheses have been checked: all coefficients are rational, the formulation is explicit, and feasibility and finite optimality have been established. The cited [Adler–Beling introduction](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf) confirms polynomial-time solvability of rational LPs with dependence on binary input length. The invocation requires neither fixed dimension nor a strong-polynomial-time algorithm.
A nonempty bounded polyhedron has an optimal vertex for a linear objective. At a vertex in \(K\)-dimensional variable space, \(K\) linearly independent active constraints determine the coordinates; this remains true for degenerate vertices.
The denominator-clearing bound is valid: the total encoding length \(S\) bounds the combined denominator bit lengths, and \(2^{2S}\) is a conservative bound on the resulting integer entries. For a nonsingular \(K\times K\) system with entries and right-hand side bounded by that quantity, determinant expansion gives the stated bound \(K!2^{2SK}\) for both Cramer determinants.
Hence coordinate numerators and denominators have bit length \(O(K(S+\log K))\). The entire vector, consisting of \(K\) coordinates, also has polynomial encoding length. This argument establishes representability; the cited LP theorem supplies the polynomial-time computation.
Exact optimality gives \(W(x^\star)=\mathrm{OPT}(b)\), and feasibility gives every type constraint and every original supply constraint. Since \(b_\ell>0\) and \(\varepsilon>0\), the inequality \(b_\ell\le(1+\varepsilon)b_\ell\) holds for every good.
The algorithm can ignore \(\varepsilon\) entirely. Its polynomial running time therefore meets the requested bound for every fixed \(m\). The stronger claim allowing variable \(m\) also follows from the explicit LP encoding.
The description of indivisible bidders receiving a demanded alternative or nothing agrees with the [Krysta–Telelis–Ventre paper](https://ranger.uta.edu/~weems/NOTES6319/PAPERSTWO/Mechanisms_for_Multi-unit_Comb.pdf). This comparison is explanatory and is not needed for the main proof.
In the example, feasibility requires \(x\le1\) and \(2x\le1\), while welfare equals \(x\). Thus \(x=1/2\) is indeed feasible and optimal. It correctly illustrates that integral demand coordinates do not force integral allocated mass.
Actionable feedback: No mathematical repair or additional clarification is 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.