d4-conf-atal-2024-0213

The paper’s strongest continuous mirror is a large batch auction for standardized ad opportunities. Imagine a platform clearing many comparable opportunities together, with many advertisers using a small number of repeated campaign profiles. A type is \(\theta=(v,\tau)\), where \(v\) is the advertiser’s value per click and \(\tau\in\{UM,RB\}\) is its class. For an \(RB\), \(\gamma\) is the paper’s shared ROI parameter. A mass \(\mu_\theta\) is the fraction of advertisers with that complete profile, and \(\tau_0=|\operatorname{supp}(\mu)|\) is the number of distinct profiles. This fits settings where millions of advertisers fall into relatively few value and bidding-policy groups.

To keep scarce supply meaningful as the population grows, give the batch a per-advertiser capacity \(q_k\) of opportunities at each of \(K\) click-through rates \(x_k\), with \(\sum_k q_k\leq 1\). This is a co-modification of the market’s supply, not the object being continuized: the population is represented by \(\mu\). A mechanism assigns each advertiser an integral slot, possibly by lottery; in aggregate, \(y_{\theta,k}\) is the mass of type \(\theta\) assigned to slot class \(k\). The liquid social welfare benchmark is the optimum of
\[ \max_y \sum_{\theta,k} v_\theta x_k y_{\theta,k} \quad\text{subject to}\quad \sum_k y_{\theta,k}\leq\mu_\theta,\qquad \sum_\theta y_{\theta,k}\leq q_k,\qquad y_{\theta,k}\geq0. \]
The \(RB\)’s value here is the paper’s willingness-to-pay \(v\), not its click revenue \(\gamma v\).

A direct mechanism must specify, for every background distribution \(\mu\), what an infinitesimal advertiser receives and pays under each reported type. Truthfulness compares those offers at fixed \(\mu\): a true \(UM\) with value \(v\) gets utility \((v-p)x\), while a true \(RB\) gets \((\gamma v-p)x\) if \(p\leq v\), and \(-\infty\) otherwise. This tagged-advertiser formulation keeps the paper’s unilateral incentive question meaningful in an atomless population. Require individual rationality and consistency as well: when everyone is a \(UM\), the rule agrees with the replicated-market limit of VCG; when everyone is an \(RB\), it agrees with the replicated-market limit of Cavallo’s mechanism. Replicating rational masses and capacities by a common factor gives a precise way to define those limits.

My lead anchor is Theorem 5, proved in this paper. It states that no incentive-compatible, individually rational, consistent mechanism can guarantee a liquid-social-welfare approximation ratio below \(5/4\) when \(\gamma\geq2\), or below \((3+\gamma)/(2+3\gamma-\gamma^2)\) when \(1<\gamma<2\). The paper proves this with a two-slot, three-bidder construction. Its continuous counterpart is the named problem Continuous BIN-Pri Approximation Frontier: given rational \(\gamma\), slot qualities and per-capita capacities, determine whether there is an anonymous direct mechanism satisfying the pointwise truthfulness, IR, and consistency conditions above whose worst-case ratio over finite-support rational \(\mu\) is strictly below
\[ r_\gamma= \begin{cases} 5/4,&\gamma\geq2,\\ (3+\gamma)/(2+3\gamma-\gamma^2),&1<\gamma<2. \end{cases} \]
The output is a mechanism or an impossibility proof. I expect the lower bound to transfer in some form: the proof’s pressure comes from incentive constraints across reports and consistency with the pure-class mechanisms, not from a search over many bidders. But whether its exact constants survive the atomless limit is open; the three-bidder witness does not itself prove that.

A second, constructive anchor is Theorem 4, also proved here. It states that BIN-Pri achieves approximation ratio at most \(3/2\) on LSW, equivalently \(W_{\text{our}}\geq(2/3)W_{\text{OPT}}\). BIN-Pri’s incentive compatibility, IR, and consistency are established earlier in the paper. Its continuous counterpart is Continuous BIN-Pri Mass Allocation: for a rational finite-support population distribution and per-capita slot capacities, construct a truthful, IR, consistent mechanism with welfare at least \(2/3\) of the feasible assignment optimum, and compute its outcome in time polynomial in \(K\), \(\tau_0\), and the input bit length. I expect this to be tractable: BIN-Pri sorts bidders and allocates slots iteratively, operations that appear to become a sweep over type masses and capacity breakpoints. That extension still needs a proof, particularly for cohorts of equal value.

These anchors cover the paper’s binary-class, private-value, ex-post ROI setting and its LSW guarantees; they do not try to continuize all of auction design. The named results are approximation and mechanism-design results, not NP-hardness or polynomial-time classifications. The continuous questions are therefore about the approximation frontier and its constructive mechanism, not a complexity-class claim the paper never makes.

The weakest point is the change from a finite auction to a batch market with per-capita slot supply. The paper studies a fixed set of advertisers and positions; it does not establish that its IC proofs or lower-bound witness persist when equal-type cohorts are split across capacity classes. The finite model’s tie-breaking and the atomless pointwise incentive conditions also need careful treatment. I think the mirror is still worth asking: advertisers grouped by value and ROI class, competing for shares of standardized opportunities, is a recognizable version of their mechanism-design problem. The key open questions are whether the \(3/2\) guarantee survives mass splitting, whether the \(r_\gamma\) obstruction survives replication, and how either result changes with multiple ROI classes.