| paper | Vulnerabilities of Single-Round Incentive Compatibility in Auto-bidding: Theory and Evidence from ROI-Constrained Online Advertising Markets |
| authors | Juncheng Li, Pingzhong Tang |
| venue | IJCAI 2024 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
The paper clearly satisfies bit (a) through Theorems 2 and 3. The proponent states precise continuous cohort problems and gives a plausible advertising interpretation, but the opponent shows that independent high-multiplicity clones change the second-price mechanism fundamentally. Whether synchronized platform-managed cohorts count as a recognised population continuization or as a new weighted finite-player model remains genuinely undecided.
fails bit none — no continuous question survives
With independent clones, a same-type clone becomes the runner-up and makes positive-multiplier allocations violate ROI feasibility; the proposed fix instead treats each mass as one strategic bidder and ignores intra-type copies.
fatal: False
It is undecided whether a platform-managed cohort with one multiplier and cohort-level second-price pricing is a legitimate high-multiplicity version of the paper's bidder model. A formal derivation from independent cloned bidders, or an explicit author-recognisable justification for cohort bidders, would settle the grade.
The candidate mirror covers Theorems 2 and 3, including equilibrium finding and revenue or welfare selection, but leaves the empirical instability, A/B-testing, non-monotonicity, and first-price comparison results alone.
The strongest honest case is a two-anchor mirror, led by Theorem 2.
Take a platform with \(N\) advertisers or campaign lines, but only \(\tau\) materially different advertiser types. A type \(t\) specifies its complete value vector \(v_t=(v_{t,1},\ldots,v_{t,m})\), ROI target, multiplier cap, and any eligibility parameters. The mass \(\mu_t\) is the fraction of campaign demand of type \(t\), with \(N\gg \tau\). A plausible regime is a large advertising platform serving many local merchants, product campaigns, or standardized campaign templates whose conversion-value predictions and ROI targets fall into a relatively small number of buckets.
The goods remain the paper’s finite set of divisible goods; continuity enters only through the advertiser population. Let \(q_j\) be the supply of good \(j\). A type-level auto-bidder chooses one multiplier \(\alpha_t\in[1,A]\), bidding \(\alpha_t v_{t,j}\) on good \(j\). Let \(x_{t,j}\) be the mass of type \(t\) receiving good \(j\), with
\[ 0\le x_{t,j}\le \mu_t,\qquad \sum_t x_{t,j}=q_j. \]
The price \(p_j\) is the second-highest type-level bid, with the paper’s tie convention. A continuous equilibrium must satisfy, for every type receiving positive mass of a good,
\[ \alpha_t v_{t,j}\ge (1-\eta)\max_s \alpha_s v_{s,j}, \]
together with second-price payment, full allocation, approximate ROI feasibility,
\[ \sum_j x_{t,j}p_j \le (1+\delta)\sum_j x_{t,j}v_{t,j}, \]
and approximate maximal pacing,
\[ \sum_j x_{t,j}p_j \ge (1-\delta)\sum_j x_{t,j}v_{t,j} \]
whenever \(\alpha_t<A\). The exact version sets \(\eta=\delta=0\).
I would call this problem Continuum Approximate Auto-Bidding Equilibrium: given rational \(\mu\), the type value vectors, good supplies, \(A\), and fixed constants \(\eta,\delta\), output \((\alpha,x,p)\) satisfying these conditions. This is recognisably the paper’s problem: it retains multiplicative pacing, ROI-constrained value maximization, second-price externality, and the same equilibrium concept. It is not merely a fractional-allocation problem; the continuous object is the population distribution \(\mu\).
This directly mirrors Theorem 2, which states: “It is PPAD-hard to find an \((\eta,\delta)\)-approximate auto-bidding equilibrium for some constant \(\eta,\delta>0\).” That theorem is proved in this paper, in Appendix G; the paper cites earlier work for the underlying PPAD circuit machinery, but not for this market result.
This is my lead anchor. I would expect hardness to transfer, placing the mirror in Class B. The reduction associates a bidder with each continuous NAND gate and uses that bidder’s multiplier to encode the gate value. In the mirror, each gate becomes a population type with a positive mass, and the associated goods and allocations are scaled by that mass. The circuit’s combinatorics live in the network of valuation profiles and runner-up prices, not in the number of individually named advertisers. One can therefore have arbitrarily many campaign instances per type while preserving the same hard gate structure. The continuous population does not dissolve the source of hardness.
The second anchor is Theorem 3, also proved in this paper, in Appendix H: “It is APX-hard to find the optimal revenue or welfare over all auto-bidding equilibria.”
The corresponding problem is Continuum Optimal-Equilibrium Selection. It has the same instance as above, but asks for an equilibrium maximizing either
\[ R(\alpha,x,p)=\sum_j q_jp_j \]
or
\[ W(\alpha,x)=\sum_{t,j}x_{t,j}v_{t,j}. \]
A finite-precision version would ask for an \(\varepsilon\)-optimal equilibrium, or for an equilibrium achieving a specified fraction of the optimum. This is a natural continuous question because revenue and welfare are already aggregate population quantities. The equilibrium set may be large, and the platform is choosing among equilibria rather than merely finding one.
I would again expect hardness to transfer, rather than a continuum-specific obstruction. The paper’s reduction uses equilibrium multiplicity to encode discrete choices: the symmetric two-bidder construction in Table 3 has asymmetric equilibria that act like \(0\)-\(1\) decisions, while bidders who never win some goods still set prices elsewhere. Two type cohorts with equal masses can reproduce precisely this phenomenon. The hard choices concern equilibrium selection and cross-market externalities, not population granularity.
The high-multiplicity interpretation is plausible when the platform manages standardized cohorts through shared auto-bidding policies. For a rational distribution \(\mu\), a finite realization has \(N\mu_t\) campaign lines of type \(t\); aggregate allocations and objectives are then normalized sums over those lines. Conversely, the continuous instance is the high-multiplicity representation of that market. The relevant limit is not “every advertising market is homogeneous,” but that some large platforms contain millions of campaigns drawn from a much smaller set of operationally meaningful types.
This mirror covers the paper’s computational results in Section 3, especially Theorems 2 and 3. It does not claim to continuize the empirical instability results, A/B-testing discussion, or first-price comparison. Nor does it rely on the fact that the paper already allows divisible goods: that is inherited outcome-space divisibility, whereas \(\mu\) is the newly continuous population object.
The weakest point is the treatment of identical bidders in a second-price auction. If many independent advertisers have exactly the same type and independently submit the same bid, one clone can become another clone’s runner-up, changing the payment rule and potentially collapsing the pacing dynamics. My mirror therefore uses a specific but plausible regime: each type is a cohort managed by one shared platform auto-bidder, so \(\alpha_t\) is a cohort action rather than a collection of independently chosen multipliers. If a referee insists that high multiplicity must mean independent cloned bidders, this particular mirror needs modification—perhaps a distribution over within-type multipliers or a tie-breaking perturbation. That is a genuine vulnerability, but it does not eliminate the broader mirror: platform-managed campaign cohorts are a sensible high-multiplicity object, and under that regime both named hardness results remain computationally meaningful continuous questions.
The two anchors are the only serious candidates, but both rely on an aggregation that is not a limit of the paper’s auction model. The obstruction is not that the paper already has divisible goods; it is that second-price payment is an order statistic over individual bidders, and order statistics do not survive this quotient by type.
Suppose \(r\ge 2\) independent bidders have the same type \(t\), value vector \(v_t\), and multiplier \(\alpha_t\). If a copy receives positive mass of good \(j\), another copy of the same type is still present in the runner-up maximum. Hence
\[ p_j=\max_{k\ne i}\alpha_kv_{k,j} \ge \alpha_t v_{t,j}. \]
This is true even if the identical bidders split the good fractionally. Consequently, for every such bidder,
\[ \sum_j x_{i,j}p_j \ge \alpha_t\sum_j x_{i,j}v_{t,j}. \]
With the paper’s ROI constraint and \(\alpha_t\ge 1\), a positive allocation to an identical clone at \(\alpha_t>1\) is therefore impossible. In the original construction, by contrast, a bidder with multiplier greater than one can win while a different bidder determines the price. Replication turns the clone itself into the runner-up and removes precisely the price externality on which the circuit gadget depends.
Allowing clones to choose different multipliers does not repair this cleanly. Only the highest-multiplier clone can win a good. A unique highest clone has vanishing mass in the continuum limit; a positive-mass set of highest clones recreates the same self-runner-up problem. To describe the resulting market one needs an endogenous distribution over \((t,\alpha)\), not merely the population vector \(\mu\). That is an infinite-dimensional equilibrium object, and the paper’s finite-dimensional auto-bidding equilibrium is no longer the problem being mirrored.
This defeats the proposed mirror of Theorem 2. Its reduction needs one independently adjustable multiplier per circuit gate and uses the resulting runner-up prices to transmit gate values. The proponent’s “one multiplier per type” works only by forcing all copies of a type to coordinate as one bidder. But then the model has added a collective-action constraint absent from the paper. Moreover, the proposed “second-highest type-level bid” explicitly ignores identical copies when computing the price. That is not a tie-breaking convention for the paper’s auction; it is a different auction rule in which an entire cohort is treated as one bidder.
That cohort model may be coherent, but it is a finite weighted market with \(\tau\) strategic cohort players and capacities \(\mu_t\). The population has not become the strategic object: one has replaced many advertisers by a single decision-maker controlling a mass of campaign demand. The masses can be represented as bidder capacities or scaled goods. The PPAD circuit can survive because one has retained one strategic cohort per gate, not because the paper admits a genuine high-multiplicity limit.
The same problem is sharper for Theorem 3. Its equilibrium-selection reduction relies on the two-bidder gadget in Table 3: one bidder’s multiplier can make it a price setter for goods it never wins. With many identical copies, a winning copy’s identical clone becomes a price setter, so the gadget’s payment structure and its asymmetric equilibria change. With cohort-level pricing, the gadget returns, but only because the cohorts are declared to be single bidders. The resulting APX-hard problem may be interesting, yet it is a weighted finite-player equilibrium-selection problem rather than a continuous-population version of the paper’s problem.
Thus every repair falls into one of three categories: independent clones, where second-price pricing degenerates; synchronized cohorts, which introduce a new collective bidder model; or distributions over within-type multipliers, which produce a new infinite-dimensional anonymous game. None gives a faithful, finite, high-multiplicity mirror of either named theorem.
That is the strongest negative case, but it is not airtight. If ChoCo is willing to treat platform-managed campaign cohorts as genuine single strategic agents and to define prices by distinct cohorts, the resulting model is plausible and computationally meaningful. I would therefore not honestly claim that no worthwhile continuous auction mirror can exist. The defensible conclusion is narrower: the proponent has not yet exhibited a continuous mirror of Theorems 2 or 3; their construction changes the strategic population precisely where the paper’s computational results depend on individual identity.
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.