Answer: Polynomial-time solvable in \(m,\tau,L\). A rational allocation attaining \(W^*\) and common rational item-linear prices giving exact utility and profit maximization can be computed.
Proposition 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 converges in a finite number of rounds. Upon convergence, y is a δ-optimal bundle, and it maximizes the buyer’s utility (seller’s profit) at prices p to within an additive error of δb (δs). If v = c, then observe that the only possible clearing prices are p = v = c. In this case, any procedure that finds clearing prices must elicit the complete information of one agent.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses of buyer types \(t\) and seller types \(s\), with complete bundle-value functions \(v_t\) and bundle-cost functions \(c_s\) on \(X=\{0,1\}^m\), find fractions \(q_{t,x}\) and \(r_{s,x}\) of each type assigned integral bundles, together with a price function \(p\). Require each type's fractions to sum to one, aggregate item demand to equal supply, and every bundle assigned positive mass to be within \(\varepsilon\) of that type's utility or profit maximum at \(p\); maximize welfare to within \(\varepsilon\) of the optimum. The permitted price class includes item-linear tariffs.
Let \(m\geq1\) and \(X=\{0,1\}^m\). A society is given by its support: nonempty lists \(T,S\) of buyer and seller types with positive binary-rational masses \(a_t,b_s\), respectively, each side totaling \(1\). The support size is \(\tau=|T|+|S|\), not the number of possible types.
Each type has a complete explicit table \(v_t:X\to\mathbb Q_{\geq0}\) or \(c_s:X\to\mathbb Q_{\geq0}\), monotone under bundle inclusion and zero at the empty bundle. Input also includes binary-rational \(\varepsilon>0\); \(L\) is the total input bit length, including these tables.
An allocation consists of rational fractions \(q_{t,x},r_{s,x}\geq0\) satisfying \(\sum_xq_{t,x}=\sum_xr_{s,x}=1\) for every respective type and \(\sum_{t,x}a_tq_{t,x}x=\sum_{s,x}b_sr_{s,x}x\).
Prices are a common unrestricted rational table \(p:X\to\mathbb Q\), including item-linear tariffs. Positive fractions must satisfy \(v_t(x)-p(x)\geq\max_{z\in X}(v_t(z)-p(z))-\varepsilon\) and, respectively, \(p(x)-c_s(x)\geq\max_{z\in X}(p(z)-c_s(z))-\varepsilon\); any splitting among qualifying bundles is permitted.
Define \(W(q,r)=\sum_{t,x}a_tq_{t,x}v_t(x)-\sum_{s,x}b_sr_{s,x}c_s(x)\), and let \(W^*\) be its maximum over all allocations satisfying the normalization and item-balance conditions. Find an allocation and prices satisfying the preceding conditions and \(W(q,r)\geq W^*-\varepsilon\).
Is this computational problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For one discrete buyer and seller, a kernel-based elicitation procedure terminates after finitely many rounds; successful termination gives a bundle whose welfare loss is at most the sum of its utility and profit errors. This is a finite-termination guarantee, not a polynomial-time bound. [Source](https://www.cs.cmu.edu/~sandholm/cs15-892F11/kernelMethodForMarketClearing.ijcai09.pdf)
No result settling this exact explicitly tabulated mass-allocation problem was identified in the literature search.
The problem is solvable in polynomial time in \(m,\tau,L\). In fact, one can compute a rational allocation with welfare exactly \(W^*\), together with common rational item-linear prices under which every positively allocated bundle is an exact utility or profit maximizer.
The proof uses the stated permission to split each type’s mass among bundles and the stated item-balance constraints.
Write \(n=|X|=2^m\). Introduce allocated-mass variables
\(y_{t,x}=a_tq_{t,x}\) and \(z_{s,x}=b_sr_{s,x}\).
Because all masses are positive, this change of variables is invertible:
\(q_{t,x}=y_{t,x}/a_t\) and \(r_{s,x}=z_{s,x}/b_s\).
Consider the linear program with objective
\( \operatorname{maximize}\quad \sum_{t\in T}\sum_{x\in X}v_t(x)y_{t,x} -\sum_{s\in S}\sum_{x\in X}c_s(x)z_{s,x}, \)
subject to
Call this program \((P)\). Its constraints are precisely the allocation constraints after the change of variables, and its objective is precisely welfare.
The feasible set is nonempty: assign all mass to the empty bundle. It is bounded, since normalization and nonnegativity imply
\(0\leq y_{t,x}\leq a_t\) and \(0\leq z_{s,x}\leq b_s\).
It is also closed. Thus the objective attains a finite maximum.
All coefficients are rational. A linear objective on a nonempty bounded rational polytope has a rational optimal vertex: an optimal face contains a vertex, and a vertex is determined by a full-rank system of active rational constraints. Consequently, allowing real variables in \((P)\) does not increase the maximum over rational allocations. Its optimal value is exactly the \(W^*\) in the question.
Associate unrestricted dual variables \(\alpha_t\), \(\beta_s\), and \(\pi_j\) with the buyer normalizations, seller normalizations, and item balances, respectively. Write
\(\pi\cdot x=\sum_{j=1}^m\pi_jx_j\).
The dual program \((D)\) is
\( \operatorname{minimize}\quad \sum_{t\in T}a_t\alpha_t+\sum_{s\in S}b_s\beta_s, \)
subject to
\( \alpha_t+\pi\cdot x\geq v_t(x) \quad(t\in T,\ x\in X), \)
and
\( \beta_s-\pi\cdot x\geq-c_s(x) \quad(s\in S,\ x\in X). \)
The signs follow directly from the item-balance constraints: a buyer variable has balance column \(x\), whereas a seller variable has balance column \(-x\).
The dual is feasible. Take \(\pi=0\),
\(\alpha_t=\max_{x\in X}v_t(x)\), and \(\beta_s=0\); the seller constraints then hold because \(c_s(x)\geq0\).
By linear-programming strong duality, since \((P)\) is feasible with finite optimum, \((D)\) has an attained optimum equal to \(W^*\). Both programs have rational optimal solutions.
Choose any optimal primal and dual solutions. Define the common tariff by
\( p(x)=\pi\cdot x \qquad(x\in X). \)
This is a permitted rational price table.
For completeness, the complementary-slackness argument can be checked directly.
Define the nonnegative dual slacks
\( d_{t,x}=\alpha_t+\pi\cdot x-v_t(x), \qquad e_{s,x}=\beta_s-\pi\cdot x+c_s(x). \)
For any primal-feasible and dual-feasible solutions, normalization and item balance give
\( \sum_ta_t\alpha_t+\sum_sb_s\beta_s-W(y,z) = \sum_{t,x}y_{t,x}d_{t,x} +\sum_{s,x}z_{s,x}e_{s,x}. \)
Indeed, expanding the right side produces the dual objective minus welfare, together with
\(\pi\cdot(\sum_{t,x}y_{t,x}x-\sum_{s,x}z_{s,x}x)\), which vanishes by item balance.
At optimality the left side is zero. Every summand on the right is nonnegative, so
\( y_{t,x}>0\Longrightarrow d_{t,x}=0, \qquad z_{s,x}>0\Longrightarrow e_{s,x}=0. \)
For a buyer, dual feasibility says
\( v_t(u)-p(u)\leq\alpha_t \qquad\text{for every }u\in X. \)
If \(q_{t,x}>0\), positivity of \(a_t\) implies \(y_{t,x}>0\), and the zero-slack condition gives
\(v_t(x)-p(x)=\alpha_t\). Therefore
\( v_t(x)-p(x)=\max_{u\in X}\bigl(v_t(u)-p(u)\bigr). \)
Similarly, seller dual feasibility says
\( p(u)-c_s(u)\leq\beta_s \qquad\text{for every }u\in X. \)
If \(r_{s,x}>0\), then \(z_{s,x}>0\), so
\(p(x)-c_s(x)=\beta_s\). Hence
\( p(x)-c_s(x)=\max_{u\in X}\bigl(p(u)-c_s(u)\bigr). \)
Thus all positive fractions satisfy the requested inequalities with zero error. The allocation also has welfare \(W^*\), and therefore satisfies the welfare requirement for every supplied \(\varepsilon>0\).
The relevant size is the explicit input length.
There are \(\tau n\) table entries. Each explicitly encoded rational entry occupies at least one bit, so \(\tau n=O(L)\). Enumerating all bundles therefore takes polynomial time in the stipulated input size.
Program \((P)\) has \(\tau n\) variables and \(\tau+m\) equality constraints, besides nonnegativity. Its coefficients are table entries, masses, and elements of \(\{0,1,-1\}\). Its full binary encoding has length polynomial in \(m,\tau,L\). The same holds for \((D)\).
The exact rational linear-programming theorem states that a rational LP can be solved, with infeasibility or unboundedness detected when applicable, in time polynomial in its binary encoding length. In the feasible finite-optimum case, it returns a rational optimal solution. See [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239). The hypotheses hold here, as verified above.
Solve both programs exactly, divide \(y_{t,x}\) by \(a_t\) and \(z_{s,x}\) by \(b_s\), and output \(p(x)=\pi\cdot x\) for every bundle. The LP solutions have polynomial encoding length; rational division and the sums defining prices preserve polynomial bit length. Thus construction of the entire allocation and price table also takes polynomial time.
The kernel procedure’s finite-termination bound is unnecessary for this model: explicit tables permit polynomial-size LPs, and the allowed fractional allocations make LP duality sufficient.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The LP formulation, dual signs, complementary-slackness calculation, and polynomial bit-complexity argument are correct. No major or minor mathematical issues were found.
The substitution \(y_{t,x}=a_tq_{t,x}\), \(z_{s,x}=b_sr_{s,x}\) is invertible because every mass is strictly positive. It preserves nonnegativity and converts each type’s normalization into the stated mass constraint.
The item-balance equations and objective also transform exactly as written. Thus feasible rational solutions of \((P)\) correspond precisely to rational allocations, with identical welfare.
Assigning all mass to the empty bundle satisfies every normalization and item-balance equation. The bounds \(0\leq y_{t,x}\leq a_t\) and \(0\leq z_{s,x}\leq b_s\) follow from nonnegativity and normalization. Consequently, the feasible region is nonempty, closed, and bounded, and the objective has a finite attained maximum.
The rationality argument is valid: a nonempty bounded rational polytope has an optimal vertex, and its vertices have rational coordinates. Hence optimizing over real variables does not change the maximum over rational allocations. The identification of the LP optimum with \(W^*\) is justified.
For a maximization LP with equality constraints and nonnegative primal variables, the dual variables are unrestricted and the dual constraints have the stated greater-than-or-equal direction.
A buyer variable has item-balance column \(x\) and objective coefficient \(v_t(x)\), giving
\(\alpha_t+\pi\cdot x\geq v_t(x)\).
A seller variable has item-balance column \(-x\) and objective coefficient \(-c_s(x)\), giving
\(\beta_s-\pi\cdot x\geq-c_s(x)\).
The dual objective correctly uses the normalization right-hand sides; the item-balance right-hand sides are zero.
The proposed dual-feasible point is valid. With \(\pi=0\), buyer feasibility follows from the definition of \(\alpha_t\), and seller feasibility follows from \(c_s(x)\geq0\).
The strong-duality application has the required hypotheses: the primal is feasible and has a finite optimum. It therefore supplies an attained dual optimum with the same value. Rational optimal solutions are also available, as required for the output.
The proposed table \(p(x)=\pi\cdot x\) is allowed by the task. Unrestricted prices permit negative item prices, and the task does not require bundle prices to be nonnegative.
The slack definitions have the correct signs. Expanding the claimed objective-gap identity yields the dual objective minus welfare plus the item-balance term, which is zero. The identity is therefore correct.
For optimal primal and dual solutions, the objective gap vanishes. Every summand is nonnegative, so every positive allocated mass has zero corresponding dual slack. This reasoning applies to any optimal primal–dual pair, without a further compatibility requirement.
Buyer dual feasibility bounds every utility by \(\alpha_t\); zero slack makes a positively allocated bundle attain that bound. Seller dual feasibility similarly bounds every profit by \(\beta_s\), with equality on positively allocated bundles. Positivity of the masses correctly transfers these statements from \(y,z\) to \(q,r\).
Thus every positive fraction is an exact best response. Exact optimal welfare and exact best responses imply both requested error guarantees for every supplied \(\varepsilon>0\).
There are \(\tau 2^m\) explicitly encoded table entries. Their total count is bounded by the input length up to encoding constants. Consequently, enumerating bundles and constructing these LPs is polynomial in the stipulated input size, despite the exponential dependence on \(m\) alone.
The variable and constraint counts are correct. Dense encoding of the constraint matrices remains polynomial in \(m,\tau,L\), and every coefficient has polynomial bit length.
The exact rational LP theorem is stated sufficiently precisely: polynomial time in binary encoding length, returning a rational optimum when the optimum is finite and feasible. Its hypotheses hold for both programs. The cited [Khachiyan publication](https://www.mathnet.ru/eng/zvmmf5239) is correctly identified.
Polynomial output length follows from that theorem. Division by positive input masses and the finite sums defining prices preserve polynomial bit length and require polynomial-time rational arithmetic. Outputting the entire allocation and price table therefore remains polynomial.
The proof covers \(m=1\), singleton supports, zero-valued tables, dependent balance constraints, and ties among maximizing bundles. None invalidates the argument.
Monotonicity is not needed for the proof; proving the result under weaker hypotheses is consistent with the task. The kernel procedure is not used as a complexity bound.
No additional clarification or repair 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.