Truthful Auctions for Automated Bidding in Online Advertising

1 Introduction

With the success of machine learning in online advertising [Zhang et al., 2014; Gharibshah and Zhu, 2021], advertisers turned to adopting automated bidding (auto-bidding) tools instead of bidding manually, bringing significant changes to the interaction between advertisers and online platforms [Google Ads, 2021; Facebook Ads, 2021]. In auto-bidding services, advertisers submit their high-level optimization objectives and constraints to the platform, and then the bidding agents, powered by machine learning algorithms, make detailed bidding decisions in each of ad auctions on behalf of the advertisers. With the help of automated bidding tools, advertisers can optimize their overall advertising objectives with respect to their financial constraints in a high-level way.

∗Zhenzhen Zheng is the corresponding author.

Under automated bidding, we revisit a fundamental problem in auction theory: whether the conventional auction model, where advertisers have private values for items (i.e., ad impressions) and conduct corresponding strategic bidding for each single auction, is still appropriate for the new advertising paradigm. As the platform can access historical data about the interactions between advertisers and users, we can estimate the potential actions of users (such as clicks and conversions), which can be regarded as public values of items for advertisers. In auto-bidding, the private information from advertisers are actually their constraints for the whole advertising campaign. These features require a new ad auction model to incentivize advertisers to truthfully reveal the high-level private constraints given the values of items are public.

In this work, we consider a new automated bidding auction model, where advertisers submit budget as well as return on investment (ROI) requirement as their (private) constraints, and aim to maximize the cumulative values of winning impressions from multiple auctions during a certain period. We analyse the truthfulness conditions with respect to the private constraints of budget and ROI. Remarkably, we show that any truthful auction mechanism for this multi-dimensional setting could be equivalently represented by a series of nondecreasing functions with budget as input. When these nondecreasing functions are realized to derive the corresponding auction mechanism, the truthful conditions of budget and ROI introduce a new value grouping phenomenon: different budget-ROI types are grouped to share the same cumulative value, and the grouping pattern is determined by a threshold ROI function (transformed from the above non-decreasing function). As the threshold ROI functions are not constrained in monotonicity, the grouping shape of budget-ROI types is generally irregular, making it difficult to obtain the closedform expression of grouping types and then the auction optimization objectives, such as revenue and social welfare.

Facing these design difficulties, we propose a family of ad auctions with personalized rank scores to optimize various design objectives. Our auction adopts rank scores as the criteria to determine item allocations, which shares the similar ideas with Generalized Second-Price (GSP) auction [Edelman et al., 2007]. In guaranteeing truthfulness for the private constraints, we design critical ROI to be the largest ROI that can win the most items without breaking the budget constraint. It equivalently transforms budget to the same dimension as ROI, thus allowing us to find a tight constraint limits the bidder from getting extra utilities and utilize this tight constraint to prevent misreporting. We conduct extensive experiments to evaluate the performances of the proposed auction mechanism under various auto-bidding settings. The evaluation results demonstrate that the designed truthful auction can generally achieve more than 90% performance (in terms of revenue and social welfare) of the optimal baselines without the consideration of truthfulness. The main contributions can be summarized as follows:

• We consider the unique features within the interaction between advertisers and online platforms in the context of automated bidding. Based on these features, we formulate a new auto-bidding auction model, where value-maximizing bidders have high-level constraints as private information and the values of items are public.
• We investigate truthfulness conditions of two-dimensional private constraints, budget and ROI, under public value setting. We provide full characterizations for the feasible space of allocation and payment for truthful auctions.
• Based on the derived truthfulness conditions, we design a family of truthful ad auction mechanisms for automated bidding. With the newly designed rank score functions, the proposed ad auction is simple and flexible to be adapted into various auto-bidding settings with different optimization goals such as revenue and social welfare.
• We evaluate our proposed auction mechanisms with various experimental settings, and the empirical results validate the effectiveness of the proposed auctions regarding its performances in terms of social welfare and revenue.

2 Preliminaries

In this section, we first motivate the considered auction design problem by the online advertising system with automated bidding services, and afterwards propose the formal auction model based on the features of automated bidding.

2.1 Online Advertising System

The working process of the online advertising auction system is illustrated in Figure 1. From an advertiser's perspective, it can be described as follows:

1. The advertiser sets the bidding configuration in autobidding interface: chooses optimization objectives (e.g., maximizing clicks or conversions) and sets cost constraints (e.g., budget per day, targeted return on investment (ROI) and maximum cost per click). The advertiser requires her realized ROI, defined as the ratio of her gained value and payment, to be higher than her targeted ROI.
2. Based on the advertiser's configuration, an auto-bidding agent represents the advertisers to make bid decisions in multiple auctions. When each user impression comes, the autobidding agents attend an ad auction to compete for the ad display opportunities.
3. The auto-bidding agent adopts data-driven algorithms to predict the value (click through rate or conversion rate) of the incoming user impression, and bid for each impression while taking the cost constraints into consideration.
4. During the multiple auctions, the advertiser can check the cumulative auction outcomes, including spent budget, received impressions, clicks, conversions and the average costs. The advertisers can further adjust their auto-bidding settings in the interface to achieve their own advertising objectives.

From the above interaction between advertisers and the platform/auctioneer, we summarize three new features about the online advertising with auto-bidding services. First, advertisers only report high-level optimization objectives and constraints in the bidding configurations for multiple auctions, but not the fine-grained bid for each auction. Second, advertisers only evaluate cumulative long-term performances and costs of multiple auctions, instead of the outcome of each individual auction. Third, since the online platform can access all the data produced in advertising, it is reasonable to claim the monetary value of an incoming impression to a specific advertiser can be calculated exactly. As the behavior patterns of advertisers and the online platform change distinctly in automated bidding, we need to investigate the mechanism design whose formats align with these new features.

2.2 AuctionModel

Based on the motivations of the above online advertising system with auto-bidding, we propose the formal auction model considered in this work. There are n advertisers competing for m items (user impressions) coming in sequence during a time period with m time slots, where only one item would appear in each time slot. 1 The advertisers are value-maximizing bidders [Fadaei and Bichler, 2016; Balseiro et al., 2022; Mehta, 2022], who care about the cumulative value of her allocated impressions across all the time slots when the payment is within their financial constraints. Each advertiser i has budget (Bi ≥ 0) and ROI (Ri > 0) constraints, which are private information and are also called as type ti = (Bi,Ri) in mechanism design literature. We denote the type profile of all the advertisers as t = (ti)ni=1 and the space of the type profile as T = ∏ni=1 Ti with t ∈ T and Ti = Bi ×Ri. We denote the reported type of the other bidders except bidder i as t-i = (t1, . . . , ti-1, ti+1, . . . , tn) and T-i = ∏nk̸=i Tk. We assume advertisers' valuations on items are public information to the platform. We use vi,j > 0 to represent the advertiser i's valuation on item j.

1 We would use advertisers with bidders, and items with impressions interchangeably throughout the work.

After collecting the budget and ROI of all the bidders, the online platform employs some auction mechanism (A, P) to decide ad allocations and payments, where A denote a (randomized) allocation rule A : T → [0, 1]n×m and P denote a (randomized) payment rule P : T → Rn . Specifically, for a reported type profile t′ ∈ T , the probability of bidder i being allocated item j is denoted by ai,j(t′ ) and the expected payment of bidder i is denoted by pi(t′ ). For any item j ∈ [m], the allocation constraint is ∑ni=1 ai,j(t′ ) ≤ 1. Bidder i's cumulative value in these auctions is

and her realized ROI is ROIi(t′ ) := vi(t′ )/pi(t′ ) (considered as +∞ if pi(t′ ) = 0).

The utility for a bidder with budget and ROI constraints and true type ti when reporting t′i is defined as

where the type profile t′ = (t′i , t′-i ).

In this work, we focus on designing truthful auction mechanisms satisfying incentive compatible (IC) and individual rationality (IR) conditions for budget and ROI, which is a two-dimensional mechanism design problem. Various multidimensional mechanism design problems are shown to be difficult in both analytical and computational aspects [Pavlov, 2011; Chen et al., 2014; Daskalakis, 2015]. In particular, we consider dominant-strategy incentive compatible (DSIC) and individual rationality (IR) direct-revelation mechanisms.

Definition 2.1. An auction mechanism is dominant strategy incentive compatible (DSIC) if ∀i ∈ [n], ti, t′i ∈ Ti, t-i ∈ T-i: ui(ti, (ti, t-i)) ≥ ui(ti, (t′i , t-i)).

Definition 2.2. An auction mechanism is individual rationality (IR) if ∀t ∈ T , i ∈ [n]: pi(t) ≤ Bi and ROIi(t) ≥ Ri.

The online platform typically has some objectives to maximize. Two common design objectives are revenue and social welfare. Revenue is defined as the sum of payment from bidders, i.e., ∑i pi(t). For social welfare, we need a synonymous metric, liquid welfare, defined as the maximum revenue that can be extracted from bidders without breaking IR constraints, to incorporate the existence of financial constraints [Azar et al., 2017; Aggarwal et al., 2019]. In our context, liquid welfare can be defined as

3 Characterization of Truthfulness

3.1 Conditions for Truthfulness

In this section, we investigate the truthfulness conditions for this multi-dimensional mechanism design problem. Due to the limitation of space, we present the detailed proofs of our results in the full version of this paper [Xing et al., 2023].

To provide an intuition about the differences between auction models with private constraint and private valuation, we start from the analysis of one private constraint. To satisfy the IC property on budget, we need to guarantee the bidders for not obtaining a higher utility by reporting a smaller or larger budget. As reporting a smaller budget will not lead a bidder to break her original budget constraint, the gained utility should decrease for reducing the budget. For the bidder misreporting a larger budget and obtaining higher values, we need to charge the bidder to break her original budget constraint, resulting in negative infinite utility to prevent misreporting.

Theorem 3.1. An auction mechanism is DSIC on budget B only if ∀i ∈ [n], R ∈ Ri, t-i ∈ T-i:

(1) vi ((B, R), t-i) is non-decreasing in B;

We can form a similar statement for ROI by showing that there is no incentive for a bidder to misreport her ROI.

Theorem3.2. An auction mechanism is DSIC on ROI R only if ∀i ∈ [n], B ∈ Bi, t-i ∈ T-i:

(1) vi ((B, R), t-i) is non-increasing in R;

Although the monotone properties required by conditions (1) in Theorem 3.1 and 3.2 seem similar to the truthfulness conditions for quasi-linear bidder with private valuations, e.g., Myerson's Lemma [Myerson, 1981], conditions (2) reveal their basic differences: assigning a payment to break at least one constraint (lead to negative infinite utility) is indispensable to prevent misreporting for private constraints.

Theorem 3.1 and 3.2 naturally provide necessary conditions on the DSIC of two-dimensional type (B,R). The following result shows that these conditions also provide the sufficient conditions. That is, if a bidder cannot obtain higher utility through misreporting one of her constraints, misreporting the two constraints can also not obtain higher utility.

Theorem3.3. An auctionmechanism is DSIC on both budget and ROI if and only if it satisfies Theorem 3.1 and 3.2.

Theorem 3.3 is proved through showing none of the misreporting may bring the bidder higher utility when conditions in Theorem 3.1 and 3.2 hold, which relies on the mathematical relationship between payment and ROI. In Theorem 3.3, the truthful conditions in Theorem 3.1 for budget appear to be independent with the truthful conditions in Theorem 3.2 for ROI. Nevertheless, the payment term actually appear in both the conditions (recall ROI = v/p), i.e., we have to use the same payment scheme to satisfy these two sets of conditions. In order to step toward the full characterization of truthfulness, we need to further analyse how payment is influenced and constrained by financial constraints and allocation.

To facilitate our discussion, we define an allocation rule A to be feasible if there exists a payment rule P such that the mechanism (A,P) is truthful. The set of feasible allocation rule is the space we can search for truthful auctions. Although there may exist multiple payment rules that constitute a truthful auction for a feasible allocation rule A, the following theorem allows us to focus on the maximum payment rule.

Theorem 3.4. For a feasible allocation rule A, assigning

for ∀i ∈ [n], (Bi,Ri) ∈ Ti, t-i ∈ T-i constitutes a truthful auction mechanism.

Theorem 3.4 naturally holds because each type is charged the maximum payment under her financial constraints. If some other payment could constitute a truthful auction with A, then improving the payment to this maximum amount would not break the originally held conditions (2) in Theorem 3.1 and Theorem 3.2. By Theorem 3.4, given any feasible allocation rule A, we could find a corresponding payment rule to constitute a truthful auction. As the bidders do not evaluate detailed allocation results of each individual auction, searching for the truthful allocation rule is equal to designing cumulative value functions vi((Bi, Ri), t-i) that can be realized. Thus, we could use the corresponding cumulative value function to represent a feasible allocation rule.

Our next step is to further shrink the consideration space of comparison in conditions of truthfulness. Previous conditions in Theorem 3.3 include comparisons between any two type sharing the same budget or ROI, e.g., comparing any (B,R) and (B′ ,R) in Theorem 3.1, which is still a large consideration space and leads to difficulties in finding the cumulative value functions. To enable analysis between "neighbouring" types, for any allocation rule A and its cumulative value function v(t), we assume the limits limB→Bi vi ((B,Ri), t-i) and limR→R+ i vi ((Bi, R), t-i) exist for any t ∈ T , i ∈ [n]. Through considering these infinitely close types and substituting the payment terms in Theorem 3.3 by the payment rule (Eq.2), conditions that constrain the payment or realized ROI of misreporting another type to break the original constraints could be converted to conditions regarding cumulative value of the type itself.

Theorem 3.5. An allocation rule A can derive a truthful auction if and only if ∀t ∈ T , i ∈ [n]:

(1) The cumulative value vi ((B,R), t-i) is non-decreasing

in B for R = Ri and non-increasing in R for B = Bi; (2) If vi ((Bi, Ri), t-i) > limB→Bi vi ((B,Ri), t-i), then

3.2 Structures of Feasible Allocation Rule

Theorem 3.5 fully characterizes the conditions of a feasible allocation rule. In this subsection, we would further exploit the structures of feasible allocation rule indicated by Theorem 3.5 to provide more instructions on truthful auction design.

By Theorem 3.5, the relation between cumulative value v and the term B × R strictly characterizes whether this type shares the same cumulative value with its neighbouring types, which allows us to further clearly represent the structure of v. Fixing the budget, with the decrease of ROI, the cumulative value assigned to the type should be increasing, notice the term B × R decreases along with R; however, condition (3) in Theorem 3.5 requires that if the cumulative value strictly increases in this process, then its value should not exceed B×R. Thus, there must exist some threshold ROI, such that the increasing cumulative value intersects with the decreasing B ×R, and the cumulative value could not increase anymore. Based on the above observation, we define

if the considered set is non-empty and bounded, or otherwise be 0. It turns out that the cumulative value assigned to this threshold ROI is exactly B × R.

Theorem 3.6. ∀i ∈ [n], t-i ∈ T-i, Bi ∈ Bi, Ri ≤ thri(Bi, t-i):

We could then combine different budgets together to obtain the complete characterization of feasible allocation in the two-dimensional type space. Since all types above the threshold ROI has cumulative value v < B ×R by the definition of thr function, they could not satisfy the condition (2) in Theorem 3.5, and thus are forced to have the same cumulative value with their neighbouring types with a smaller budget.

Theorem 3.7. ∀i ∈ [n], t-i ∈ T-i, Bi ∈ Bi\{0}, Ri > thri(Bi, t-i):

Since the types below (Theorem 3.6) and above (Theorem 3.7) the ROI threshold have both been fully described, the cumulative values on the entire type space could be fully defined if thri(Bi, t-i) is given and t-i is fixed. We provide an example in Figure 2 to illustrate these characterizations. For types below the threshold ROI curve and have the same budget B (i.e., types lie in the same vertical line), they share the same cumulative value thri(B)×B. For each type above the curve, its cumulative value is equal to that of its neighbouring type with a smaller budget until it reaches some type on the threshold ROI curve. This is equivalent to search horizontally to the left to find the closest type on its corresponding ROI threshold, where all the types along this horizontal search share the same cumulative value.

We have shown that each feasible two-dimensional cumulative value function (whose input is (B,R)) for a single bidder could be represented by a one-dimensional threshold ROI function (whose input is B) when other bidders' profile is fixed, but it is unknown what kinds of one-dimensional threshold ROI functions could represent a feasible cumulative value function. By condition (1) in Theorem 3.5, the cumulative value when R is infinitely close to 0 should be increasing for different B, which indicates thri(B, t-i) × B needs to be non-decreasing in B. Since every cumulative value function mapped from a non-decreasing thri(B, t-i) × B satisfies Theorem 3.5, this becomes the only requirement for a feasible thri function. For convenience in notations, we denote gi(Bi, t-i) = thri(Bi, t-i) × Bi. We denote V as the space of feasible cumulative value function when i and t-i are fixed, i.e., vi : Ti → R+, and denote G as the space of non-decreasing function g : R+ → R+ with g(0) = 0.

Corollary 3.8. There exists a bijective map m : G → V with

where we define sup ∅ = 0.

In other words, given any one-dimensional non-decreasing function with g(0) = 0, we could transform it to a feasible 2 cumulative value function by the above mapping process.

4 Truthful Auction Design

The derived structure of feasible allocation rules give rise to a value grouping phenomenon. Viewing the above process of finding the cumulative value of a certain type given threshold ROI curve in a reverse way, every type on the threshold ROI curve shares the same cumulative value with two groups of types: the types vertically below it, as well as the types locate horizontally right to it and above its corresponding threshold ROI, as shown in Figure 2. This intricate value grouping phenomenon are enforced by the truthful conditions instead of the optimization requirement. As we can observe in Figure 2, since the horizontal search terminates when meeting a type on the threshold ROI curve, the grouping shape is determined by the relative rank of thri(Bi, t-i) for different Bi. However, though thri(Bi, t-i) is required to keep g(B) non-decreasing, it is not required to be monotone itself, which leads the terminate of horizontal search and the grouping shapes to be irregular. This also brings difficulties in deriving general closed-form conditions for the group of Input: Bidder's reported type (Bi,Ri), and non-increasing rank score functions fi,j .

2 Our feasibility is with respective to truthfulness, and does not specify how to realize the allocations from detailed items.

Algorithm 1: A Family of Simple Truthful Auctions

Output: Bidder's allocated items Ai and payment pi. 1 Initialize Ai = {} for i ∈ [n]; 2 Compute virtual bids bi,j ← vi,j × fi,j(Ri); 3 for each item j ∈ [m] do 4 Find bidder i0 with the highest virtual bid bi0,j; 5 Record the second highest bid cj ←maxi̸=i0 bi,j; 6 Add item j into Ai0 and set ai0,j = 1; 7 for each bidder i ∈ [n] do 8 Compute ROI ri,j = f -1 i,j ( cj vi,j ) required for winning the item j ∈ Ai; 9 Find a largest Rc i ∈ Ri s.t. ∑j∈Ai I (Rc i ≤ ri,j) × vi,j Rc i ≥ Bi, and let d ← the difference between left-hand side and right-hand side of the above inequality; 10 if d > 0 then 11 Find the items j ′ with ri,j ′ = Rc i , and remove parts of these items with value d/Rc i ; 12 if Ri ≤ Rc i then 13 Remove the items with ri,j < Rc i fromAi; 14 pi ←min (∑j∈Ai vi,j·ai,j Ri , Bi) ; 15 return (Ai, pi) for i ∈ [n].

types to share the same allocation. Furthermore, although the cumulative values of the grouping types are forced to be the same, their payment are calculated by Theorem 3.4, leading to varying payments between grouping types and the nonlinear revenue with respective to the threshold ROI.

The above characteristics of value grouping phenomenon, i.e., irregularity in grouping shape and non-linear payment, make any analytical or mathematical programming approach difficult to adopt. To reach feasible and implementable auction design, we propose a family of simple truthful auctions based on newly designed rank score functions.

The detailed auction mechanism is presented in Algorithm 1. For each item, bidders are ranked based on their virtual bids bi,j, which is defined as vi,j multiplying a rank score fi,j (Ri) with some pre-defined non-increasing function fi,j (Line 2). The items are then temporarily allocated to each bidder with the highest virtual bids (Line 3-6). After the candidate allocation set Ai for each bidder i has been determined, we compute the the corresponding ROI requirement ri,j for the bidder i to rank the first in item j ∈ Ai, i.e., bidder i needs to report Ri ≤ ri,j in order to maintain ranked first for item j (Line 8). The critical ROI in Line 9 is our key design to guarantee truthfulness, which computes the largest ROI a bidder could report to win enough items in Ai and spend out her budget. Intuitively, critical ROI simulates the best-response ROI of the bidder given her budget constraint, which does not involve and thus keeps independent of her true ROI constraint. We naturally utilize this critical ROI, which transforms the budget to the same dimension of ROI, as the threshold ROI

function and design the remaining parts based on the truthful conditions in Section 3. Line 10-11 are designed to guarantee the value of remaining items in Ai would exactly equal to the budget of the bidder times the computed critical ROI (Theorem 3.6). Line 12-13 are designed to guarantee the types with ROI larger than the corresponding critical ROI would be allocated based on their reported ROI (Theorem 3.7) and get all items with ri,j ≥ Ri. Line 14 determines the payment for each bidder based on Theorem 3.4. Due to its low time complexity, Algorithm 1 has good implementation scalability.

Theorem 4.1. If the pre-determined functions fi,j(R) are non-increasing with R, then the auction mechanism corresponding to Algorithm 1 is truthful.

Our proof is conducted through figuring out and verifying the corresponding g(B) and threshold ROI function of Algorithm 1. We can design personalized fi,j(R) for bidders and items according to the auction objective and prior knowledge before the advertising campaign, such as the type distribution of bidders and the information of incoming items.

5 Experiments

In this section, we conduct experiments with synthetic data to validate the performance of our proposed auctions.

5.1 Experimental Setup

There are two sets of experiments with i.i.d. and non-i.i.d. bidders, respectively. We vary the number of bidders and items to simulate the changes in demand and supply. The presented results are averaged by 50 runs. We choose distribution parameters based on the common fluctuations in advertising markets, and normalize the lower bound of vi,j .

Symmetric bidders Bidders are symmetric with vi,j ∼ U[1, 4], Bi ∼ U[40, 80] and Ri ∼ U[1, 3], where U[a, b] is the uniform distribution within the range [a, b]. 3

Mixed bidders There are low and high distributions for vi,j, Bi and Ri as bidders' possible types. Specifically, vi,j ∼ U[1, 2] or vi,j ∼ U[2, 3], Bi ∼ U[20, 40] or Bi ∼ U[80, 100], and Ri ∼ U[1, 2] or Ri ∼ U[2, 3]. Combinations of these categories result in 8 groups of bidders.

Baseline Auctions Since no existing mechanism guarantees the IC properties of both budget and ROI, we consider common repeated auction formats: first-price and second-price auctions. Due to their non-truthfulness (see full version of this paper), we involve misreporting for these auctions.

• Repeated first-price and second-price auctions: The auctioneer holds first-price (second-price) auctions for every single item, where bidder i bids vi,j/Ri for item j. The auctioneer allocates the item to the highest ranking bidder who has remaining budget to afford, and charge the first-price (secondprice) payment. We simulate bidders' misreporting behaviors by the classical best-response dynamics with the true profile as starting points. In repeated first-price (second-price) auctions, the bidders have no incentive to misreport their budget. We calculate the best response ROI as the smallest ROI that achieves the highest utility in historical auctions.

3 We have tested several other parameters under uniform distribution, and the trends of results are the same.

• Non-truthful Optimal Baseline: The optimal offline revenue could be computed through linear programming, where we set each bidder i's payment to item j as exactly vi,j ×ai,j/Ri, and her total payment is constrained to not exceed Bi.

Evaluation Metrics We consider revenue and liquid welfare as the optimization goal. Since the payment formula (Eq.2) in Theorem 3.4 aligns with the definition of liquid welfare in equation (Eq.1) when no bidder receives negative infinite utility, the metrics of revenue and liquid welfare would be the same for truthful auctions, and we will thus only report revenue in our results. Besides, as advertisers may have fluctuating auction performances across time slots, fairness should also be considered in order to preserve bidders' willingness to attend the auctions. Using liquid welfare to substitute the traditional valuation function [Bez´akov´a and Dani, 2005; Chakrabarty et al., 2009], fairness is defined as

Rank Score Function We adopt rank scores in the form fi,j(R) = αi,j × e-βR, where αi,j is drawn from a rectified normal distribution N(µi, σ2 i ), and β, µi, σi are pre-set parameters. In f(R), β is used to adjust the impact of ROI on equivalent bids, and α maintains the rank scores of various bidders in a comparable range. Since items may be discarded when some bidders win excessive items (Line 13 in Algorithm 1), in order to avoid loss in welfare and revenue, we should give other bidders non-trivial winning opportunities when the supply is sufficient, which is provided by the randomness in α ∼ N(µi, σ2 i ). For each automated bidding environment, we set rank score function parameters to be the same for bidders following the same distribution, and choose the parameters with better revenue in this environment.

5.2 Experimental Results

Symmetric bidders The revenue of our truthful auction (referred as DSIC) and the baseline auctions with different number of bidders is reported in Figure 3a, and revenue when number of items changes is reported in Figure 3b. Our truthful auction achieves better revenue than first-price and second-price auctions, and generally achieves more than 90% revenue of the near optimal baseline. Remarkably, first-price auctions displays evident decrease in revenue when the items are excessive, which also leads to decreases in fairness (Figure 3c). This is because the bidders exceedingly increase their reported ROI when facing some unsold items with low prices, leading all their payment to decrease proportionally.

In Figure 3c, we report the fairness results under different number of items a fixed number of 40 bidders as in Figure 3b. As designed in the rank score function, our auction does not allocate excessive items to a certain bidder to avoid waste of items, and thus achieves better fairness then the optimal baseline when the number of items is in the range of 600 to 1200. When items are in shortage (200/400 items in Figure 3c), our truthful auction harms the fairness to some extent due to the pursuit of revenue. We can control the tradeoff between fairness and revenue with different rank score functions through the parameter β. Figure 3d reports a set of revenue and fairness performances with different β in the same setting as 400

items in Figure 3c. To achieve higher revenue, it is inevitable to have discriminating allocation among different bidders and harms the fairness when items are not abundant.

Mixed bidders Instead of presenting similar trends, we demonstrate the importance of choosing appropriate rank score functions in non-i.i.d. settings. We choose three groups of rank score functions respectively with good performance in three typical settings: 40 mixed bidders with 200/1000/1600 items, and test their performances in the other two settings. The results are presented in Figure 4, where DSIC-n represents the truthful auction with rank score functions performing well in the Setting n. The DSIC-n mechanism only perform well in Setting n, and the reason should come from the distinct allocation approaches needed to achieve high revenue for different number of items. For example, to achieve high revenue when items are in shortage (Setting 1), DSIC-1 auction allocates most items to the bidders with high value and low ROI, leading to allocating excessive items to these bidders and neglecting other bidders in Setting 2 and 3.

6 RelatedWork

Due to the unique features compared to traditional ad auctions, auction design and game theoretical analysis for automated bidding come into researchers' view in recent years. Our work could be classified as considering the incentive of bidders when setting automated bidding parameters. Under this topic, [Li et al., 2020] provided distributed bidding algorithms for IC issues assuming public values and private ROI. [Balseiro et al., 2021] studied the optimal mechanism design for bidders with ROI constraint under different information structure. [Balseiro et al., 2022] considered the mechanism design with private ROI constraint and public budget, and derived the optimal auction for all the two-bidder cases and some specific multi-bidder cases.

Another closely relevant line of work is mechanism design for financially-constrained quasi-linear bidders. Since [Laffont and Robert, 1996], intensive research has been conducted for bidders with budget constraint [Borgs et al., 2005; Bhattacharya et al., 2010; Dobzinski et al., 2008; Pai and Vohra, 2014]. [Szymanski and Lee, 2006] analysed the impact of ROI constraints on bidding and revenue of several common auction forms, and [Golrezaei et al., 2021] firstly considered auction design for bidders with ROI constraints. Distinct from the above work 4 , we consider both budget and ROI as private constraints for value-maximizing bidders, which fits the real automated bidding and reveals the complex value grouping phenomenon for the first time.

7 Conclusion

In this work, we have considered truthful auto-bidding auction design for bidders with private budget and ROI constraints across multiple impressions, while the values of impressions are public to the auctioneer. We have characterized the truthfulness conditions in this new auto-bidding auction model, which involves irregular grouping constraints on bidders' cumulative utilities. We have proposed a series of simple truthful auction mechanisms with flexible rank score functions as a solution to this automated bidding auction design problem. The experimental results validate the performances and flexibility of the proposed auction mechanisms.

Acknowledgements

This work was supported in part by National Key R&D Program of China No. 2018AAA0100900, in part by China NSF grant No. 62132018, U2268204, 62272307, 61902248, 61972254, 61972252, 62025204, 62072303, in part by Shanghai Science and Technology fund 20PJ1407900, and in part by Alibaba Group through Alibaba Innovative Research Program. The opinions, findings, conclusions, and recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies or the government.

4 More related work are covered in the full version of this paper.