| paper | d4-conf-ijcai-2023-0852 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given \(n\) auction slots, a finite set \(T\) of advertiser types, rational masses \(\mu_t\) summing to \(1\), rational budget and ROI targets \((\widehat B_t,\widehat\gamma_t)\), rational piecewise-polynomial value densities \(f_t\), rival shading parameters \(\bar\beta_t>0\), and precision \(\varepsilon>0\), each auction slot is drawn independently from \(\mu\), and a type-\(s\) advertiser with value \(V_s\sim F_s\) bids \(\bar\beta_s V_s\). For each supported type \(t\), compute an interval of width at most \(\varepsilon\) containing an optimal shading parameter \(\beta_t>0\) maximizing \(U_t(\beta_t)=\mathbb E[(V_t-D_t)\mathbf 1\{\beta_tV_t\ge D_t\}]\), subject to \(\mathbb E[D_t\mathbf 1\{\beta_tV_t\ge D_t\}]\le\widehat B_t\) and \(\mathbb E[((1+\widehat\gamma_t)D_t-V_t)\mathbf 1\{\beta_tV_t\ge D_t\}]\le0\), where \(D_t\) is the maximum rival bid and has CDF \(H(z)^{n-1}\), with \(H(z)=\sum_{s\in T}\mu_sF_s(z/\bar\beta_s)\).
A pool of advertisers is a continuous society over complete campaign types \(t\), with mass \(\mu_t\) for each type’s value distribution, budget, and ROI target. Each auction draws \(n\) advertiser slots independently from that society. Given the other types’ shading parameters, choose a best-response shading parameter for each supported type by solving the paper’s expected-utility maximization with its budget and ROI constraints.
Theorem 2 does not give a bit-complexity bound for arbitrary differentiable value distributions, so a formal complexity result needs an explicit finite input encoding.
fatal: False
The mirror covers Theorem 2’s optimal shading computation, applied to every supported advertiser type. It leaves the paper’s truthfulness, equilibrium, convergence, and welfare results outside this mirror.
The strongest honest case is narrow: Theorem 2, proved in this paper, gives an algorithm for choosing a buyer’s optimal shading parameter. The paper does not offer a named hardness result or a formal complexity classification, so this is an algorithmic lead rather than a hardness mirror.
Here is a population version that keeps the buyer’s optimization problem intact. Consider a large pool of advertisers, with \(N\) advertisers divided among \(\tau\) recurring campaign types, where \(N\gg\tau\). A type \(t\) consists of a value distribution \(F_t\), a reported budget \(\widehat B_t\), and a reported ROI target \(\widehat\gamma_t\). Advertisers of the same type are interchangeable for this model; \(\mu_t\) is their fraction of the pool. For each impression, \(n\) advertisers are sampled independently from that pool. Each advertiser of type \(t\) uses shading parameter \(\beta_t\), bidding \(\beta_t v\) when its value is \(v\).
This makes the population of advertisers the continuous object. It does not count the paper’s already-continuous value distributions as continuization. Given opponents’ type-level shading policy \(\bar\beta\), their bid CDF is \(H(z)=\sum_s\mu_s F_s(z/\bar\beta_s)\), with the CDF understood as \(0\) or \(1\) outside its support. The highest rival bid \(D\) then has CDF \(H(z)^{n-1}\). Thus the population shares determine the rival-bid distribution faced by a representative advertiser of each type.
Call the resulting problem Type-Distribution Auto-Bidding Best Response. Its instance is \((n,T,\mu,(F_t,\widehat B_t,\widehat\gamma_t)_{t\in T},\bar\beta)\). For each type \(t\), choose \(\beta_t>0\) to maximize \(U_t(\beta_t)=\mathbb E[(V_t-D)\mathbf 1\{\beta_tV_t\ge D\}]\), subject to \(P_t(\beta_t)=\mathbb E[D\mathbf 1\{\beta_tV_t\ge D\}]\le\widehat B_t\) and \(\mathbb E[((1+\widehat\gamma_t)D-V_t)\mathbf 1\{\beta_tV_t\ge D\}]\le0\). The solution is the optimal parameter for each supported type; an approximate version can return an interval of width \(\varepsilon\) containing each optimum.
Theorem 2 is the anchor for this question. It says that Algorithm 1 correctly solves Program (3): maximize expected utility subject to the budget and ROI constraints. The algorithm sets \(\beta_i^1=1\) if the budget is at least \(B_H=P_i(1)\), and otherwise finds \(\beta_i^1\) by solving \(P_i(\beta)=B_i\). It sets \(\beta_i^2=1\) if the target ROI is at most \(\gamma_L=U_i(1)/P_i(1)\), and otherwise solves \(h_i(\beta)=0\), where \(h_i(\beta)=\mathbb E[((1+\gamma_i)D_i-v_i)\mathbf 1\{\beta v_i\ge D_i\}]\). It returns \(\min\{\beta_i^1,\beta_i^2\}\). The paper proves this result here, using the monotonicity properties established in Lemmas 1–5; it is not a result cited from elsewhere.
I expect the stated best-response problem to be tractable in the paper’s evaluation model: apply those threshold searches once per supported type. The computation depends on \(\tau\), not on the number \(N\) of advertisers. With rational masses and suitably represented densities—for example, rational splines satisfying the paper’s assumptions—the mixture rival distribution is constructible from the type data. A formal polynomial-time claim still needs a precise encoding and bit-complexity analysis: the paper describes binary search and calls its method efficient, but does not supply that analysis for arbitrary density inputs.
This mirror covers the paper’s optimal shading subproblem in Section 3. It does not claim to continuize the outcome space, and it does not cover the paper’s truthfulness, equilibrium, or welfare results. It naturally generates a further question: does repeatedly applying the type-wise best-response map converge to a population equilibrium, and under what conditions does the paper’s Corollary 5 extend to this type-distribution model?
The weakest point is that Theorem 2 already solves the problem for a single buyer once the rival-bid distribution is known. The population distribution \(\mu\) supplies that distribution, but the theorem itself does not show that replacing named advertisers with type masses creates new tractability. The scenario also assumes impressions draw advertisers from a large pool according to stable type shares. That is a narrower claim than a general continuum model of advertising markets. It is still a plausible mirror: the paper studies online advertisers with repeated, distributional payoffs, and its buyer-level inputs are precisely the attributes that make advertisers of one type indistinguishable for this optimization.
Theorem 2 is the only strong anchor, and it makes the negative case difficult: the paper really does prove an algorithm for a computational optimization problem. The limitation is that it proves correctness, not a running-time bound. Its inputs are arbitrary differentiable distributions, with no finite encoding specified, and its binary searches assume that the relevant integrals and threshold comparisons can be computed. So the theorem gives a useful structural characterization of a one-variable problem, but not a complexity result in the programme’s sense.
For the proposed type-population mirror, let \(H(z)=\sum_s\mu_sF_s(z/\bar\beta_s)\). With \(n\) advertisers sampled per auction, a type-\(t\) buyer faces a rival-bid CDF \(H(z)^{n-1}\). Substituting that distribution into Program (3) gives exactly the same optimization problem as in Theorem 2. The masses affect the distribution used in the integrals; they do not couple the type-wise optimizations or change their structure. Even the stronger version in which all \(N\) advertisers compete in each auction gives a maximum-bid CDF formed from powers of the type-specific bid CDFs. Each type’s best response is still the same scalar threshold calculation.
That leaves equilibrium computation as the best alternative mirror. But with finitely many types it is a finite-dimensional game over \(\tau\) shading parameters. The paper already proves equilibrium existence for its \(n\)-buyer game and gives a contraction condition for iterative best response. Aggregating identical buyers may reduce the dimension substantially, but it looks like a symmetry reduction of that game, rather than a new continuous-optimization problem. It could still be useful when the number of advertisers is much larger than the number of types; the case against it is that the proposed mirror does not expose a distinct computational obstacle or a need for the programme’s continuous-optimization tools.
I would not claim that no sensible scenario exists. Advertisers or campaigns sharing a value model, budget, and ROI target are a plausible high-multiplicity regime, and the authors could recognize it. The honest negative case is narrower: this paper’s optimal-shading result appears to transfer almost unchanged, while its equilibrium result already has the relevant finite-dimensional structure. That makes the proposed mirror look low priority, but it does not establish that no worthwhile continuous mirror exists.
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.