Answer: Yes. Exact greedy selection runs in polynomial time and achieves the requested approximation guarantee.
Theorem 3 — class: algorithmic
Given a finite item set \(X\), candidate set \(Z\), recommendation limit \(k\), nonnegative rational item affinities \(W_{ij}\), and supported user types \(T\) with rational masses \(\mu_t\) summing to \(1\), each type has observed items \(I_t\), nonnegative ratings \(r_i(t)\), and nonnegative rational pair affinities \(A(t,t')\). For \(f(x)=\min\{x,1\}\), define \(F_\mu(S)=\sum_{t\in T}\mu_t\bigl(\sum_{t'\in T}\mu_{t'}A(t,t')\bigr)\sum_{i\in I_t}r_i(t)f(\sum_{j\in S}W_{ij})\). Compute \(\hat S\subseteq Z\), \(|\hat S|\le k\), such that \(F_\mu(\hat S)\ge\bigl(1-(1-1/k)^k\bigr)\max_{S\subseteq Z,\ |S|\le k}F_\mu(S)\).
Let \(X\) be a finite item set, \(m=|X|\). A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has observed items \(I_t\subseteq X\) and nonnegative binary rational ratings \(r_i(t)\). Set \(I=\bigcup_{t\in T}I_t\) and \(Z=X\setminus I\), and assume an integer recommendation limit \(1\le k\le |Z|\).
Input affinities \(W_{ij}\), for \(i,j\in X\), and \(A(t,t')\), for \(t,t'\in T\), are nonnegative binary rationals, with no symmetry or transitivity requirements. Types describe an atomless population: distinct individuals of the same type interact, so \(A(t,t)\) is included.
With identity user saturation and item saturation \(f(x)=\min\{x,1\}\), define \(F_\mu(S)=\sum_{t\in T}\mu_t\bigl(\sum_{t'\in T}\mu_{t'}A(t,t')\bigr)\sum_{i\in I_t}r_i(t)f\bigl(\sum_{j\in S}W_{ij}\bigr)\) for \(S\subseteq Z\). Let \(L\) be the total binary input length.
Is there an algorithm, polynomial in \(m,\tau,k,L\), that always returns \(\hat S\subseteq Z\), \(|\hat S|\le k\), satisfying \(F_\mu(\hat S)\ge\bigl(1-(1-1/k)^k\bigr)\max_{S\subseteq Z,\ |S|\le k}F_\mu(S)\)?
For finite user lists, the corresponding group recommendation objective has the greedy approximation guarantee \(1-(1-1/k)^k\). [Source](https://cdn.aaai.org/ojs/11650/11650-13-15178-1-2-20201228.pdf)
The same bound is established for arbitrary normalized nondecreasing submodular set functions under a cardinality constraint. [Original result](https://thibaut.horel.org/submodularity/papers/nemhauser1978.pdf) No separate treatment of the exact distributional formulation above was located.
Yes. Exact greedy selection runs in time polynomial in \(m,\tau,k,L\) and achieves the requested factor
\(1-(1-1/k)^k\).
The proof below establishes both the approximation guarantee and the bit complexity directly for the given distributional formulation.
For each \(t\in T\), define
\(b_t=\sum_{t'\in T}\mu_{t'}A(t,t')\).
For each \(i\in I\), define
\(c_i=\sum_{t:\,i\in I_t}\mu_t b_t r_i(t)\).
All these coefficients are nonnegative rational numbers. Rearranging the finite sums in the given objective yields
\[
\]
\(F_\mu(S)=\sum_{i\in I}c_i\min\{\sum_{j\in S}W_{ij},1\}\)
for every \(S\subseteq Z\).
The sum defining \(b_t\) includes \(t'=t\), exactly as required by the atomless-population interpretation. Thus this rearrangement preserves the stated objective, including all diagonal interactions.
Write \(F=F_\mu\) and \(h_i(S)=\sum_{j\in S}W_{ij}\).
Normalization follows from \(h_i(\varnothing)=0\):
\(F(\varnothing)=0\).
If \(S\subseteq R\), nonnegativity of the affinities gives \(h_i(S)\le h_i(R)\). Since \(x\mapsto\min\{x,1\}\) is nondecreasing and \(c_i\ge0\), we obtain \(F(S)\le F(R)\).
For \(e\in Z\setminus S\), define its marginal gain by
\(\Delta(e\mid S)=F(S\cup\{e\})-F(S)\).
For any \(x,w\ge0\),
\(\min\{x+w,1\}-\min\{x,1\}=\min\{w,\max\{1-x,0\}\}\):
when \(x\ge1\), both sides are zero; when \(x<1\), both sides equal \(\min\{w,1-x\}\).
Consequently,
\[
\]
\(\Delta(e\mid S)=\sum_{i\in I}c_i\min\{W_{ie},\max\{1-h_i(S),0\}\}\).
If \(S\subseteq R\subseteq Z\) and \(e\notin R\), then \(h_i(S)\le h_i(R)\). Hence each summand in this formula is at least as large for \(S\) as for \(R\), giving
\(\Delta(e\mid S)\ge\Delta(e\mid R)\).
This is the diminishing-returns definition of submodularity. Therefore \(F\) is normalized, nondecreasing, and submodular on the finite ground set \(Z\). No symmetry or transitivity assumption was used.
Start with \(S_0=\varnothing\). For each \(\ell=0,\ldots,k-1\), choose an item \(e_{\ell+1}\in Z\setminus S_\ell\) maximizing \(\Delta(e\mid S_\ell)\), using exact rational comparisons, and set
\(S_{\ell+1}=S_\ell\cup\{e_{\ell+1}\}\).
Break ties arbitrarily and return \(\hat S=S_k\).
Because \(k\le|Z|\), every iteration has an available item, and \(|\hat S|=k\).
Let \(O\subseteq Z\), \(|O|\le k\), maximize \(F\), and write \(\mathrm{OPT}=F(O)\). Such an \(O\) exists because the feasible family is finite.
Fix \(\ell<k\). Monotonicity gives
\(\mathrm{OPT}-F(S_\ell)\le F(S_\ell\cup O)-F(S_\ell)\).
Enumerate \(O\setminus S_\ell\) as \(o_1,\ldots,o_q\). Telescoping the gain from adding these items, then applying diminishing returns to each addition, gives
\[
\]
\(F(S_\ell\cup O)-F(S_\ell)
=\sum_{a=1}^{q}\Delta(o_a\mid S_\ell\cup\{o_1,\ldots,o_{a-1}\})
\le\sum_{a=1}^{q}\Delta(o_a\mid S_\ell)\).
Every marginal in the last sum is at most the greedy marginal. Since \(q\le k\) and all marginals are nonnegative,
\[
\]
\(\mathrm{OPT}-F(S_\ell)
\le k\bigl(F(S_{\ell+1})-F(S_\ell)\bigr)\).
Define \(R_\ell=\mathrm{OPT}-F(S_\ell)\). Each \(S_\ell\) is feasible, so \(R_\ell\ge0\). Rearranging the preceding inequality gives
\(R_{\ell+1}\le(1-1/k)R_\ell\).
Since \(R_0=\mathrm{OPT}\), applying this recurrence over the \(k\) iterations yields
\(R_k\le(1-1/k)^k\mathrm{OPT}\).
Therefore
\[
\]
\(F_\mu(\hat S)\ge\bigl(1-(1-1/k)^k\bigr)\mathrm{OPT}\).
This argument also covers \(\mathrm{OPT}=0\) and \(k=1\); it never divides by the optimum.
The recurrence is the classical cardinality-constrained greedy argument of [Nemhauser, Wolsey, and Fisher](https://thibaut.horel.org/submodularity/papers/nemhauser1978.pdf). Here its hypotheses and its conclusion have been proved explicitly for the supplied objective.
It remains to justify exact greedy comparisons in the binary-input model.
Represent each input rational as an integer numerator divided by a positive integer denominator. Let \(D\) be the product of all input denominators. The binary length of \(D\) is at most \(O(L)\), because the sum of their binary lengths is at most \(L\). Each input rational can therefore be represented with denominator \(D\) and an integer numerator of \(O(L)\) bits.
Using these representations:
For the last assertion, the capped increment
\(\min\{W_{ie},\max\{1-h_i(S),0\}\}\)
has denominator \(D\), and multiplying by \(c_i\) gives denominator \(D^5\).
All numerator lengths remain polynomially bounded. Indeed, each input value is at most \(2^{O(L)}\); a coefficient \(c_i\) is a sum of at most \(\tau^2\) products of four input values; a load sums at most \(k\) affinities; and a marginal sums at most \(m\) coefficient-weighted increments. Thus the integers involved have
\(O(L+\log m+\log\tau+\log k)\) bits, with absolute constant factors. Exact comparison of marginal gains reduces to comparison of their integer numerators over the common denominator \(D^5\).
Computing all \(b_t\) requires \(O(\tau^2)\) arithmetic operations, and computing all \(c_i\) requires \(O(\tau m)\). Maintain the loads \(h_i(S_\ell)\). Each greedy iteration evaluates at most \(m\) candidates, each using at most \(m\) summands, and updates at most \(m\) loads. The greedy phase therefore uses \(O(km^2)\) arithmetic operations.
Integer addition, multiplication, comparison, and exact division on polynomial-length integers take polynomial time. Consequently the entire algorithm runs in time polynomial in \(m,\tau,k,L\). It operates directly on the support list and never expands rational masses into individual users.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The output establishes a polynomial-time algorithm achieving the requested approximation factor for the supplied support-list formulation. No major or minor mathematical gaps were found. This establishes polynomial-time approximation with the specified guarantee; it does not claim polynomial-time exact optimization.
The definitions of \(b_t\) and \(c_i\) correctly collect the factors multiplying each item's saturated load. Expanding \(c_i\) gives precisely the original contribution from all types observing \(i\). Rearranging these finite sums is valid.
All coefficients are nonnegative because masses, affinities, and ratings are nonnegative. The sum defining \(b_t\) includes the diagonal interaction \(A(t,t)\). No symmetry, transitivity, or finite-user interpretation is introduced.
Finding: Correct and complete.
Normalization follows because every load at the empty set is zero.
Monotonicity follows from nonnegative item affinities: enlarging the recommendation set increases each load, and saturation is nondecreasing.
The identity
\[
\min\{x+w,1\}-\min\{x,1\}
=\min\{w,\max\{1-x,0\}\}
\]
is correct for all \(x,w\ge0\). Both cases in the output are valid, including the boundary \(x=1\).
Its application to each item gives the stated marginal formula. When \(S\subseteq R\), the remaining unsaturated capacity for each item can only decrease. Taking the minimum with the same nonnegative affinity preserves this ordering, and multiplying by nonnegative coefficients and summing preserves it again. Thus the claimed diminishing-returns inequality holds.
Finding: Correct and complete.
The algorithm is well-defined throughout: at iteration \(\ell<k\), the selected set has size \(\ell\), and \(k\le|Z|\) ensures an available candidate.
An optimal feasible set exists because the ground set is finite. The comparison with \(S_\ell\cup O\) uses monotonicity correctly; that union need not itself satisfy the cardinality constraint.
The telescoping equality is valid. For each term, the item being added is absent from the conditioning set, so the previously established diminishing-returns property applies with its required hypotheses satisfied.
Every item in \(O\setminus S_\ell\) is an eligible greedy candidate. Its marginal is therefore bounded by the chosen marginal. The replacement of the number of such items by \(k\) is valid because the greedy marginal is nonnegative.
The resulting residual recurrence is correctly rearranged and iterated. Each \(S_\ell\) is feasible, so its residual is nonnegative. The final factor is exactly the one requested.
The argument also handles:
The cited classical result is historical attribution rather than an unverified theorem application: the output supplies the full argument it needs.
Finding: Correct and complete.
The common-denominator construction is valid. The product \(D\) has binary length bounded by the sum of the input denominator lengths, hence by \(O(L)\). Converting an input rational to denominator \(D\) also gives a numerator with \(O(L)\) bits.
The stated common denominators are correct:
These are valid representations; the fractions need not be reduced.
The numerator-length estimate is sound. Each coefficient expands into at most \(\tau^2\) products of four input values. Loads sum at most \(k\) affinities, and marginals sum at most \(m\) weighted increments. Fixed powers of \(D\) contribute \(O(L)\) bits, while these numbers of summands contribute only logarithmic terms. No arithmetic stage introduces an uncontrolled growth in bit length.
The operation counts also follow from the described implementation: \(O(\tau^2)\) for type aggregation, \(O(\tau m)\) for item aggregation, and \(O(km^2)\) for candidate evaluation and load updates. All operations involve polynomial-length integers, including conversion to the common denominator and exact comparisons.
The algorithm uses the supplied support directly and does not expand masses into individual users.
Finding: Correct and complete.
None is needed to make the mathematical argument verifiable.
⟨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.