Answer: Yes. A deterministic polynomial-time construction produces an efficiently samplable distribution \(P\) satisfying \(V(P)\ge(1-1/e-\varepsilon)\mathrm{OPT}\), with success probability \(1\).
Theorem 3.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet ε > 0 and α ∈N. Assume an oracle that, in poly(n, m, ε−1) time and with high probability, out- puts an additive ε/(nk)-approximation to the problem (3). Then Algorithm ε-prob greedy in poly(n, m, ε−1) time computes vectors x1, . . . , xk satisfying g(ES∼x1,...,xk[f(S)]) ≥ 1 −1 e −ε · opt with probability at least 1 −µ−α, where µ = max{n, m}. Here, for k vectors x1, . . . , xk each non-negative and of one-norm 1, ES∼x1,...,xk[f(S)] is the expected value result- ing from generating a set S of size at most k by indepen- dently sampling the t-th element according to xt for t ∈[k].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a seed universe \(U\), a limit \(k\), a finite support \(T\) of audience types with rational masses \(\mu_t>0\) summing to \(1\), monotone submodular per-capita benefit functions \(f_t:2^U\to\mathbb{R}_{\ge 0}\), and rational \(\lambda\in(0,1)\), compute an efficiently samplable distribution \(P\) over sets \(S\subseteq U\) with \(|S|\le k\) whose value is at least \((1-1/e-\varepsilon)\mathrm{OPT}\), where \(\mathrm{OPT}=\max_P\left[\min_{t\in T}\mathbb{E}_{S\sim P}[f_t(S)]+\lambda\sum_{t\in T}\mu_t\mathbb{E}_{S\sim P}[f_t(S)]\right]\).
Let \(U\) have size \(m\ge1\), and let \(1\le k\le m\) be an integer. A society is given by its support: a list \(T\) of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts supported types, not all possible types.
Each type has a nonnegative monotone submodular benefit function \(f_t\), given by a value oracle returning binary rationals. Assume \(f_t(S)\le B\) for every feasible set, where \(B\) is bounded by a fixed polynomial in \(m,\tau\), and each type has some feasible set with benefit at least \(1\). Let \(L\) denote the total explicit input bit length plus the maximum oracle-answer bit length.
For rational \(\lambda\in(0,1)\), let \(\mathcal S=\{S\subseteq U:|S|\le k\}\). For any probability distribution \(P\) on \(\mathcal S\), define \(V(P)=\min_{t\in T}\mathbb E_{S\sim P}[f_t(S)]+\lambda\sum_{t\in T}\mu_t\mathbb E_{S\sim P}[f_t(S)]\) and \(\mathrm{OPT}=\max_P V(P)\). Output distributions may be represented by sampling algorithms.
For every rational \(0<\varepsilon<1-1/e\), can a randomized algorithm, with probability at least \(2/3\), compute an efficiently samplable distribution \(P\) satisfying \(V(P)\ge(1-1/e-\varepsilon)\mathrm{OPT}\), using time and value-oracle queries polynomial in \(m,\tau,L,k,\varepsilon^{-1}\)?
Known results: for finitely many agents, a randomized polynomial-time \((1-1/e-\varepsilon)\)-approximation is established for cardinality-constrained ex-ante aggregation under the stated benefit bounds and suitable concave aggregation assumptions. The finite-support mass-weighted objective above is already covered by that general result; consequently this target is settled, not open. [Verified source](https://ojs.aaai.org/index.php/AAAI/article/view/38428/42390).
Yes. In fact, a deterministic polynomial-time algorithm can construct a distribution with polynomial support satisfying the requested guarantee. Randomness is needed only to sample from that distribution.
This conclusion agrees with Theorem 3.1 of Becker, Kodric, and Vinci, [*Greedily Maximizing Ex-Ante Fairness*](https://ojs.aaai.org/index.php/AAAI/article/view/38428/42390). Below is a self-contained proof for the objective in the question.
Write \(\alpha=1-1/e\). For each supported type \(t\), define
\(h_t(S)=f_t(S)+\lambda\sum_{s\in T}\mu_s f_s(S).\)
These functions are nonnegative, monotone, and submodular: each is a nonnegative linear combination of functions with those properties. Moreover,
\(V(P)=\min_{t\in T}\mathbb E_{S\sim P}[h_t(S)].\)
Thus the task is to maximize the minimum expected payoff among the \(\tau\) functions \(h_t\).
Because \(\mathcal S\) is finite and \(V\) is continuous on its probability simplex, an optimal distribution \(P^\star\) exists. Choose, for each \(t\), a feasible witness \(A_t\) with \(f_t(A_t)\ge1\). The uniform mixture of these witnesses gives every type expected benefit at least \(1/\tau\). Consequently,
\(\mathrm{OPT}\ge1/\tau.\)
The algorithm will not need to find these witnesses.
We first compute an integer upper bound without assuming that \(B\) is explicitly supplied. Query all singleton values and set
\(C=\left\lceil\max_{t\in T}\sum_{u\in U}f_t(\{u\})\right\rceil,\qquad M=2C.\)
For any nonempty set \(S\), telescoping its elements and applying diminishing returns gives
\(f_t(S)\le f_t(\varnothing)+\sum_{u\in S}\bigl(f_t(\{u\})-f_t(\varnothing)\bigr)\le\sum_{u\in S}f_t(\{u\}).\)
For the empty set, monotonicity and \(m\ge1\) give \(f_t(\varnothing)\le f_t(\{u\})\) for any \(u\in U\). Therefore \(f_t(S)\le C\) for every \(S\subseteq U\).
The witness assumption implies \(C\ge1\). Since singletons are feasible, the given bound implies \(C\le mB+1\). Finally,
\(0\le h_t(S)\le(1+\lambda)C\le M.\)
Hence \(M\) is computable and polynomially bounded in \(m,\tau\).
For any probability vector \(q=(q_t)_{t\in T}\), consider
\(F_q(S)=\sum_{t\in T}q_t h_t(S)=\sum_{t\in T}(q_t+\lambda\mu_t)f_t(S).\)
This is a nonnegative monotone submodular function. Its values and marginal gains can be computed using the given value oracles.
Starting at \(\varnothing\), perform \(k\) greedy steps, each adding an unused element of maximum marginal gain. Let \(A_j\) denote the set after \(j\) steps, and let \(O\) maximize \(F_q\) over \(\mathcal S\).
Monotonicity and diminishing returns imply
\(F_q(O)-F_q(A_j)\le F_q(A_j\cup O)-F_q(A_j)\le\sum_{u\in O\setminus A_j}\bigl(F_q(A_j\cup\{u\})-F_q(A_j)\bigr).\)
There are at most \(k\) summands. Thus, for \(j<k\), greedy obtains
\(F_q(A_{j+1})-F_q(A_j)\ge\bigl(F_q(O)-F_q(A_j)\bigr)/k.\)
Iterating this recurrence and using \(F_q(\varnothing)\ge0\) yields
\(F_q(A_k)\ge\bigl(1-(1-1/k)^k\bigr)F_q(O)\ge\alpha F_q(O).\)
The last inequality is immediate for \(k=1\); for \(k>1\), it follows from \(\log(1-1/k)\le-1/k\).
Furthermore,
\(\max_{S\in\mathcal S}F_q(S)\ge\mathbb E_{S\sim P^\star}[F_q(S)]=\sum_tq_t\mathbb E_{P^\star}[h_t(S)]\ge\mathrm{OPT}.\)
Therefore the greedy set \(S_q\) satisfies
\(\sum_tq_t h_t(S_q)\ge\alpha\,\mathrm{OPT}.\)
This comparison is with the optimal unrestricted distribution, not merely the optimal deterministic set.
Set
\(\eta=\varepsilon/(2M\tau),\)
and let \(N\) be the smallest power of two satisfying
\(N\ge4M^2\tau^3/\varepsilon^2.\)
Initialize \(w_{1,t}=1\) for every type. For rounds \(r=1,\ldots,N\):
\(w_{r+1,t}=w_{r,t}(1-\eta\ell_{r,t})\).
All losses satisfy \(0\le\ell_{r,t}\le1\). Also \(0<\eta<1/2\), so every weight remains positive.
Output the distribution \(P\) that chooses a uniformly random round \(r\in\{1,\ldots,N\}\) and returns \(S_r\).
Let \(W_r=\sum_t w_{r,t}\). The update gives
\(W_{r+1}=W_r\left(1-\eta\sum_tq_{r,t}\ell_{r,t}\right).\)
Using \(\log(1-z)\le-z\), and \(W_1=\tau\), we obtain
\(\log W_{N+1}\le\log\tau-\eta\sum_{r=1}^N\sum_tq_{r,t}\ell_{r,t}.\)
For \(0\le z\le1/2\), the complementary inequality is
\(\log(1-z)\ge-z-z^2.\)
Indeed, the function \(\log(1-z)+z+z^2\) vanishes at zero and has derivative \(z(1-2z)/(1-z)\ge0\) on this interval.
Applying this inequality to the update of any fixed type \(t\), and using \(\ell_{r,t}^2\le1\), gives
\(\log w_{N+1,t}\ge-\eta\sum_{r=1}^N\ell_{r,t}-\eta^2N.\)
Since \(w_{N+1,t}\le W_{N+1}\), combining the two bounds and rearranging yields
\(\frac1N\sum_{r=1}^N\ell_{r,t}\ge\frac1N\sum_{r=1}^N\sum_sq_{r,s}\ell_{r,s}-\eta-\frac{\log\tau}{\eta N}.\)
Multiplying by \(M\) and taking the minimum over \(t\), we conclude
\(V(P)\ge\frac1N\sum_{r=1}^N\sum_tq_{r,t}h_t(S_r)-M\eta-\frac{M\log\tau}{\eta N}.\)
Section 3 bounds every round’s weighted payoff below by \(\alpha\,\mathrm{OPT}\). Moreover,
\(M\eta=\varepsilon/(2\tau),\)
and the choice of \(N\), together with \(\log\tau\le\tau\), implies
\(\frac{M\log\tau}{\eta N}=\frac{2M^2\tau\log\tau}{\varepsilon N}\le\frac{\varepsilon\log\tau}{2\tau^2}\le\frac{\varepsilon}{2\tau}.\)
Therefore
\(V(P)\ge\alpha\,\mathrm{OPT}-\varepsilon/\tau.\)
Finally, \(\mathrm{OPT}\ge1/\tau\), so
\(V(P)\ge(\alpha-\varepsilon)\mathrm{OPT}=(1-1/e-\varepsilon)\mathrm{OPT}.\)
Every step is deterministic, so the construction succeeds with probability \(1\), exceeding the required \(2/3\).
The initial bound requires \(m\tau\) oracle queries. Each greedy call uses at most \(O(km\tau)\) queries, and evaluating its final payoffs requires at most another \(\tau\). Thus the total query count is \(O(m\tau+Nkm\tau)\), which is polynomial in the required parameters because \(M\le2(mB+1)\).
Exact rational arithmetic also has polynomial bit complexity. Each payoff \(h_t(S_r)\) is a sum of \(\tau+1\) products of input or oracle rationals, so its bit length is polynomial in \(\tau,L\). Each weight is a product of at most \(N\) rational update factors of polynomial bit length; its numerator and denominator therefore have polynomial bit length. Normalizing the weights and evaluating greedy comparisons preserve polynomial bit length and require polynomial time.
The stored list \(S_1,\ldots,S_N\) has polynomial size. Because \(N\) is a power of two, sampling a uniform round uses exactly \(\log_2N\) independent fair bits. Returning its stored feasible set takes polynomial time.
In particular, the algorithm depends on the number \(\tau\) of supported types, with no dependence on reciprocals of their masses.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned approximation problem. Its construction and analysis are correct, including the stronger claim that the distribution can be constructed deterministically. I found no major or minor mathematical issues.
Each \(h_t\) is a nonnegative linear combination of the given functions, so nonnegativity, monotonicity, and submodularity are preserved. The mass-weighted term is independent of the index over which the minimum is taken, giving exactly
\(V(P)=\min_t\mathbb E_P[h_t(S)]\).
The feasible family is finite and nonempty. Its probability simplex is compact, and the minimum of finitely many linear functions is continuous. Thus an optimal distribution exists.
The witness mixture correctly establishes \(\mathrm{OPT}\ge1/\tau\): for each type, its own witness contributes at least \(1/\tau\), and all other contributions and the mass-weighted term are nonnegative. The witnesses are used only for analysis, so the algorithm does not need to find them.
The telescoping inequality does not assume \(f_t(\varnothing)=0\). For a nonempty set \(S\), its intermediate upper bound equals
\(\sum_{u\in S}f_t(\{u\})-(|S|-1)f_t(\varnothing)\), which is at most the singleton sum by nonnegativity.
The empty-set argument is valid because \(m\ge1\). Consequently, \(C\) bounds every set value, even though the task supplies \(B\) only for feasible sets.
Since \(k\ge1\), all singletons are feasible, giving \(C\le mB+1\). The witness assumption gives \(C\ge1\), so \(M=2C\) is positive and polynomially bounded. Finally, \(\sum_s\mu_s=1\) and \(0<\lambda<1\) justify \(0\le h_t(S)\le M\).
The expression for \(F_q\) has nonnegative coefficients, so its asserted properties hold. The comparison with \(A_j\cup O\) is legitimate even if that union is infeasible: the functions are defined and submodular on all subsets.
The marginal-sum inequality follows from diminishing returns. For \(j<k\), an unused element exists because \(k\le m\). Also, \(F_q(O)\ge F_q(A_j)\), since \(A_j\) is feasible. Thus the greedy marginal bound and its recurrence have the correct sign.
Iteration gives the stated factor without requiring normalization at the empty set. The cases \(k=1\) and \(k>1\) are handled correctly.
The comparison with \(P^\star\) is also valid: every expected \(h_t\)-payoff under \(P^\star\) is at least \(\mathrm{OPT}\), and \(q\) is a probability vector. Hence every round achieves weighted payoff at least \(\alpha\mathrm{OPT}\), with respect to the distributional optimum.
The normalized losses lie in \([0,1]\). Since \(M\ge2\), \(\tau\ge1\), and \(\varepsilon<1\), the learning rate satisfies \(0<\eta<1/2\). Every update factor is positive, so every normalization is defined.
Each stored set has exactly \(k\) elements and is therefore feasible. Uniformly selecting a stored round defines a valid distribution; repeated sets simply receive their combined probability.
Both logarithmic inequalities are applied within their valid domains. The derivative supplied for the lower inequality is correct.
Comparing the lower bound on \(\log w_{N+1,t}\) with the upper bound on \(\log W_{N+1}\) yields the displayed regret inequality with the correct direction. Multiplication by \(M\) and minimization over types then give the claimed bound on \(V(P)\).
Substituting \(\eta\) and the lower bound on \(N\) gives errors at most \(\varepsilon/(2\tau)\) each. The inequality \(\log\tau\le\tau\) is valid for every integer \(\tau\ge1\), including \(\tau=1\), where the logarithmic term vanishes.
Therefore \(V(P)\ge\alpha\mathrm{OPT}-\varepsilon/\tau\). The previously established lower bound on \(\mathrm{OPT}\) correctly converts this into \(V(P)\ge(\alpha-\varepsilon)\mathrm{OPT}\).
Taking the smallest qualifying power of two increases the required round count by less than a factor of two. Thus \(N\) remains polynomial in the stated parameters.
The oracle-query count is valid. Greedy queries feasible sets, while its analysis may use larger sets without querying them.
Exact arithmetic remains polynomial: each update factor uses payoffs computed directly from input and oracle rationals, whose bit lengths are polynomially bounded. Multiplying at most \(N\) such factors adds their bit lengths. Summing and normalizing the resulting \(\tau\) weights, and performing greedy comparisons, therefore also require polynomial bit length and time.
The stored list has polynomial size. Power-of-two support permits exact uniform sampling using \(\log_2N\) fair bits. No reciprocal-mass dependence is introduced.
The cited [Theorem 3.1](https://ojs.aaai.org/index.php/AAAI/article/view/38428/42390) concerns the stated cardinality-constrained ex-ante approximation setting and includes additional aggregation and oracle assumptions. The prover mentions it as corroboration; no step of the submitted proof relies on applying it. Consequently, the absence of a detailed theorem-hypothesis mapping does not create a gap in this self-contained argument.
The output establishes the requested polynomial-time approximation guarantee and deterministic construction success. No 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.