# autobidding_with_budget_and_roi_constrained_buyers__250fe12f.pdf

Auto-bidding with Budget and ROI Constrained Buyers

Xiaodong Liu and Weiran Shen

Gaoling School of Artificial Intelligence, Renmin University of China {xiaodong.liu, shenweiran}@ruc.edu.cn

In online advertising markets, an increasing number of advertisers are adopting auto-bidders to buy advertising slots. This tool simplifies the process of optimizing bids based on various financial constraints. In our study, we focus on second-price auctions where bidders have both private budget and private ROI (return on investment) constraints. We formulate the auto-bidding system design problem as a mathematical program and analyze the autobidders bidding strategy under such constraints. We demonstrate that our design ensures truthfulness, i.e., among all pure and mixed strategies, always reporting the truthful budget and ROI is an optimal strategy for the bidders. Although the program is non-convex, we provide a fast algorithm to compute the optimal bidding strategy for the bidders based on our analysis. We also study the welfare and provide a lower bound for the Po A (price of anarchy). Moreover, we prove that if all bidders utilize our auto-bidding system, a Bayesian Nash equilibrium exists. We provide a sufficient condition under which the iterated best response process converges to such an equilibrium. Finally, we conduct extensive experiments to empirically evaluate the effectiveness of our design.

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 Tik Tok.

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.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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 Po A (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 Related Works

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] 7 [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:

xi(b) = 1 if bi bj, j 0 otherwise , (1)

pi(b) = maxj =i bj if bi bj, j 0 otherwise . (2)

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[Di I{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[Di I(bi Di)] > 0, we define the buyer i s ROI as E[(vi Di)I{bi Di}]

E[Di I{bi Di}] .

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

Buyer i s bid satisfies the ROI constraint if:

E[(vi Di)I{bi Di}]

E[Di I{bi Di}] γi.

A major 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 strategies1 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. Since we assume

E[Di I(bi Di)] > 0,

the ROI constraint becomes:

E[(vi Di)I{bi Di}] γi E[Di I{bi Di}].

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

E{[(1 + γi)Di vi]I{βivi Di} 0.

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:

maximize: E[(vi Di)I{βivi Di}] subject to: E[Di I{βivi Di}] Bi E[((1 + γi)Di vi)I{βivi Di}] 0 (3)

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

1Although 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.

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.

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

Pi(βi) = E[Di I{βivi Di}]

0 Digi(Di) d Difi(vi) dvi. (4)

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

hi(βi) = E[((1 + γi)Di vi)I{βivi Di}]

0 [(1 + γi)Di vi]gi(Di) d Difi(vi) dvi.

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:

Ui(βi) = E[(vi Di)I{βivi Di}]

0 (vi Di)gi(Di) d Difi(vi) dvi (6)

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.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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

BH = Pi(1) = E[Di I{vi Di}]. (7) 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

γL = E[(vi Di)I{vi Di}]

E[Di I{vi Di}] (8)

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[Di I{vi Di}] and γL = E[vi I{vi Di}]

E[Di I{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).

Figure 1: The relationship between (Bi, γi) and (Pi, Γi).

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

5 Use binary search to solve equation Pi(β1 i ) = Bi, where Pi(βi) is defined in Function (4);

6 if γi γL then

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

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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.

BH = E[Di I{vi Di}] = Z 10

10 d Di 1 10 dv = 5

γL = E[vi I{vi Di}]

E[Di I{vi Di}] 1 =

R 10 0 v R v 0 d Di dv R 10 0 R v 0 Di d Di dv 1 = 1.

Now we compute the two thresholds β1 i and β2 i . If Bi 5

3, we have β1 i = 1. Otherwise, if Bi < 5

3, we can obtain β1 i by solving the equation E[Di I{β1vi Di}] = Bi. In this

example, we can get the closed-form solution β1 i = q

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

E{[(1 + γi)Di vi]I(βvi Di)} = 0.

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.

(a) ROI vs payment

(b) Utility vs payment

Figure 2: The buyer s ROI and utility as a function the the payment.

5 Equilibrium Analysis

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

|Fi(vi) Fi(v i)| M|vi v i|, i [n].

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 following:

(n 1)mn 1Dn 1 i Digi(Di, β i) (n 1)M v.

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

β = max 2B (n 1)M 2 v3 , 1 1 + γ

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 7 [β, 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:

β(t+1) = X(β(t)), t = 0, 1, 2, . . .

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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 (M 2+βξ)Di

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

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

X(β) X(β + ϵ) 1 (M 3 + Mβξ)(n + 1) ϵ 1

12(n 1)βn+2mn vn 3 ,

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

(M 3 + Mβξ)(n + 1)

12(n 1)βn+2mn vn 3 < 1,

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

βt+1 = X(βt), t = 0, 1, 2, . . .

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

SW(β) = Ev F (v)

i=1 vixi(b)

where F(v) = Q 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:

Po A = min F minβ EQ(F ) SW(β)

maxβ SW(β) .

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., Po A β.

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.

(a) ROI vs payment

(b) Utility vs payment

Figure 3: The buyer s expected ROI, utility and payment for different budget and ROI constraints.

(a) Payment vs budget constraint

(b) Actual ROI vs target ROI

Figure 4: Comparison between the buyer s actual payment and ROI and the corresponding constraints.

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

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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 i Pin You [Liao et al., 2014]. The i Pin You 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 i Pin You 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).

(a) Competitors value distribution.

(b) Buyer i s value distribution.

Figure 5: Value distributions obtained from the i Pin You data set.

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

Figure 6: The buyer s ROI and utility with 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 i Pin You 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 i Pin You 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.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

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).

References [Aggarwal et al., 2006] Gagan Aggarwal, Ashish Goel, and Rajeev Motwani. Truthful auctions for pricing search keywords. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 1 7, 2006. [Aggarwal et al., 2019] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. Autobidding with constraints. In International Conference on Web and Internet Economics, pages 17 30. Springer, 2019. [Balseiro and Gur, 2019] Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952 3968, 2019. [Balseiro et al., 2015] Santiago R Balseiro, Omar Besbes, and Gabriel Y Weintraub. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science, 61(4):864 884, 2015. [Balseiro et al., 2017] Santiago Balseiro, Anthony Kim, Mohammad Mahdian, and Vahab Mirrokni. Budget management strategies in repeated auctions. In Proceedings of the 26th International Conference on World Wide Web, pages 15 23, 2017. [Balseiro et al., 2021a] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Robust auction design in the auto-bidding world. Advances in Neural Information Processing Systems, 34:17777 17788, 2021. [Balseiro et al., 2021b] Santiago R Balseiro, Yuan Deng, Jieming Mao, Vahab S Mirrokni, and Song Zuo. The landscape of auto-bidding auctions: Value versus utility maximization. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 132 133, 2021. [Balseiro et al., 2022] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Optimal mechanisms for value maximizers with budget constraints via target clipping. Available at SSRN, 2022. [Borgs et al., 2007] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mohammad Mahdian. Dynamics of bid optimization in online advertisement auctions. In Proceedings of the 16th international conference on World Wide Web, pages 531 540, 2007. [Brouwer, 1911] Luitzen Egbertus Jan Brouwer. Uber abbildung von mannigfaltigkeiten. Mathematische annalen, 71(1):97 115, 1911. [Chen et al., 2021] Xi Chen, Christian Kroer, and Rachitesh Kumar. The complexity of pacing for second-price auctions. ar Xiv preprint ar Xiv:2103.13969, 2021.

[Clarke, 1971] Edward H Clarke. Multipart pricing of public goods. Public choice, pages 17 33, 1971.

[Conitzer et al., 2017] Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. Multiplicative pacing equilibria in auction markets. ar Xiv preprint ar Xiv:1706.07151, 2017.

[Conitzer et al., 2018] Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Eric Sodomka, Nicolas E Stier-Moses, and Chris Wilkens. Pacing equilibrium in first-price auction markets. ar Xiv preprint ar Xiv:1811.07166, 2018.

[Conitzer et al., 2022] Vincent Conitzer, Christian Kroer, Eric Sodomka, and Nicolas E Stier-Moses. Multiplicative pacing equilibria in auction markets. Operations Research, 70(2):963 989, 2022.

[Cramton et al., 2004] Peter Cramton, Yoav Shoham, Richard Steinberg, et al. Combinatorial auctions. Technical report, University of Maryland, Department of Economics-Peter Cramton, 2004.

[Deng et al., 2021] Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. Towards efficient auctions in an auto-bidding world. In Proceedings of the Web Conference 2021, pages 3965 3973, 2021.

[Edelman et al., 2007] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American economic review, 97(1):242 259, 2007.

[Golrezaei et al., 2021] Negin Golrezaei, Ilan Lobel, and Renato Paes Leme. Auction design for roi-constrained buyers. In Proceedings of the Web Conference 2021, pages 3941 3952, 2021.

[Groves, 1973] Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617 631, 1973.

[Gummadi et al., 2012] Ramakrishna Gummadi, Peter Key, and Alexandre Proutiere. Repeated auctions under budget constraints: Optimal bidding strategies and equilibria. In the Eighth Ad Auction Workshop, volume 4, 2012.

[Liao et al., 2014] Hairen Liao, Lingxiao Peng, Zhenchuan Liu, and Xuehua Shen. ipinyou global rtb bidding algorithm competition dataset. In Proceedings of the Eighth International Workshop on Data Mining for Online Advertising, pages 1 6, 2014.

[Mehta, 2022] Aranyak Mehta. Auction design in an autobidding setting: Randomization improves efficiency beyond vcg. In Proceedings of the ACM Web Conference 2022, pages 173 181, 2022.

[Myerson, 1981] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58 73, 1981.

[Pai and Vohra, 2014] Mallesh M Pai and Rakesh Vohra. Optimal auctions with financially constrained buyers. Journal of Economic Theory, 150:383 425, 2014.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)

[Shen et al., 2020] Weiran Shen, Binghui Peng, Hanpeng Liu, Michael Zhang, Ruohan Qian, Yan Hong, Zhi Guo, Zongyao Ding, Pengjun Lu, and Pingzhong Tang. Reinforcement mechanism design: With applications to dynamic pricing in sponsored search auctions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2236 2243, 2020. [Statista, 2022] Statista. Digital ad spend worldwide 2026. https://www.statista.com/statistics/237974/ online-advertising-spending-worldwide/, 2022. Accessed: 2023-05-25. [Varian, 2007] Hal R Varian. Position auctions. international Journal of industrial Organization, 25(6):1163 1178, 2007. [Vickrey, 1961] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8 37, 1961.

Proceedings of the Thirty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI-23)