| paper | d4-conf-sigecom-2009-0016 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
Given rational cohort masses \(\mu_\theta\) summing to \(1\), values \(v_\theta\), unknown shared click rates \(p_\theta\), a per-advertiser quota \(q\), and \(H\le q\), form \(N\mu_\theta\) individually identifiable advertisers of each type and run \(T_N=HN\) rounds. Each round selects one eligible advertiser and observes only that advertiser’s click; determine the minimax expected regret as \(N\to\infty\) among deterministic, normalized, truthful mechanisms with bid-independent exploratory rounds, against the static benchmark maximizing \(\sum_\theta x_\theta v_\theta p_\theta\) subject to \(0\le x_\theta\le q\mu_\theta\) and \(\sum_\theta x_\theta=H\). When a best cohort has enough capacity for all \(H\) and has a fixed \(\delta\)-gap over the runner-up, determine whether the paper’s polynomial gap-regret phenomenon persists.
A \(\tau\)-type advertiser population with masses \(\mu\); finite-\(N\) individuals retain their bids, click histories, and remaining quotas, while \(\mu\) determines cohort capacities and the static welfare benchmark.
With common \(p_\theta\), clicks pool across advertisers, while \(\mu\) does not encode individual reports or histories; the original \(k\)-arm lower bound therefore does not carry over automatically.
fatal: False
Covers Theorem 3’s worst-case regret bound and its \(\delta\)-gap question; leaves the structural characterizations, matching upper-bound mechanism, and randomized and adversarial results aside.
The strongest positive mirror I can make is for the paper’s online learning problem in a large advertiser market. Picture many advertisers in a few cohorts: members of each cohort share a value per click, click probability, and impression quota, but remain individually identifiable and able to submit bids. If the number of advertisers is \(N\) and the number of cohorts is \(\tau\), the regime is \(N\gg\tau\). The mass \(\mu_\theta\) of cohort \(\theta\) is its fraction of the advertiser population.
My lead anchor is Theorem 3, proved in this paper. For the stochastic multi-armed bandit problem, it says that a deterministic exploration-separated allocation rule has regret \(R(T)=\Omega(k^{1/3}T^{2/3})\). It also says that if its worst-case regret is \(O(T^\gamma)\), for \(\gamma<1\), then for every fixed \(\delta\leq 1/4\) and every \(\varepsilon>0\), its worst-case regret on \(\delta\)-gap instances is \(\Omega(\delta T^{2(1-\gamma)-\varepsilon})\). The paper proves these bounds; its later regret section gives the detailed arguments. This is a lower bound on achievable performance, not a conventional NP-hardness result.
Here is the mirror I would hand to a prover: Continuous Advertiser-Pool Regret. An instance gives a finite type set \(\Theta\), rational population masses \(\mu_\theta\) summing to one, values \(v_\theta\leq V_{\max}\), unknown click-through rates \(p_\theta\), an impression quota \(q\) per advertiser, and a per-capita horizon \(H\). In the finite approximations, cohort \(\theta\) has about \(N\mu_\theta\) advertisers and the horizon is \(T_N=HN\) rounds. Each round assigns one impression to a named advertiser, and a click is an independent Bernoulli outcome with that advertiser’s cohort rate. A deterministic online rule sees only past assigned-ad clicks. For the mirror of Theorem 3, restrict to exploration-separated rules; for the mechanism-design version, also require normalized payments based on observed clicks and dominant-strategy truthfulness for every click realization.
The cumulative exposure per unit population to type \(\theta\) is \(x_\theta\), with \(0\leq x_\theta\leq q\mu_\theta\) and \(\sum_\theta x_\theta=H\). Regret is total expected welfare lost against the best feasible fixed type allocation, which maximizes \(\sum_\theta x_\theta v_\theta p_\theta\) subject to those constraints. The question is to determine the minimax regret rate as \(N\) grows with \(\mu\), \(H\), and \(\tau\) fixed, and to give a matching mechanism or lower bound. In the regime where quotas do not constrain the best types, I would expect an exploration-versus-exploitation lower bound to persist, with dependence on the distinct types and possibly their masses. Establishing the right rate—and whether \(\delta\)-gap instances still force polynomial regret—is the concrete deliverable.
I expect the regret obstruction to transfer in that interior regime: representing advertiser cohorts by fractional masses should not by itself remove the cost of learning under truthfulness. The paper’s existing high-multiplicity perspective supports asking the question; it is not a novelty collision. A fixed-support population can also be approximated by finite cohorts, so there is a clear route for testing which parts of the discrete proof survive.
The weak point is substantial: in the paper, \(k\) counts independently selectable advertisers, while cohort members here share a click model, and the per-advertiser quota is an added model feature. Without a quota or another supply rule that scales with population, the masses may have no effect at all: if every positive-mass type can be selected freely, only the support matters. And the \(N\)-to-\(\infty\) limit may change individual incentive constraints. So this is a plausible PPC extension the authors might recognize, but the paper does not already establish the proposed continuous regret bound.
Theorem 3 is a real algorithmic anchor: it bounds regret for exploration-separated rules against the best fixed advertiser. The \(\delta\)-gap bound is a second statement about that same online problem. I would not argue that the paper lacks named results. The problem is that the proposed continuum cannot preserve the anchor’s benchmark, advertiser-level incentives, and population masses together.
In the paper, a round selects one named advertiser, whose bid and observed click history affect later allocation and payment. Truthfulness is required for each advertiser and every click realization. A mass \(\mu_\theta\) records how many advertisers share a cohort description, but it does not record which person received impressions or accumulated which click history. Keeping those identities and histories preserves the original mechanism, while leaving the population distribution unable to summarize its state. Pooling them makes a different mechanism-design problem: an individual bid deviation has zero mass in the continuum, so aggregate allocation rules cannot express the source’s individual incentive constraint. Treating a whole cohort’s report as the deviation gives a group incentive notion absent from the paper.
The proposed per-advertiser quota exposes a separate mismatch. With a fixed quota \(q\), an individual advertiser cannot be the best fixed arm for \(T=HN\) rounds as \(N\) grows. The proposed benchmark, which allocates exposure across types subject to \(x_\theta\leq q\mu_\theta\), therefore replaces the paper’s best-fixed-arm benchmark. That may define a sensible finite-supply bandit problem, but its regret theorem would require a new analysis of a different comparator and feasible set. If quotas instead grow enough to let one advertiser receive all \(T\) impressions, the source benchmark survives, while cohort masses cease to constrain the allocation in the proposed way.
The \(\delta\)-gap result encounters the same issue. Its gap is between the expected rewards of individual arms; duplicating advertisers with the same value and CTR adds supply, not new reward types. Grouping them yields a \(\tau\)-arm learning problem with mass-based capacity limits. Any polynomial regret claim for that model would be a new result about finite-supply learning, rather than a population mirror of the paper’s gap theorem.
So the strongest case against is a scaling conflict: preserving the named-arm benchmark leaves cohort mass without a meaningful role; making mass govern per-capita supply changes the benchmark; and taking an atomless limit loses individual incentive constraints from the aggregate model. A large advertiser market could still motivate worthwhile bandit research. I cannot honestly rule out every useful extension. But the proponent’s quota model is best described as a re-modeling lead, not a faithful continuous-population mirror of this paper’s anchors.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.