Answer: Exactly solvable in polynomial time; therefore admits an \(m+1\)-approximation in time polynomial in \(m,\tau,L\).
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 2 provides an m + 1 approximation of the optimal outcome according to Equation 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given item categories with per-capita supplies \(b_i\) and bidder types \(t\) with masses \(\mu_t\), bundles \(S_t\), values \(v_t\), and cohort-withdrawal probabilities \(p_t\), compute an initial allocation and contingent repairs maximizing expected social welfare when at most one type cohort withdraws.
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) item categories with positive per-capita supplies \(b_i\), and \(\tau\geq2\) known single-minded types with nonempty bundles \(S_t\subseteq\{1,\ldots,m\}\) and values \(v_t>0\). Serving one unit of type mass consumes one unit of each category in its bundle; mass may be split between served and unserved agents.
All numerical inputs are binary rationals; \(L\) is their total encoding length together with the bundle descriptions. Exogenous probabilities satisfy \(0\leq p_t<1/2\) and \(\sum_t p_t\leq1\): event \(k\), of probability \(p_k\), removes the entire type cohort \(k\); otherwise no cohort withdraws, and no further withdrawal occurs.
An allocation specifies initially served masses \(0\leq x_t\leq\mu_t\) and additional served masses \(r_{kt}\geq0\) following event \(k\), with \(r_{kk}=0\) and \(x_t+r_{kt}\leq\mu_t\) for \(t\neq k\). Nonwithdrawn initial recipients retain their bundles; unused supplies may be discarded, and there are no repair costs or minimum-welfare requirements.
Feasibility requires \(\sum_{t:i\in S_t}x_t\leq b_i\) and \(\sum_{t\neq k:i\in S_t}(x_t+r_{kt})\leq b_i\) for every category \(i\) and event \(k\).
Expected welfare is \(W(x,r)=\sum_t(1-p_t)v_tx_t+\sum_k p_k\sum_{t\neq k}v_tr_{kt}\); let \(\mathrm{OPT}\) be its maximum over feasible allocations and repairs.
Does this continuous allocation problem admit an \((m+1)\)-approximation in time polynomial in \(m,\tau,L\), or is achieving this approximation ratio NP-hard?
For discrete single-minded bidders with unit item supplies and irrevocable assignments, a polynomial-time \((m+1)\)-approximation for expected welfare under single-bid withdrawal is reported by [Holland and O’Sullivan](https://www.ijcai.org/Proceedings/07/Papers/212.pdf).
No result settling this approximation question for the specified continuous cohort-withdrawal model was located.
The problem is exactly solvable in time polynomial in \(m,\tau,L\). Consequently, it admits an \((m+1)\)-approximation.
Exact linear-programming formulation. Let \(T=\{1,\ldots,\tau\}\), define \(a_{it}=1\) when \(i\in S_t\) and \(a_{it}=0\) otherwise, and put \(q=1-\sum_{k\in T}p_k\). By hypothesis, \(q\geq0\).
For each ordered pair \(k,t\in T\) with \(t\neq k\), introduce \(y_{kt}\), the total mass of type \(t\) served after event \(k\). Consider the following linear program in the variables \(x_t\) and \(y_{kt}\):
\[ \text{maximize}\quad q\sum_{t\in T}v_tx_t+ \sum_{k\in T}p_k\sum_{t\neq k}v_ty_{kt}, \]
subject to
\[ 0\leq x_t\leq\mu_t \qquad(t\in T), \]
\[ x_t\leq y_{kt}\leq\mu_t \qquad(k,t\in T,\ t\neq k), \]
\[ \sum_{t\in T}a_{it}x_t\leq b_i \qquad(i=1,\ldots,m), \]
\[ \sum_{t\neq k}a_{it}y_{kt}\leq b_i \qquad(i=1,\ldots,m,\ k\in T). \]
The lower bounds \(y_{kt}\geq x_t\) express retention of every nonwithdrawn initial recipient’s bundle.
Proof of equivalence. Given any feasible allocation and repairs, set \(y_{kt}=x_t+r_{kt}\) for \(t\neq k\). The original mass bounds, nonnegative repair bounds, and capacity constraints imply every displayed LP constraint.
Conversely, given any feasible LP solution, set \(r_{kt}=y_{kt}-x_t\) for \(t\neq k\), and \(r_{kk}=0\). These repairs are nonnegative, satisfy \(x_t+r_{kt}\leq\mu_t\), and meet every original capacity constraint. Thus the two feasible sets correspond bijectively.
Their objective values also agree. Indeed,
\[ \begin{aligned} q\sum_t v_tx_t+\sum_kp_k\sum_{t\neq k}v_ty_{kt} &=\sum_t\left(q+\sum_{k\neq t}p_k\right)v_tx_t +\sum_kp_k\sum_{t\neq k}v_tr_{kt}\\ &=\sum_t(1-p_t)v_tx_t +\sum_kp_k\sum_{t\neq k}v_tr_{kt}\\ &=W(x,r). \end{aligned} \]
The second equality uses \(q+\sum_{k\neq t}p_k=1-p_t\). Therefore the LP optimum equals \(\mathrm{OPT}\) exactly.
Polynomial bit complexity. The LP has \(\tau+\tau(\tau-1)=\tau^2\) variables and \(2\tau^2+m(\tau+1)\) scalar inequalities. In particular, its size depends on the listed support, with no enumeration of other possible types.
All constraint coefficients belong to \(\{-1,0,1\}\), and all right-hand sides are supplied rational numbers. The objective coefficients are \(qv_t\) and \(p_kv_t\). Computing \(q\) and these products requires polynomially many bit operations and produces rational numbers of polynomial encoding length. For example, a common denominator for the sum defining \(q\) can be the product of the input denominators; its binary length is at most their total binary length. Consequently, the entire LP has encoding length polynomial in \(m,\tau,L\).
The feasible region is nonempty because \(x=y=0\) is feasible. It is closed and bounded because every variable lies between zero and its corresponding \(\mu_t\). Hence the linear objective attains a finite maximum.
The polynomial-time theorem for rational linear programming computes an exact rational optimum in time polynomial in the LP’s encoding length; exact optimization, including rational recovery, is discussed in [Vishnoi’s linear-programming lecture notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf). All its required hypotheses hold here. Recovering \(r_{kt}=y_{kt}-x_t\) also takes polynomial time.
The resulting allocation satisfies \(W(x,r)=\mathrm{OPT}\geq\mathrm{OPT}/(m+1)\). This settles the specified continuous model for all admissible inputs.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The LP represents the specified continuous cohort-withdrawal model exactly, has polynomial encoding length, and satisfies the hypotheses of polynomial-time rational linear programming. No major or minor mathematical issues were found.
For each event \(k\) and surviving type \(t\neq k\), \(y_{kt}\) denotes total served mass after withdrawal. The constraints \(x_t\leq y_{kt}\leq\mu_t\) correctly express both retention of initial recipients and the cohort mass bound.
Omitting \(y_{kk}\) correctly represents withdrawal of the entire cohort \(k\). The initial capacity constraints and event-specific capacity constraints match the task. No integrality constraint is needed because the task explicitly permits splitting mass.
Starting with an original feasible allocation, the substitution \(y_{kt}=x_t+r_{kt}\) satisfies every LP constraint: nonnegative repairs give \(y_{kt}\geq x_t\), cohort bounds give \(y_{kt}\leq\mu_t\), and the event capacity constraints become precisely the displayed LP inequalities.
Conversely, \(r_{kt}=y_{kt}-x_t\) for \(t\neq k\), together with \(r_{kk}=0\), satisfies all original repair and capacity constraints. These transformations are inverse to each other because the diagonal repairs are fixed at zero. The claimed bijection is therefore correct.
The no-withdrawal probability is \(q=1-\sum_kp_k\geq0\). After substituting \(y_{kt}=x_t+r_{kt}\), the coefficient of \(v_tx_t\) is \(q+\sum_{k\neq t}p_k=1-p_t\). The coefficient of each repair contribution is \(p_kv_t\), exactly as in the task.
Thus the objective equality holds for every corresponding feasible pair, not merely at an optimum. Consequently, the LP optimum equals \(\mathrm{OPT}\).
The variable count is correct: \(\tau+\tau(\tau-1)=\tau^2\).
Counting each side of a two-sided bound separately gives \(2\tau\) initial mass inequalities and \(2\tau(\tau-1)\) event mass inequalities. Adding \(m\) initial capacity inequalities and \(m\tau\) event capacity inequalities yields exactly \(2\tau^2+m(\tau+1)\) scalar inequalities.
The constraint coefficients are in \(\{-1,0,1\}\), and the right-hand sides are input rationals. The stated denominator-product bound correctly establishes polynomial encoding length for \(q\). Multiplication by input values also preserves polynomial encoding length for the objective coefficients. Repetition of coefficients and right-hand sides across polynomially many entries remains polynomial.
The construction uses only the listed support; it does not enumerate other possible bundles or types.
The zero solution is feasible because all supplies are positive. Every variable is bounded between zero and its corresponding \(\mu_t\), and the constraints define a closed set. Hence the feasible region is nonempty and compact, and the linear objective attains a finite maximum.
The invoked theorem is applicable: a rational LP with a nonempty feasible region and a finite attained optimum admits an exact rational optimal solution computable in time polynomial in its encoding length. The cited [Vishnoi lecture notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf), immediately following Theorem 1, explicitly discuss conversion to exact optimization by rational recovery. The prover invokes this general result; it does not require optimal-solution uniqueness or a supplied interior starting point.
Recovering the repairs by rational subtraction takes polynomial time.
An exact optimal allocation satisfies \(W(x,r)=\mathrm{OPT}\geq\mathrm{OPT}/(m+1)\), since welfare is nonnegative and \(m\geq1\).
Zero-probability events cause no difficulty: their feasibility constraints remain enforced, as the task requires. The case \(q=0\) likewise preserves the formulation and objective identity. Unused categories, overlapping bundles, and multiple optimal allocations introduce no missing hypothesis.
No additional clarification or repair is needed. The continuous approximation question is settled by the exact polynomial-time formulation.
⟨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.