Answer: —
Theorem 15 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet Rf be a decomposable committee scor- ing rule defined through a family of scoring functions fm,k(i1, . . . , ik) = γ(1) m,k(i1) + γ(2) m,k(i2) + · · · + γ(k) m,k(ik), where γ = (γ(t) m,k)tkm is a family of polynomial-time com- putable single-winner scoring functions. If for each m, each k 2 [m], each i 2 [k −1] and each p 2 [m], it holds that γi−1(p) ≥γi(p), then there is a polynomial-time al- gorithm that, given an election E = (C, V ) and a commit- tee size k, outputs a committee W such that scoreE(W) ≥ (1 −1 e) maxS✓C,|W |=k scoreE(S).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates, committee size \(k\), a finite set \(T\) of complete ranking types, rational masses \(\mu\in\Delta^{|T|}\), and decomposable scores \(f_{m,k}(i_1,\ldots,i_k)=\sum_{j=1}^{k}\gamma^{(j)}_{m,k}(i_j)\) satisfying the paper's adjacent-layer condition, compute a committee \(S\subseteq C\) with \(|S|=k\) such that \(F_\mu(S)\ge (1-1/e)\max_{|S'|=k}F_\mu(S')\), where \(F_\mu(S)=\sum_{r\in T}\mu_r f_{m,k}(\operatorname{pos}_r(S))\).
Given a candidate set \(C\) with \(|C|=m\geq1\) and an integer \(1\leq k\leq m\), a society is given by its support: a list \(T\) of \(\tau\) distinct strict complete ranking types, each with positive binary-rational mass \(\mu_r\), where \(\sum_{r\in T}\mu_r=1\). Here \(\tau=|T|\) is the support size, not the number of possible rankings.
The input also contains binary-encoded nonnegative integer scoring tables \(\gamma^{(j)}_{m,k}:\{1,\ldots,m\}\to\mathbb Z_{\geq0}\), nonincreasing in position, satisfying \(\gamma^{(j)}_{m,k}(p)\geq\gamma^{(j+1)}_{m,k}(p)\) for every \(1\leq j<k\) and \(1\leq p\leq m\). Let \(L\) denote the total input bit length.
For a committee \(S\subseteq C\) of size \(k\), let \(\operatorname{pos}_r(S)=(i_1,\ldots,i_k)\) list its members' positions in ranking \(r\) in increasing order, with position \(1\) best. Define \(f_{m,k}(i_1,\ldots,i_k)=\sum_{j=1}^k\gamma^{(j)}_{m,k}(i_j)\) and \(F_\mu(S)=\sum_{r\in T}\mu_r f_{m,k}(\operatorname{pos}_r(S))\). Any qualifying committee may be returned; ties impose no additional requirement.
Is there an algorithm, polynomial in \(m,\tau,k,L\), that always returns a committee \(S\) with \(|S|=k\) and \(F_\mu(S)\geq(1-1/e)\max_{S'\subseteq C,\,|S'|=k}F_\mu(S')\), or is achieving this approximation guarantee NP-hard?
For explicitly listed, equally weighted voters, a polynomial-time \((1-1/e)\)-approximation is asserted for decomposable scoring rules with polynomial-time computable scores under the intended consecutive-layer condition. [Discrete approximation result](https://www.ijcai.org/Proceedings/16/Papers/043.pdf)
No result explicitly treating this same approximation problem with binary-rational support masses was identified in the search.
The full approximation-versus-hardness question remains unresolved. I establish two new results:
NOTES.All unconditional claims below are proved independently. The transfer statements explicitly identify the discrete algorithm they assume.
Write $\gamma_j$ for $\gamma^{(j)}_{m,k}$, and let
$$ \operatorname{OPT} = \max_{\substack{S\subseteq C\\ |S|=k}}F_\mu(S). $$
For any $S\subseteq C$, let $i_1<\cdots<i_{|S|}$ be its selected positions in ranking $r$. Define
$$ G_r(S) = \sum_{j=1}^{\min(k,|S|)}\gamma_j(i_j), \qquad G(S) = \sum_{r\in T}\mu_rG_r(S). $$
Thus $G(S)=F_\mu(S)$ when $|S|=k$, and $G(\varnothing)=0$.
Each $G_r$ is monotone. When a candidate is added, every retained order statistic weakly decreases in position, so its contribution weakly increases. If the number of retained order statistics increases, the new contribution is nonnegative. Positive weighted sums preserve monotonicity, so $G$ is monotone.
The cases $k=1$ and $k=m$ are exactly solvable: evaluate every singleton in the first case, and return $C$ in the second. The arguments below address the general input class.
Put
$$ A=\gamma_1(1). $$
Layer dominance and position monotonicity imply
$$ 0\leq\gamma_j(p)\leq A $$
for every $j$ and $p$. If $A=0$, every score is zero and any size-$k$ committee qualifies. Hence assume $A>0$.
For each candidate $c$, define its first-place mass by
$$ q_c = \sum_{\substack{r\in T\\ \operatorname{pos}_r(c)=1}}\mu_r. $$
Every ranking has exactly one first-place candidate, so
$$ \sum_{c\in C}q_c=1. $$
Let $S_0$ contain the $k$ candidates with largest $q_c$. Their total first-place mass is at least $k/m$. Indeed, the average of the $k$ largest numbers in a list is at least the average of the entire list.
Whenever a ranking's first-place candidate belongs to $S_0$, its committee score is at least $A$. All other contributions are nonnegative. Consequently,
$$ \operatorname{OPT} \geq F_\mu(S_0) \geq \frac{k}{m}A. $$
On the other hand, every size-$k$ committee has individual ranking score at most $kA$. Thus, for every ranking $r$ and every size-$k$ committee $S$,
$$ 0 \leq f_{m,k}(\operatorname{pos}_r(S)) \leq kA \leq m\operatorname{OPT}. $$
This bound is independent of the smallest mass and of the numerical magnitude of the scoring entries.
Let $N>\tau$ be an integer. Define
$$ n_r=\lfloor N\mu_r\rfloor, \qquad N'=\sum_{r\in T}n_r, $$
and define the unnormalized rounded objective
$$ \widetilde F(S) = \frac1N \sum_{r\in T}n_r f_{m,k}(\operatorname{pos}_r(S)). $$
Then $N'>0$, $N'\leq N$, and every size-$k$ committee satisfies
$$ 0 \leq F_\mu(S)-\widetilde F(S) \leq \frac{m\tau}{N}\operatorname{OPT}. $$
In particular,
$$ \max_{|S|=k}\widetilde F(S) \geq \left(1-\frac{m\tau}{N}\right)\operatorname{OPT}. $$
Because $\sum_rN\mu_r=N$ and $\lfloor x\rfloor>x-1$,
$$ N' > N-\tau > 0. $$
Also, $N'\leq N$.
For every ranking,
$$ 0\leq \mu_r-\frac{n_r}{N}<\frac1N. $$
The scoring entries are nonnegative, so
$$ 0 \leq F_\mu(S)-\widetilde F(S) = \sum_{r\in T} \left(\mu_r-\frac{n_r}{N}\right) f_{m,k}(\operatorname{pos}_r(S)). $$
Applying the bound from Section 2 gives
$$ F_\mu(S)-\widetilde F(S) \leq \frac{\tau}{N}m\operatorname{OPT}. $$
Apply this inequality to an optimal committee to obtain the final assertion. $\square$
The rounded electorate consists of $n_r$ explicitly listed copies of ranking $r$, omitting types with $n_r=0$. Its ordinary total-score objective is $N\widetilde F$, so multiplying by $N$ does not change approximation ratios.
For rational $\varepsilon\in(0,1)$, choose
$$ N=\left\lceil\frac{m\tau}{\varepsilon}\right\rceil. $$
The rounded electorate then has at most $N$ voters, and the error is at most $\varepsilon\operatorname{OPT}$ for every committee.
Each $n_r$ can be computed exactly from the binary-rational input. Explicitly writing the rounded electorate takes time polynomial in $m,\tau,L,$ and $1/\varepsilon$. The scoring tables are unchanged.
Assume an algorithm $\mathcal A$ has the following properties:
This is a uniform premise concerning algorithms with scoring tables supplied as input. A theorem stated separately for each fixed rule family does not automatically establish this uniform premise.
The cited [IJCAI paper, Theorem 15](https://www.ijcai.org/Proceedings/16/Papers/043.pdf) asserts the discrete $1-1/e$ guarantee but does not supply its algorithm or proof. The following statements are implications from the precise premise above.
Run $\mathcal A$ on the rounded electorate from Section 3, and let $S$ be its output. Since its total-score objective is $N\widetilde F$,
$$ \widetilde F(S) \geq \rho\max_{|W|=k}\widetilde F(W). $$
Rounding only decreases scores. Therefore,
$$ F_\mu(S) \geq \widetilde F(S) \geq \rho\left(1-\frac{m\tau}{N}\right)\operatorname{OPT}. $$
With $N=\lceil m\tau/\varepsilon\rceil$, this implies
$$ F_\mu(S) \geq \rho(1-\varepsilon)\operatorname{OPT} \geq (\rho-\varepsilon)\operatorname{OPT}. $$
Consequently, if the supplied discrete assertion admits the uniform formulation above, then for every rational $\varepsilon\in(0,1)$ there is an algorithm, polynomial in $m,\tau,k,L,$ and $1/\varepsilon$, returning a committee satisfying
$$ F_\mu(S) \geq \left(1-\frac1e-\varepsilon\right)\operatorname{OPT}. $$
This does not establish the exact requested factor.
Put
$$ \alpha=1-\frac1e. $$
Suppose the discrete algorithm instead guarantees
$$ \rho\geq\alpha+\eta, $$
where $\eta>0$ is an explicitly available rational number and $1/\eta$ is polynomially bounded in the input parameters. Choose
$$ N=\left\lceil\frac{2m\tau}{\eta}\right\rceil. $$
Then
$$ F_\mu(S) \geq \rho\left(1-\frac{\eta}{2}\right)\operatorname{OPT} \geq \left(\rho-\frac{\eta}{2}\right)\operatorname{OPT} \geq \left(\alpha+\frac{\eta}{2}\right)\operatorname{OPT}. $$
Here the second inequality uses $\rho\leq1$. This gives the exact requested guarantee in polynomial time.
One particularly useful possible discrete guarantee is
$$ \beta_k = 1-\left(1-\frac1k\right)^k. $$
It satisfies
$$ \beta_k-\alpha>\frac{1}{12k}. $$
To verify this, first take $k\geq2$. The inequality
$$ \log(1-x)\leq-x-\frac{x^2}{2} $$
for $0<x<1$ follows by integrating $1/(1-t)\geq1+t$. Hence
$$ \left(1-\frac1k\right)^k \leq e^{-1}e^{-1/(2k)}. $$
For $0\leq x\leq1$,
$$ 1-e^{-x} = \int_0^x e^{-t}\,dt \geq \int_0^x(1-t)\,dt \geq \frac{x}{2}. $$
It follows that
$$ \beta_k-\alpha \geq e^{-1}\left(1-e^{-1/(2k)}\right) \geq \frac{1}{4ek} > \frac{1}{12k}. $$
The last inequality uses $e<3$, which follows from the series for $e$ and $n!\geq2^{n-1}$, with strict inequality for some terms. For $k=1$, the assertion follows from $\beta_1-\alpha=1/e>1/3$.
Thus a uniform discrete $\beta_k$-approximation would settle the weighted target: taking
$$ N=24m\tau k $$
suffices. Such a discrete guarantee has not been established here for the full scoring-table class.
The next result is unconditional.
Because every ranking is a relabeling of the canonical order $1,\ldots,m$, it suffices to examine the function
$$ g(X) = \sum_{j=1}^{\min(k,|X|)}\gamma_j(p_j), $$
where $p_1<\cdots<p_{|X|}$ are the elements of $X\subseteq\{1,\ldots,m\}$.
Define auxiliary zero tables and layer differences by
$$ \gamma_{k+1}(p)=\gamma_{k+2}(p)=0, $$
$$ \delta_j(p)=\gamma_j(p)-\gamma_{j+1}(p) \quad (1\leq j\leq k), \qquad \delta_{k+1}(p)=0. $$
All $\delta_j(p)$ are nonnegative.
A set function is submodular exactly when, for every $X$ and distinct $a,b\notin X$,
$$ g(X\cup\{a\})+g(X\cup\{b\}) - g(X)-g(X\cup\{a,b\}) \geq0. $$
Indeed, this inequality says that adding one element cannot increase another element's marginal. Applying it successively along a chain proves the general diminishing-returns inequality.
Assume $a<b$, and put
$$ \ell=1+|X\cap\{1,\ldots,b-1\}|. $$
If $\ell>k$, adding $b$ changes neither $g(X)$ nor $g(X\cup\{a\})$, so the displayed expression is zero.
Suppose $\ell\leq k$. Put $s=\min(k,|X|)$, and denote the retained selected positions after $b$ by
$$ b<p_\ell<\cdots<p_s. $$
The list is empty when $s=\ell-1$.
Adding $b$ to $X$ gives it layer $\ell$ and shifts each retained position $p_i$ from layer $i$ to layer $i+1$. Thus its marginal is
$$ \gamma_\ell(b) + \sum_{i=\ell}^{s} \bigl(\gamma_{i+1}(p_i)-\gamma_i(p_i)\bigr). $$
After $a$ has also been added, $b$ receives layer $\ell+1$, and the same positions have their layer indices increased by one. The auxiliary zero tables account for positions dropped by truncation at $k$. Subtracting the two marginals gives
$$ D(X;a,b) = \delta_\ell(b) + \sum_{i=\ell}^{s} \bigl(\delta_{i+1}(p_i)-\delta_i(p_i)\bigr). $$
This calculation depends on the selected positions before $b$ only through their number.
For such a configuration to exist, $b-1$ positions must accommodate the $\ell-1$ selected positions before $b$ and the unselected position $a$. Equivalently,
$$ b\geq\ell+1. $$
Conversely, whenever this inequality holds, any increasing tail of length at most $k-\ell+1$ is realizable: choose $a=1$ and choose $\ell-1$ positions from $\{2,\ldots,b-1\}$.
Sets larger than $k$ introduce no additional expressions, because positions below the first $k$ contribute zero throughout the calculation.
For $q\in\{1,\ldots,m\}$, define
$$ V_{k+1}(q)=0. $$
For $i=k,k-1,\ldots,1$, define
$$ V_i(q) = \min\left( 0,\; \min_{p>q} \left[ \delta_{i+1}(p)-\delta_i(p)+V_{i+1}(p) \right] \right). $$
An empty inner minimum is ignored.
The value $V_i(q)$ is the minimum sum obtainable from an increasing tail after $q$, beginning at layer $i$. Choosing zero means taking an empty tail. Otherwise, choose its first position $p$, pay the corresponding summand, and optimize the remaining tail using $V_{i+1}(p)$. This interpretation follows by backward induction on $i$.
Therefore, for fixed $\ell,b$, the minimum possible pairwise expression is
$$ \delta_\ell(b)+V_\ell(b). $$
We obtain the following exact criterion:
$$ \boxed{ g\text{ is submodular} \iff \delta_\ell(b)+V_\ell(b)\geq0 \text{ for every } 1\leq\ell\leq k,\quad \ell+1\leq b\leq m. } $$
Necessity follows because every minimizing tail is realizable. Sufficiency follows because every pairwise marginal expression is either zero or one of the expressions bounded by the criterion.
The direct implementation takes $O(km^2)$ integer operations. It can be reduced to $O(km)$ by computing suffix minima of
$$ \delta_{i+1}(p)-\delta_i(p)+V_{i+1}(p) $$
for each row $i$. Every tail contains at most $k$ terms of absolute value at most $A$, so all intermediate integers have polynomial bit length.
This is consequently a polynomial-time recognition algorithm.
If the criterion in Section 5 holds, every $G_r$ is submodular, because it is a relabeling of $g$. Positive weighted sums preserve submodularity. Thus $G$ is normalized, monotone, and submodular.
Run greedy for $k$ additions, choosing at each step a candidate of maximum marginal value. Let $S_t$ be the committee after $t$ additions, and let $O$ be an optimal size-$k$ committee.
Monotonicity and diminishing returns give
$$ G(O)-G(S_t) \leq G(O\cup S_t)-G(S_t) \leq \sum_{c\in O\setminus S_t} \bigl(G(S_t\cup\{c\})-G(S_t)\bigr). $$
There are at most $k$ summands. The greedy marginal is therefore at least
$$ \frac{G(O)-G(S_t)}{k}. $$
Starting from $G(\varnothing)=0$ and iterating gives
$$ F_\mu(S_k) = G(S_k) \geq \left(1-\left(1-\frac1k\right)^k\right)G(O) \geq \left(1-\frac1e\right)\operatorname{OPT}. $$
All evaluations and comparisons can be exact. Write $\mu_r=a_r/b_r$, and put
$$ D=\prod_{r\in T}b_r, \qquad w_r=\frac{a_rD}{b_r}. $$
Then $w_r$ are positive integers, $\sum_rw_r=D$, and
$$ DG(S)=\sum_{r\in T}w_rG_r(S). $$
The bit length of $D$ is at most the sum of the denominator bit lengths, up to an additive constant. Moreover,
$$ 0\leq DG(S)\leq DkA. $$
Thus these integer calculations have polynomial bit length. Greedy uses at most $km$ score evaluations, each computable directly from the $\tau$ rankings. Its running time is polynomial in $m,\tau,k,L$.
The position-drop condition from NOTES is
$$ \gamma_j(p)-\gamma_j(p+1) \geq \gamma_{j+1}(p)-\gamma_{j+1}(p+1) $$
for $j<k$ and $p<m$.
This condition says that each $\delta_j$ with $j<k$ is nonincreasing in position. The same is true of $\delta_k=\gamma_k$ by the original hypotheses.
For a nonempty tail, the expression from Section 5 telescopes as
$$ D(X;a,b) = \delta_\ell(b)-\delta_\ell(p_\ell) + \sum_{i=\ell+1}^{s} \bigl(\delta_i(p_{i-1})-\delta_i(p_i)\bigr) + \delta_{s+1}(p_s). $$
Every term is nonnegative. An empty tail gives $D(X;a,b)=\delta_\ell(b)\geq0$. Thus the earlier condition implies the exact criterion.
The converse fails. For every $m\geq3$, take $k=2$ and
$$ \gamma_1(p)=3 \quad\text{for all }p, $$
$$ \gamma_2(p)= \begin{cases} 2,&p<m,\\ 1,&p=m. \end{cases} $$
These tables satisfy all original hypotheses, but violate the position-drop condition at $p=m-1$.
Let $z$ be the last-ranked candidate, and call the other candidates good. The extended score is:
Adding $z$ to a set containing respectively zero, one, or at least two good candidates has marginal $3,1,$ or $0$.
For an added good candidate, the marginal depends on the existing number $h$ of good candidates and whether $z$ is present:
$$ \begin{array}{c|cc} & z\text{ absent} & z\text{ present}\\ \hline h=0 & 3 & 1\\ h=1 & 2 & 1\\ h\geq2 & 0 & 0 \end{array} $$
As a set grows, $h$ can only increase and $z$ can only change from absent to present. The displayed marginals never increase. Hence this extension is submodular, proving strict enlargement.
For example, take $m=4$, $k=3$, and
$$ \gamma_1=(1,1,1,1), \qquad \gamma_2=(1,1,0,0), \qquad \gamma_3=(0,0,0,0). $$
All original hypotheses hold. In the canonical ranking, let $X=\{3\}$ and add positions $1$ and $2$. Then
$$ g(\{3\})=g(\{1,3\})=g(\{2,3\})=1, \qquad g(\{1,2,3\})=2. $$
The pairwise submodularity expression is therefore $-1$. Thus recognition followed by greedy does not solve the full class.
The mass-compression lemma isolates a concrete route to a complete solution: a uniform discrete guarantee of $\beta_k$, or any inverse-polynomial excess over $1-1/e$, would yield the exact weighted guarantee with only polynomially many rounded voters.
A uniform discrete guarantee of exactly $1-1/e$ yields arbitrarily close guarantees by this argument, but the proof loses a positive amount and does not establish the exact factor.
Independently, the submodularity criterion settles the requested guarantee for a larger, polynomially recognizable subclass. Inputs outside that subclass still require another approximation argument or an approximation-hardness reduction.
⟨structured verdict parsed — rendered above⟩
Overall assessment: valid partial progress; the full target remains unresolved. The unconditional arguments are correct, and the approximation transfers are correctly presented as conditional. I found no false mathematical step. The major limitation is that neither a polynomial-time algorithm with the exact requested guarantee for every admissible input nor approximation hardness is established.
The extension $G_r$ is well-defined for every subset, including subsets larger than $k$. Adding a candidate weakly improves every retained order statistic; when another term is retained, that term is nonnegative. Thus the monotonicity argument is valid.
The identity $G(S)=F_\mu(S)$ for $|S|=k$ is immediate. The cases $k=1$ and $k=m$ are correctly handled by singleton evaluation and returning $C$, respectively.
Position monotonicity and layer dominance give $0\leq\gamma_j(p)\leq A$. If $A=0$, all scoring entries vanish, so the zero-score case is fully resolved.
The first-place masses sum to one. Consequently, the $k$ largest first-place masses sum to at least $k/m$. Each ranking whose first-place candidate is selected contributes at least $A$, giving
$$
\operatorname{OPT}\geq \frac{kA}{m}.
$$
Combining this with the per-ranking upper bound $kA$ correctly yields
$$
f_{m,k}(\operatorname{pos}_r(S))\leq m\operatorname{OPT}.
$$
This reasoning does not require a lower bound on individual support masses.
The floor inequalities correctly establish
$$
N-\tau<N'\leq N,
$$
so $N'>0$ whenever $N>\tau$. Types rounded to zero may be omitted.
The rounding errors are nonnegative and smaller than $1/N$. Applying the preceding per-ranking bound gives the stated uniform error bound for every size-$k$ committee. Evaluating that bound at an optimal committee proves the lower bound on the rounded optimum.
For $\varepsilon\in(0,1)$, the selected value
$$
N=\left\lceil\frac{m\tau}{\varepsilon}\right\rceil
$$
satisfies $N>\tau$. Computing the multiplicities exactly and explicitly listing at most $N$ rankings takes time polynomial in the stated parameters and $1/\varepsilon$. Binary encoding of the original masses creates no omitted numerical obstacle here.
Multiplication of the rounded objective by $N$ preserves approximation ratios. Since rounding decreases every committee score, the deduction
$$
F_\mu(S)\geq\rho\left(1-\frac{m\tau}{N}\right)\operatorname{OPT}
$$
is correct. The subsequent bound by $(\rho-\varepsilon)\operatorname{OPT}$ uses $\rho\leq1$ correctly.
The distinction between a uniform algorithm accepting scoring tables as input and an algorithm for each fixed rule family is substantive and correctly identified. The [cited paper’s Theorem 15](https://www.ijcai.org/Proceedings/16/Papers/043.pdf) states a discrete approximation result for polynomial-time computable scoring families; it does not provide an algorithm or proof in that paper. The prover does not treat this citation as establishing the stronger uniform premise, so there is no unjustified theorem application in the transfer argument.
As written, the transfer proves an arbitrarily close approximation only under its explicit algorithmic premise. It does not establish the exact requested factor.
Given the stated available rational excess $\eta$, the chosen $N$ makes the rounding loss at most $\eta/2$. The inequality
$$
\rho\left(1-\frac{\eta}{2}\right)\geq\rho-\frac{\eta}{2}
$$
follows from $\rho\leq1$, and the claimed final guarantee follows.
The bound on $\beta_k-\alpha$ is also correct. For $k\geq2$, both integral inequalities have the stated ranges and yield
$$
\beta_k-\alpha\geq\frac{1}{4ek}>\frac{1}{12k}.
$$
The separate calculation for $k=1$ is valid. Thus $N=24m\tau k$ suffices if a uniform discrete $\beta_k$-approximation exists.
The prover explicitly acknowledges that this discrete guarantee has not been established for the full input class. This is a missing premise for completing that route, not an error in the conditional implication.
The pairwise inequality stated is equivalent to diminishing returns for a set function on a finite ground set. The explanation by successive additions supplies the relevant equivalence.
If $\ell>k$, inserting $b$ affects neither truncated score, as claimed. For $\ell\leq k$, the displayed marginal correctly accounts for inserting $b$ and shifting retained tail positions. After insertion of $a<b$, the layer indices increase by one. The auxiliary zero layers correctly handle truncation, including the boundary $\ell=k$.
Subtracting these marginals gives exactly
$$
\delta_\ell(b)+
\sum_{i=\ell}^{s}\bigl(\delta_{i+1}(p_i)-\delta_i(p_i)\bigr).
$$
Positions before $b$ affect this expression only through their count.
The feasibility condition $b\geq\ell+1$ is necessary and sufficient: there must be room for $\ell-1$ selected positions and the additional unselected position $a$. The construction stated in the proof realizes every tail considered by the dynamic program. Extra selected positions beyond the first $k$ cannot affect the expression.
The recurrence for $V_i(q)$ correctly minimizes over empty tails and increasing nonempty tails. Its backward-induction interpretation establishes both necessity and sufficiency of the boxed criterion.
The operation counts and polynomial bit-length bounds are valid. This recognizes submodularity of the canonical extension $g$, and hence of each relabeled per-ranking extension. It does not claim to recognize every society for which the weighted sum happens to be submodular.
On recognized inputs, relabeling and positive weighted summation preserve submodularity. Together with the earlier monotonicity and normalization, this supplies every hypothesis needed by the greedy argument.
The bound comparing the remaining optimum gap with the sum of available marginals is valid. Greedy selects a marginal at least the gap divided by $k$, producing the stated recurrence and the factor $\beta_k$. The comparison $\beta_k\geq1-1/e$ also holds, including $k=1$.
Clearing denominators by their product yields exact integer comparisons with polynomial bit length. The upper bound $DG(S)\leq DkA$ is correct. Thus the claimed polynomial running time on the recognized subclass is established.
The position-drop condition is explicitly restated, so the unavailable reference to NOTES does not prevent verification. It makes each $\delta_j$ nonincreasing, including $\delta_k$ under the original hypotheses. The displayed telescoping identity is correct, and every term is nonnegative.
The strict-enlargement example satisfies position monotonicity and layer dominance, while violating the position-drop condition. Its listed scores and marginal table are correct. These marginals never increase under set inclusion, establishing submodularity.
The final example also satisfies the original hypotheses. Its four scores are correctly computed, and its pairwise expression equals $-1$. This establishes that the recognition criterion excludes some admissible inputs. It supplies no approximation-hardness conclusion, and the prover does not claim one.
Actionable feedback. No repair is needed for the unconditional lemmas or the conditional implications. To resolve USER_TASK, the next output must establish either the exact weighted guarantee for all admissible scoring tables or hardness of achieving that guarantee. If pursuing the proposed compression route, it must substantiate the uniform discrete algorithm and its available inverse-polynomial excess. Repeating the exact discrete factor alone does not close the demonstrated rounding loss.
⟨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.