Auto-bidding with Budget and ROI Constrained Buyers

1 Introduction

Ever since the seminal works of the Vickrey-Clarke-Groves (VCG) auction [Vickrey, 1961; Clarke, 1971; Groves, 1973] and Myerson's optimal auction [Myerson, 1981], the auction design problem has been one of the central topics at the intersection of economics and computer science, leading to the development and implementation of various auction mechanisms across numerous fields [Cramton et al., 2004; Aggarwal et al., 2006; Varian, 2007; Edelman et al., 2007].

One of the most successful applications of auction theory is online advertising, which is a large and still growing business. Online advertising has become the main source of revenue for many Internet companies, such as Meta, Google, and TikTok.

∗To whom correspondence should be addressed.

According to the statistics by Statista [2022], 521 billion dollars have been spent on digital advertisements in 2021. Most online ad platforms adopt the second-price auction or its variants. The appeal of the second-price auction lies in its truthfulness, where buyers are incentivized to report their true values as bids. Additionally, the second-price auction is known for maximizing social welfare, ensuring that the buyer with the highest value ultimately secures the item or ad slot.

Although the second-price auction is truthful, many bidders are still constantly changing their bids on these platforms. This behavior can be attributed to the presence of various financial constraints faced by advertisers, including budget limitations and profitability considerations. Consequently, advertisers often find it challenging to bid their true values, as doing so may conflict with their constraints, such as exceeding their allocated budget. However, setting finegrained bids for different auctions is a notoriously difficult task for advertisers, and only those large advertisers have the ability to fine-tune the bidding strategy. Conversely, smaller advertisers, who may be more constrained by financial limitations, often lack the capacity to optimize their bids effectively.

Auto-bidding systems have gained significant popularity among advertisers as they aim to simplify the bidding process in online advertising. These systems only require advertisers to provide high-level financial targets, such as their budget and target CPA (cost per acquisition), instead of setting separate bids for each auction. The auto-bidding system then leverages these targets to compute optimized bids and participate in auctions on behalf of the advertisers. Such autobidding systems optimize the advertisers' bids for them and allow them to focus more on high-level goals. Thus more and more advertisers are adopting auto-bidding systems.

The simplest auto-bidding strategy only considers the budget constraint for the bidders [Borgs et al., 2007; Pai and Vohra, 2014; Conitzer et al., 2018; Balseiro et al., 2017]. They ensure that the buyers' actual payment does not exceed their budget. Another set of strategies considers the bidder's return on investment (ROI) constraints, which is also called the return on spend (ROS) constraint in some research [Golrezaei et al., 2021; Balseiro et al., 2021b]. Aggarwal et al. [2019] assume that the bidders' budget and ROI constraints are publicly known, and Balseiro et al. [2022] consider both constraints but assume that the buyers' budget is publicly known, while the buyers' ROI constraint is privately known.

To the best of our knowledge, there is no existing work that considers both private budget and private ROI constraints. In our paper, we focus on this setting and assume the underlying auction mechanism is the second-price auction with no reserve prices.

1.1 Our Contributions

In this paper, we formulate the problem as a mathematical program and analyze the properties of the optimal solution. We then propose an efficient algorithm based on theoretical analysis to compute the optimal strategy. We also show that under our mechanism, reporting the truthful budget and ROI targets is the optimal strategy even if the buyers can adopt mixed strategies. Furthermore, we show that an equilibrium always exists if all bidders adopt our auto-bidding algorithm. We then give a sufficient condition under which the iterated best response process converges to such an equilibrium. We also analyze the social welfare of the auto-bidding strategy and provide a lower bound for the PoA (price of anarchy). In the end, we conduct extensive experiments based on both synthetic and realistic data sets to demonstrate the performance of our bidding strategy.

1.2 RelatedWorks

Budget Constraint: In the online advertising literature, Balseiro and Gur [2019] propose adaptive pacing algorithms to control the buyer's payment within the budget. Balseiro et al. [2017] provide a detailed comparison of budget management strategies commonly used in practice. Conitzer et al. [2022] and Chen et al. [2021] study the computational complexity in the pacing equilibrium.

ROI Constraint: Aggarwal et al. [2019] study the setting where the bidders are value maximizers with ROI constraint. Golrezaei et al. [2021] analyze the setting where the bidders are utility maximizers with ROI constraint in secondprice auctions with reserve prices. They show that the buyer's optimal strategy is to shade his bid, i.e., bid lower than his valuation. Such shading strategies can also be found in [Balseiro et al., 2015; Balseiro and Gur, 2019; Conitzer et al., 2017; Gummadi et al., 2012].

Social Welfare: Aggarwal et al. [2019] show that the truthful mechanism can achieve at least half of the optimal social welfare when bidders have financial constraints. Balseiro et al. [2021a] and Deng et al. [2021] study how to use boost and reserve price to improve the social welfare when autobidders are value maximizers under ROI constraints. Mehta [2022] studies how to use randomized mechanism to improve social welfare under the auto-bidding setting. Balseiro et al. [2021b] and Balseiro et al. [2022] analyze the setting where the buyer's ROI target is private and the budget constraint is public. Their settings are all different from ours as we consider both private budget constraints and private ROI targets.

Bayesian Nash Equilibrium: Both Aggarwal et al. [2019] and our paper consider the existence of a Bayesian Nash equilibrium. However, Aggarwal et al. [2019] assume there is only one particular impression and the queries and slots form a continuum, while we make assumptions about bidders' value distributions.

2 Preliminaries

We consider the online advertising setting where there is a seller with an item for sale to n buyers. Let [n] = {1, 2, · · · , n} denote the set of buyers. Each buyer i ∈ [n] has a value vi for the item, drawn independently from a publicly known cumulative distribution function Fi(vi) : [0, ¯ v] ↦→ [0, 1] for some 0 < ¯ v < +∞. Assume Fi(vi) is differentiable and fi(vi) is the corresponding probability density function. Let v = (v1, v2, · · · , vn) be the value profile, which contains the values of all buyers. Similarly, let v-i = (v1, · · · , vi-1, vi+1, · · · , vn) denote the value profile of all buyers except buyer i. Though the value distribution Fi(vi), i ∈ [n] is publicly known, the realized value vi is only known to buyer i. Let bi be the bid of buyer i. Similarly, we define b = (b1, b2, · · · , bn) as the bid profile of all buyers and b-i = (b1, · · · , bi-1, bi+1, · · · , bn) as the bid profile of all buyers except buyer i.

Assume that the seller uses the second-price auction as the base auction mechanism, which is widely used in the online advertising industry, especially in ad exchanges. In a second-price auction, the bidder with the highest bid wins the item and pays the second highest bid. Let x(b) = (x1(b), . . . , xn(b)) be the allocation rule and p(b) = (p1(b), . . . , pn(b)) the payment rule:

If there are more than one highest bids, we can break ties arbitrarily. Assume that buyer i's utility functions ui are quasi-linear, i.e., ui(vi) = vix(bi, b-i) - p(bi, b-i).

For a buyer i, let Di = maxj̸=i bj be the highest bid of all other buyers, which is a random variable. Denote by Gi(Di) and gi(Di) the cumulative distribution function and the probability density function of Di, respectively. Since Fi(vi) is differentiable for all i, Di also has a density function, which implies that the probability of bi = Di is simply 0. Thus the tie-breaking rule does not affect the auction outcome.

We consider the setting where all buyers have both budget and ROI constraints. Let Bi and γi be the budget and ROI constraints of buyer i. Formally, buyer i's bids bi satisfies the budget constraint if:E[DiI{bi ≥ Di}] ≤ Bi,

where the function I(·) is the indicator function, and the expectation is taken over both bi and Di. Since the seller uses a second-price auction, buyer i wins the auction only if bi ≥ Di. And when buyer i wins, their payment is Di. Thus the left-hand side of the above equation is simply their expected payment in the auction.

The ROI can be defined as follows.

Definition 1 (Return on Investment). Buyer i's return on investment is the ratio between his expected gain from the auction and his expected payment. Formally, assuming E[DiI(bi ≥ Di)] > 0, we define the buyer i's ROI as

Buyer i's bid satisfies the ROI constraint if:

Amajor reason for the buyer's ROI constraint is that the buyer has outside options. Suppose that the buyer can have a profit margin of 5% if they invest the money elsewhere. Then they will only participate in the auction if they can secure an ROI of at least 5% in the advertising platform. We assume that both Bi and γi are the private information of buyer i, and thus need to be reported to the platform.

Throughout the paper, we assume that the budget Bi has a lower bound B > 0, as a 0 budget simply indicates that the buyer does not want to participate in the auctions. Also, we assume that the ROI γi has an upper bound ¯ γ with ¯ γ > 0, since no platform cannot guarantee an arbitrarily high ROI.

Note that in both two constraints, we consider the expected utility and payment. This is because buyers participate in large volumes of online ad auctions each day, and focusing on the expected quantities makes more sense than considering only a single auction.

We follow literature convention (see, e.g., [Golrezaei et al., 2021; Mehta, 2022]) and focus on shading strategies 1 for the bidders: bi = βivi. We restrict βi to be a positive number (i.e., βi > 0) for obvious reasons. We call βi the shading parameter.

the ROI constraint becomes:

Plugging in the bidding strategy bi = βivi, we obtain the following inequality for the ROI constraint:

In this paper, we first consider how to design an autobidding strategy (which is fully characterized by the parameter βi) for each buyer given their reported budget and ROI. We assume that the buyers' utility is -∞ if either constraint is violated, i.e., the constraints are hard constraints. With the above discussion, we can formulate the problem as a mathematical program based on Bi and γi:

3 The Optimal Shading Parameter

If the buyer i does not have financial constraints, their optimal strategy is to use their valuations as the bids (βi = 1) in a second-price auction. However, when the bidders have financial constraints, they may try to shade their bids and use a different parameter βi. In this section, we first analyze the properties of Program (3) when buyer i has both budget and ROI constraints. Then we propose an efficient algorithm to solve this program based on the properties, although Program (3) is non-convex.

1 Although the strategy is called a shading strategy in our paper, we actually allow βi to be larger than 1. However, later analyses show that the optimal βi never exceeds 1, and hence a "shading" strategy.

3.1 Properties of the Optimal Parameter

In this section, we derive important properties of Program (3) that will be useful for designing our algorithm. Due to space limit, we defer all the proofs to the Appendix.

We first analyze the feasible region of Program 3. For simplicity, define the bidder i's expected payment as

Lemma 1. The buyer's expected payment Pi(βi) is monotone increasing with respect to βi.

According to Lemma 1, we must have βi ≤ P -1 i (Bi) in order to satisfy the bidder's budget constraint Pi(βi) ≤ Bi. Therefore, the budget constraint actually restricts βi to the interval (0, P -1 i (Bi)].

Then we analyze the ROI constraint. Define

The following lemma analyzes how hi(βi) changes with respect to βi.

Lemma 2. Function hi(βi) is monotone decreasing in (0, 1 1+γi ], and monotone increasing in ( 1 1+γi , +∞).

It is easy to see that hi(0) = 0. Then Lemma 2 implies that there is at most one ˆ β > 0 such that hi( ˆ β) = 0.

Lemma 3. If there exists ˆ β > 0 with hi(ˆ β) = 0, then the ROI constraint is equivalent to βi ≤ ˆ β. Otherwise, we have hi(βi) < 0, ∀βi ∈ (0, +∞).

Lemma 3 says that the ROI constraint either requires βi to be in the interval (0, ˆ β] or imposes no restrictions on βi (i.e., βi should be in the interval (0,+∞)).

Combining Lemma 1 and 3, we can immediately get the following corollary:

Corollary 1. The feasible region of Program (3) is an interval (0, ¯ β]. If there exists ˆ β > 0 with hi(ˆ β) = 0, ¯ β = min{P -1 i (Bi), ˆ β}. Otherwise, ¯ β = P -1 i (Bi).

Now we analyze the objective function. Write buyer i's expected utility as a function of βi:

Lemma 4. The buyer's utility is monotone increasing with respect to βi when βi ≤ 1, and monotone decreasing with respect to βi when βi > 1.

Lemma 4 shows that the utility function is maximized when βi = 1 if there is no restriction on β. However, we already know from Corollary 1 that the feasible region of Program (3) is an interval. The following result is straightforward from Lemma 4 and Corollary 1.

Corollary 2. The optimal solution βi to program (3) satisfies 0 < βi ≤ 1.

Since βi ≤ 1 and the expected payment of the buyer is monotone in βi, the maximum possible payment is obtained when βi = 1. Define the maximum possible payment as

Therefore, we have the following corollary:

Corollary 3. If the buyer's budget Bi satisfies Bi ≥ BH , the buyer's budget constraint will have no effect on the value of βi, i.e., The budget constraint will always be satisfied.

In this paper, we only consider the case B ≤ BH , since otherwise, the budget constraint will always be satisfied.

Now we show that choosing a larger βi yields a lower ROI.

Lemma 5. The actual ROI of buyer i is monotone decreasing with respect to βi. And as βi approaches 0, the ROI approaches infinity.

Define

to be the ROI if buyer i bids their values, i.e., βi = 1. Similarly, we have the following corollary:

Corollary 4. When buyer i's ROI γi satisfies γi ≤ γ L, the buyer's ROI constraint can always be satisfied for all βi ∈ (0, 1].

Let Pi denote the buyer's expected payment and Γi denote the buyer i's actual ROI after using the bidding strategy βi obtained by solving the above program. Combining the above properties, we can get the theorem below.

Theorem 1. Let Bi and γi be the reported budget constraint and the ROI constraint of buyer i. Define BH = E[DiI{vi ≥ Di}] and γ L = E[viI{vi≥Di}] E[DiI{vi≥Di}] -1. The relation between point (Bi, γi) and the expected payment and ROI point (Pi, Γi) is shown in Figure 1, where the solid curve are the set of all points that satisfy both the budget constraints and ROI constraints simultaneously, and

• if (Bi, γi) lies in area 1, the realized point (Pi, Γi) is the point right above (Bi, γi) in the solid curve and satisfies Pi = Bi;
• if (Bi, γi) lies in area 2, the realized point (Pi, Γi) is the point to the left of (Bi, γi) in the curve and satisfies Γi = γi;
• if (Bi, γi) lies in area 3, the realized point (Pi, Γi) is (BH , γ L).

3.2 Algorithm

Since Program (3) is non-convex, it is not easy to directly find it solution. In this section, we present an indirect algorithm based on the theoretical analyses so far.

Theorem 2. Algorithm 1 can correctly solve the Program (3).

Algorithm 1: Finding the optimal βi

Input: The buyer's budget constraint Bi and ROI

target γi. Output: The buyer's best bidding strategy βi 1 Compute BH and γ L according to Equation (7) and (8); 2 if Bi ≥ BH then 3 β1 i ← 1; 4 else 5 Use binary search to solve equation Pi(β1 i ) = Bi, where Pi(βi) is defined in Function (4); 6 if γi ≤ γ L then 7 β2 i ← 1; 8 else 9 Use binary search to solve equation hi(β2 i ) = 0, where hi(βi) is defined in Function (5); 10 return βi =min{β1 i , β2 i }

4 Strategic Issues

In the above analyses, we only study how to optimize bidder i's utility given their reported Bi and γi, but have not considered their strategic behaviors. The following results show that if the auto-bidding system optimizes the buyer's bids by solving Program (3), the buyer's best response is to report Bi and γi truthfully. We omit all the proofs due to the space limit.

Lemma 6. Buyer i's optimal pure strategy is to report (Bi, γi) truthfully.

Lemma 6 only considers deterministic strategies. Now we show that reporting the true Bi and γi is also the optimal strategy even if we consider mixed strategies.

Suppose buyer i uses a mixed strategy that leads to a distribution of possible βi's. Thus the expected payment and utility becomes Eβi [Pi(βi)] and Eβi [Ui(βi)]. Note that the expected ROI is Eβi [Ui(βi)] Eβi [Pi(βi)] rather than Eβi [Γi(βi)]. Therefore, we cannot directly analyze how the expected ROI changes, but focus on Eβi [Pi(βi)] and Eβi [Ui(βi)] instead.

Lemma 7. View Ui(βi) and Pi(βi) as a parametric equation, which induces an implicit function Ui(Pi). The function Ui(Pi) is concave.

Theorem 3. Buyer i's optimal strategy is to report (Bi, γi) truthfully, even if mixed strategies are considered.

Now we give an example here to illustrate our results.

Example 1. Suppose there is a bidder i with vi drawn from the uniform distribution U[0, 10]. Assume that Di also follows the uniform distribution U[0, 10].

We first compute BH and γ L.

Now we compute the two thresholds β1 i and β2 i . If Bi ≥ 53 , we have β1 i = 1. Otherwise, if Bi < 5 3 , we can obtain β1 i by solving the equation E[DiI{β1 vi ≥ Di}] = Bi. In this example, we can get the closed-form solution β1 i = √ 35 Bi.

As for β2 i , if γi ≤ 1, we have β2 i = 1 and if γi > 1, the threshold is β2 i = 2 1+γi , which is the solution to equation

The optimal solution is βi = min{β1 i , β2 i }. We compute the payments and utilities for different βi's. The results are shown in Figure 2, which confirms Lemma 5 and 7.

5 EquilibriumAnalysis

Until now, we have analyzed the behavior of a single bidder. The bidder will shade their bids to satisfy the budget and ROI constraints. In this section, we analyze the Bayesian game induced by the auto-bidding system. We show the existence of a Bayesian Nash equilibrium and provide a sufficient condition for the iterated best response process to converge to such an equilibrium. We also analyze the social welfare of the auto-bidding system. We make the following additional assumptions about fi(vi) that hold for a wide range of value distributions:

1. For any i, fi(vi) is bounded by m≤ fi(vi) ≤M;
2. There exits ξ > 0, such that fi(vi) is ξ-Lipschitz for all i, i.e., |fi(vi) - fi(v′i )|≤ ξ|vi - v′i |.

Since for any i and value vi ∈ [0, ¯ v], fi(vi) ≤ M, it follows that the function Fi(v) is M-Lipschitz. Formally, for any value vi, v′i ∈ [0, ¯ v], we have

The shading parameters βi depend on the bidders' budget and ROI constraints. Since both the budget and ROI constraints are bounded, we can provide a lower bound for βi.

Let β = [β1, β2, . . . , βn] denote a shading profile, and β-i = [β1, β2, . . . , βi-1, βi+1, . . . , βn] the shading profile of all buyers except for bidder i. For each bidder i, β-i will induce a probability density function gi(Di, β-i) over Di = maxj̸=i bj , as the other bidders' bids depend on β-i.

We first prove the following lemmas, which will be useful for later arguments.

Lemma 8. Given any β-i, gi(Di, β-i) satisfies the follow-

With the above lemma, we can bound βi from below. The intuition is that although a small enough βi may satisfy both the budget and the ROI constraints, it also lowers the bidder's utility according to Lemma 4.

Lemma 9. Define

If each bidder i's financial constraints satisfy Bi ≥ B and γi ≤ ¯ γ, then for all bidders, we have βi ≥ β, ∀i ∈ [n].

5.1 Existence of Bayesian Nash Equilibrium

In this section, we prove that if all the bidders use our autobidding system, then there exists a Bayesian Nash equilibrium in the Bayesian game induced by our mechanism. We also show that the iterated best response process converges to such an equilibrium under certain technical conditions.

Given any shading profile β, for each bidder i, β-i will induce a probability distribution gi(Di, β-i) over Di = maxj̸=i bj, Let β′ i be the optimal solution to Program (3) by using gi(Di, β-i), i.e., β′ i can be viewed as a "best response" to β-i. Define function X : [β, 1]n ↦→ [β, 1]n such that Xi(β) = β′ i . Note that we assume that the bidders only can report Bi ∈ [B, +∞) and γi ∈ (0, ¯ γ], the program (3) always has solutions and its solution always lies in [β, 1]. Therefore, the function X is well-defined. It is clear that an equilibrium exists if the function X has a fixed point. To show this, we first prove that a small change in βk with k ̸= i will not affect gi(Di, β-i) too much for any i (Lemma 10). Then we show that a slight perturbation in gi(Di, β-i) does not result in a sudden change in bidder i's response (Lemma 11). In the end, we show that even if all bidders change their strategies simultaneously, the change of function X can still be bounded (Lemma 12), which indicates that X is continuous. And with Brouwer's fixed point theorem, we know that X has a fixed point (Theorem 4).

Starting from any initial β(0) , we define an iteration process as follows:

We perform convergence analysis of the above process. We show that under certain conditions, X becomes a contraction, and the convergence immediately follows (Theorem 5).

Lemma 10. Given any β, if the parameter βk is changed to βk + ϵk, then for any i ̸= k, the probability density function gi(Di, β-i) changes at most (M2+βξ)Di β3 |ϵk |.

Lemma 11. Given any β, if the parameter βk for bidder k is changed to βk + ϵk, then for any i, Xi(β) changes at most (M3+Mβξ)(n+1)|ϵk| 12(n-1)βn+2mn ¯ vn-3 .

Lemma 12. Let ϵ = (ϵ1, ϵ2, . . . , ϵn). For any β, function X(β) satisfies the following:

where ∥·∥1 is the 1-norm operator.

The above 3 lemmas show that the function X is continuous. Now we are ready to apply Brouwer's fixed point theorem to prove the existence of an equilibrium

Theorem 4. For any problem instance satisfying the 3 assumptions specified at the beginning of this section, there exists a Bayesian Nash equilibrium β, such that for each i, βi is the best response to β-i.

Corollary 5. If

starting from any β0 , the following iteration process converges to an equilibrium:

5.2 Welfare Analysis

In this section, we analyze the social welfare of the autobidding system. We show that our mechanism always achieves a certain fraction of the optimal welfare.

Definition 2. (Social Welfare) Given any shading parameter profile β, the social welfare is defined as

where F(v) = ∏i Fi(vi) is the joint value distribution and bi = βivi.

Definition 3 (Price of Anarchy). Given any instance described by F(v), Let EQ(F) be the set of all the equilibria of the instance. The price of anarchy is defined as the worst ratio between the optimal social welfare and the social welfare in the worst equilibrium among all instances satisfying assumptions described in Section 5:

The optimal welfare is simply the welfare of the secondprice auction, which can be achieved by setting βi = 1 for all i. The following result shows that the price of anarchy of our mechanism is at least β, i.e., our mechanism always achieves at least β fraction of the optimal welfare.

Theorem 5. The price of anarchy of our mechanism is at least β, i.e., PoA ≥ β.

6 Experiments

In this section, we conduct experiments based on an open data set and report the experiment results.

We first consider a relatively simple case. Suppose that there are only five i.i.d. buyers. The value of each buyer is drawn from the uniform distribution U[0, 10]. Assuming that only one buyer has financial constraints and other four buyers simply bid their true values. The buyer's budget constraint is drawn randomly from a uniform distribution U[0, 3] and the ROI target is drawn randomly from a uniform distribution U[0, 5]. We randomly sample 10000 budget constraint and ROI target pairs. For each pair, we simulate 1,000,000 auctions and compute the average payment and the utility. The results are shown in Figure 3 and Figure 4.

In Figure 3(a), the blue curve show how the actual ROI and payment changes. Note that although we have shown that the ROI approaches infinity as the payment goes to 0, the actual ROI can never reach infinity in the experiments.

Figure 3(b) shows that the buyer's utility function is indeed concave with respect to the payment. A mixed strategy leads to a point in the figure that is a convex combination of different points in the curve. Since the curve is convex, a mixed strategy cannot benefit the buyer. The curve also means that the effect of investing more money eventually diminishes.

Figure 4(a) shows that the buyer's actual payment is always lower than the buyer's budget satisfying the buyer's budget constraint. Similarly, Figure 4(b) shows that for the buyer's actual ROI is always higher than the buyer's ROI target, satisfying the buyer's ROI constraint.

Then we conduct experiments based on the open data set iPinYou [Liao et al., 2014]. The iPinYou data set is published by a major demand-side platform (DSP) and contains auction logs of 24 days in 3 auction seasons. The data set includes 78 million bid records with 24 million impressions. In our experiment, we select one day's impression log data in the 2nd season to estimate the competitor's highest bid's distribution.

Our chosen data contains five advertisers. We select one of them and use the "paying price" column as the competitor's highest bid. The advertiser participates in different auction platforms such as Goolge, Alibaba, and Tencent. We focus on the data from one platform and plot histogram of the competitor's highest bids in Figure 5(a). We fit the data to a lognormal distribution and plot the PDF of the fitted distribution as the orange curve.

Unfortunately, in the iPinYou dataset, the platform use a special strategy which always places a very high bid to win as many auctions as possible to collect data about the competitors' highest bids. Therefore, there is no data about the valuation of the advertiser in the DSP. To conduct the experiments, we assume that there are 3 major bidders [Shen et al., 2020] in the auction platform, and that they have i.i.d. valuations and bid their values. Also, we assume that our chosen buyer also follows the same value distribution, which we show in Figure 5(b).

Similar to the previous experiment, the budget constraint is drawn randomly from uniform distribution U[0, 300] and the ROI target is drawn randomly from distribution U[0, 5]. We randomly sample 10000 budget constraint and ROI target pairs and simulate 1, 000, 000 auctions for each pair to compute the expected payment and utility. The results are shown in Figure 6 and Figure 7.

The ROI is quite significant when the buyer's available budget is small, meaning that a small investment can lead to a substantial profit. In Figure 7(b), we can see a flat line when the target ROI is relatively small. This is because, according to Lemma 3, there is a lower bound γ L for the actual ROI. These points are also the highest points in Figure 7(a), since when the ROI reaches the lower bound, the payment also hits the upper bound BH .

• (a) ROI vs payment
• (b) Utility vs payment
• (a) Payment vs budget constraint.
• (b) Actual ROI vs target ROI.

Figure 7: The buyer's actual payment and ROI, and the corresponding constraints.

Figure 8 shows how the welfare changes with respect to β in both experiments. Since there is only one buyer with financial constraints in our experiments, Figure 8 shows how much it can affect the welfare by changing β for only one buyer. Note that the optimal welfare is simply the point with β = 1. Even when β = 0, our auto-bidding strategy achieves about 96% and 84% of the optimal welfare, In the experiments with the synthetic data set and the iPinYou data set, respectively. Interestingly, in Figure 8(a), the welfare drops quickly when β decreases, while in Figure 8(b), the welfare ratio is still above 90% for β = 0.2.

• (a) Welfare of the experiments with synthetic data set. (b) Welfare of the experiments with iPinYou data set.

Figure 8: The relationship between the social welfare with β.

7 Conclusion

In this paper, we consider the auto-bidding problem in second-price auctions with the buyers having both budget and ROI constraints. We consider the buyer's bidding strategy and show that reporting the truthful budget and ROI targets is the optimal strategy even if they consider mixed strategies. We also show that the equilibrium exists under some assumptions and give a sufficient condition to find the equilibrium using iterated best response.

Acknowledgements

We thank all the anonymous reviewers for their helpful comments. This work was supported in part by the National Natural Science Foundation of China (No. 62106273 & No. 72192805), the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China (22XNKJ16).