Incentive-Compatible Auction Mechanisms for Automated Bidding with Budget and ROI Constraints

This article, accepted at IJCAI 2023, studies auction design for automated bidding in online advertising where advertisers report high‑level constraints—budget and return‑on‑investment (ROI)—instead of per‑impression bids. The authors model a multi‑item auction in which advertisers aim to maximize cumulative value over many rounds while respecting private economic constraints.

Abstract: Automated bidding has become the dominant paradigm in ad auctions. Advertisers submit private constraints (budget, ROI) and the platform runs a learning‑driven bidding agent. The paper derives incentive‑compatible (DSIC) conditions for truthful reporting of these constraints and shows that any feasible allocation rule can be expressed as a family of non‑decreasing functions of the budget. Because these functions often produce irregular value‑grouping, a closed‑form design objective is difficult. To address this, the authors propose a family of personalized ranking‑score auctions that extend the generalized second‑price (GSP) mechanism, using a “key ROI” that converts budget limits into an ROI dimension.

Auction Model (Section 2): There are n advertisers competing for m items (user impressions) over time. Each advertiser i has a private type (budget B_i, ROI R_i) and a known valuation v_{i,t} for item t. The platform collects reported types (\hat B_i, \hat R_i) and selects a (randomized) allocation rule x_i(·) and payment rule p_i(·). DSIC and individual rationality (IR) are defined in the standard direct‑revelation framework.

Feasibility Region (Section 3): The authors prove that any DSIC‑IR mechanism can be represented by a set of non‑decreasing budget functions and non‑increasing ROI functions satisfying a series of lemmas (Lemma 3‑4) and Theorem 5 (necessity and sufficiency). They further characterize the payment rule that maximizes revenue while preserving DSIC‑IR (Theorem 6‑9).

Mechanism Design (Section 4): Based on the feasibility analysis, a practical mechanism is built around a personalized ranking function s_i = f(B_i, R_i, v_{i,t}). Items are allocated to the highest score; the second‑highest score determines the ROI needed to win (the “key ROI”). This key ROI is the maximum ROI that allows the advertiser to exhaust its budget, ensuring truthful reporting of the tighter constraint.

Experimental Results (Section 5): The proposed mechanisms are evaluated in i.i.d. and non‑i.i.d. advertiser environments. Compared with repeated first‑price, second‑price, and LP‑based optimal benchmarks (which are not DSIC), the new auctions achieve higher liquid welfare and revenue, approaching the theoretical optimum. The experiments also illustrate trade‑offs between fairness and revenue that can be tuned via the ranking‑function parameters.

Conclusion (Section 6): The work introduces a novel auction model for auto‑bidding with private budget and ROI constraints, derives DSIC‑IR conditions, and proposes flexible, easy‑to‑implement mechanisms validated by experiments. The study bridges mechanism design and automated bidding, offering practical designs for large‑scale ad platforms.