Answer: Polynomial-time solvable, even exactly.
Theorem 2.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf all agents have $\MOPH$-$k$ valuations, then there exists an algorithm that gives $k+1$ approximation to the optimal social welfare. This algorithm runs in polynomial time given an access to demand oracles for the valuations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) item categories, \(\tau\) complete valuation types with rational masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_j\), and normalized monotone \(\mathcal{MOPH}\)-\(k\) valuations \(v_t\) accessible by demand oracles, find a feasible allocation maximizing welfare. Variables \(x_{t,S}\geq 0\) give the fraction of the whole population of type \(t\) assigned the integral bundle \(S\subseteq[m]\); require \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S\ni j}x_{t,S}\leq q_j\), and maximize \(\sum_{t,S}x_{t,S}v_t(S)\).
Let \(M=[m]\), with \(m\geq1\) and \(1\leq k\leq m\). A society is given by its support: the list of \(\tau\) complete valuation types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types. Supplies are binary rationals \(q_j\geq0\).
Each type has a normalized monotone valuation \(v_t:2^M\to\mathbb{Q}_{\geq0}\), promised to be \(\mathcal{MPH}\)-\(k\): \(v_t(S)=\max_{\ell\in\mathcal{I}_t}\sum_{\emptyset\neq E\subseteq S,\,|E|\leq k}w_{t,\ell,E}\), with nonnegative weights and an arbitrary index set. This representation need not be supplied.
An exact demand oracle, queried at nonnegative rational item prices \(p_j\), returns any bundle maximizing \(v_t(S)-\sum_{j\in S}p_j\); exact value queries are also available. Let \(L\) include the numerical input length and a supplied bound on the binary length of every valuation value; count oracle calls and bit operations separately.
An allocation assigns masses \(x_{t,S}\geq0\) to integral bundles \(S\subseteq M\), including the empty bundle, with \(\sum_{S\subseteq M}x_{t,S}=\mu_t\) and \(\sum_{t,S:\,j\in S}x_{t,S}\leq q_j\). Welfare is \(W(x)=\sum_{t,S}x_{t,S}v_t(S)\), and \(\mathrm{OPT}\) is its maximum over feasible allocations; allocations are represented by their nonzero entries.
Can a feasible allocation with expected welfare at least \(\mathrm{OPT}/(k+1)\) be computed in polynomial time in \(m,\tau,k,L\), with polynomially many exact oracle calls, or is achieving this approximation NP-hard even when the oracles have polynomial-time implementations?
For finitely many agents and single-copy items, a polynomial-time randomized demand-oracle algorithm achieves expected welfare at least \(\mathrm{OPT}/(k+1)\). The associated configuration LP is known to be solvable in polynomial time with demand queries ([Feige et al.](https://www.cs.tau.ac.il/~mfeldman/papers/FFIILSc15.pdf)); this verified statement concerns unit agent and item capacities.
The problem is polynomial-time solvable, even exactly. A deterministic algorithm computes a feasible allocation of welfare \(\mathrm{OPT}\), using polynomially many exact demand and value queries and polynomially many additional bit operations in \(m,\tau,L\). The allocation can have at most \(m+\tau\) nonzero entries.
The proof applies to every normalized monotone valuation satisfying the stated oracle and encoding assumptions; the \(\mathcal{MPH}\)-\(k\) promise is unnecessary.
Consider the finite, exponentially sized linear program
\(\displaystyle \max_{x\geq0}\ \sum_{t=1}^{\tau}\sum_{S\subseteq M}v_t(S)x_{t,S}, \)
subject to
\(\displaystyle \sum_{S\subseteq M}x_{t,S}=\mu_t \quad(t\in[\tau]), \)
and
\(\displaystyle \sum_{t=1}^{\tau}\sum_{S\ni j}x_{t,S}\leq q_j \quad(j\in M). \)
Call this program \(\mathrm{P}\). Its feasible solutions are exactly the allocations in the question, so its optimum is \(\mathrm{OPT}\).
It is feasible: assign mass \(\mu_t\) to the empty bundle for each type. Its feasible region is compact, since every coordinate satisfies \(0\leq x_{t,S}\leq\mu_t\). Consequently, its optimum is finite and attained.
Associate an unrestricted dual variable \(\alpha_t\) with each type equality and a nonnegative variable \(p_j\) with each supply constraint. The dual is
\(\displaystyle \min_{\alpha,p}\ \sum_{t=1}^{\tau}\mu_t\alpha_t+\sum_{j=1}^{m}q_jp_j, \)
subject to
\(\displaystyle \alpha_t+\sum_{j\in S}p_j\geq v_t(S) \quad(t\in[\tau],\ S\subseteq M), \qquad p_j\geq0. \)
Call this program \(\mathrm{D}\). The empty-bundle inequality implies \(\alpha_t\geq0\), because normalization gives \(v_t(\emptyset)=0\).
The dual is feasible: take \(p=0\) and \(\alpha_t=v_t(M)\). Monotonicity verifies every bundle inequality. Finite-dimensional LP strong duality therefore gives an attained dual optimum equal to \(\mathrm{OPT}\).
The crucial dimension is \(d=m+\tau\): the dual has only \(d\) variables, regardless of the number of bundles.
We construct a strong separation oracle for the feasible region of \(\mathrm{D}\). Its input is a rational point \((\alpha,p)\).
\(\displaystyle v_t(S_t)-\sum_{j\in S_t}p_j>\alpha_t, \)
return the violated defining inequality
\(\displaystyle \alpha_t+\sum_{j\in S_t}p_j\geq v_t(S_t). \)
To justify the final certification, the demand guarantee gives, for every \(S\subseteq M\),
\(\displaystyle v_t(S)-\sum_{j\in S}p_j \leq v_t(S_t)-\sum_{j\in S_t}p_j \leq\alpha_t. \)
Thus every bundle inequality holds. Arbitrary tie-breaking is harmless because every returned demand bundle attains the same maximum utility.
Each separation call uses at most \(\tau\) demand queries and \(\tau\) value queries. Its remaining arithmetic is polynomial in the encoding length of its input and in \(m,\tau,L\).
We use the following standard rational-polyhedral oracle theorem:
Given a rational polyhedron in dimension \(d\), a bound on the encoding length of its defining inequalities, and a strong separation oracle returning such inequalities, exact linear optimization is oracle-polynomial. When the optimum is finite and attained, optimal dual multipliers supported on polynomially many returned inequalities can also be recovered.
The multiplier-recovery statement is the essential additional ingredient beyond computing an optimal objective value. It is the GLS oracle-duality result, Lemma 6.5.15, discussed explicitly in [*On Finding Exact Solutions of Linear Programs in the Oracle Model*, Section 1.1](https://ir.cwi.nl/pub/35149/35149.pdf).
All hypotheses hold here:
The theorem therefore provides exact optimal multipliers on polynomially many defining inequalities. We now identify these multipliers with an allocation.
For this purpose, regard all coordinates \((\alpha,p)\) as unrestricted variables, and treat \(p_j\geq0\) as explicit inequalities. Let \(x_{t,S}\geq0\) denote the multiplier of the bundle inequality indexed by \((t,S)\), and let \(s_j\geq0\) denote the multiplier of \(p_j\geq0\).
The standard LP dual of this inequality formulation has equations
\(\displaystyle \sum_{S\subseteq M}x_{t,S}=\mu_t \quad(t\in[\tau]), \)
and
\(\displaystyle \sum_{t=1}^{\tau}\sum_{S\ni j}x_{t,S}+s_j=q_j \quad(j\in M). \)
Its objective is
\(\displaystyle \max\ \sum_{t,S}v_t(S)x_{t,S}, \)
because the inequalities \(p_j\geq0\) have zero right-hand side.
Thus the recovered optimal multipliers give exactly a feasible allocation, together with supply slacks. Its welfare equals \(\mathrm{OPT}\). Empty-bundle multipliers are included as ordinary allocation entries.
Recovery supplies only polynomially many bundle columns and supply-slack columns. Restrict the preceding standard-form LP to these columns. The recovered solution is feasible and has objective \(\mathrm{OPT}\). Every feasible solution of the restricted LP is feasible for the full LP, so its optimum is exactly \(\mathrm{OPT}\).
Solve this explicit rational LP and obtain an optimal basic feasible solution. It has \(d=m+\tau\) equality rows, hence at most \(d\) positive variables, including supply slacks. Its allocation therefore has at most \(m+\tau\) nonzero entries.
Its coordinates also have polynomial encoding length. Indeed, the constraint matrix has coefficients in \(\{0,1\}\). A basic solution is determined by a nonsingular square submatrix of order at most \(d\). Hadamard’s inequality bounds its determinant by \(d^{d/2}\); clearing the denominators of the supplied right-hand sides and applying Cramer’s rule gives polynomial binary length in \(d,L\).
The oracle algorithm makes polynomially many separation calls at rational points of polynomial encoding length. Consequently:
These bounds are also polynomial in \(m,\tau,k,L\).
For finitely many agents and single-copy items, the configuration LP allows fractional assignments that must subsequently be rounded to an integral allocation; this is the setting of the cited [Feige et al. paper](https://www.cs.tau.ac.il/~mfeldman/papers/FFIILSc15.pdf).
Here, the masses \(x_{t,S}\) themselves constitute the requested allocation. The argument above verifies separation and allocation recovery directly for arbitrary rational masses and supplies, without extending a unit-capacity rounding theorem.
The deterministic output \(x^\star\) satisfies
\(\displaystyle \mathbb{E}[W(x^\star)] =W(x^\star) =\mathrm{OPT} \geq\frac{\mathrm{OPT}}{k+1}. \)
⟨structured verdict parsed — rendered above⟩
The prover’s exact polynomial-time claim is correct. The argument establishes an optimal feasible allocation with polynomial output size, polynomially many oracle calls, and polynomial additional bit complexity. I found no major or minor mathematical issues.
The variables \(x_{t,S}\) are precisely the permitted allocation masses. The type equalities, supply inequalities, and objective reproduce the task’s definition without introducing an integrality requirement.
Assigning each type’s mass to the empty bundle proves feasibility, including when some or all supplies are zero. The feasible region is closed and bounded: every variable lies in \([0,\mu_t]\), and there are finitely many variables. Compactness and attainment therefore follow. The exponential number of variables does not invalidate this existence argument.
Equality constraints give unrestricted variables \(\alpha_t\), while supply upper bounds give nonnegative variables \(p_j\). The resulting bundle inequalities and minimization objective have the correct signs.
Normalization makes the empty-bundle inequality exactly \(\alpha_t\geq0\). Monotonicity verifies the proposed feasible dual point \(p=0\), \(\alpha_t=v_t(M)\). Both LPs are finite-dimensional, and the primal is feasible with a finite attained optimum, so the strong-duality conclusion is valid.
The dual dimension is indeed \(m+\tau\), with \(\tau\) counting supported types.
Negative prices are rejected before any demand query, so every demand call satisfies the oracle’s stipulated domain. Negative \(\alpha_t\) values are separated by actual empty-bundle constraints.
At nonnegative prices, exact demand maximizes the utility appearing in the bundle inequalities. Consequently, checking a maximizing bundle suffices to check all inequalities for that type. The displayed implication establishing feasibility is correct. Arbitrary demand tie-breaking does not affect the maximum utility.
Every returned separator is an original defining inequality, with its bundle explicitly identified. The oracle-call count and rational-arithmetic bounds per separation call are correct.
This is the essential nontrivial theorem invocation: obtaining an optimal dual point alone would not produce the requested allocation.
The cited paper’s discussion of rational polyhedra explicitly attributes recovery of optimal multipliers on oracle inequalities to GLS Lemma 6.5.15 under a polynomial encoding bound on returned separators. It also describes recovery using a polynomially bounded collection of inequalities. Thus the cited result supports the ingredient used here. [*On Finding Exact Solutions of Linear Programs in the Oracle Model*, Section 1.1, printed page 2705](https://ir.cwi.nl/pub/35149/35149.pdf).
The write-up checks the relevant hypotheses: finite rational dimension, bounded inequality encoding, bounded returned-separator encoding, rational objective data, and a finite attained optimum. The supplied valuation-value length bound is sufficient despite the exponentially many bundle inequalities.
The argument invokes the rational bit-complexity result; it does not incorrectly infer polynomial bit complexity merely from the paper’s newer real-arithmetic bounds.
Treating \(p_j\geq0\) as explicit inequalities and all coordinates as unrestricted yields the stated equality-form dual.
The coefficient of each \(\alpha_t\) gives
\[
\sum_S x_{t,S}=\mu_t,
\]
and the coefficient of each \(p_j\) gives
\[
\sum_{t,S:\,j\in S}x_{t,S}+s_j=q_j.
\]
Nonnegative \(s_j\) therefore enforce the supply upper bounds. The bundle multipliers contribute \(v_t(S)x_{t,S}\) to the objective; price-nonnegativity multipliers contribute zero. Empty-bundle multipliers correctly remain allocation entries. Optimal multiplier recovery consequently establishes welfare \(\mathrm{OPT}\).
Restricting to recovered columns preserves an optimal feasible solution. Conversely, every restricted feasible solution is feasible in the full LP, so the restricted optimum equals \(\mathrm{OPT}\).
An optimal basic feasible solution has at most \(m+\tau\) positive variables, including slack variables. Hence the allocation support has at most that many entries. Possible redundant equality rows only reduce the bound.
The matrix entries are in \(\{0,1\}\). The stated Hadamard bound is valid, and clearing the supplied right-hand-side denominators followed by Cramer’s rule gives polynomial binary length. Encoding each supported bundle also requires only \(m\) membership bits.
Zero supplies, supplies exceeding total mass, zero valuations, and boundary values of \(m\) and \(k\) cause no failure. The proof uses neither an MPH representation nor the MPH promise.
The finite-agent rounding theorem is not needed: fractional masses are themselves the requested output. The deterministic optimum has expected welfare equal to \(\mathrm{OPT}\), which satisfies the requested approximation guarantee.
Actionable feedback: No mathematical repair or additional clarification is necessary.
⟨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.