| paper | d4-conf-sigecom-2010-0032 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(R(D)=1\) for every admissible \(D\), and \(\sup_D R(D)=1\). A deterministic policy attains the benchmark at every stopping level and is computable in time polynomial in \(m,\tau,q,L\). The bound \(H(D)\) is sharp only when \(q=1\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 6.1
statement extracted from the paper’s text layer
Given at most τ advertiser types \(t=(k_t,c_t)\), with rational masses μ_t summing to \(1\), and a finite rational distribution \(D\) over per-capita total supply \(S\), impressions arrive as infinitesimal supply and the stopping level is hidden. An online policy irrevocably advances advertiser mass through progress states \(0,\ldots,k_t\), earning \(c_t\) per unit mass that completes its campaign. The clairvoyant benchmark at supply \(s\) is \(\max\{\sum_t c_t x_t:\sum_t k_t x_t\le s,\ 0\le x_t\le μ_t\}\). For inputs with binary encoding length \(L\), characterize the minimum worst-case ratio \(\sup_{μ,D}\inf_A \mathbb{E}[\mathrm{OPT}_{μ}(S)]/\mathbb{E}[W_A(S)]\), and determine whether the cumulative-hazard lower bound from Proposition 6.1 has a tight analogue with a policy computable in time polynomial in τ, the support size of \(D\), campaign demands, and \(L\).
A continuum of advertisers with mass μ_t for each full campaign type \((k_t,c_t)\); per-capita supply arrives online with hidden stop \(S\sim D\). Policies irrevocably track partial progress by type and earn value only on completed campaigns, measured against the clairvoyant fractional-knapsack benchmark.
The proposed formulation does not specify how supply scales per capita or how partial campaign progress is tracked and made irrevocable, so its online policy model needs those details fixed.
fatal: False
Covers the online welfare bounds for knapsack valuations in Propositions 6.1 and 6.2 and the KnapsackGuess policy; it leaves the truthful unit-demand results and online-envy-free bounds in Sections 3–5 untouched.
The strongest honest mirror is the paper’s online allocation problem for knapsack valuations in Section 6. Its named results are competitive-ratio bounds, not P-versus-NP classifications, but they ask what online algorithms can achieve and give a clean continuous optimization question.
Proposition 6.1, proved in this paper (with the proof printed as Proposition A.10), says that for supply drawn from an arbitrary distribution \(D\), no algorithm can guarantee a better than \(\sum_{i=1}^{m} h_i\) approximation to optimal welfare. The construction uses \(m\) bidders: bidder \(i\) needs \(m+i\) items and has value \(1/\Pr[\ell\ge i]\). No two bidders’ demands can be met together at any possible supply level. The expected offline optimum is \(\sum_i h_i\), while an online algorithm can achieve expected welfare only \(1\) on the constructed instance.
Proposition 6.2, also proved here, supplies the matching upper bound: for every supply distribution \(D\), the paper’s KnapsackGuess algorithm achieves an approximation ratio of at most \(\sum_{i=1}^{m} h_i\). Together, these results exactly characterize the paper’s discrete worst-case ratio for that model.
Here is the continuous population version I would hand to a prover. A society has finite support \(\mathcal T=\{(k_t,c_t)\}_{t=1}^{\tau}\) and rational type masses \(\mu_t\ge 0\), with \(\sum_t\mu_t=1\). Type \(t\) means an advertiser who values a campaign at \(c_t\) if it receives at least \(k_t\) impressions, and gets no value otherwise. Interpret \(\mu_t\) as a cohort in a large population. A known rational distribution \(D\) determines the total supply, which arrives online and stops at an unannounced point \(S\). The allocator may commit any mass \(x_t\in[0,\mu_t]\) of a cohort to receive its complete campaign bundle; an individual campaign remains all-or-nothing. The clairvoyant benchmark at supply \(s\) is
\[ \mathrm{OPT}_{\mu}(s)= \max\left\{\sum_t c_t x_t: \sum_t k_t x_t\le s,\quad 0\le x_t\le\mu_t\right\}. \]
The continuous problem is to characterize and compute the best expected approximation ratio
\[ \alpha^*(\tau,D,L)= \sup_{\substack{|\operatorname{supp}(\mu)|\le\tau\\ \text{input bit length}\le L}} \ \inf_A \frac{\mathbb E_{S\sim D}[\mathrm{OPT}_{\mu}(S)]} {\mathbb E_{S\sim D,\,A}[W_{\mu}(S)]}, \]
where \(A\) sees the type masses and \(D\), allocates supply as it arrives, and cannot see the stopping point in advance. This is an online allocation problem, with no truthfulness requirement, matching the scope of Section 6. In a finite-grid version of \(D\), the paper’s candidate bound is \(\sum_i h_i\); for a smooth supply limit, the corresponding hazard quantity would naturally be an integrated hazard.
These are two sides of one concrete question: does the cumulative-hazard lower bound of Proposition 6.1 persist for a continuous society, and can a policy matching it be computed as in Proposition 6.2? I expect the algorithm-design side to be Class A for fixed or moderate \(\tau\): the offline benchmark is a small fractional knapsack LP over types, and the supply law is explicit. I would not expect the lower bound to transfer unchanged at fixed \(\tau\). The continuous version should reveal whether the obstruction depends on having many distinct bidders or instead comes from the unknown stopping point itself.
The regime is plausible in a narrow but real setting: a large ad exchange with many advertisers using a small catalogue of standardized campaign plans, each with a common impression threshold and value. The type is the full pair \((k_t,c_t)\); mass is the fraction of advertisers using that plan. The online action is which campaign cohorts to complete as impressions arrive, and the objective is expected welfare.
The soft spot is substantial: Proposition 6.1’s construction has a different demand and value for every bidder, so its support grows with the population. It does not establish a lower bound when \(N\gg\tau\), and fractional cohort selection may erase its argument. That limits the result as evidence for a continuous lower bound, but it makes the mirror worth asking: it tests exactly whether this online welfare barrier survives high multiplicity. This case covers the knapsack results in Section 6; it does not claim to mirror the paper’s truthful unit-demand results in Sections 3–5.
The only anchor is Propositions 6.1 and 6.2. They are named algorithmic results, so the “no result to mirror” objection does not settle this. But their result is a competitive ratio for online allocation: one bound applies to every algorithm, and the other gives a matching algorithm. The proposed mirror turns that into an optimal-policy question over fluid cohorts. That is coherent, but it does not yet specify a computational problem: \(D\) may be a finite rational input or a smooth law, and the policy’s representation, precision, and running-time measure are absent. Without those, \(\inf_A\) asks for the best online performance, not whether it can be computed efficiently.
There is also a scaling choice hidden in the mirror. Proposition 6.1 uses \(n\) individually specified bidders and integer supply up to \(m\). Its lower-bound construction gives bidder \(i\) a distinct demand and value, so its type support grows with the population. With a fixed number \(\tau\) of types, those bidders merge into cohorts and the proof’s one-bidder-per-supply-level construction disappears. That observation alone is not a reason to reject the mirror—the point may be to learn whether the bound survives aggregation.
To define that fixed-\(\tau\) regime, though, supply must scale with population. If there are \(N\) advertisers, each needing \(k_t\) impressions, and \(\mu_t\) is a fraction of the population, then the relevant supply is per capita, \(S_N/N\). The paper’s hazard sum \(\sum_i h_i(D)\) is over integer supply levels; under scaling, its limit depends on how the laws \(D_N\) are chosen. An integrated hazard is a candidate, not an automatic translation. And the offline fractional knapsack LP does not specify the online fluid policy: the model still needs to say how partial campaign progress is tracked and what allocations are irrevocable.
These are substantial gaps in the proposed formulation, but they are repairable. A finite rational supply grid, a stated per-capita scaling, and a finite representation for policies would make the fixed-\(\tau\) question reviewable. Standardized campaign cohorts could plausibly supply the regime, though identical full types require advertisers to share both demand and value; that is a narrower story than merely sharing a campaign plan.
So the strongest case against is that the paper’s sharp Section 6 result depends on individually calibrated bidders and an integer stopping horizon, while the proposed continuum replaces both with a new fluid online-control model whose input and complexity are not yet defined. That is a real reason to doubt this particular formulation’s readiness. It does not support the universal claim that no worthwhile mirror exists: the scaling and policy choices are tractable to specify, and the resulting fixed-support question could be worth asking. The negative case is weak at the point where it must rule out that repaired mirror.
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.