| paper | d4-conf-ijcai-2017-0502 |
| 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: Yes. A deterministic nonanticipative measurable subset-valued policy guarantees $1-1/e$ on every allowed continuous stream, and the optimal uniform competitive ratio is $1-1/e$. The attaining construction uses countably many allocation changes; finite implementations achieve $1-1/e-\varepsilon$ in polynomial time. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a unit-mass ordered stream \(\theta(u)\), \(u\in[0,1]\), of finite-support request types \(\theta=(T_\theta,(b_i(\theta))_{i\in N})\), with fixed ad lengths \(t_i\), each infinitesimal request must receive an integral set \(S(u)\subseteq N\) satisfying \(\sum_{i\in S(u)}t_i\le T_{\theta(u)}\). Advertiser \(i\)'s total spend is \(\int_0^1 b_i(\theta(u))\mathbf{1}[i\in S(u)]\,du\le B_i\), and revenue is the integral of the total payments. For finite, rationally encoded stream profiles whose future is hidden from the policy, determine whether a nonanticipative policy can guarantee revenue at least \((1-1/e)\) times the offline optimum in the limit where per-request bids are negligible relative to budgets scaled with population size; also determine the best achievable ratio if that guarantee fails.
Advertisers \(N\) have budgets \(B_i\) per unit population and fixed ad lengths \(t_i\). A request type \(\theta\) specifies viewing capacity \(T_\theta\) and bids \(b_i(\theta)\); the unit-mass population is an ordered, piecewise-constant stream with support size \(\tau\) and an encoded number \(q\) of arrival-order blocks. Each unit of mass receives an integral feasible ad set, while a cohort may split across sets. A causal policy sees the current type and stream prefix; its integrated revenue is compared with the offline optimum for the full stream.
The input's complexity also depends on the number of arrival-order blocks \(q\), which support size \(\tau\) does not bound; the proponent does not establish how large \(q\) can be in the intended regime.
fatal: False
This mirror covers the standard video-ad allocation result in Theorem 1. It leaves the richer envy-free, user-dependent-length result in Theorem 2 and the experimental comparisons outside the question.
The strongest mirror is the paper’s envy-free video-ad allocation problem, with the standard allocation problem as a cleaner second anchor. Both are online results, so the continuous instance must retain arrival order: the population is continuous, but the algorithm still learns user types as requests arrive.
A plausible regime is a large streaming platform serving many ad requests against a comparatively small advertiser set. The paper itself reports a dataset of \(21{,}306{,}810\) queries and \(82\) ads. A type could be a request’s viewing capacity, its bid from each advertiser, and—where relevant—the length of each ad for that request. Requests with identical values for all those fields are indistinguishable for the problem. Standardized contexts or broad preference cohorts could yield many requests but moderate support \(\tau\). Advertiser budgets and revenue are measured per unit of total request mass, corresponding to campaigns whose budgets scale with the audience; then an individual request’s bid is a vanishing share of an advertiser’s total budget.
My lead question is \(\textsc{EF-VideoAllocation-Online}_{\infty}\). Fix advertisers \(N\), each with budget \(B_i\) and original ad length \(t_i\). A request type \(\theta\) contains a viewing capacity \(T_\theta\), bids \(b_i(\theta)\), and user-dependent ad lengths \(t_i(\theta)\). The population is an ordered stream \(\theta(u)\), \(u\in[0,1]\), with finite support \(\tau\); its type masses are \(\mu_\theta=|\{u:\theta(u)=\theta\}|\). The stream may be represented by a finite piecewise-constant profile with rational breakpoints, but the future profile is hidden from the online policy.
At each arrival coordinate \(u\), the policy assigns that request an outcome \((p(u),S(u))\), where \(S(u)\subseteq N\) is the set of ads shown and \(p_i(u)\) is the charge to advertiser \(i\). Each request’s bundle remains an ordinary feasible set: \(\sum_{i\in S(u)}t_i(\theta(u))\le T_{\theta(u)}\). Its prices must obey the request’s bids, be zero for unallocated advertisers, and satisfy the paper’s envy condition: if \(i,i'\in S(u)\) and \(t_i\ge t_{i'}\), then \(p_i(u)\ge p_{i'}(u)\). Across the population, \(\int_0^1p_i(u)\,du\le B_i\). The objective is to maximize \(\int_0^1\sum_i p_i(u)\,du\). A solution is a nonanticipative online policy assigning such outcomes, with its revenue compared against the offline optimum that knows the whole stream. Although each request gets an integral bundle, a measurable cohort can be split among different bundles; the resulting type-level averages are fractional.
The anchor is Theorem 2, proved in this paper. It states that for the authors’ general outcome framework, if each arrival’s feasible outcome set is subset-closed and has an \(\alpha\)-approximation algorithm for maximizing weighted revenue, Algorithm 1 is \(\alpha(1-1/\gamma)(1-R_{\max})\)-competitive, where \(\gamma=(1+R_{\max}/\alpha)^{1/R_{\max}}\) and \(R_{\max}\) is the maximum price-to-budget ratio. The paper’s envy-free, user-dependent-length model fits that framework; Lemma 1 gives an exact pseudo-polynomial outcome optimizer for it. In the small-bid limit, the theorem’s guarantee tends to \(\alpha(1-1/e^{1/\alpha})\), and to \(1-1/e\) when \(\alpha=1\). The continuous question is whether the same guarantee, or the best possible one, holds for the atomless online population with the stated type representation. I expect this to be tractable in the small-bid regime, through a continuous primal-dual process and the paper’s per-type optimization. The paper proves the finite-arrival theorem; it does not itself prove this continuum extension.
The second question, \(\textsc{VideoAllocation-Online}_{\infty}\), mirrors the paper’s standard model without envy-free pricing or user-dependent lengths. A type is \(\theta=(T_\theta,(b_i(\theta))_{i\in N})\); the advertisers’ ad lengths \(t_i\) are fixed. At each \(u\), assign a set \(S(u)\) with \(\sum_{i\in S(u)}t_i\le T_{\theta(u)}\). Maximize \(\int_0^1\sum_{i\in S(u)}b_i(\theta(u))\,du\) subject to \(\int_0^1\mathbf{1}[i\in S(u)]b_i(\theta(u))\,du\le B_i\) for every advertiser. Again, the requested solution is an online policy, not just an offline allocation.
Its anchor is Theorem 1, proved in this paper. Under the small-bid assumption, it gives a polynomial-time \((1-1/e-\varepsilon)\)-competitive algorithm for every constant \(\varepsilon>0\), and a pseudo-polynomial-time \((1-1/e)\)-competitive algorithm. The proof places the problem in the cited Goel et al. framework and uses knapsack optimization: approximate knapsack gives the polynomial-time guarantee, and exact pseudo-polynomial knapsack gives the latter. I expect the continuous analogue to be tractable by the same limiting primal-dual approach, with knapsack pricing for each type. A further question is how the guarantee depends on \(\tau\), the encoded type data, and any restriction on capacity values.
The paper has no named hardness result to anchor a continuum-specific-hardness question. These two algorithmic anchors are the useful ones: they are the paper’s central results and ask about the same allocation decisions, budget constraints, and online information pattern.
The main vulnerability is type diversity. The reported dataset establishes enormous request volume, but the paper does not report how many distinct complete types its requests form. In its richer model, a type includes every advertiser’s bid and every user-dependent ad length, so personalized data could make \(\tau\) nearly as large as the population. The mirror is strongest for platforms that serve repeated, standardized request cohorts; establishing that such cohorts preserve the paper’s economically relevant variation would be part of the work.
The best case against these mirrors is that both theorems are about an ordered online stream, while the programme’s central object is a society specified by type masses. The allocation at arrival \(j\) depends on the advertiser budgets left after the preceding arrivals. A distribution \(\mu\) over request types therefore does not specify the input to either online problem: two streams with the same \(\mu\) can present the same requests in different orders and give the policy different information and budget states.
That challenges Theorem 1’s proposed continuous question. To preserve its adversarial online guarantee, the mirror needs an ordered path \(\theta(u)\), not just masses \(\mu_\theta\). A finitely encoded path needs an additional description of its order—say, \(q\) blocks or change points. If arrival position is folded into a request’s complete type, repeated requests cease to be the same type; if it is kept as a separate clock, the input’s complexity is no longer captured by support size alone. The continuous problem can be formulated as online control over a path, but that makes chronology essential to the model rather than a byproduct of high multiplicity.
The obstacle is sharper for Theorem 2. Its exact user type includes a capacity, a bid from every advertiser, and user-dependent lengths for every ad. The paper does not establish that many requests share these complete vectors; its millions of queries and 82 ads establish volume, not small exact support. In the personalized setting, support could grow nearly with the number of requests. Grouping similar requests would require an approximation argument, while removing personalization retreats toward the simpler setting of Theorem 1. Either way, the paper’s online information pattern and its most detailed model resist compression to a distribution over a modest number of types.
This is a real concern about whether the proposed mirrors deliver the programme’s usual high-multiplicity object. It is not the decisive “no named result” argument: Theorems 1 and 2 are computational results, stated as competitive guarantees. Nor does it show that a continuous online model is impossible.
The strongest rescue is also plausible: standardized request cohorts arriving in a finite sequence of epochs, with budgets scaled to audience size. That yields an ordered continuous population with manageable support and a clear online question. I cannot rule out that an author would recognize it as their problem. So the negative case is strongest against the paper’s exact, personalized stream as a support-sized society; it does not honestly establish that no worthwhile continuous mirror exists in any 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.