d4-conf-aaai-2026-2003 (d4-conf-aaai-2026-2003)

Given \(m\) candidates, a committee bound \(k\), and \(\tau\) voter types with binary-rational masses \(\mu_t\ge 0\) summing to \(1\) and rational ballots \(u_t:C\to\mathbb{Q}_{\ge 0}\), candidates arrive in a uniformly random order. When \(c\) arrives, a policy observes \(u_t(c)\) for each type and irrevocably accepts or rejects \(c\), selecting at most \(k\) candidates. For \(W\subseteq C\), define \(\mathrm{NW}_{\mu}(W)=\sum_t\mu_t\log(1+\sum_{c\in W}u_t(c))\) and \(\mathrm{OPT}_{\mu}=\max_{|W|\le k}\mathrm{NW}_{\mu}(W)\). Does there exist a policy running in time polynomial in \(m,\tau,L\), where \(L\) is the input bit length, such that \(\mathbb{E}[\mathrm{NW}_{\mu}(W)]\ge ((1-1/e)/7)\mathrm{OPT}_{\mu}\)?

Let \(C\) contain \(m\) candidates and let \(k\) be an integer with \(2\le k<m\). A society is given by its support: a list of \(\tau\ge1\) 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 an additive ballot \(u_t:C\to\mathbb Q_{\ge0}\), encoded in binary. Let \(L\) be the total bit length of the instance, including all ballots.
The instance is fixed before candidates arrive in a uniformly random permutation. Initially a policy knows \(m,k,\tau\) and the masses; ballot entries for a candidate are revealed only upon its arrival. Each candidate must immediately be accepted or rejected irrevocably, with at most \(k\) acceptances. Internal randomization is allowed.
For \(W\subseteq C\), define \(\mathrm{NW}_{\mu}(W)=\sum_{t=1}^{\tau}\mu_t\log(1+\sum_{c\in W}u_t(c))\), using the natural logarithm, and \(\mathrm{OPT}_{\mu}=\max_{W\subseteq C,\,|W|\le k}\mathrm{NW}_{\mu}(W)\).
Computation uses the ordinary bit model; exact real arithmetic and exact logarithmic comparison oracles are not supplied. A policy may resolve ties by any fixed or randomized rule.

Does there exist an online policy with total running time polynomial in \(m,\tau,k,L\) that, for every such instance, satisfies \(\mathbb E[\mathrm{NW}_{\mu}(W)]\ge\frac{1-1/e}{7}\mathrm{OPT}_{\mu}\), where expectation includes arrival order and internal randomness?

For finitely many equally weighted voters, Online Nash Rule is stated to run in polynomial time and achieve the same expected approximation ratio. [Papasotiropoulos and Pishbin](https://arxiv.org/html/2511.23097v1)
For monotone nonnegative submodular objectives, the same ratio is known in the secretary model with value-oracle access restricted to arrived candidates; this is an oracle result, rather than a bit-complexity result for rational type masses. [Bateni, Hajiaghayi, and Zadimoghaddam](https://mhbateni.com/academic/pubs/secretary-10.pdf)

Result

Yes. There is a deterministic online policy, using polynomial-time rational arithmetic, such that
\( \mathbb E[\mathrm{NW}_{\mu}(W)]\ge \frac{99}{998}\mathrm{OPT}_{\mu}. \)
This is stronger than the requested guarantee.

Consecutive-block selection underlies the cited [Online Nash Rule](https://arxiv.org/html/2511.23097v1) and [submodular secretary algorithm](https://mhbateni.com/academic/pubs/secretary-10.pdf). The proof below establishes the guarantee directly, including the bit complexity of approximate marginal comparisons.

1. The objective and its marginal gains

Write \(f(W)=\mathrm{NW}_{\mu}(W)\), and define
\(f(c\mid A)=f(A\cup\{c\})-f(A)\).

For \(c\notin A\), additivity gives
\( \displaystyle f(c\mid A)=\sum_{t=1}^{\tau}\mu_t\log\!\left(1+\frac{u_t(c)}{1+\sum_{d\in A}u_t(d)}\right). \)

Every summand is nonnegative. Thus \(f(\varnothing)=0\), and \(f\) is nonnegative and monotone.

If \(A\subseteq B\) and \(c\notin B\), then
\( \displaystyle \frac{u_t(c)}{1+\sum_{d\in A}u_t(d)} \ge \frac{u_t(c)}{1+\sum_{d\in B}u_t(d)}. \)
Since logarithm is increasing and the masses are positive, \(f(c\mid A)\ge f(c\mid B)\). This is the diminishing-marginals definition of submodularity.

2. A rational approximation to logarithm

We construct a rational-valued function \(h\), computable on rational inputs \(y\ge1\), satisfying
\( \displaystyle \rho\log y\le h(y)\le\log y,\qquad \rho=\frac{99}{100}. \)

First let \(1\le q\le2\), set \(z=(q-1)/(q+1)\), and define
\( \displaystyle H(q)=2z+\frac{2z^3}{3}. \)

Here \(0\le z\le1/3\). Integrating the uniformly convergent geometric series on this interval gives
\( \displaystyle \log q=2\int_0^z\frac{dv}{1-v^2} =2\sum_{j=0}^{\infty}\frac{z^{2j+1}}{2j+1}. \)

Consequently,
\( \displaystyle 0\le\log q-H(q)\le\frac{2z^5}{5(1-z^2)}. \)
For \(z>0\), using \(\log q\ge2z\), we obtain
\( \displaystyle \frac{\log q-H(q)}{\log q} \le\frac{z^4}{5(1-z^2)}\le\frac1{360}. \)
For \(z=0\), both values are zero. Hence
\( \displaystyle \frac{359}{360}\log q\le H(q)\le\log q. \)

For arbitrary rational \(y\ge1\), find the integer \(a\ge0\) satisfying \(2^a\le y<2^{a+1}\), and put \(q=y/2^a\). Define
\( \displaystyle h(y)=aH(2)+H(q). \)

Because \(\log y=a\log2+\log q\) and both terms are nonnegative, the preceding bounds imply
\( \displaystyle \frac{359}{360}\log y\le h(y)\le\log y, \)
which proves the claimed bounds with \(\rho=99/100\).

This construction uses only rational arithmetic. The integer \(a\) can be found by comparisons with powers of two; computing a logarithm is unnecessary.

For an arrived candidate \(c\) and a previously accepted set \(A\), define its rational score
\( \displaystyle \widehat g_A(c)= \sum_{t=1}^{\tau}\mu_t h\!\left(1+\frac{u_t(c)}{1+\sum_{d\in A}u_t(d)}\right). \)

Termwise approximation and nonnegative weights give
\[ \displaystyle \rho f(c\mid A)\le\widehat g_A(c)\le f(c\mid A). \tag{1} \]

3. The online policy

Partition the arrival positions into \(k\) consecutive blocks, with sizes differing by at most one. These boundaries depend only on \(m,k\). Let \(S_i\) denote the candidates arriving in block \(i\), and let \(T_i\) be the accepted set after that block, with \(T_0=\varnothing\).

Within block \(i\), scores are computed relative to the fixed set \(T_{i-1}\). Break score ties by any fixed, arrival-independent ordering of candidate identifiers.

For a block of size \(s\):

• If \(s=1\), accept its candidate.
• If \(s\ge2\), reject its first \(r=\lfloor s/2\rfloor\) candidates and record their highest score, including the tie-breaking priority.
• Accept the first subsequent candidate ranked above that recorded candidate, if one exists.
• Reject every other candidate in the block.

Thus the policy accepts at most one candidate per block, and therefore at most \(k\) candidates. Every score uses only the current candidate’s ballot and previously accepted candidates.

4. Expected gain within a block

Condition on all block memberships and on the complete history preceding block \(i\). The order within the current block remains uniform. Its scores are fixed under this conditioning, because \(T_{i-1}\) is fixed.

For \(s\ge2\), consider the event that the highest-ranked candidate lies after the sample and the second-highest-ranked candidate lies in the sample. On this event, the policy selects the highest-ranked candidate. Its probability is
\( \displaystyle \frac{s-r}{s}\frac{r}{s-1} =\frac{r(s-r)}{s(s-1)}\ge\frac14. \)

Indeed, \(r(s-r)=s^2/4\) when \(s\) is even, and \(r(s-r)=(s^2-1)/4\) when \(s\) is odd; either expression is at least \(s(s-1)/4\). For \(s=1\), selection succeeds with probability one.

Whenever the highest-score candidate is selected, (1) implies that its true marginal is at least
\( \displaystyle \max_{c\in S_i}\widehat g_{T_{i-1}}(c) \ge\rho\max_{c\in S_i}f(c\mid T_{i-1}). \)
On all other events, the gain is nonnegative.

Writing \(\Delta_i=f(T_i)-f(T_{i-1})\), we therefore have, for any designated candidate \(b\in S_i\) whose designation does not depend on the within-block order,
\[ \displaystyle \mathbb E[\Delta_i\mid\text{block memberships, preceding history, designation}] \ge\frac{\rho}{4}f(b\mid T_{i-1}). \tag{2} \]

5. A benchmark with one optimum candidate per block

By monotonicity, fix an optimal set \(O\) of exactly \(k\) candidates.

For analysis only, choose one candidate uniformly from \(O\cap S_i\) whenever this intersection is nonempty. Make these choices independently of the within-block orders. Let \(R\subseteq O\) be the resulting representative set.

We prove
\[ \displaystyle \mathbb E[f(R)]\ge\frac12f(O). \tag{3} \]

Put \(\ell=\lfloor m/k\rfloor\ge1\). Every block has size \(s\ge\ell\). If \(s>m-k\), its intersection with \(O\) is necessarily nonempty. Otherwise, its probability of being empty is
\( \displaystyle \prod_{j=0}^{s-1}\frac{m-k-j}{m-j} \le\left(1-\frac{k}{m}\right)^s \le\left(\frac{\ell}{\ell+1}\right)^\ell \le\frac12. \)

The middle bound uses \(m<k(\ell+1)\). The last bound follows from the binomial inequality
\( (1+1/\ell)^\ell\ge1+\ell(1/\ell)=2 \).

Therefore \(\mathbb E[|R|]\ge k/2\). By symmetry of the uniform permutation and the uniform representative choices, every candidate of \(O\) has the same inclusion probability \(p\). Thus \(p=\mathbb E[|R|]/k\ge1/2\).

To translate this into welfare, order \(O=\{o_1,\ldots,o_k\}\), put \(O_j=\{o_1,\ldots,o_j\}\), and define
\(d_j=f(O_j)-f(O_{j-1})\ge0\).
Telescoping over the members of any realization of \(R\), submodularity gives
\( \displaystyle f(R)\ge\sum_{j=1}^{k}\mathbf1_{\{o_j\in R\}}d_j. \)
The reason is that the preceding selected members form a subset of \(O_{j-1}\), so their marginal for \(o_j\) is at least \(d_j\).

Taking expectations yields
\( \displaystyle \mathbb E[f(R)]\ge p\sum_{j=1}^{k}d_j =p f(O)\ge\frac12f(O), \)
proving (3). No independence between inclusion events is required.

6. Charging the benchmark to the policy

For each nonempty \(O\cap S_i\), denote its representative by \(b_i\). Monotonicity and submodularity imply, for every realization,
\[ \displaystyle f(R)\le f(T_k\cup R) \le f(T_k)+\sum_i f(b_i\mid T_k) \le f(T_k)+\sum_i f(b_i\mid T_{i-1}), \tag{4} \]
where the sums range over blocks having representatives.

Conditional on block memberships, preceding history, and the representative choices, the current within-block order is uniform. Thus (2) applies to \(b_i\). Summing its expectations gives
\[ \displaystyle \mathbb E[f(T_k)]\ge\beta\, \mathbb E\!\left[\sum_i f(b_i\mid T_{i-1})\right], \qquad \beta=\frac{\rho}{4}=\frac{99}{400}. \tag{5} \]

Let \(F=\mathbb E[f(T_k)]\) and \(G=\mathbb E[f(R)]\). Equations (4)–(5) give \(G\le F+F/\beta\), so, using (3),
\( \displaystyle F\ge\frac{\beta}{1+\beta}G =\frac{99}{499}G \ge\frac{99}{998}\mathrm{OPT}_{\mu}. \)

Finally, \(e<3\), so
\( \displaystyle \frac{1-1/e}{7}<\frac{2}{21}<\frac{99}{998}. \)
The second inequality follows from \(2\cdot998=1996<2079=99\cdot21\). For completeness, \(e<3\) follows from its series and \(n!\ge2^{n-1}\) for \(n\ge2\), with strict inequality for \(n\ge3\).

7. Polynomial bit complexity

Maintain each type’s accepted utility sum exactly as a rational number. A sum of at most \(k\) input rationals has numerator and denominator lengths bounded by \(O(kL+\log k)\), using a product of their denominators.

Consequently, every rational argument of \(h\) has polynomial bit length. For an argument of bit length \(B\), its exponent \(a\) is at most \(B\). Finding \(a\), forming \(2^a\), and evaluating the fixed-degree rational expression \(H\) all take polynomial time and produce polynomial-length rational numbers.

Each candidate score sums \(\tau\) such rational expressions multiplied by the input masses. Rational addition and exact rational comparisons therefore remain polynomial in \(\tau,k,L\). There are at most \(m\tau\) logarithm-approximation evaluations and a polynomial number of other arithmetic operations.

Hence the policy’s total running time is polynomial in \(m,\tau,k,L\). It does not need to know \(L\) before arrivals, replicate types according to their masses, or perform exact logarithmic comparisons.

⟨structured verdict parsed — rendered above⟩

The prover’s answer resolves the task. The policy is feasible online, its approximation analysis is correct, and its rational computations have polynomial total bit complexity. I found no major or minor issues requiring repair.

1. Objective and marginal gains

The marginal formula is correct for \(c\notin A\). Its denominators are strictly positive because all utilities are nonnegative.

The conclusions \(f(\varnothing)=0\), nonnegativity, and monotonicity follow directly. For \(A\subseteq B\) and \(c\notin B\), increasing the accumulated utility decreases each displayed ratio. Applying the increasing logarithm and positive masses proves diminishing marginal gains, hence submodularity.

There is no assumption of integral utilities or equally weighted types.

2. Rational logarithm approximation

The substitution \(z=(q-1)/(q+1)\) correctly gives \(0\le z\le1/3\) when \(1\le q\le2\). The geometric series converges uniformly on this interval, justifying its integration.

After the first two terms, the remainder satisfies the stated bound because every remaining denominator is at least \(5\). Dividing by \(\log q\ge2z\) for \(z>0\) gives the claimed relative-error estimate. At the endpoint, the numerical calculation is
\( (1/3)^4/[5(1-1/9)]=1/360 \).
The case \(z=0\) is handled separately and correctly.

The decomposition \(y=2^a q\), with \(1\le q<2\), is valid for every rational \(y\ge1\). Adding the lower and upper bounds for the two nonnegative logarithmic terms proves the bounds on \(h\). Since \(359/360>99/100\), the weaker constant \(\rho=99/100\) is valid.

Positive masses preserve these bounds when summed. Consequently, inequality (1) holds, including when the true marginal is zero. No subtraction of approximate objective values is used.

3. Online feasibility

The block boundaries depend only on known parameters. Every score uses the current ballot and utilities of previously accepted candidates, all of which are available.

Scores remain relative to the fixed set \(T_{i-1}\) throughout block \(i\), as required by the analysis. The sampling and selection instructions accept at most one candidate per block, so the total number accepted is at most \(k\).

The fixed, arrival-independent tie-breaking order makes each block’s ranking strict even when rational scores coincide. It does not require knowledge of unrevealed ballots. The policy is deterministic once this order is fixed.

4. Expected gain within a block

Conditioning on all block memberships and the preceding history leaves the current block’s order uniform. Under this conditioning, both \(T_{i-1}\) and the scores of the current block’s candidates are fixed.

The probability that the highest-ranked candidate is after the sample and the second-highest-ranked candidate is in the sample is correctly computed as
\(r(s-r)/[s(s-1)]\).
On this event, the sample maximum is the second-highest-ranked candidate. Every subsequent candidate preceding the highest-ranked one is below that threshold, so the policy selects the highest-ranked candidate.

The parity calculations establish the lower bound \(1/4\) for every \(s\ge2\), including \(s=2\). Singleton blocks are correctly handled separately.

For a selected score maximizer \(c^*\), inequality (1) gives
\(f(c^*\mid T_{i-1})\ge\widehat g_{T_{i-1}}(c^*)\ge\rho\max_{c\in S_i}f(c\mid T_{i-1})\).
On other events, gains are nonnegative. This proves (2) for a designated candidate whose choice does not depend on the current block’s order.

5. Representative benchmark

An optimum of exactly \(k\) candidates exists: the finite feasible family has a maximizer, and monotonicity allows any smaller maximizing set to be extended to size \(k\).

For a block of size \(s\le m-k\), the displayed product is the correct probability of avoiding all \(k\) optimum candidates. Each factor is at most \(1-k/m\). For \(s>m-k\), emptiness is impossible.

With \(\ell=\lfloor m/k\rfloor\), the bounds \(s\ge\ell\) and \(m<k(\ell+1)\) justify the next estimate. The stated binomial inequality proves the final bound \(1/2\), including \(\ell=1\). Thus the expected number of representatives is at least \(k/2\).

Uniform permutation and uniform representative selection treat all members of \(O\) symmetrically, even if block sizes differ. Therefore each optimum candidate has inclusion probability at least \(1/2\).

The telescoping comparison is valid: preceding members of \(R\) form a subset of the corresponding prefix of \(O\), so submodularity bounds their marginal contributions below by \(d_j\). Taking expectations requires only the individual inclusion probabilities. Inequality (3) follows without independence between inclusion events.

6. Charging and final constant

Every inequality in (4) is valid:

• Monotonicity gives \(f(R)\le f(T_k\cup R)\).
• Submodularity bounds the gain from adjoining \(R\) by the sum of its marginals relative to \(T_k\).
• Since \(T_{i-1}\subseteq T_k\), diminishing marginal gains bounds those marginals by the corresponding earlier ones.

If a representative already belongs to \(T_k\), its marginal there is zero under the stated definition; the inequalities remain valid.

The representative choices use block memberships and independent auxiliary randomness, so conditioning on them preserves the uniform current-block order. Consequently, (2) applies. Blocks without representatives contribute zero to the benchmark sum and nonnegative policy gain. Telescoping the policy gains proves (5).

The subsequent algebra is correct:
\(F\ge[\beta/(1+\beta)]G\), with \(\beta=99/400\), yields
\(F\ge(99/499)G\ge(99/998)\mathrm{OPT}_{\mu}\).

The comparison with the requested constant is also correct. The supplied factorial estimate proves \(e<3\), and \(1996<2079\) verifies \(2/21<99/998\).

7. Polynomial bit complexity and edge cases

Accepted utility sums have polynomial-length rational representations. Forming marginal arguments involves rational operations on those sums and input utilities, so their bit lengths remain polynomial.

For a rational argument of bit length \(B\), the exponent \(a\) is bounded by \(B\). Its search, construction of \(2^a\), and fixed-degree evaluation of \(H\) therefore require polynomial time and produce polynomial-length outputs.

Multiplication by encoded masses and summation over \(\tau\) types retain polynomial bit length: a product of the participating denominators has bit length bounded by the sum of their bit lengths. Exact rational comparisons also take polynomial time. There are at most \(m\tau\) evaluations of \(h\), establishing the claimed total bound.

The argument handles zero utilities, zero optimum welfare, singleton blocks, tied scores, and arbitrarily small positive rational masses. It does not require knowing \(L\) before arrivals.

No external approximation theorem is needed to complete the proof, and no additional clarification is required.

⟨structured verdict parsed — rendered above⟩