| paper | d4-conf-aaai-2016-0233 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: The guarantee \(\mathrm{OPT}_{\pi}\ge\tfrac12\mathrm{OPT}\) holds for every admissible instance and every supplied order \(\pi\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational type masses \(\mu_t\ge 0\) summing to \(1\), per-unit values \(\bar v_t\), fatigue rates \(\delta_t\ge 0\), and feed mass \(\rho\in(0,1]\), choose a measurable schedule \(z:[0,\rho]\to T\) with \(|\{x:z(x)=t\}|\le\mu_t\) to maximize \(W(z)=\int_0^\rho \bar v_{z(x)}\exp(-\int_0^x\delta_{z(y)}\,dy)\,dx\). For every supplied total order \(\pi\) on \(T\), does the best schedule whose nonempty type blocks follow \(\pi\) achieve at least half the unrestricted optimum?
A nonatomic sponsored feed where each type \(t\) has advertiser mass \(\mu_t\), value \(\bar v_t\), and fatigue rate \(\delta_t\); a schedule assigns type mass along feed positions, and welfare discounts each position by the accumulated cascade fatigue.
The mirror requires a feed with \(\Theta(n)\) slots and per-placement fatigue that vanishes as the market grows, so its relevance is confined to a narrow long-feed regime.
fatal: False
Covers Theorem 1’s half-welfare guarantee for order-restricted allocation when \(\lambda_k=1\); leaves the equilibrium PoA and PoS results, the ad-pruning algorithm, and nonconstant prominence profiles outside the mirror.
I would make the lead Continuum-SORTED-ADS, anchored on Theorem 1, proved in this paper. The theorem says that when the position factors are \(1\), for *every* total order \(\prec_{\mathrm{ads}}\), the best allocation respecting that order has social welfare at least half the unrestricted optimum: \(SW(\theta^*_{\prec_{\mathrm{ads}}})/SW(\theta^*)\ge 1/2\). Here \(\theta^*_{\prec_{\mathrm{ads}}}\) is the best allocation whose occupied ads appear in the prescribed order, and \(\theta^*\) is the best allocation without that restriction. The paper’s SORTED-ADS algorithm computes the order-restricted allocation; Theorem 1 proves its approximation guarantee. This is an approximation result, not a hardness result. The paper says exact APDC allocation is commonly conjectured to be FNP-hard, but that hardness is not established here.
A plausible high-multiplicity setting is a long sponsored feed with many advertisers but relatively few distinct campaign profiles. A type \(t\) records an advertiser’s quality \(q_t\), value \(v_t\), and fatigue parameter; all advertisers of that type share those attributes. Let \(\mu_t\) be the fraction of advertisers of type \(t\), with \(\sum_t\mu_t=1\), and write \(\bar v_t=q_tv_t\). Suppose the feed has \(K_n\) positions among \(n\) advertisers, with \(K_n/n\to\rho\in(0,1]\). To get a nondegenerate cascade over that many positions, let a type-\(t\) ad’s continuation probability be \(c_{t,n}=1-\delta_t/n\), for a fixed fatigue rate \(\delta_t\ge0\). Set the interior position factors to \(1\), as in Theorem 1’s setting.
The continuous instance has rational masses \(\mu_t\), rates \(\delta_t\), a feed length \(\rho\), and types \(t\in T\). A feasible allocation is a measurable schedule \(z:[0,\rho]\to T\), using each type for at most its available mass: \(\lvert\{x:z(x)=t\}\rvert\le\mu_t\). Its per-capita welfare is
\[
W(z)=\int_0^\rho \bar v_{z(x)}
\exp\!\left(-\int_0^x\delta_{z(y)}\,dy\right)\,dx.
\]
The problem asks for a welfare-maximizing schedule \(z\) and its value. For any supplied total order \(\pi\) of the types, the mirrored Theorem 1 question is whether the best schedule whose nonempty type blocks follow \(\pi\) always achieves at least \(\tfrac12\max_z W(z)\). The schedule itself—not an encoding—is the solution.
This is a direct large-market limit of the paper’s allocation problem. With \(n_t=n\mu_t\) advertisers of each type, the finite normalized welfare is \(n^{-1}\sum_{s=1}^{K_n}\bar v_{t_s}\prod_{j<s}(1-\delta_{t_j}/n)\), which converges to \(W(z)\). Ordering all advertisers in contiguous type blocks and applying Theorem 1 gives the half-welfare guarantee in the limit. The continuous population is the advertisers; the proportional slot supply is the co-modification that makes their available mass constrain the allocation.
I expect Class A in this restricted regime. With position factors \(1\), an adjacent-swap comparison orders types by \(\bar v_t/\delta_t\); the continuum optimum takes available mass in that order until the feed is filled. Thus the unrestricted optimum is obtained by sorting the \(\tau\) types. The order-restricted half-guarantee also follows from the finite theorem by the limit above. Computing the exact order-restricted schedule may need its own bit-complexity analysis; the finite \(O(NK)\) dynamic program alone does not prove a polynomial bound in \(\tau\) and input bit length.
The authors have a good reason to recognize this as their problem: it retains their welfare objective, advertiser attributes, sequential cascade, and ordered allocation decision, while turning repeated advertiser profiles into supplies of mass. It covers Theorem 1’s no-position-effect allocation result, not the paper’s GSP/VCG equilibrium or revenue analysis.
The weakest point is the regime. The paper’s experiments use at most ten slots; this mirror uses a long feed with \(K_n\) proportional to the advertiser population and continuation probabilities approaching \(1\) at rate \(1/n\). That can describe a low-dropout sponsored feed, but it is narrower than ordinary short-page search auctions. With fixed \(K\), advertiser masses largely cease to constrain the limit, so this particular continuous model would lose much of its force. A natural next question is whether the half-guarantee survives a smoothly varying position-prominence profile in the continuum.
Theorem 1 is a real computational result, so the objection cannot be that the paper has nothing to mirror. The problem is finding a sponsored-search regime in which its continuous version adds anything.
With a fixed number \(K\) of slots—the setting the paper studies and tests—let \(n\) grow while the type set stays finite and every supported type has positive mass. Eventually there are at least \(K\) advertisers of every type. The type masses then stop affecting which allocations are feasible: each type is simply an available supply of interchangeable ads, and only \(K\) ads can be selected. Normalize welfare per advertiser and it tends to zero; leave it unnormalized and the limit remains a finite-slot allocation problem. In either case, the continuous population has lost its role as a computational object.
The proposed escape, \(K_n\) proportional to \(n\), avoids that collapse by changing the auction regime. It also needs \(c_{t,n}=1-\delta_t/n\): with fixed type-level continuation probabilities below \(1\), welfare decays geometrically down the feed, so deep positions and most of the population cease to matter. This scaling makes fatigue per ad shrink as the market grows. Together with \(\lambda_s=1\), it describes a long feed with no position loss and vanishing per-placement fatigue, rather than the short sponsored-search pages motivating the paper.
Even granting that regime, the proposed half-welfare question is a limit of Theorem 1, not a new computational problem. For finitely many types, the order-restricted schedule just uses available mass in the supplied order; without the order restriction, the \(\lambda_s=1\) objective is optimized by ordering types by \(\bar v_t/\delta_t\), with the zero-fatigue cases handled first. The finite theorem already gives the half guarantee for every \(n\), so the continuous guarantee follows by taking the limit. That is mathematically sound, but it does not chart a new complexity landscape.
A broader mirror with a nonconstant position profile could pose a less immediate scheduling or control problem. That is also where this negative case is weakest: a long feed with many similar campaign profiles is not inconceivable, and the resulting population limit might be worth studying if the authors recognize it as their allocation problem. But that would be a different mirror from the Theorem 1 anchor, and I cannot honestly rule out every worthwhile scenario.
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.