Answer: —
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 achieves a 4−approximation to the optimal envy-free revenue when all buyers have budgets that are at least their valuations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), item supplies \(q_j\), and types \(t=(S_t,v_t,b_t)\) with \(b_t \ge v_t\), compute in time polynomial in \(m,\tau,L\) item prices \(\rho_j\) and masses \(z_{t,X}\) assigned to integral bundles \(X\subseteq S_t\). Require \(\sum_X z_{t,X}=\mu_t\), \(\sum_{t,X:j\in X}z_{t,X}\le q_j\), and every bundle receiving positive mass to maximize that type’s affordable utility at \(\rho\). The revenue must be at least \(\mathrm{OPT}_{BP}/4\), where \(\mathrm{OPT}_{BP}\) is the maximum revenue of a feasible, individually rational, bundle-price envy-free allocation on the same instance.
Let \(J\) contain \(m\ge1\) item labels. A society is given by its support: \(\tau\ge1\) types \(t=(S_t,v_t,b_t)\), with \(S_t\subseteq J\), positive binary-rational masses \(\mu_t\) summing to \(1\), and rational \(b_t\ge v_t>0\). Here \(\tau\) is the support size, not the number of possible types. Supplies \(q_j\ge0\) are binary rationals; \(L\) is the total input bit length.
Each individual receives an integral bundle, containing at most one of each label. Utility is \(u_t(X,p)=v_t|X\cap S_t|-p\) when \(0\le p\le b_t\), and \(-\infty\) otherwise; the outside option is \((\varnothing,0)\).
An item-price outcome consists of nonnegative rational prices \(\rho_j\) and nonnegative rational masses \(z_{t,X}\), for \(X\subseteq S_t\), satisfying \(\sum_Xz_{t,X}=\mu_t\) and \(\sum_{t,X:j\in X}z_{t,X}\le q_j\). Every positively assigned bundle must maximize \(u_t(Y,\sum_{j\in Y}\rho_j)\) over all \(Y\subseteq J\); any utility tie is allowed. Revenue is \(R=\sum_{t,X}z_{t,X}\sum_{j\in X}\rho_j\). Only positive entries need be listed.
For the bundle-price benchmark, use nonnegative masses \(a_{t,X}\), now allowing \(X\subseteq J\), with the same mass and supply constraints, and a common nonnegative price \(P(X)\) for each assigned bundle. Every positively assigned \(X\) must satisfy \(u_t(X,P(X))\ge0\) and \(u_t(X,P(X))\ge u_t(Y,P(Y))\) for every bundle \(Y\) assigned positive mass to any type. Include the free outside option; unassigned bundles are unavailable, and unions or subbundles are not automatically offered. Let \(\mathrm{OPT}_{BP}\) be the supremum of \(\sum_{t,X}a_{t,X}P(X)\) over these outcomes.
Does an algorithm running in time polynomial in \(m,\tau,L\) always compute an item-price outcome with \(R\ge\mathrm{OPT}_{BP}/4\)?
For finite buyers and one copy of each item, a polynomial-time item-price algorithm achieves revenue at least one quarter of the optimal individually rational, bundle-price envy-free revenue when every budget is at least its per-item value. [Source](https://arxiv.org/pdf/1610.09221)
No result settling this exact continuous approximation question was identified in the literature search.
The general quarter-approximation question remains unresolved here. I prove the following additional results:
These results address price selection and representation, but the running time of the general price enumeration depends exponentially on $m$. They do not establish the requested uniform polynomial-time guarantee.
Throughout, let $\mathrm{OPT}_{IP}$ denote the supremum of revenue over item-price outcomes, and put
$$ V=\max_t v_t, \qquad B=\max_t b_t. $$
Both suprema are finite: individual rationality bounds every type’s average payment by $b_t$, so every outcome has revenue at most $\sum_t\mu_t b_t$.
The following facts are needed for the price-selection argument. I give their proofs so that the argument is self-contained.
Fix nonnegative rational item prices $\rho$.
Removing labels outside $S_t$ from an affordable bundle preserves its value and weakly reduces its payment. Consequently, maximizing utility over subsets of $S_t$ gives the same maximum as maximizing over all subsets of $J$.
Define
$$ W_t=\{j\in S_t:\rho_j<v_t\}, \qquad Z_t=\{j\in S_t:\rho_j=v_t\}. $$
Suppose first that $\sum_{j\in W_t}\rho_j\le b_t$. Every affordable interested bundle has utility at most
$$ \sum_{j\in W_t}(v_t-\rho_j), $$
and $W_t$ attains this bound. Equality requires including every label in $W_t$ and excluding every label priced above $v_t$. Thus the demanded interested bundles are exactly
$$ W_t\cup H, \qquad H\subseteq Z_t, \qquad |H|\le r_t, $$
where
$$ r_t= \min\left\{ |Z_t|, \left\lfloor \frac{b_t-\sum_{j\in W_t}\rho_j}{v_t} \right\rfloor \right\}. $$
Now suppose that $\sum_{j\in W_t}\rho_j>b_t$. Sort the prices in $S_t$ as
$$ \pi_1\le\cdots\le\pi_n, \qquad C_k=\sum_{i=1}^k\pi_i, \qquad C_0=0. $$
Let $d_t$ be the largest $k$ with $C_k\le b_t$. Because $C_{|W_t|}>b_t$, we have $d_t<|W_t|$. For every $1\le k\le d_t$,
$$ (v_tk-C_k)-(v_t(k-1)-C_{k-1}) = v_t-\pi_k>0. $$
A cheapest $k$-element subset maximizes utility among bundles of cardinality $k$. No cardinality greater than $d_t$ is affordable. Therefore every maximizing interested bundle is a cheapest $d_t$-element subset.
The assumption $b_t\ge v_t$ ensures $d_t\ge1$: a label in $W_t$ has price less than $v_t$ and is affordable. Define
$$ c_t=\pi_{d_t}, \qquad F_t=\{j\in S_t:\rho_j<c_t\}, \qquad E_t=\{j\in S_t:\rho_j=c_t\}, \qquad h_t=d_t-|F_t|. $$
The demanded bundles are exactly $F_t\cup H$ with $H\subseteq E_t$ and $|H|=h_t$.
In both cases, demand therefore has the form
$$ \mathcal D_t = \{F_t\cup H:H\subseteq E_t,\ \ell_t\le |H|\le u_t\}. $$
In the first case, $F_t=W_t$, $E_t=Z_t$, $\ell_t=0$, and $u_t=r_t$. In the second case, $\ell_t=u_t=h_t$.
Every member of type $t$ must receive all labels in $F_t$. Define the residual supplies
$$ Q_j=q_j-\sum_{t:j\in F_t}\mu_t. $$
A negative $Q_j$ makes these prices infeasible. Otherwise introduce $x_{tj}$ for $j\in E_t$, representing the mass of type $t$ receiving optional label $j$. The necessary constraints are
$$ 0\le x_{tj}\le\mu_t, $$
$$ \ell_t\mu_t \le \sum_{j\in E_t}x_{tj} \le u_t\mu_t, $$
$$ \sum_{t:j\in E_t}x_{tj}\le Q_j. $$
They are also sufficient.
To prove sufficiency, fix a type and write $y_j=x_{tj}/\mu_t$. Append $u_t-\ell_t$ dummy coordinates in $[0,1]$ so that all coordinates sum to the integer $u_t$. This is possible because the required dummy sum is
$$ u_t-\sum_j y_j\in[0,u_t-\ell_t]. $$
Place consecutive half-open intervals of the coordinate lengths along $[0,u_t)$. For $U$ uniformly distributed on $[0,1)$, select a coordinate if its interval contains a point $U+k$ for an integer $k$.
Apart from finitely many endpoint values of $U$, exactly $u_t$ coordinates are selected. An interval of length at most one contains at most one such point, and its selection probability equals its length. Discarding the dummy coordinates leaves between $\ell_t$ and $u_t$ original labels, with original inclusion probabilities $y_j$.
Partitioning $[0,1)$ at the fractional parts of the interval endpoints produces an explicit rational distribution with at most $2m+1$ pieces. The case $u_t=0$ simply gives the deterministic empty optional set. Adding $F_t$ and multiplying probabilities by $\mu_t$ gives the required allocation.
Revenue at these prices is
$$ \sum_t\mu_t\sum_{j\in F_t}\rho_j + \sum_t\sum_{j\in E_t}\rho_jx_{tj}. $$
Thus feasibility and maximum revenue at fixed prices are computable by a rational linear program with at most $\tau m$ variables.
The resulting bundle list can be reduced to at most $\tau+m$ positive entries. Indeed, over that list, preserve each type’s total mass and each label’s total allocated mass. An extreme point of this nonempty bounded polytope has at most $\tau+m$ positive coordinates: otherwise its positive columns are linearly dependent, yielding a nonzero perturbation in both directions that preserves all these equalities. Preserving label loads also preserves revenue.
I will use regions specified by rational linear equalities and weak or strict inequalities.
Let $C$ be a nonempty bounded set specified by such constraints, and let $\overline C_{\mathrm{weak}}$ be obtained by replacing its strict inequalities by weak ones.
Then $\overline C_{\mathrm{weak}}$ is the closure of $C$. To see this, choose $p^0\in C$. For any $p^*\in\overline C_{\mathrm{weak}}$ and $0<\lambda<1$, the point
$$ p^\lambda=(1-\lambda)p^*+\lambda p^0 $$
satisfies all equalities and weak inequalities, and satisfies every originally strict inequality strictly. Hence $p^\lambda\in C$ and $p^\lambda\to p^*$.
Consequently, the supremum of an affine function on $C$ is its maximum on $\overline C_{\mathrm{weak}}$, computable by rational linear programming.
Strict feasibility can also be checked by linear programming. Write each strict constraint as $f_i(p)>0$, replace it by $f_i(p)\ge\eta$, impose $0\le\eta\le1$, and maximize $\eta$. The original region is nonempty exactly when the optimum is positive.
For $H$ hyperplanes in dimension $d$, the number of nonempty sign regions, including lower-dimensional regions, is at most
$$ \sum_{i=0}^d 2^i\binom Hi. $$
Here a sign region specifies, for every defining affine function, whether it is negative, zero, or positive.
For completeness, let $F(H,d)$ be the maximum number of regions. On inserting the last hyperplane, an old region that is cut transversely becomes two regions plus its intersection with that hyperplane, increasing the count by two. The distinct intersections are regions of the induced arrangement in dimension $d-1$. Thus
$$ F(H,d)\le F(H-1,d)+2F(H-1,d-1). $$
The displayed bound follows from this recurrence and the initial conditions $F(0,d)=F(H,0)=1$.
An algorithm can insert hyperplanes successively, extend each retained sign pattern by the three possible signs, and test feasibility using the preceding linear program. In fixed dimension, this takes polynomial time in $H$ and the coefficient encoding length.
For each fixed $m$, there is an algorithm polynomial in $\tau$, $L$, and the encoding length of a rational $\varepsilon\in(0,1)$ that:
$$ R\ge(1-\varepsilon)\mathrm{OPT}_{IP}. $$
The theorem concerns a supremum; it does not assert that an optimal outcome always exists.
It suffices to consider prices in $[0,V]^m$.
Indeed, a label priced above $V$ cannot occur in a positively assigned interested bundle: removing it strictly increases utility. Replace every price above $V$ by $V$. Previously assigned bundles keep their payments.
For any type, removing the newly reduced labels from any newly affordable alternative weakly increases its utility, since those labels still have price at least that type’s value. The remaining bundle uses unchanged prices and was an available alternative before the reduction. Therefore no newly affordable alternative has utility greater than the utility of the previously assigned bundle.
This replacement preserves the outcome and its revenue.
Inside $[0,V]^m$, use the following hyperplanes:
$$ \rho_i=\rho_j, \qquad \rho_j=v_t, \qquad \sum_{j\in A}\rho_j=b_t \quad (A\subseteq S_t), $$
together with the box-boundary hyperplanes.
There are at most
$$ O(m^2+\tau m+\tau 2^m) $$
hyperplanes.
Within a sign region:
The demand description from Section 1 is therefore constant throughout the region. In particular, the sets $F_t,E_t$ and integers $\ell_t,u_t$ are fixed.
Partition the types into $\mathcal A$, those in the first demand case, and $\mathcal B$, those in the second.
For $t\in\mathcal A$, every optional label has price exactly $v_t$ throughout the region.
For $t\in\mathcal B$, choose any $e_t\in E_t$. Every optional label has price $\rho_{e_t}$, and the allocation constraints require total optional mass $h_t\mu_t$. Its optional payment is therefore always $h_t\mu_t\rho_{e_t}$, regardless of how those optional labels are distributed.
The compact allocation polytope from Section 1 depends only on the region. Define
$$ C= \max_x \sum_{t\in\mathcal A}\sum_{j\in E_t}v_tx_{tj} $$
over that polytope. If it is infeasible, discard the region. Otherwise, maximum feasible revenue at any price in the region is exactly
$$ F(\rho)= \sum_t\mu_t\sum_{j\in F_t}\rho_j + \sum_{t\in\mathcal B}\mu_th_t\rho_{e_t} + C. $$
This is affine in $\rho$. Moreover, one allocation solution attaining $C$ is optimal throughout the region.
Enumerate all nonempty price regions. For each region with feasible allocation constraints:
Every admissible price belongs to one region, so the largest value is exactly $\mathrm{OPT}_{IP}$.
For a region attaining that supremum, let $\rho^*$ maximize $F$ over its weak closure and let $\rho^0$ be a rational point in the region. Set
$$ \rho^\varepsilon = (1-\varepsilon)\rho^*+\varepsilon\rho^0. $$
This price vector lies in the original region. Since $F(\rho^0)$ is revenue from a feasible outcome, it is nonnegative. Thus
$$ F(\rho^\varepsilon) = (1-\varepsilon)\mathrm{OPT}_{IP} + \varepsilon F(\rho^0) \ge (1-\varepsilon)\mathrm{OPT}_{IP}. $$
Use the region’s optimal allocation solution and the decomposition from Section 1 to produce the outcome.
For fixed $m$, the number of hyperplanes and regions is polynomial in $\tau$. Every linear program has polynomial size and rational coefficients of polynomial encoding length. This proves the theorem.
A related affine structure holds for the benchmark despite the apparent products of allocation masses and bundle prices.
For each fixed $m$, $\mathrm{OPT}_{BP}$ can be computed exactly as a rational number in polynomial time. For rational $\varepsilon\in(0,1)$, a bundle-price outcome with revenue at least
$$ (1-\varepsilon)\mathrm{OPT}_{BP} $$
can also be produced in polynomial time.
An assigned empty bundle must have price zero by individual rationality. Treat it as the free outside option.
There are $N=2^m-1$ nonempty bundles. Enumerate every subset $M$ of them as a possible menu, with price variables $P_X$ for $X\in M$. It suffices to impose $0\le P_X\le B$, because every genuinely assigned bundle must be affordable to some type.
For this intermediate optimization, allow some menu entries to remain unassigned. This does not change the supremum:
For a fixed menu, use hyperplanes for affordability,
$$ P_X=b_t, $$
and utility comparisons, including comparison with the outside option,
$$ P_X-P_Y = v_t\bigl(|X\cap S_t|-|Y\cap S_t|\bigr). $$
For the outside option, take $Y=\varnothing$ and $P_Y=0$. Include the price-box boundaries.
Within each sign region, the set $\mathcal D_t$ of affordable utility-maximizing menu bundles, including the outside option, is fixed.
Choose a reference bundle $X_t^0\in\mathcal D_t$ for each type. For every $X\in\mathcal D_t$, utility equality gives
$$ P_X-P_{X_t^0} = v_t\bigl(|X\cap S_t|-|X_t^0\cap S_t|\bigr). $$
Consequently, for an allocation supported on these demand sets,
$$ \sum_{t,X}a_{t,X}P_X = \sum_t\mu_tP_{X_t^0} + \sum_{t,X}a_{t,X}v_t \bigl(|X\cap S_t|-|X_t^0\cap S_t|\bigr). $$
The second sum is a linear objective in the allocation masses with coefficients independent of prices. Its maximum $C$ is obtained from the mass and supply linear program over the fixed demand sets.
Maximum revenue in the region is thus the affine function
$$ F(P)=\sum_t\mu_tP_{X_t^0}+C. $$
If a reference bundle is the outside option, its reference price is zero.
Now maximize this affine function over the weak closure of every feasible region and take the largest value over all menus. The same convex-mixture argument as in Section 3 produces an outcome within a factor $1-\varepsilon$ of that value.
For fixed $m$, both the menu size and price-space dimension are constants. There are polynomially many hyperplanes and regions in $\tau$, and every allocation linear program has polynomial size. This proves the theorem.
The preceding algorithms have expensive enumeration when $m$ varies. Nevertheless, their underlying optimization has polynomial-size rational representations.
Every bundle-price outcome is dominated in revenue by one with at most $\tau+m$ positive type-bundle entries.
To prove this, fix its offered menu and prices. For each type, retain only its utility-maximizing affordable menu bundles and the outside option when maximizing. Optimize revenue over allocation masses on these demand sets.
The original allocation is feasible. The allocation polytope is bounded because each type’s total mass is fixed. Hence an optimal extreme point exists.
If that extreme point had more than $\tau+m$ positive entries, the corresponding columns of the $\tau$ type-mass rows and $m$ label-load rows would be linearly dependent. A sufficiently small nonzero perturbation in both directions would preserve nonnegativity, all type masses, and all label loads. This contradicts extremality.
Finally, delete every unassigned menu entry. This preserves validity and revenue.
Fix at most $\tau+m$ proposed positive pairs $(t,X)$. Let $a_{t,X}>0$ be their masses, $P_X$ the common prices of their distinct nonempty bundles, and $U_t$ the utility received by type $t$.
For an assigned pair, impose
$$ U_t=v_t|X\cap S_t|-P_X, \qquad P_X\le b_t. $$
Also impose $U_t\ge0$, the type-mass equalities, and the supply inequalities.
For each type $t$ and offered bundle $Y$, choose one of two affordability branches:
$$ P_Y\le b_t, \qquad U_t\ge v_t|Y\cap S_t|-P_Y, $$
or
$$ P_Y>b_t. $$
These conditions are exactly the required individual rationality and envy-freeness conditions. Every offered bundle is actually offered because some proposed pair assigns it positive mass.
Revenue becomes a linear function:
$$ R= \sum_{t,X}a_{t,X}v_t|X\cap S_t| - \sum_t\mu_tU_t. $$
Indeed, substitute the assigned-pair utility equalities and use $\sum_Xa_{t,X}=\mu_t$.
All variables can be bounded:
$$ 0\le P_X\le B, \qquad 0\le U_t\le mV, \qquad 0\le a_{t,X}\le\mu_t. $$
Thus, for a fixed support and affordability pattern, optimization is over a bounded rational linear system with some strict inequalities. Its number of variables and coefficient encoding lengths are polynomial in $m,\tau,L$.
Standard rational linear programming gives polynomial encoding bounds for vertices: a vertex is obtained by solving a nonsingular subsystem with no more equations than variables, and determinant bounds give polynomial bit length when the dimension and coefficient bit lengths are polynomial.
Applying this fact to the preceding systems yields:
For item pricing, there are finitely many demand regions. The allocation and price linear programs from Section 3 have polynomial dimension and polynomial coefficient encoding length, even though there may be exponentially many regions.
For bundle pricing, there are finitely many sparse supports and affordability patterns. Sparsification loses no revenue, and each feasible pattern has the bounded linear description above. Its supremum is the optimum over its weak closure. Taking the maximum over this finite collection preserves rationality and the uniform encoding bound.
Near-optimal outcomes follow by mixing a closure optimizer with a strictly feasible rational point. Such a point of polynomial encoding length is obtained by the positive-margin linear program from Section 2. The allocation decompositions and support reductions preserve polynomial encoding length.
There is also a certificate consequence. For a rational threshold $T$, each of the following decision problems belongs to $\mathrm{NP}$:
To justify the encoding bound for an exact threshold, add $R\ge T$ to the appropriate linear system before maximizing the strict-inequality margin. If a feasible outcome exists, this system has a positive-margin solution, and a rational vertex supplies a polynomial-size witness. The item-price witness can be checked using the exact demand calculation from Section 1; the bundle-price witness can be checked directly against its polynomial-size offered menu.
This statement concerns existence of an outcome attaining the threshold. It does not replace that condition by a comparison with a possibly unattained supremum.
Suppose $|S_t|\le1$ for every type. A polynomial-time item-price algorithm achieves $\mathrm{OPT}_{BP}$ exactly.
The values and budgets may be heterogeneous.
Consider any bundle-price outcome. Types with empty interest sets pay zero by individual rationality.
For each label $j$ occurring in an offered bundle, let
$$ p_j=\min\{P(X):X\text{ is offered and }j\in X\}. $$
Consider a type with $S_t=\{j\}$ that receives a bundle containing $j$ at price $P$. Individual rationality gives $P\le v_t$ and $P\le b_t$. Because $p_j\le P$, a bundle attaining $p_j$ is affordable. Envy-freeness gives
$$ v_t-P\ge v_t-p_j, $$
so $P=p_j$.
Moreover, if $v_t>p_j$, the cheapest offered bundle containing $j$ is affordable because
$$ p_j<v_t\le b_t, $$
and gives strictly positive utility. Every member of this type must therefore receive a bundle containing $j$.
Replace each assigned bundle by its recipient’s interested singleton when it contains that singleton, and otherwise by the outside option. Price singleton $j$ at $p_j$. For a label in no offered bundle, choose a price strictly above $V$.
This replacement weakly reduces every supply load and preserves revenue. It is item-price envy-free:
Thus every bundle-price outcome is matched in revenue by an item-price outcome.
Each label can now be optimized independently. For every distinct value $p$ among types interested in $j$, define
$$ H_j(p)=\sum_{t:S_t=\{j\},\ v_t>p}\mu_t, $$
$$ E_j(p)=\sum_{t:S_t=\{j\},\ v_t=p}\mu_t. $$
Price $p$ is feasible exactly when
$$ H_j(p)\le q_j. $$
Its maximum revenue is
$$ r_j(p)=p\min\{q_j,H_j(p)+E_j(p)\}. $$
Serve all strictly demanding types, then fill the remaining capacity with indifferent types. The largest interested value is always a feasible candidate.
These candidate prices dominate all other feasible prices with positive revenue. Given such a price $P$, let $p$ be the smallest interested value satisfying $v_t\ge P$. Every buyer served at $P$ remains willing and affordable at $p$, and every type strictly demanding at $p$ already strictly demanded at $P$. Keeping the same allocation therefore remains feasible and weakly increases revenue.
Choose the best candidate independently for every label. Since each type is interested in at most one label, the resulting allocations combine without any additional budget or demand interaction.
The algorithm uses at most $\tau$ candidates per label and polynomial-time rational arithmetic. It dominates every bundle-price outcome. Conversely, restricting an item-price outcome to its assigned bundles gives a valid bundle-price outcome. Hence the algorithm’s revenue equals $\mathrm{OPT}_{BP}$.
The general question now has a finite rational optimization description, polynomial-size near-optimal outcomes, and polynomial-time price optimization for fixed $m$. The exact singleton-interest result also permits arbitrary heterogeneous values and rational supplies.
What is missing is a bound connecting the two revenue suprema for arbitrary interest sets, together with a uniform polynomial-time construction meeting the exact requested threshold. None of the price-region arguments proves
$$ R\ge\frac{\mathrm{OPT}_{BP}}4 $$
for general inputs. The fixed-$m$ enumeration has an exponent depending on $m$, and polynomial-size certificates do not themselves provide polynomial-time search.
⟨structured verdict parsed — rendered above⟩
The output establishes substantive partial results, but does not settle the requested quarter approximation. Its fixed-dimension optimization arguments, representation bounds, and singleton-interest result are sound in substance. I found two minor specification issues and no false central step.
1. Scope and finiteness
The prover correctly distinguishes its results from the target: polynomial time for each fixed $m$ does not imply time polynomial jointly in $m,\tau,L$.
The bound
$$ R\le\sum_t\mu_t b_t $$
is valid for both models. Every positively assigned bundle must be affordable: item-price demand includes the outside option, and bundle-price individual rationality excludes utility $-\infty$. Thus both suprema are finite.
2. Exact demand description — Section 1.1
The reduction to interested bundles is valid. Removing labels outside $S_t$ preserves value, weakly reduces payment, and preserves affordability.
In the first case, the stated utility bound is correct. Equality requires every strictly positive-surplus label and excludes every negative-surplus label. Labels priced exactly at $v_t$ contribute zero surplus, and their number is limited precisely by the remaining budget. The formula for $r_t$ is therefore correct, including the cases of an empty interest set or no zero-surplus labels.
In the second case:
Consequently, maximizing bundles are exactly the cheapest $d_t$-element subsets. The description using $F_t,E_t,h_t$ correctly accounts for ties at the cutoff.
The use of $b_t\ge v_t$ to obtain $d_t\ge1$ is justified. There is no missing demand case.
3. Compact allocation and decomposition — Section 1.2
The residual-supply constraints are necessary, since every member of a type receives every label in $F_t$.
The sufficiency construction is also valid. After adding dummy coordinates, the total interval length is the integer $u_t$. The sampling procedure selects exactly $u_t$ coordinates, with each coordinate’s inclusion probability equal to its length. Discarding at most $u_t-\ell_t$ dummy coordinates leaves an admissible optional set.
The claimed support bound is valid: there are at most
$$ |E_t|+u_t-\ell_t\le2m $$
coordinates, so partitioning at fractional interval endpoints gives at most $2m+1$ pieces. Rational input coordinates yield rational probabilities. The separate treatment of $u_t=0$ covers the degenerate construction.
The fixed-price revenue formula is correct. The subsequent support reduction preserves type masses, all label loads, demand validity, and item-price revenue. The linear-dependence argument correctly bounds the number of positive entries by $\tau+m$.
4. Open regions and arrangements — Section 2
The closure argument is valid under the stated nonemptiness assumption. Mixing a weakly feasible point with a point satisfying every strict constraint preserves all weak constraints and makes every original strict inequality strict.
The positive-margin linear program correctly tests strict feasibility. A point satisfying finitely many strict inequalities has a positive minimum slack; the bound $\eta\le1$ does not affect whether positive slack exists.
The arrangement bound includes lower-dimensional sign regions. The insertion recurrence gives the stated upper bound, and successive sign-pattern extension with feasibility testing yields polynomial enumeration in fixed dimension. Degenerate or repeated hyperplanes do not invalidate the upper bound.
5. Fixed-$m$ item-price optimization — Section 3
The price truncation argument is valid. An interested label priced above $V$ cannot occur in a demanded bundle. After lowering such prices to $V$, removing those labels from an alternative weakly increases its utility and leaves an alternative evaluated at unchanged prices. Thus previously assigned bundles remain optimal and their payments remain unchanged.
The proposed arrangement fixes all information required by the demand description:
Hence the allocation polytope is constant within each region.
The affine revenue argument is correct. First-case optional labels have price $v_t$; second-case optional labels have a common price and a fixed total assigned mass. Consequently, a single allocation maximizing $C$ works throughout the region.
Optimizing over weak closures computes the supremum, without assuming boundary prices retain the region’s demand. The mixture construction returns to the original region, where that allocation is valid, and establishes
$$ R\ge(1-\varepsilon)\mathrm{OPT}_{IP}. $$
The running-time conclusion is correctly limited to fixed $m$.
6. Fixed-$m$ bundle-price optimization — Section 4
Allowing temporarily unassigned menu entries does not change the supremum. Deleting them weakens the envy constraints and preserves assigned payments.
The bound $P_X\le B$ is valid for genuinely assigned bundles. The affordability and utility-comparison hyperplanes determine demand throughout each region, including comparisons with the outside option.
The revenue linearization follows from equality of utilities among demanded bundles and the fixed type masses. Although $C$ need not itself be nonnegative, the complete affine objective is feasible revenue and is nonnegative within the region. This suffices for the mixture guarantee.
The dimension and menu count are constants when $m$ is fixed. Thus this theorem is justified, but supplies no uniform polynomial-time algorithm.
7. Sparse supports and encoding bounds — Section 5
The bundle-price sparsification argument is correct. At fixed prices and menu, the original allocation lies in the demand allocation polytope. An optimal extreme point exists, and the stated perturbation argument bounds its positive entries by $\tau+m$. Deleting newly unassigned menu entries preserves validity.
For a fixed sparse support and affordability pattern, the utility equalities and conditional envy inequalities correctly express the benchmark constraints. The revenue identity
$$ R= \sum_{t,X}a_{t,X}v_t|X\cap S_t| - \sum_t\mu_tU_t $$
is correct: the assigned-pair utility equalities eliminate prices, and the type-mass equalities eliminate products involving $U_t$.
Minor issue: Section 5.2 introduces price variables only for nonempty bundles, but then writes assigned-pair equalities that can involve the empty bundle. It should explicitly retain the convention $P_{\varnothing}=0$ in this formulation. The convention already appears earlier, so this is a notation issue rather than a substantive gap.
The bounds on prices, utilities, and masses are valid. Rational vertex encoding bounds apply because each relevant system has polynomial dimension and coefficients of polynomial encoding length. Exponentially many regions or support patterns do not invalidate a uniform bit-length bound on each candidate optimum.
The finite-maximum and weak-closure arguments therefore justify rational suprema of polynomial encoding length. The positive-margin and mixture arguments justify polynomial-size near-optimal outcomes.
The certificate claims also stand. Adding the exact threshold before testing strict feasibility preserves the distinction between attaining a threshold and merely having that threshold as an unattained supremum. Verification uses the proved demand calculation for item prices and the polynomial-size offered menu for bundle prices.
8. Singleton-interest result — Section 6
The benchmark comparison is correct.
A type interested only in $j$ pays zero for a bundle lacking $j$, by individual rationality. If it receives a bundle containing $j$, individual rationality makes that payment at most $v_t$. The cheapest offered bundle containing $j$ is then affordable, and envy-freeness forces the assigned payment to equal $p_j$.
If $v_t>p_j$, that cheapest bundle gives strictly positive utility, so the type’s entire mass must receive a bundle containing $j$. Replacing assigned bundles by interested singletons or the outside option therefore preserves revenue, weakly reduces supplies used, and satisfies item-price demand.
The candidate-price feasibility condition and revenue formula are correct. At a candidate value $p$, all mass with value strictly above $p$ must be served, while equal-value mass can be allocated up to remaining capacity.
The candidate-dominance argument is valid: raising a feasible positive-revenue price to the next interested value preserves willingness of previously served types and creates no additional strictly demanding types.
Minor issue: The instruction to choose the best candidate for every label is undefined when no type is interested in that label. For example, $m=\tau=1$ and $S_1=\varnothing$ produces an empty candidate set. This does not undermine the theorem, but the algorithm must explicitly specify its treatment of such labels, including the case where all interest sets are empty.
The reverse benchmark comparison is valid: restricting an item-price outcome to its assigned bundles preserves individual rationality and envy-freeness. Thus the singleton-interest algorithm attains $\mathrm{OPT}_{BP}$ once the routine empty-candidate case is specified.
9. What is established and what remains missing
The genuine progress consists of:
The general approximation question remains unresolved. The output establishes neither a quarter-factor comparison for arbitrary interest sets nor a construction meeting that factor in time polynomial jointly in $m,\tau,L$. These are acknowledged limitations, not concealed errors.
The minimum write-up repairs are to state the empty-bundle price convention in Section 5.2 and specify the algorithm’s behavior for labels with no interested types. Neither repair resolves the general approximation question.
⟨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.