d4-conf-sigecom-2010-0020 (d4-conf-sigecom-2010-0020)

Fix a rational distribution \(\mu\) over \(\tau\) advertiser classes, each with a common value \(v_\theta\) and click-reward law \(F_\theta\). For population sizes \(N\) with \(N\mu_\theta\) integral, each advertiser submits an individual bid; a mechanism assigns one impression per round for \(T\) rounds and pays advertisers afterward. Among deterministic and randomized mechanism families that are ex-post truthful and normalized for every individual report and fixed click realization, determine the best regret rates as \(N\) grows, uniformly over these populations, against the truthful-profile benchmark \(T\max_\theta b_\theta p_\theta\), where \(p_\theta\) is the mean of \(F_\theta\). Characterize whether type-level pooling yields a nondegenerate limit of scaled per-advertiser impressions and payments, such as \(N\mathbb{E}[X_i]\) and \(N\mathbb{E}[P_i]\), while preserving those individual incentive constraints.

A society is given by its support: the list of \(\tau\geq2\) advertiser classes with positive binary-rational masses \(\mu_\theta\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Class \(\theta\) has private value \(v_\theta\geq0\) and an unknown reward law \(F_\theta\) on \([0,1]\), with mean \(p_\theta\). For finite encoding, values and laws have rational finite descriptions. For each admissible \(N\), there are \(N\mu_\theta\) individually strategic advertisers in class \(\theta\). Class membership and masses are public; values and reward laws are withheld from the mechanism.
There is \(m=1\) impression slot per round for \(T\geq1\) rounds. Each advertiser submits an individual bid \(b_i\geq0\) before allocation. The mechanism selects one advertiser each round, observes only that advertiser's reward, and afterward charges a possibly signed payment \(P_i\). Stochastic rewards are independent across advertisers and rounds, with the corresponding class law. Let \(X_i\) count impressions and \(C_i\) sum rewards; utility is \(v_iC_i-P_i\).
For every fixed table \(\rho\in[0,1]^{N\times T}\) of potential rewards, every individual value and report, and every vector of others' reports, truthful reporting must maximize expected utility over mechanism randomness. These constraints apply even off the common-value profiles. Ex-post normalization means \(\mathbb E_M[C_i\mid b,\rho]=0\) implies \(\mathbb E_M[P_i\mid b,\rho]=0\). Payments must be computed from the observed history.
At truthful profiles define \(R_M=T\max_\theta v_\theta p_\theta-\mathbb E[\sum_i v_iC_i]\), and \(\mathcal R_M(N,T,\mu,B)=\sup_{0\leq v_\theta\leq B,\,F_\theta}R_M\); the mechanism is not told \(B>0\). State running times in \(m,\tau,L,N,T\), where \(L\) is the total rational encoding length, including reports.
For pooling, require limits \(N\mathbb E[X_i]\to x_\theta\) and \(N\mathbb E[P_i]\to q_\theta\), uniformly over advertisers in each class, along admissible \(N\to\infty\), for each fixed truthful society and \(T\). Call the limit nondegenerate if all limits are finite and some \(x_\theta>0\); payment limits may be signed or zero.

What are the optimal uniform regret rates \(\mathcal R_M(N,T,\mu,B)\) for deterministic and randomized ex-post truthful, ex-post normalized mechanism families as \(N\) grows, allowing arbitrary \(T=T(N)\)?
Does a separation between their regret rates persist, and which optimal rates are compatible with the specified pooling limits while preserving every individual's incentive constraints?

For two individual advertisers with an unknown bid bound, deterministic mechanisms satisfying these constraints and a uniform bound \(\widetilde O(BT^\gamma)\) require \(\gamma\geq2/3\), whereas randomized mechanisms achieve \(\gamma=1/2\). [Verified source](https://arxiv.org/pdf/1004.3630v5).
No result settling this exact replicated-class problem and its pooling limits was identified in the literature search.

Result and scope

Fix the support and masses \(\mu\), and write \(n_\theta=N\mu_\theta\). Once every class contains at least two advertisers, the optimal uniform regret rate for both deterministic and randomized mechanisms is
\[ B\min\{T,\sqrt{\tau T}\}. \]
Thus the deterministic–randomized regret separation disappears under replication. Randomization remains necessary for the specified pooling limits:

| Mechanism family | Optimal uniform regret | Compatible with finite, nondegenerate pooling? |
|---|---|---|
| Deterministic | \(\Theta(B\min\{T,\sqrt{\tau T}\})\) | No |
| Randomized | \(\Theta(B\min\{T,\sqrt{\tau T}\})\) | Yes, with all payments zero |

These statements hold with absolute constants, uniformly over \(B>0\), \(T\geq1\), and all admissible \(N\) satisfying \(n_\theta\geq2\). In particular, for fixed positive masses they hold eventually along every choice of \(T=T(N)\).

The construction uses weak dominant-strategy truthfulness: truthful reporting maximizes utility, but need not uniquely maximize it. This is the requirement in the question. Reports can affect other advertisers’ allocations without affecting the reporting advertiser’s own utility. The statistical learning problem remains nontrivial.

1. A deterministic truthful construction

For each class \(\theta\), choose two distinct advertisers using only public identities:

• an informant \(s_\theta\);
• a recipient \(r_\theta\).

Set \(w_\theta=b_{s_\theta}\). Ignore every other bid, including every recipient’s bid. Allocate impressions exclusively to the recipients, using the class policy specified below and its observed rewards. Set \(P_i=0\) for every advertiser.

Individual incentive constraints

Fix an arbitrary potential-reward table \(\rho\), an advertiser \(i\), its value, and every other report. No common-value assumption is used here.

If \(i\) is an informant or an unused advertiser, it receives no impressions and pays nothing. Its utility is identically zero, regardless of its report.

If \(i\) is a recipient, its report is ignored by the entire mechanism. Consequently, changing its report cannot change the allocation history, its rewards, or its payment.

Thus each advertiser’s utility is independent of its own report. Truthful reporting is a dominant strategy for every fixed \(\rho\), including off the common-value profiles. Normalization holds because all payments are zero, and those payments are computable from the observed history.

At a truthful society, \(w_\theta=v_\theta\). Therefore the mechanism knows the correct class values through the informants’ reports, while learning the unknown laws through recipients’ rewards.

2. A finite-precision class policy with optimal regret

Here is a deterministic policy, together with a proof of its regret bound. Its indices are rational approximations of the MOSS indices of Audibert and Bubeck. [Their original paper, Figure 3 and Theorem 5](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/01/COLT09_AB.pdf), establishes the corresponding optimal stochastic-bandit rate. The argument below also verifies the finite-precision variant used here.

Write \(K=\tau\) and \(H=\max_\theta w_\theta\).

If \(H=0\), allocate every round to the first recipient. At truthful profiles, regret is then zero.

If \(T<K\), also use the first recipient. Regret is at most \(BT\), which is the required rate in this regime.

Suppose henceforth that \(H>0\) and \(T\geq K\). When class \(\theta\) produces an observed reward \(r\), feed the policy the quantized reward
\[ Y=\frac{\lfloor T(w_\theta/H)r\rfloor}{T}. \]
These rewards lie in \([0,1]\). At truthful profiles, their class means, denoted \(a_\theta\), satisfy
\[ 0\leq \frac{v_\theta p_\theta}{H}-a_\theta\leq\frac1T. \]

Let \(\eta=1/T\). For every positive sample count \(s\leq T\), compute a rational \(u_s\) satisfying
\[ r_s\leq u_s\leq r_s+\eta, \qquad r_s=\sqrt{\frac{\max\{\log(T/(Ks)),0\}}{s}}. \]
An unobserved class has index \(+\infty\). A class with \(s\) observations and empirical mean \(\widehat a_{\theta,s}\) has index \(\widehat a_{\theta,s}+u_s\). Each round, select a class of maximal index, breaking ties by a fixed class order.

We now prove that its expected regret on the quantized rewards is at most \(42\sqrt{KT}+2\).

2.1 Controlling pessimism about an optimal class

Let \(a_*=\max_\theta a_\theta\), fix an optimal class, and put \(A=T/K\). Predraw an infinite independent reward sequence for each class; the observations reveal successive elements of the selected class’s sequence. This is valid because rewards are independent and identically distributed within a class.

For the optimal class define
\[ Z=\left(a_*-\min_{1\leq s\leq T} \{\widehat a_{*,s}+r_s\}\right)_+. \]
Its actual index is always at least \(a_*-Z\), because \(u_s\geq r_s\).

We claim that \(\mathbb E[Z]\leq8/\sqrt A\). To prove this, let \(S_s=\sum_{\ell=1}^s(a_*-Y_{*,\ell})\). For \(h\geq0\), the maximal Hoeffding inequality gives
\[ \Pr\left(\max_{1\leq s\leq u}S_s\geq h\right) \leq \exp(-2h^2/u). \]
For noninteger \(u\), the maximum is over integer \(s\leq u\). This inequality follows by applying the exponential supermartingale associated with Hoeffding’s moment bound, stopping at the first crossing, and optimizing its parameter.

For the early sample counts, partition into intervals \(u/2<s\leq u\), where \(u=A2^{-j}\) and \(j\geq0\). If \(\widehat a_{*,s}+r_s<a_*-z\) anywhere in such an interval, then
\[ S_s> sz+\sqrt{s\log(A/s)} \geq \frac{uz}{2}+ \sqrt{\frac u2\log(A/u)}. \]
The maximal inequality therefore bounds that event’s probability by
\[ \frac uA\exp(-uz^2/2). \]

For the remaining sample counts use intervals \(u<s\leq2u\), where \(u=A2^j\). Here \(r_s=0\), and the analogous probability is at most \(\exp(-uz^2)\).

A union bound followed by integration over \(z\geq0\) yields
\[ \mathbb E[Z]\leq \frac{\sqrt{\pi/2}+\sqrt{\pi}/2} {1-2^{-1/2}}\frac1{\sqrt A} <\frac8{\sqrt A}. \]

2.2 Controlling selections of suboptimal classes

Write \(\Delta_\theta=a_*-a_\theta\) and \(\delta_0=A^{-1/2}\). Suppose a class with positive previous sample count \(s\) is selected and
\[ \Delta_\theta>\delta_0+2Z+2\eta. \]
Because its index is at least the optimal class’s index,
\[ \widehat a_{\theta,s}-a_\theta+r_s \geq\Delta_\theta-Z-\eta >\Delta_\theta/2. \]

Each previous sample count can precede at most one selection of that class. Its first selection contributes at most one additional occurrence. Hence, pathwise,
\[ \begin{aligned} \sum_{t=1}^T\Delta_{\theta_t} \leq {}&T\delta_0+2TZ+2T\eta\\ &+\sum_{\theta:\Delta_\theta>\delta_0}\Delta_\theta \left(1+\sum_{s=1}^T \mathbf1\{\widehat a_{\theta,s}-a_\theta+r_s \geq\Delta_\theta/2\}\right). \end{aligned} \]

For a fixed positive gap \(\Delta\), put
\[ g=\max\{1,\log(A\Delta^2)\}, \qquad s_0=\left\lceil\frac{16g}{\Delta^2}\right\rceil. \]
For \(s\geq s_0\), the definition of \(r_s\) gives \(r_s\leq\Delta/4\). Hoeffding’s inequality consequently gives
\[ \Pr(\widehat a_{\theta,s}-a_\theta+r_s \geq\Delta/2) \leq e^{-s\Delta^2/8}. \]
Using \(\sum_{s=1}^{\infty}e^{-s\Delta^2/8}\leq8/\Delta^2\), and \(0<\Delta\leq1\), we obtain
\[ 1+\sum_{s=1}^T \Pr(\widehat a_{\theta,s}-a_\theta+r_s \geq\Delta/2) \leq\frac{25g}{\Delta^2}. \]

When \(\Delta>\delta_0\), set \(y=\Delta\sqrt A>1\). The elementary inequality \(\max\{1,2\log y\}/y\leq1\) implies \(g/\Delta\leq\sqrt A\). Taking expectations in the pathwise bound therefore gives
\[ \mathbb E\left[\sum_{t=1}^T\Delta_{\theta_t}\right] \leq(1+16+25)\sqrt{KT}+2 =42\sqrt{KT}+2. \]

2.3 Returning to the original rewards

Quantization decreases each normalized class mean by at most \(1/T\). Its effect on regret is therefore at most \(1\) over the entire horizon. Multiplication by \(H\leq B\) gives
\[ R_M\leq H(42\sqrt{\tau T}+3) \leq50B\sqrt{\tau T}. \]
Also, \(R_M\leq BT\), since all values and rewards are nonnegative. Combining the regimes proves
\[ \mathcal R_M(N,T,\mu,B) \leq50B\min\{T,\sqrt{\tau T}\}. \]

The mechanism uses the reported quantity \(H\), never the withheld bound \(B\).

3. A matching lower bound for every mechanism

The lower bound uses only Bernoulli laws with rational parameters and applies without incentive constraints.

Choose a rational \(w\in[B/2,B]\), and give every advertiser value \(w\). Thus truthful reports reveal no information about reward means.

Let \(\mathsf P_0\) be the history law when every class has Bernoulli mean \(1/2\). For each class \(j\), let \(\mathsf P_j\) be the history law when only class \(j\) instead has mean \(1/2+\varepsilon\). Choose a dyadic rational satisfying
\[ \frac1{16}\min\{1,\sqrt{\tau/T}\} \leq\varepsilon\leq \frac18\min\{1,\sqrt{\tau/T}\}. \]

Let \(K_j\) count allocations to class \(j\). The chain rule for relative entropy gives
\[ D_{\mathrm{KL}}(\mathsf P_0\Vert\mathsf P_j) = \mathbb E_0[K_j]\, \operatorname{kl}(1/2,1/2+\varepsilon) \leq3\varepsilon^2\mathbb E_0[K_j]. \]
Indeed, conditional action kernels are the same under the two environments. Only observed rewards from class \(j\) contribute relative entropy. Choosing among different advertisers within that class provides no additional information.

Pinsker’s inequality and \(0\leq K_j\leq T\) imply
\[ \mathbb E_j[K_j] \leq\mathbb E_0[K_j]+ T\varepsilon\sqrt{\frac32\mathbb E_0[K_j]}. \]
Since \(\sum_j\mathbb E_0[K_j]=T\), averaging and applying Cauchy–Schwarz gives
\[ \frac1\tau\sum_j\mathbb E_j[K_j] \leq\frac T\tau+ T\varepsilon\sqrt{\frac{3T}{2\tau}} \leq\frac{3T}{4}. \]
The last inequality uses \(\tau\geq2\) and
\(\varepsilon\sqrt{T/\tau}\leq1/8\).

In environment \(j\), regret is \(w\varepsilon(T-\mathbb E_j[K_j])\). Some environment therefore has regret at least
\[ \frac{w\varepsilon T}{4} \geq\frac B{128}\min\{T,\sqrt{\tau T}\}. \]

This proves the matching lower bound for deterministic mechanisms, randomized mechanisms, and randomized mechanisms satisfying pooling. Population growth cannot improve this information bound: there remains only one observed reward per round.

4. Randomized pooling at the optimal rate

Modify the construction as follows. Independently in each class, choose the ordered pair \((r_\theta,s_\theta)\) uniformly among all pairs of distinct advertisers. Then run precisely the deterministic mechanism above, with all payments zero.

Incentives

The role lottery is independent of reports. Conditional on every realized set of roles, the argument in Section 1 proves truthfulness for every fixed reward table. Thus this mechanism is universally truthful, which is stronger than the required truthfulness in expectation.

Pooling limits

Fix a truthful society and a horizon \(T\). Let \(A_\theta\) be the expected number of class-\(\theta\) selections by the class policy.

The vector \((A_\theta)_\theta\) is independent of \(N\): informants report \(v_\theta\), and each selected recipient supplies independent samples from \(F_\theta\), regardless of its identity.

For any advertiser \(i\) in class \(\theta\), its probability of being the recipient is \(1/n_\theta\). Conditional on being the recipient, its expected impression count is \(A_\theta\). Consequently,
\[ N\mathbb E[X_i] =\frac{A_\theta}{\mu_\theta}, \qquad N\mathbb E[P_i]=0. \]
These are exact equalities for every admissible \(N\) with \(n_\theta\geq2\). In particular, convergence is uniform within each class, with
\[ x_\theta=\frac{A_\theta}{\mu_\theta}, \qquad q_\theta=0. \]
All limits are finite. Since exactly one impression is allocated each round,
\[ \sum_\theta\mu_\theta x_\theta =\sum_\theta A_\theta=T>0. \]
Hence the limit is nondegenerate. Randomization leaves the class-level reward distribution and the regret bound unchanged.

5. Deterministic pooling is impossible

This obstruction does not depend on truthfulness or payments.

Fix any positive rational common values and set every law to the point mass at \(1\). Fix \(T\geq1\). For a deterministic mechanism, every \(X_i\) is then a deterministic nonnegative integer, and \(\sum_iX_i=T\).

Suppose the required uniform pooling limits existed, with all \(x_\theta\) finite. Uniform convergence and finite support would give a finite constant \(C\) such that, for all sufficiently large admissible \(N\), every advertiser satisfies \(NX_i\leq C\).

For \(N>C\), this implies \(X_i<1\). Integrality forces \(X_i=0\) for every advertiser, contradicting \(\sum_iX_i=T\).

Thus no deterministic family satisfies the specified finite pooling limits on every truthful society, even if its regret is unrestricted.

6. Asymptotics and computation

For fixed masses, every class has two advertisers whenever
\[ N\geq N_0(\mu):= \left\lceil\frac2{\min_\theta\mu_\theta}\right\rceil. \]
For earlier admissible populations, define the family using any bid-independent allocation schedule and zero payments. This preserves every incentive constraint and gives regret at most \(BT\). The optimal bounds established above apply uniformly once \(N\geq N_0(\mu)\), including for arbitrary \(T(N)\).

Pooling in the question is explicitly a fixed-\(T\) requirement. The randomized construction satisfies it for every fixed \(T\). If one instead demanded finite uniform limits along \(T(N)\to\infty\), compulsory allocation would make that impossible: summing the scaled impression counts against the fixed masses gives \(T(N)\).

For computation, \(m=1\) throughout; no extension to multiple slots is claimed. Rational upper approximations \(u_s\) can be precomputed to accuracy \(1/T\) in \(T\operatorname{poly}(\log(T\tau))\) bit operations. Quantized sample sums and empirical means have \(O(\log T)\)-bit encodings. Scanning the \(\tau\) indices each round gives a total rational computation bound
\[ O\!\left((N+\tau T) \operatorname{poly}(L+\log(NT))\right). \]
The randomized construction additionally uses an expected \(O(\tau\log N)\) unbiased random bits to choose its roles.

This bit bound counts rational observed rewards in the total encoding length \(L\). If a finite rational description of a law permits genuinely real-valued observations, the corresponding precise statement is the same rational computation bound plus \(O(T\log T)\) exact reward comparisons against rational thresholds. A law description alone does not specify a bit-access model for an exact real draw.

Finally, the [cited two-advertiser result](https://arxiv.org/pdf/1004.3630v5) is consistent with these conclusions. With one advertiser per class, one cannot separate an informant from a recipient. Replication supplies that separation, while the welfare guarantee here is required only at common-value truthful profiles.

⟨structured verdict parsed — rendered above⟩

The regret and pooling conclusions are correct. The construction preserves every individual’s incentive constraints, the upper and lower regret bounds match, and the deterministic pooling obstruction is valid. The only clarification needed concerns the computational model for real-valued observations; it does not affect the mathematical conclusions.

• Scope and claimed rate

The claimed rate is \(\Theta(B\min\{T,\sqrt{\tau T}\})\), uniformly once every class contains at least two advertisers.

The proof establishes precisely this eventual population regime. Its treatment of smaller admissible populations supplies a truthful family with regret at most \(BT\), without claiming the matching rate there. For fixed positive masses, the stated threshold \(N_0(\mu)=\lceil 2/\min_\theta\mu_\theta\rceil\) is sufficient.

The constants in the regret bounds do not depend on the masses, \(N\), \(B\), or \(T\). Consequently, the conclusion applies along arbitrary choices of \(T=T(N)\) once the population threshold is reached.

• Deterministic construction and individual incentives

The informant and recipient in each class are distinct and chosen independently of reports. This distinction is essential and is explicitly enforced.

An informant never receives an impression and always pays zero. Its utility therefore remains zero even when its report changes allocations to other advertisers.

A recipient’s report is ignored by the entire mechanism. For any fixed potential-reward table and fixed other reports, changing its report leaves its allocation history and payment unchanged. Unused advertisers likewise receive zero utility independently of their reports.

These arguments apply to individual deviations at arbitrary profiles. They do not assume that deviating advertisers retain their class’s common value. Thus the construction satisfies the task’s off-profile incentive requirements.

All payments are zero, so ex-post normalization and computation of payments from observed history hold immediately. At truthful common-value profiles, the informants reveal the correct class values.

Finding: This part is correct.

• Bandit reduction and quantization

When \(H>0\), the transformed observations lie in \([0,1]\). The floor operation gives the claimed normalized mean error between zero and \(1/T\).

At truthful profiles, each recipient’s observations are independent across rounds and have the appropriate class law. Thus the class policy is a stochastic bandit policy with \(\tau\) arms.

The cases \(H=0\) and \(T<\tau\) are handled correctly. In particular, when \(T<\tau\), \(\min\{T,\sqrt{\tau T}\}=T\), so the elementary \(BT\) bound has the required order.

The MOSS reference is accurate: Figure 3 gives the stated indices, and Theorem 5 establishes a distribution-free bound for independent stochastic rewards supported on \([0,1]\). Those hypotheses hold here. The finite-precision modification is also analyzed separately, so the proof does not rely on applying that theorem unchanged to approximate indices. See the [original paper](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/01/COLT09_AB.pdf).

Finding: The reduction is valid.

• Pessimism bound in Section 2.1

The centered increments defining \(S_s\) are independent, mean zero, and have range length at most one. These are the hypotheses needed for the displayed maximal Hoeffding bound.

On an early interval \(u/2<s\leq u\), both \(s\geq u/2\) and \(\log(A/s)\geq\log(A/u)\) hold. Therefore the stated lower bound on the crossing threshold is valid. Substitution into the maximal inequality yields the factor
\((u/A)\exp(-uz^2/2)\); dropping the nonnegative cross term only weakens the bound.

On a late interval \(u<s\leq2u\), \(s>A\), so \(r_s=0\). Applying the maximal bound up to \(2u\) gives \(\exp(-uz^2)\), as claimed.

The intervals cover all positive sample counts. Empty intervals and interval portions beyond \(T\) contribute nothing. Integration of the two geometric sums gives exactly the displayed coefficient, which is less than eight.

Finding: \(\mathbb E[Z]\leq8/\sqrt A\) is justified.

• Suboptimal selections in Section 2.2

If a previously sampled suboptimal class is selected while the optimal class remains unobserved, its finite index cannot beat the optimal class’s infinite index. Thus the finite-index comparison used in the proof is valid whenever needed.

The approximate bonus contributes at most \(\eta\), and the optimal index is at least \(a_*-Z\). The stated gap condition therefore implies the displayed empirical-deviation event.

Each previous sample count can precede at most one selection of its class. First selections are explicitly included. This justifies the pathwise counting inequality without any independence assumption involving \(Z\).

For \(s\geq s_0\), the logarithmic term is at most \(g\), and \(s\geq16g/\Delta^2\). Hence \(r_s\leq\Delta/4\). Hoeffding then gives the stated exponent \(s\Delta^2/8\).

The occurrence bound correctly accommodates the ceiling in \(s_0\), the first selection, and the exponential tail: using \(\Delta\leq1\) and \(g\geq1\), the coefficient \(25g/\Delta^2\) suffices.

Finally, \(\max\{1,2\log y\}/y\leq1\) holds for \(y>1\). Thus each relevant class contributes at most \(25\sqrt A\), and summing over at most \(K\) classes gives the claimed bound
\(42\sqrt{KT}+2\).

Finding: The counting argument and constants are correct.

• Return to original welfare

The proof bounds expected pseudo-regret. Independence of the current reward from the previous history makes this equal to the relevant expected welfare loss for the transformed rewards.

Quantization changes each normalized mean downward by at most \(1/T\). Its total additional regret cost is therefore at most one over \(T\) rounds. Multiplication by \(H\leq B\) yields the stated original-reward bound.

Combining that bound with \(R_M\leq BT\) gives the asserted uniform upper rate. The mechanism uses \(H\), not the unknown bound \(B\).

Finding: The upper bound is established.

• Matching information lower bound

Rational \(w\in[B/2,B]\) exists for every \(B>0\), and the specified dyadic interval for \(\varepsilon\) is nonempty. All Bernoulli parameters remain valid rational probabilities.

The relative-entropy chain rule applies to adaptive mechanisms because, conditional on a fixed history and reports, their action kernels agree across environments. Only observations from the modified class contribute divergence.

The Bernoulli divergence bound is valid throughout \(\varepsilon\leq1/8\). Pinsker’s inequality, together with \(0\leq K_j\leq T\), gives the displayed expectation comparison.

Averaging and Cauchy–Schwarz are applied correctly. The resulting fraction is at most
\(1/2+\sqrt{3/2}/8<3/4\). Hence some environment has regret at least \(w\varepsilon T/4\), yielding the stated constant \(B/128\).

This argument permits arbitrary individual selections and mechanism randomization. Replication does not provide extra observed samples.

Finding: The lower bound applies to every mechanism, including those satisfying pooling.

• Randomized pooling and deterministic impossibility

The role lottery is independent of reports. Conditional on any realized roles, the deterministic incentive argument remains valid for every fixed reward table. Universal truthfulness therefore follows.

At a fixed truthful society and fixed \(T\), the expected class selection counts are independent of recipient identities and \(N\). The equality
\(N\mathbb E[X_i]=A_\theta/\mu_\theta\) follows from the uniform recipient probability. It holds exactly and uniformly within each class. Payments have zero limits.

Finiteness follows from \(A_\theta\leq T\), and nondegeneracy follows from \(\sum_\theta A_\theta=T>0\).

For deterministic mechanisms, point-mass reward laws eliminate environmental randomness. Impression counts are then integers. Uniform convergence to finite limits across finitely many classes supplies a common bound on \(NX_i\), eventually forcing every \(X_i\) to be zero. This contradicts compulsory allocation of \(T\) impressions.

Finding: Both pooling conclusions are proved. The distinction between fixed-\(T\) pooling and growing horizons is correctly maintained.

• Computation: minor clarification

For rational observations, the stated storage sizes and polynomial rational computation bound are consistent with the construction. Uniform role sampling also has the claimed expected random-bit cost.

However, a rational finite description of a law need not make its realized observations rational. The prover correctly acknowledges this and states an additional exact-comparison requirement.

Minor issue: The final computation statement should explicitly identify the observation-access model and whether \(L\) includes realized rational observations. Otherwise its bit-operation bound can be read as unconditional for every finitely described law.

Minimum clarification: State that the pure bit-operation bound applies to rational observations with their encoding lengths counted in \(L\); for real-valued observations, state that the bound is conditional on the stipulated exact-comparison oracle. No further regret or incentive argument is needed.

The cited two-advertiser result is also represented accurately. Its assumptions and exponent comparison appear in [the supplied source](https://arxiv.org/pdf/1004.3630v5). The replicated construction does not contradict it: its welfare guarantee is restricted to common-value class profiles, while its individual incentive guarantee holds at arbitrary profiles.

⟨structured verdict parsed — rendered above⟩