Answer: Yes; a feasible plan with the required welfare guarantee can be computed in time \(f(m)\operatorname{poly}(\tau,L,1/\epsilon)\), with at most \(\tau+m+1\) atoms.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe rounding scheme described in Algorithm A gives integrality gap IG of at most maxα∈[0,1]( 2c 2c−1+α)α with the amount of money s = c · n · vmax for any given constant c > 1/2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), valuations \(v_t\in\mathbb{Q}_{\ge0}^d\), and per-capita supplies \(q_j\), with cash supply \(\sigma=cv_{\max}\) for fixed \(c>1/2\), compute a finite-support plan \(\pi_t\) over integral bundles \(k\in\mathbb{Z}_{\ge0}^d\) and cash \(r\ge0\). Require \(\pi_t\) to have total mass \(\mu_t\), \(\sum_t\int k_j\,d\pi_t\le q_j\), and \(\sum_t\int r\,d\pi_t\le\sigma\); achieve \(W(\pi)=\exp(\sum_t\int\log(v_t\cdot k+r)\,d\pi_t)\ge(1-\epsilon)F/B(c)\) in time \(f(d)\operatorname{poly}(\tau,L,1/\epsilon)\), where \(F\) is the fractional MNW optimum under the same per-capita supplies.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass encoded as a binary rational; \(\tau\) is the support size, not the number of possible types. Normalize \(\sum_t\mu_t=1\).
There are \(m:=d\ge1\) categories of indivisible goods, with per-capita supplies \(q_j\in\mathbb Q_{\ge0}\); type \(t\) has additive valuations \(v_t\in\mathbb Q_{\ge0}^{m}\). Cash has utility one per unit for every type. Fix a rational constant \(c>1/2\), define \(v_{\max}=\max_{t,j}v_{tj}\), and set the per-capita cash supply to \(\sigma=cv_{\max}\).
A plan consists of finite-support nonnegative measures \(\pi_t\) on \(\mathbb Z_{\ge0}^{m}\times\mathbb R_{\ge0}\), with \(\pi_t\) of total mass \(\mu_t\). Feasibility requires \(\sum_t\int k_j\,d\pi_t\le q_j\) for every category and \(\sum_t\int r\,d\pi_t\le\sigma\). Output atom masses and cash amounts as binary rationals.
Define \(W(\pi)=\exp\bigl(\sum_t\int\log(v_t\cdot k+r)\,d\pi_t\bigr)\), with \(\log0=-\infty\) and \(\exp(-\infty)=0\).
The fractional MNW benchmark is \(F=\max\exp\bigl(\sum_t\mu_t\log(v_t\cdot x_t+r_t)\bigr)\), over \(x_t\in\mathbb R_{\ge0}^{m}\), \(r_t\ge0\), subject to \(\sum_t\mu_tx_{tj}\le q_j\) and \(\sum_t\mu_tr_t\le\sigma\). Set \(B(c)=\max_{\alpha\in[0,1]}\bigl(2c/(2c-1+\alpha)\bigr)^\alpha\). Let \(L\) be the total binary input length, including rational \(\epsilon\in(0,1)\).
Can a feasible finite-support plan satisfying \(W(\pi)\ge(1-\epsilon)F/B(c)\) always be computed in time \(f(m)\operatorname{poly}(\tau,L,1/\epsilon)\), for some computable function \(f\)?
For finite lists of agents, a polynomial-time rounding algorithm achieves welfare at least the fractional MNW optimum divided by \(B(c)\), with total cash \(cnv_{\max}\). [Dementiev, Gravin and Ignatiev](https://journals.sagepub.com/doi/full/10.3233/FAIA251380).
No result settling this precise continuous approximation question was located.
Result. Yes. The finite-agent theorem in the question, together with fixed-dimensional integer programming and exact oracle linear programming, gives the requested algorithm. The output can have at most \(\tau+m+1\) atoms in total.
The proof uses finite replication only to establish the existence of a bounded witness. The algorithm searches for a suitable plan through an implicit linear program.
1. Algorithmic tools
We use two standard results.
First, a bounded rational integer linear program with \(D\) variables can be optimized exactly in time \(g(D)S^{O(1)}\), where \(S\) is its binary encoding length, \(g\) is computable, and the polynomial exponent is independent of \(D\). Rational coefficients can be cleared; optimization follows from integer feasibility by binary search over the bounded objective range. This is the fixed-parameter form of the Lenstra–Kannan integer-programming theorem. [Kannan, *Minkowski’s Convex Body Theorem and Integer Programming*](https://pubsonline.informs.org/doi/abs/10.1287/moor.12.3.415).
Second, we use the following consequence of exact rational oracle linear programming:
Consider a finite rational linear program with \(s\) rows and an implicitly represented set of columns. Suppose all column coefficients, objective coefficients, and right-hand sides have a known uniform binary encoding bound \(\beta\). If an exact separation oracle for its dual returns an original violated constraint, then a feasible, bounded primal can be optimized exactly, with an explicit optimal primal solution recovered, using polynomially many oracle calls and additional bit operations in \(s\) and \(\beta\).
This includes recovery of a polynomial number of primal columns; solving the resulting explicit restricted LP yields an optimal basic solution. The result applies also to unbounded or lower-dimensional dual polyhedra. [Grötschel, Lovász and Schrijver, *Rational Polyhedra*](https://link.springer.com/chapter/10.1007/978-3-642-78240-4_7).
2. A bounded witness from finite replication
If \(v_{\max}=0\), then \(\sigma=F=0\). Giving every type the single atom \((0,0)\), of mass \(\mu_t\), settles this case.
Henceforth suppose \(v_{\max}>0\), so \(\sigma>0\). In particular, giving everybody cash \(\sigma\) shows \(F\ge \sigma>0\).
Let \(N\) be the product of the denominators of all \(\mu_t\) and \(q_j\), in their input representations. Then
\(\displaystyle N\mu_t\in\mathbb Z_{>0},\qquad K_j:=Nq_j\in\mathbb Z_{\ge0},\qquad \log N=O(L).\)
Consider a finite instance with \(N\mu_t\) agents of type \(t\), \(K_j\) separate copies of category \(j\), and total cash \(N\sigma\).
Its fractional MNW optimum equals \(F\). Indeed:
These two directions establish equality of the optima.
There is a minor issue if categories attaining \(v_{\max}\) have zero supply. Define
\(\displaystyle V_0=\max_{\substack{t,j\\q_j>0}}v_{tj},\)
with \(V_0=0\) if no category has positive supply. If \(V_0=0\), supplied goods contribute no utility. Jensen’s inequality gives \(F=\sigma\), attained by uniform cash, so this case is also solved.
Otherwise, the finite instance has maximum item value \(V_0>0\), and its cash supply is
\(\displaystyle N\sigma=c_0NV_0,\qquad c_0:=\frac{cv_{\max}}{V_0}\ge c>\frac12.\)
The supplied finite-agent theorem applies. Rational valuations cause no difficulty: multiplying all valuations and cash by a common denominator makes valuations integral and preserves welfare ratios.
Also, \(B\) is nonincreasing on \((1/2,\infty)\). For every fixed \(\alpha\in[0,1]\),
\(\displaystyle \frac{2x}{2x-1+\alpha}=1+\frac{1-\alpha}{2x-1+\alpha}\)
is nonincreasing in \(x>1/2\). Raising to the nonnegative power \(\alpha\) and taking the maximum preserves that property.
Consequently, the finite-agent theorem supplies an allocation whose welfare is at least \(F/B(c_0)\ge F/B(c)\). Represent each agent by an atom of mass \(1/N\) in its type’s measure. This gives a feasible finite-support plan \(\pi^{(0)}\) satisfying
\(\displaystyle W(\pi^{(0)})\ge \frac{F}{B(c)},\qquad 0\le k_j\le K_j,\qquad 0\le r\le N\sigma.\)
Here we use exactly the finite-agent guarantee stated in the question. [Dementiev, Gravin and Ignatiev, Theorem 2](https://journals.sagepub.com/doi/full/10.3233/FAIA251380).
The algorithm will not construct this expanded instance or this witness.
3. Discretizing cash while preserving feasibility
Set
\(\displaystyle \eta:=\frac{\epsilon}{8},\qquad a:=\eta\sigma,\qquad h:=\eta a=\eta^2\sigma.\)
At every atom of \(\pi^{(0)}\), first replace cash \(r\) by
\(\displaystyle r'=(1-\eta)r+\eta\sigma.\)
The total population mass is one, so total cash remains at most
\(\displaystyle (1-\eta)\sigma+\eta\sigma=\sigma.\)
Goods are unchanged. For an atom of type \(t\), writing its original utility as \(u=v_t\cdot k+r\), its new utility satisfies
\(\displaystyle u'=v_t\cdot k+r'\ge(1-\eta)u,\qquad u'\ge a.\)
Next round cash down to a multiple of \(h\):
\(\displaystyle r''=h\left\lfloor\frac{r'}h\right\rfloor.\)
This preserves feasibility. Since \(0\le r'-r''<h=\eta a\le\eta u'\),
\(\displaystyle u''=v_t\cdot k+r''\ge(1-\eta)u'.\)
The resulting plan \(\pi^{(2)}\) therefore satisfies
\(\displaystyle W(\pi^{(2)})\ge(1-\eta)^2\frac{F}{B(c)}.\)
Moreover, \(r'\le N\sigma\), because both \(r\) and \(\sigma\) are at most \(N\sigma\). Thus all its atoms have the form \((k,hz)\), where
\(\displaystyle 0\le k_j\le K_j,\qquad 0\le z\le Z:=\left\lfloor\frac{N\sigma}{h}\right\rfloor=\left\lfloor\frac{N}{\eta^2}\right\rfloor.\)
Define
\(\displaystyle U_0:=\frac a2,\qquad M:=N\left(v_{\max}\sum_jq_j+\sigma\right).\)
Every atom of \(\pi^{(2)}\) has utility in \([U_0,M]\): the lower bound follows from \(u''\ge(1-\eta)a\ge a/2\), and the upper bound follows from the bounds on goods and cash.
All of \(N,K_j,Z,h,U_0,M\) have polynomial binary encoding length.
4. A polynomial number of utility thresholds
Let
\(\displaystyle U_\ell=U_0(1+\eta)^\ell,\)
and let \(H\) be the smallest integer such that \(U_H\ge M\). The thresholds can be constructed by exact rational multiplication and comparison.
Because
\(\displaystyle \frac{M}{U_0}=\frac{2N}{\eta}\left(1+\frac{\sum_jq_j}{c}\right)\)
and \(\log(1+\eta)\ge\eta/2\), we have
\(\displaystyle H=O\left(\frac{L+\log(1/\epsilon)}{\epsilon}\right).\)
Every threshold also has polynomial encoding length: it is a product of \(H\) rational factors of polynomial encoding length.
For each threshold, compute a rational coefficient \(b_\ell\) satisfying
\(\displaystyle \log U_\ell-\eta\le b_\ell\le\log U_\ell.\)
These coefficients are computable in polynomial bit time. For completeness, range reduction writes a positive rational as \(2^ey\), with \(1\le y<2\). The identity
\(\displaystyle \log y=2\sum_{i=0}^{\infty}\frac{z^{2i+1}}{2i+1},\qquad z=\frac{y-1}{y+1}\in[0,1/3)\)
has geometrically decreasing tails; the same series computes \(\log2\). Approximating both terms sufficiently accurately gives a rational approximation to \(\log U_\ell\) within \(\eta/2\). Subtracting \(\eta/2\) gives the required \(b_\ell\). The number of terms and the rational arithmetic lengths are polynomial in the input length and \(\log(1/\eta)\).
If \(u\in[U_0,M]\), choose the largest \(\ell\le H\) such that \(U_\ell\le u\). Then
\(\displaystyle b_\ell\ge\log u-\log(1+\eta)-\eta\ge\log u-2\eta.\)
Thus these finitely many labels approximate log utility from below.
5. The implicit linear program
For each type \(t\), threshold label \(\ell\), and integer vector \((k,z)\) satisfying
\(\displaystyle 0\le k_j\le K_j,\qquad 0\le z\le Z,\qquad v_t\cdot k+hz\ge U_\ell,\)
introduce a nonnegative variable \(y_{t,\ell,k,z}\). It represents population mass assigned the atom \((k,hz)\) with label \(\ell\).
Consider the finite, implicit LP
\(\displaystyle \max\sum_{t,\ell,k,z}b_\ell y_{t,\ell,k,z},\)
subject to
\(\displaystyle \sum_{\ell,k,z}y_{t,\ell,k,z}=\mu_t\quad\text{for every }t,\)
\(\displaystyle \sum_{t,\ell,k,z}k_jy_{t,\ell,k,z}\le q_j\quad\text{for every }j,\)
\(\displaystyle \sum_{t,\ell,k,z}hz\,y_{t,\ell,k,z}\le\sigma.\)
It has \(\tau+m+1\) rows. Its column set is finite, and every coefficient has a uniform polynomial encoding bound. It is feasible: label every atom of \(\pi^{(2)}\) by the threshold chosen in Section 4. It is bounded because its variables have total mass one and its objective coefficients belong to the finite list \(b_0,\ldots,b_H\).
Let its optimum be \(P^\star\). The labeled witness gives
\(\displaystyle P^\star\ge\log W(\pi^{(2)})-2\eta.\)
Conversely, every feasible LP solution specifies a feasible plan \(\pi\), after dropping labels and merging identical atoms. Column eligibility and the choice of \(b_\ell\) imply
\(\displaystyle \log(v_t\cdot k+hz)\ge\log U_\ell\ge b_\ell.\)
Therefore
\(\displaystyle \log W(\pi)\ge\sum_{t,\ell,k,z}b_\ell y_{t,\ell,k,z}.\)
6. Separation uses only \(m+1\) integer variables
The dual has unrestricted variables \(A_t\), nonnegative goods prices \(p_j\), and a nonnegative cash price \(\lambda\). Its objective is
\(\displaystyle \min\sum_t\mu_tA_t+\sum_jq_jp_j+\sigma\lambda,\)
and its column constraints are
\(\displaystyle A_t+p\cdot k+\lambda hz\ge b_\ell.\)
For a rational candidate dual point, first check \(p_j,\lambda\ge0\). For each pair \((t,\ell)\), solve exactly the bounded integer linear program
\(\displaystyle \min\;p\cdot k+\lambda hz,\)
subject to
\(\displaystyle k\in\mathbb Z_{\ge0}^{m},\quad z\in\mathbb Z_{\ge0},\quad k_j\le K_j,\quad z\le Z,\quad v_t\cdot k+hz\ge U_\ell.\)
There are exactly \(m+1\) integer variables. All constraints and the objective are rational linear expressions.
If this problem is infeasible, that pair has no columns. Otherwise, its minimizing vector yields a violated dual constraint precisely when its minimum is less than \(b_\ell-A_t\). If no pair produces a violation, all dual constraints hold. This is an exact separation oracle returning original column constraints.
There are \(\tau(H+1)\) integer programs per oracle call. By the integer-programming theorem, the oracle runs in time
\(\displaystyle g(m+1)\operatorname{poly}(\tau,L,1/\epsilon,\text{query length}).\)
The exact oracle-LP theorem now applies: the dual dimension is \(\tau+m+1\), and its inequalities have a uniform polynomial encoding bound. It recovers an explicit optimal primal solution in the desired parameterized running time.
Taking an optimal basic solution of the recovered restricted LP gives at most \(\tau+m+1\) positive atom variables. Its masses are binary rationals of polynomial length: each basic solution is determined by a rational system of at most \(\tau+m+1\) equations with polynomial-length coefficients, so determinant bounds give polynomial-length numerators and denominators. Its cash amounts \(hz\) likewise have polynomial encoding length.
7. Welfare guarantee and running time
Let \(\widehat\pi\) be the plan obtained from this optimal LP solution. Combining the proved inequalities gives
\(\displaystyle \log W(\widehat\pi)\ge P^\star\ge\log W(\pi^{(2)})-2\eta,\)
hence
\(\displaystyle W(\widehat\pi)\ge e^{-2\eta}(1-\eta)^2\frac{F}{B(c)}.\)
Since \(\eta=\epsilon/8<1/8\),
\(\displaystyle e^{-2\eta}(1-\eta)^2\ge(1-2\eta)^2\ge1-4\eta=1-\epsilon/2\ge1-\epsilon.\)
Thus
\(\displaystyle W(\widehat\pi)\ge(1-\epsilon)\frac{F}{B(c)}.\)
Feasibility holds exactly through the LP constraints. The algorithm uses polynomially many thresholds, polynomial-length rational data, and polynomially many oracle calls. Only integer optimization contributes a nonpolynomial parameter dependence, and its dimension is \(m+1\). Absorbing that dependence into a computable function \(f\), the total running time is
\(\displaystyle f(m)\operatorname{poly}(\tau,L,1/\epsilon).\)
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument resolves the requested approximation question: it establishes an algorithm running in \(f(m)\operatorname{poly}(\tau,L,1/\epsilon)\), producing an exactly feasible rational plan with at most \(\tau+m+1\) atoms. I found no mathematical or algorithmic gap requiring repair.
The complexity conclusion is fixed-parameter tractability in \(m\), and therefore polynomial time for each fixed \(m\). It does not establish polynomial time when \(m\) varies unrestrictedly.
The integer-programming result is stated in the required form: dependence on the number of integer variables is confined to a computable function, while the encoding-length exponent is independent of that dimension. The programs used later have explicit bounds on every variable, rational linear constraints, and rational linear objectives. Clearing denominators and reducing optimization to bounded integer feasibility are legitimate. [Kannan’s paper](https://pubsonline.informs.org/doi/abs/10.1287/moor.12.3.415) supports the claimed dimension dependence.
The oracle-LP result includes the essential feature of recovering an explicit primal solution, rather than merely optimizing the dual. Its hypotheses include bounded rational encoding lengths and separation by original constraints. These are sufficient for recovery using polynomially many columns, including when the dual is unbounded as a set or lower-dimensional. This is consistent with the bounded-output oracle dual-recovery results in [Grötschel–Lovász–Schrijver, Section 6.5](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).
When \(v_{\max}=0\), all goods and cash yield zero utility, so \(F=0\). The proposed zero allocation is feasible and satisfies the requested inequality.
When \(v_{\max}>0\), uniform cash \(\sigma\) is feasible and gives \(F\ge\sigma>0\). Thus logarithms of the positive benchmark used subsequently are legitimate.
If \(V_0=0\), every supplied good has zero value to every type; categories with zero supply cannot contribute utility. Jensen’s inequality bounds fractional welfare by \(\sigma\), and uniform cash attains that bound. The second early termination is therefore valid.
The denominator product makes \(N\mu_t\) positive integers and \(K_j=Nq_j\) nonnegative integers. Its binary length is polynomial even though its numerical value can be exponential.
Both benchmark comparisons are valid:
The geometric-mean normalization is consistent because each replicated agent has weight \(1/N\), and each type consequently has total weight \(\mu_t\).
The adjustment to \(c_0=cv_{\max}/V_0\) correctly identifies the finite instance’s cash parameter. The displayed identity proves that \(B\) is nonincreasing, including the endpoint values of \(\alpha\). The finite theorem therefore supplies the claimed witness with welfare at least \(F/B(c)\). The theorem’s welfare benchmark and cash assumption match this use. [Dementiev–Gravin–Ignatiev, Theorem 2](https://journals.sagepub.com/doi/full/10.3233/FAIA251380).
Individual bounds \(k_j\le K_j\) and \(r\le N\sigma\) follow from nonnegative allocations and the total finite supplies. The exponentially large replicated instance is used only for existence.
The first replacement preserves the cash budget because population mass is one. Nonnegative goods valuations justify both \(u'\ge(1-\eta)u\) and \(u'\ge a\).
Rounding cash down preserves feasibility. The rounding loss is less than \(h=\eta a\), which is at most \(\eta u'\). Hence the second multiplicative utility bound is valid.
Since the total population mass is one, the two pointwise multiplicative bounds give exactly the stated welfare factor \((1-\eta)^2\).
The bounds on \(z\), the positive utility floor \(U_0\), and the upper utility bound \(M\) all check out. Their rational encoding lengths are polynomial in the permitted parameters.
The expression for \(M/U_0\) is algebraically correct. The threshold count follows from the polynomial logarithmic magnitude of the rational input data and the stated lower bound on \(\log(1+\eta)\).
Exact multiplication produces rational thresholds with polynomial encoding length in \(L\) and \(1/\epsilon\).
The range-reduction series supports rational logarithmic approximation with the stated precision. Negative range-reduction exponents introduce no problem because the argument requires a two-sided approximation before subtracting \(\eta/2\).
Choosing the largest eligible threshold loses at most \(\log(1+\eta)\), and the coefficient approximation loses at most \(\eta\). Thus the bound \(b_\ell\ge\log u-2\eta\) is valid. The endpoint case \(u=U_H\) also satisfies it.
The discretized witness proves LP feasibility without requiring the algorithm to construct that witness.
Type equalities imply total variable mass one. Consequently the finite objective-coefficient list bounds the objective, even if some coefficients are negative.
Both objective comparisons have the correct direction:
Merging identical atoms preserves masses, resource consumption, and welfare.
The displayed dual has the correct signs: type multipliers are unrestricted, while multipliers for goods and cash upper bounds are nonnegative.
For each type-label pair, minimizing resource price over eligible integer bundles identifies a violation exactly when the minimum is less than \(b_\ell-A_t\). Empty eligibility sets impose no constraint.
Each pricing problem uses exactly \(m+1\) integer variables. The bounds remain encoded in binary; the oracle does not enumerate their numerical ranges.
The oracle returns original column constraints with uniformly bounded encoding lengths, together with identifiable bundles. Sign constraints are checked explicitly. These facts satisfy the stated oracle-LP hypotheses and permit explicit primal recovery.
The basic-solution atom bound accounts for all \(\tau+m+1\) resource and mass rows. Slack variables cannot increase the number of positive atom variables beyond this bound. The determinant argument correctly bounds rational output lengths.
The combined welfare inequality follows directly from the preceding comparisons. The final elementary estimate is valid throughout \(0<\eta<1/8\), and its factor is at least \(1-\epsilon\).
Feasibility is exact because the recovered rational solution satisfies the LP constraints exactly.
Threshold construction, rational arithmetic, oracle-call counts, and query lengths are polynomial in the stated parameters. The only nonpolynomial dependence is integer optimization in dimension \(m+1\), giving the requested computable factor \(f(m)\).
Actionable feedback: No repair is required. The proof establishes the requested fixed-parameter approximation guarantee. Under the supplied classification definitions, this is recorded as “other” because an unrestricted polynomial-time bound in \(m\) is not established.
⟨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.