Vulnerabilities of Single-Round Incentive Compatibility in Auto-bidding: Theory and Evidence from ROI-Constrained Online Advertising Markets

1 Introduction

Auto-bidding has become a corner stone of modern advertising markets. For better end-to-end performance and customer experience, platforms now provide algorithmic agents to set fine-grained bids for advertisers, who only need to submit campaign-level optimization objectives and constraints. As a result, the community has seen a surge of publications on auto-bidding in recent years.

One of the most notable features of the auto-bidding paradigm is the change of roles played by advertisers and platforms. Traditionally advertisers are assumed to bid rationally for each individual ad slot, and thus the real-time bidding (RTB) literature focuses on developing algorithms for advertisers to maximize their objectives subject to different constraints and auction rules, while the auction design literature, anticipating the best response of advertisers or RTB algorithms, explores new auction rules to optimize various goals of the platform. However, in auto-bidding markets, most of the technical components are under the management of the platform: auto-bidders provided by the platform will compete with each other, based on valuations predicted by the platform, under auction rules that are also designed by the platform. Such a greater control over the market imposes a more diverse set of requirements upon the designer. The auction design literature has long been focusing on incentive compatibility and welfare/revenue guarantee, but the desiderata of an auto-bidding mechanism are far beyond these two. Google AdSense's partial shift at 2021 from second to first price auction 1 might serve as an exemplary demonstration of this perplexity.

∗The full version is at https://arxiv.org/abs/2210.06107.

Despite the evolution of ecosystems, first and second price auction remain as the dominant mechanisms used in practice. In this paper, we study the mathematical model abstracted from real-world first and second price auction markets with ROI-constrained auto-bidders. In addition to theoretic interests, our work are also motivated by real-world observations. Traditional interpretations of some phenomena may confuse both sides of the market and lead to business choices detrimental in the long run. Our goal is thus to develop a deeper understanding of auto-bidding at the market scale, and provide practitioners a more holistic view to facilitate decision making. We will show, through a series of theoretical and empirical results, that the dominant advantage of second price auction over first price is, in many regards, reversed in the world of auto-bidding. It will be made clear throughout the journey how IC, instead of simplifying the reasoning of both bidders and auctioneers, unnecessarily complicates the game in a profound way.

1.1 ROI-Constrained Auto-biddingMarkets and Related Works

Previously much effort was spent on the study of auto-bidders with budget constraints [Karande et al., 2013; Charles et al., 2013; Balseiro and Gur, 2019; Gao and Kroer, 2020; Chen et al., 2021a; Balseiro et al., 2021b; Conitzer et al., 2022a; Conitzer et al., 2022b], but Return-on-Investment (ROI), another widely adopted auto-bidding option, received much less attention until very recently [Golrezaei et al., 2021; Balseiro et al., 2021c; Deng et al., 2021]. For campaigns with ROI-constraints, advertisers should submit either a target ROI, a target Return-on-Ad-Spend or a target Costper-Action (tROI/tROAS/tCPA). 2 The objective of the autobidder is then to maximize the acquired value while keeping the average spend for each unit of value below the target threshold. ROI-constrained auto-bidders are dominating in market share in many regions of the world. There is also recent empirical evidence [Golrezaei et al., 2021] fromGoogle AdX that advertisers are indeed ROI-constrained.

1 In November 17, 2021, Google moves the AdSense auction for Content, Video, and Games from second price auction to first price, while keeping Search and Shopping as before [Google, 2021].

An advertiser's value for an ad slot (to which we will refer as a generic good throughout the rest of the paper) is typically given by the product of the conversion-rate (predicted by the platform) and the value of each conversion. For ROIconstrained campaigns, the latter part is the amount of money that the advertiser is willing to pay the platform for each (unit of) conversion. 2 Truthful bidding for each individual auction is ex-post optimal for non-constrained quasi-linear utility-maximizing bidders. But for ROI-constrained valuemaximizers, it is possible to raise bids above values to win more while keeping the average spend of each conversion below the threshold. In this paper, auto-bidders will take values as given and be restricted to the multiplicative pacing strategy, 2 wherein the bids of each bidder could only be generated through scaling the values for all goods by a common multiplier of its choice. There is always a multiplier that is expost bidder-optimal in second price auction, and the strategy is one of the most implemented in the industry regardless of auction formats (in particular, it remains popular in first price auction 3 ).

Table 1 positions our market model within the growing literature on auto-bidding. Existing works differ in the modeling of advertisers' valuations and utilities. Traditionally the valuation of each bidder is modeled as being drawn from a stochastic process independently of each other. We adopt a framework first studied by Conitzer et al. [2022b; 2022a], where the valuation is given as the (fixed) input and can be viewed as a discretized density function or a realized sample of an arbitrary joint distribution. In particular, the correlation prevalent in advertising can thus be captured. For utilities, previous research mainly focuses on budgetconstraints, and our paper complements the recent line of work on ROI-constraints. Babaioff et al. [2021] also consider ROI, but they model bidding behaviors with respect to the marginal ROI of each individual auction rather than the average ROI across.

Deng et al. [2021] and its follow-up work [Balseiro et al., 2021a] study a model that largely coincide with ours. Their goal is to design mechanisms having revenue and welfare guarantees when the designer has fairly accurate signals on the valuation. Though we will also report some results on revenue and welfare, we emphasize that, for today's large scale auto-bidding systems, auction (combined with auto-bidding strategies) acts more like an efficient distributed algorithm to match demand with supply and compute market-clearing prices. With this mentality, our work covers a broader range of properties and focuses heavily on their possible practical impacts on advertisers and platforms. We also differ in the adopted solution concept. We allow fractional allocation and incorporate the tie-breaking rule into the solution concept, which is not only well-motivated, but also guarantees the existence of equilibrium even though the market is discrete and discontinuous. In contrast, Balseiro et al. [2021a] break ties lexicographically and more complex auctions like VCG and GSP are considered there. So they choose a weaker solution concept called undominated bids and avoid the discussion of existence. Nonetheless, this distinction diminishes for large markets as the result of a single auction becomes negligible.

2 See Appendix B for more notes on terminology.

3 Possibly surprisingly, we will show in Section 6 that it will not bring incentive issues for first price auction and it is in the interests of a platform to enforce so. In contrast, both bidders and sellers have incentives to deviate from it in second price auction (Appendix J.3).

Auto-bidding or RTB algorithms have been studied for a long time. Such works typically assume a stationary environment and optimize various objectives for a single advertiser. They fail to capture other bidders' responses invoked by the action of the focal agent, and the resulting equilibrium outcome may not fulfill the initial design goal if all the bidders implement the same strategy (see, e.g., Appendix L.1). One notable exception is the work by Aggarwal et al. [2019], who were aware of this problem and tried to prove the existence of an equilibrium. But their treatment of equilibrium is incomplete (see a discussion in Appendix C).

Researchers have shown that the computation of equilibrium bears some inherent hardness with budget-constrained multiplicative pacing bidders. For computing any equilibrium, we improve previous result to show that it is PPADhard to approximate within constant parameters (for budgetconstraints, it was shown to be hard to approximate within polynomially small parameters [Chen et al., 2021a]). Our result is built on a more concise reduction quite distinct from the previous one. We also improve the NP-hardness result of optimizing revenue/welfare [Conitzer et al., 2022b] to APXhardness. Moreover, the source of these hardness and the vulnerabilities of IC are demonstrated more clearly with our constructions, which we believe could help both researchers and practitioners better extrapolate our techniques and insights.

1.2 Single-round Incentive Compatibility

The classic revelation principle ensures us that, when designing single-item auctions, any implementable allocation rule could be implemented in an incentive compatible way by directly eliciting bidders' private information (in most cases only the valuations to the item to be sold are needed). By focusing on IC mechanisms, the designer loses nothing while bidders could be prevented from strategic behaviors. In comparison, the characterization and computation of equilibrium in first price auction is notoriously hard (see, e.g., [FilosRatsikas et al., 2021] and the survey therein).

Though second price auction is only IC for single-item auctions, it possesses another fascinating property in autobidding markets: from a single bidder's perspective, each individual auction comes with a winning price independent of its own bid (which is essentially an equivalent statement of IC). As a consequence, the (ex-post/offline) task of each autobidder is a linear program for bidders with linear constraints like ROI and budget. The optimal solution can be well approximated by the multiplicative pacing strategy, which is simple to implement and performs well even in the online setting [Balseiro and Gur, 2019; Balseiro et al., 2022]. This provides second price auction an illusory strategyproofness that could be called ex-post IC: every advertiser could truthfully report its tROI and happily accept the equilibrium bids given by its proxy auto-bidder as deviating unilaterally will not bring extra profit at the moment.

Nonetheless, even long before the advent of the autobidding era, experiments have revealed that bidders' behaviors in second price auction are far from truthful (see, e.g., [Kagel and Levin, 2011]). Recall that, in second price auction, the price is set by the runner-up, but paid by the winner. In some senses, both the winner and the runner-up care little about the absolute magnitudes of their own bids: only the ranking (first and second) is important. This can also be seen from the linear program optimizing utility for the auto-bidder (see, e.g., [Aggarwal et al., 2019]), where no decision variable denoting bids appears and the solution only prescribes whether each auction should be won or not. However, the bid of the runner-up always means a lot to the winner. A wellknown enemy of IC due to this runner-up-winner interdependence is externality, i.e., the utility of a bidder depends on the allocation and payment of not only itself, but also others.

It should not be surprising that externality makes manipulation worthwhile since IC is not designed for the job. In our auto-bidding markets, the objective of each auto-bidder is defined clearly without externality. 4 However, auto-bidders adjust bids based on the overall performance across all auctions. Even though at equilibrium changing bids unilaterally could not benefit the manipulator immediately, it may trigger a cascade of responses that shift the whole market state. This creates a kind of externality that is internalized into the outcome of the shifted equilibrium. It is worthwhile to point out that, for some results in this paper, it seems to be the multiplicative pacing strategy that leads to a property. Actually it is irrelevant of the specific bidding strategy or even the ROI-constraint: for simultaneous auctions with single-round IC, bidders will always bid strategically across all auctions, 5 which is enough to establish those results.

4 Another common scenario where IC fails is that bidders do not have complete knowledge of their valuations. This is not an issue either in our case.

Letting the (bids of) opponents determine the payment of the winner is the key to establish IC for single-item auctions, but it is also the key to open the Pandora's box in auto-bidding markets, as will be detailed in the remainder of this paper.

1.3 Contributions

In this paper, we consider the auto-bidding market where ROI-constrained value-maximizing bidders compete with each other in simultaneous auctions. Our main focus is second price auction: behaviors of auto-bidders within first price auction markets will be discussed at the very end.

We start by formulating our own solution concept of the market (and its approximate version), named auto-bidding equilibrium, since a pure Nash equilibrium may not always exist. The equilibrium reasonably captures the expected steady-state that the auto-bidders intend to reach collectively, and its guaranteed existence puts our study on a solid theoretical footing. Our most important results are as follows:

• It is PPAD-hard to find an approximate auto-bidding equilibrium within constant parameters.
• It is APX-hard to optimize revenue or welfare over all auto-bidding equilibria.
• Non-monotonicity: an advertiser who raises its tROI/tROAS (or equivalently, lowers the tCPA) at the equilibrium could end up with a higher revenue after deviation (through a natural equilibrium transition process to resolve multiplicity).

Besides their own significance, the constructions used in establishing these results reveal many crucial structures of the market and highlight the role played by IC. They serve as the foundation to comprehend and interpret other characteristics of the market.

We proceed to explore several practical concerns of great consequence. For advertisers, we show that the market suffers severe utility instability and input sensitivity issues. For platforms, we demonstrate that biases exist broadly in the widely-used A/B testing. Finally, we give a comprehensive comparison between first and second price auction, and show that first price auction is generally exempted from the above undesirable properties and performs better. As an application of our results, we give our guess about why Google AdSense moves from second to first price auction in a partial manner.

5 Even a non-constrained utility-maximizer could manipulate if one of its opponents has constraints. Truthful reporting is secure only when all the other bidders are insensitive to each other's bid.

2 Markets and Equilibria

We consider a market where a set of bidders N = {1, . . . , n} compete for a set of divisible goods M = {1, . . . , m}. Without loss of generality, the tROIs of all bidders are set to zero (equivalently, tROAS of one), 6 i.e., each bidder's spend should be no more than its acquired value. We use vi,j to denote the value of bidder i to good j. For each good j, there is at least one bidder i such that vi,j > 0. The platform simultaneously runs a single-item second price auction for every good. Auto-bidders are restricted to apply multiplicative pacing strategies: the action space of bidder i is the set of undominated multipliers αi ∈ [1,A], 7 and its bid for good j is αivi,j. Multiplicative pacing is ex-post bidder-optimal, as shown in Proposition 1. The omitted proof follows from a linear programming formulation of the ROI-constrained value maximization problem, and the result is widely known in both the literature and the industry.

Proposition 1. Suppose that bidders can bid arbitrarily across auctions. Holding all other bidders' bids, each bidder has a best response wherein bids are generated by scaling its valuations of all goods by a uniform multiplier, given that it could freely choose to win any fraction of a good of which it is a tied winner.

To complete the picture, one's first intuition may be to specify a tie-breaking rule, make the allocation x ∈ [0, 1]n×m (where xi,j is the fraction of good j allocated to bidder i) uniquely determined by α, define bidder's utility as the ROIconstrained valuation:

and study the pure Nash equilibrium (PNE) of the game. However, in Appendix D, we will give an example where, no matter how ties are broken, a PNE does not exist. On closer inspection, we find that the steady-state of the market can be captured instead by the solution concept defined below.

Definition 1. An auto-bidding equilibrium (α, x) consists of multipliers α ∈ [1,A]n and allocation x ∈ [0, 1]n×m such that

• bidders with the highest bid win the good: if xi,j > 0, αivi,j =maxk αkvk,j for all i, j;
• winner pays the second price: if xi,j > 0, then pj = maxk̸=i αkvk,j for all i, j;
• full allocation of goods: ∑i xi,j = 1 for all j;

6 See Appendix D on why this is WLOG. Later we may sometimes change the tCPA of a bidder by a factor λ, by which we mean all the valuations of this bidder is scaled by λ.

7 Fixing other bidders' bids, αi = 1 always weakly dominates any αi < 1. The cap A can safely be replaced by +∞ for most cases. See more discussion in Appendix D.

• ROI-feasible: ∑j xi,jpj ≤ ∑j xi,jvi,j for all i;
• maximal pacing: unless αi = A, ∑j xi,jpj = ∑j xi,jvi,j for all i.

The auction rules and ROI-constraints are directly imposed by the first four conditions, while the best responses among bidders are encoded in the maximal pacing condition in a less straightforward way. To see this, note that, from bidder i's perspective, given the winning price of each good, αi acts as a marginal-ROI threshold: it will win all goods in whole with a marginal ROI strictly larger than 1 αi -1 and lose those with ROI strictly lower. At any auto-bidding equilibrium, if αi > 1, αi (and the resulting vector of bids with bi = αivi,j) is exactly a best response since the marginal ROI of any good lost or tied is strictly lower than zero, and winning anymore will definitely violate the ROI-constraint. If, however, αi = 1 and bidder i is only allocated a fraction of some good as in the example given in Appendix D, αi is technically not a best response (for the normal form game) but the maximal pacing condition is still satisfied. For such bidders, their opponents could always oscillate their multipliers around the equilibrium point to achieve the corresponding stable allocation.

Theorem 1. An auto-bidding equilibrium always exists.

The proof is in Appendix F. In addition, the definition and existence result can be extended to incorporate reserve prices and additive boosts (see Appendix E), both of which are common practice in the industry.

The relaxed version of the equilibrium, named (η, δ)- approximate auto-bidding equilibrium, is defined as follows:

• bidders with bids close enough to the highest can win the good: if xi,j > 0, αivi,j ≥ (1 - η)maxk αkvk,j (if there is a reserve price rj, winner's bid should also be no less than (1- η)rj);
• winner pays the second price (even if it is the bidder with the second highest bid; if there is a reserve price, the price is the maximum of the reserve price and the second price);
• full allocation of goods;
• approximately ROI-feasible: ∑j xi,jpj ≤ (1 + δ) ∑j xi,jvi,j for all i;
• approximately maximal pacing: unless αi = A, ∑j xi,jpj ≥ (1- δ) ∑j xi,jvi,j for all i.

3 Computational Complexities

In this section, we demonstrate two different kinds of intractability or unpredictability of the market. Our first result shows that, in general, it is hard for a market to reach a stable state. But even for cases where an equilibrium is easy to achieve, the difference among equilibria may be large, and the second result tells us that, in general, it is hard to determine how large the difference is.

At a high level, the interdependence that the (bid of) runner-up determines the payment of the winner endows the market with a structure similar to Boolean operators (electronic components and conductive wires). In digital electronics, a functionally complete set of operators can be assembled to compute any Boolean function. In our model, it is PPADhard to find an equilibrium since it can encode any stable state of a circuit that is continuous. When optimizing revenue or welfare, the circuit structure collapses to discrete choices that correspond to equilibrium selection, and the problem becomes NP-hard (and APX-hard since the correspondence is almost exact). Note that hardness does not only exist in the family of instances constructed in the reduction: for a generally hard problem, it is possible but usually non-trivial to identify a meaningful subset of instances that are computationally tractable.

Our focus here is the many complex structures brought into the market by IC. Nonetheless, to explore equilibrium properties quantitatively, we develop two algorithms (see Appendix I for details) to compute equilibrium. Their own properties are beyond the scope of this paper.

3.1 Complexity of Finding Any Equilibrium

Theorem 2. It is PPAD-hard to find an (η, δ)-approximate auto-bidding equilibrium for some constant η, δ > 0.

The full proof is in Appendix G. We will use equilibria in a properly constructed market to encode feasible states of a circuit, which is one of the most fundamental and frequently used objects in complexity theory [Chen et al., 2009; Rubinstein, 2018]. Papadimitriou and Peng [2021] show that a circuit consisting only of a continuous version of NAND (NOT-AND) gate is enough to capture PPAD-hardness, in analogy to the functional completeness of NAND gate in digital electronics. The continuous gate computes the function that sums all (at most 3) inputs and inverts the result: for a gate u, given all the input values yw of its incoming gates w ∈ Nu, its own value yu should satisfy that

An assignment y of values to gates is feasible if the above constraints are satisfied for all gates. The key construction of our reduction is given in Table 2. (This is a simplified version: in the full proof we will remove the reliance on reserve prices and take approximation into account.) We will associate each gate u with a bidder of the same name and use its multiplier αu to encode the gate's value yu (with yu = αu/2 - 1). The valuation profiles are calibrated such that bidder u would always win all input goods w1,w2,w3 but at varying prices, determined by (multipliers of) their corresponding input bidders. The correspondence between bidder u and gate u is almost straightforward:

• If the sum of input prices is too high, to satisfy its ROIconstraint, bidder u could not even win good u in whole and thus won't raise αu above 2.
• If the sum is too low, good ¯u is required to satisfy bidder u's appetite for more valuation, which forces αu to be fixed at 4.
• If input prices sum to exactly 0.5, bidder u can freely choose αu as long as it is allocated u in whole but not ¯u at all.

Intuitively, the hardness of finding a feasible state of a circuit lies in the coordination among the interconnected gates. Given any value assignment, for each unsatisfied gate u, the corresponding αu in the constructed market is either too large (input goods are too expensive and ROI-constraint is violated) or too small (input goods are too cheap and bidder u has the incentive to win ¯u). Consider hypothetically that we apply a naive search algorithm 8 where, for each non-equilibrium assignment y, we choose some unsatisfied u, lower αu by a small amount if it is too large, and raise it if it is too small. As we adjust αu (or yu) for a bidder (gate), the payments (sums of inputs) of its outgoing neighbors change accordingly, which may also change their directions of adjustment (e.g., a bidder goes from ROI-feasible to infeasible). As gates can be assembled arbitrarily, we can imagine how hard it is to find a state that satisfies the constraints of all bidders/gates.

In retrospect, IC requires the payment of the winner to be determined externally by other bidders. As a result, nothing is local in the market and we can connect bidders in a way that encodes any circuit perfectly. You may think that the market constructed in the reduction can be simplified, e.g., by setting a reserve price for the input good such that its price would no longer be affected by the input bidder and an equilibrium could be easier to find. However, this requires much knowledge of the specific market a priori such as an upper bound of a bidder's multiplier, which is typically impossible. In general markets, the aforementioned chasing behavior is even more complex: e.g., if a gate bidder lowers its multiplier, the consequence is simply lowering payments for its outgoing neighbors and increase their ROIs, but in general markets it may also lose goods it previously won and instead decrease ROI for the opponent who now wins the item with a negative marginal ROI. See the non-monotonicity instance in Section 4 for an example of this complex cascading phenomenon.

3.2 Complexity of Finding Revenue orWelfare Optimal Equilibrium

Theorem 3. It is APX-hard to find the optimal revenue or welfare over all auto-bidding equilibria.

8 Theoretically, any problem in PPAD can be reduced to the generic End-Of-The-Line problem (by which the class is defined), where we are given (1) a directed graph consisting solely of nonintersecting directed paths (lines) and (2) a vertex with no predecessor (the start of a line). The task is to find a vertex with no successor (the end of a line). There is a natural algorithm (inevitably inefficient if PPAD ̸= P) that simply searches along any path. The search procedure we depict here shares a similar spirit, but it may (or may not) circulate and is only used to give some intuition.

The full proof is in Appendix H. When dealing with optimization problems, besides encoding a feasible circuit state into equilibrium, we also need to relate the objective (revenue/welfare) of the market owner to one that is hard to optimize within the circuit. Interestingly, it is still the encoding of feasibility that reveals more distinctive structures of the problem. 9 The latter step only involves simple operations (max and sum) that are naturally embedded in the auction rules (winner pays the largest non-winning bid) and bidder's rationale (aggregating outcomes across all auctions).

The problem to be reduced is of discrete nature, and we will encode a 0-1 choice using equilibrium multiplicity as shown in Table 3. Here the market is symmetric in valuation but has equilibria that represents two extremes in allocation: bidder i (1 or 2) wins both good 1 and 2 with αi ≥ 2 and α-i = 1. There is another equilibrium where α1 = α2 = 2 and each bidder gets the good it values the most, which is natural, fair and revenue-optimal within the sub-market consisting of good 1 and 2. But we will see in the full proof that it is often advantageous for the seller to choose the asymmetric equilibrium as it frequently dominates the symmetric one in revenue of the whole market. The reason lies in the last column of Table 3: though bidder 1 and 2 will never win those goods, they are price-setters and it is usually profitable to enforce a high multiplier on one, rather than letting them share the sub-market fairly but both bid at a moderate level.

The reduction clearly demonstrates the "externality" created by IC: each pair of bidders in the sub-market characterized by Table 3 determines the clearing prices of some other auctions they will never win (though such knowledge is hard to acquire a priori in practice). On the other hand, if the seller is able to engage in the choice of equilibrium, it may favor those unfair outcomes that, though less profitable locally, could drive up revenue from goods outside these sub-markets. See Appendix J.2 and L for further discussion on externality among sub-markets and Appendix J.3 on how sellers could prevent those unwanted equilibria by actively elevating the bid landscape without breaking single-round IC.

4 Non-monotonicity

With auto-bidding built into the mechanism, advertisers are effectively playing a meta-game through reporting tROIs. In single-item first or second price auctions, raising one's bid will never decrease its winning probability. In real-world markets, advertisers also expect ROI monotonicity, i.e., lowering tROI/tROAS (raising tCPA) should bring them more valuation. Due to equilibrium multiplicity, however, it is not clear how to define utility functions for the advertiser game, let alone monotonicity. We avoid this technicality by examining a proper equilibrium transition process, from which we can see how the runner-up-winner interdependence triggers the chain reaction that is complex and counter-intuitive.

9 Here feasibility should be encoded in a way such that all the equilibria are known and easily enumerable. The hardness comes from finding the best (not any) one.

The deviation of the manipulator and the transition of equilibrium work as follows. At round 0, the manipulator i0 changes its tCPA to a fraction r < 1 of the original, resulting in a valuation profile v′ such that v′i0,j = rvi0,j, ∀j. Each bidder then applies an iterative method (see Appendix I.2) to optimize their utilities and collectively find the new equilibrium. The behavior of the algorithm is very intuitive: if the current ROI (aggregated over a moving window of recent rounds) is too high, lower the multiplier, and vice versa. To make the transition smooth, αi0 is divided by r right after the tCPA modification such that the fine-grained bids of the manipulator are kept unchanged at the moment.

The detail of the non-monotone example is in Appendix J.1. Here we give a high-level description of the process. At the old equilibrium, good 1 is the only good won by i0, and it is shared between i0 and another bidder i1. i0 initiates the dynamics by lowering αi0 , since its ROI-constraint is now violated after the update of tCPA. However, i1 does not want to win good 1 completely, otherwise its ROI-constraint will also be violated. So i1 lowers its multiplier as well, which further triggers the same behavior for bidder i2. As a result, i0, i1 and i2 reach an almost perfect coordination where the multiplicative ratios among their multipliers remain nearly constant all the way through the transition. There is another bidder, i3, who pays less due to the lowered second prices set by i0, i1 and i2. Therefore it tries to win more goods by gradually raising its multiplier. During the process, i2 and i1 pay more for goods whose second prices are set by i3, and thus they have to give up goods of which they are one of the tied winners (these goods have the lowest marginal ROIs): i2 gives up good 2 to i1, and i1 wins more good 2 but loses good 1 to i0 to balance its deficit, which contributes to the success of the manipulation of i0. In the end, i3 takes a fraction of good 2 away from i1 to bind its ROI-constraint, and i1 compensates this by taking a fraction of good 1 from i0. Nonetheless, i0 still benefits from lowering its tCPA.

5 Practical Properties of the Market

5.1 Utility Instability for Advertisers

Besides high-quality value estimation and bid optimization, platforms are also trying to serve many other needs of their clients, among which utility (i.e., the total acquired value) stability stands out because (1) advertisers expect a smooth experience, and more importantly (2) utility is the most prominent feedback on how successful their advertising campaigns are. As a result, utility instability may bring confusions and put many good campaigns at the risk of being forfeited prematurely. Our experiments (see Appendix K.1) show that, in markets generated from several different stochastic processes, a large utility gap between the worst and the best equilibrium for an advertiser is quite often to be observed, and it is fairly common that an advertiser wins nothing in some equilibrium but acquires a significant positive value in others. The gap seems to reduce for thicker markets, but large-scale realistic instances suffer another type of instability: sensitivity to input valuations (see Appendix K.2).

Instability differs in degree market-by-market and we will give more analysis in Appendix K.3. To get a basic idea, consider a two-bidder market that is symmetric in the sense that goods appear in pair, of which one is valued v1 and v2 and the other is valued v2 and v1 by bidder 1 and 2, respectively (note that the key construction in the proof of APX-hardness shares a similar structure). There is always an equilibrium where bidder 1 wins all goods, and one where bidder 2 wins all. Depending on specific valuation profiles, there may also be many intermediate ones. From a dynamic point of view, committing a higher multiplier would make the opponent pay more, and the bidder who quits the price war first would lower its multiplier to satisfy its ROI-constraint (and also the opponent's) but lose the market share.

In addition, the above prototypical example distinguishes two sources of instability: an intensely competitive landscape and the IC property. First price auction also suffers highsensitivity if it holds for a large percentage of goods that the values of top bidders are extremely close. However, in first price auction, competition is local and direct, i.e., bid or value perturbations only affect the auctions in which they happen. But in second price auction, any fluctuation will propagate to the whole market through the runner-up-winner interdependence and the impact is more widespread and unpredictable.

5.2 Interference in A/B Testing for Platforms

A/B testing is an indispensable tool to evaluate new technologies and assist business decisions. In a typical setup, users in experiment are randomly assigned to either a treatment or a control variant (e.g., different reserve pricing strategies), and metrics are aggregated within each group to compare and see which variant is better. The same idea can also be applied to randomize advertisers. An ideal experiment requires the Stable Unit Treatment Value Assumption (SUTVA) to hold, which generally means that there should be no interference between the treatment and the control group. Ad-side experiments (regardless of auction formats) clearly violate SUTVA since all ads compete for the same set of goods, and user-side violation (in non-auction scenarios) is also common in practice. We show empirically that an unpredictable 10 bias exists broadly in naive implementations of both user-side and adside A/B testing in second price auction markets. The bias comes from the fact that bidders' behaviors in the (counterfactual) A/A, A/B and B/B tests are all different. Experiment details and more discussion can be found in Appendix L, where we also propose a simple approach to discerning biases and designing less-biased experiments.

10 It is known that A/B testing in two-sided markets suffers from cannibalization bias [Blake and Coey, 2014; Liu et al., 2020], which often enlarges the estimated advantages of the better variant. Such a bias may actually increase the experimental power since practitioners care more about whether a treatment is better, rather than how much better. In contrast, the interference introduced by IC is complex and it may lead to wrong decisions easily.

6 First Price Auction versus Second Price Auction: Within and Beyond Auto-bidding

With first price auction, no auto-bidding is needed and the platform simply allocates goods to bidders with the highest (tROI-discounted) valuations, which are also charged as payments. The best possible revenue (see Appendix J.3) is naturally achieved. Quasi-linear utility makes no difference for advertisers and it is a dominant strategy to report their tROIs truthfully. Even if they prefer spending less with the same acquired value, the incentive to deviate diminishes as the market becomes thicker. 11 First price auction does not provide advertisers an ex-post optimal outcome. However, advertisers should happily accept it since it is still fair/envy-free as it relates closely to the classic competitive equilibrium in Fisher markets (see Appendix N).

Besides revenue-optimality, strategyproofness and fairness, first price auction also dominates in almost all the other aspects studied in this paper: (1) market outcome is unique; (2) computation is straightforward; (3) ROI-monotone; (4) no interference among sub-markets; (5) competition is direct and local; even if the competition is so intense that the utility becomes unstable, it can easily be smoothed by actively applying small perturbations or probabilistic allocations [Borgs et al., 2007]. It shares with second price auction the problem of biases in ad-side A/B testing since it is rooted in the setup itself, irrelevant to auction formats. Budget-constrained markets share similar results [Conitzer et al., 2022a]: (1) the equilibrium is unique; (2) computation is convex and tractable; (3) budget-monotone. Since budget should still be paced, there remains interference among sub-markets and the competition is less direct than within ROI-constrained markets. Nonetheless, with first price auction, the market is convex and more predictable, in contrast to the complex combinatorial structure of second price auction that is difficult to deal with.

In Appendix O, we extrapolate from our model to the case where advertisers may submit tROIs for several different submarkets (e.g., via targeting in practice). We argue that, if optional sub-markets are coarse-grained and advertisers do not have enough knowledge to differentiate them, the market could still be well captured by our model and first price auction mostly retains the upper hand. As an application of our results, we also give our guess on why Google moves from second to first price auction for only Content, Video and Games, but not Search and Shopping.

7 Conclusion

In this paper, we study a model that abstracts several most influential features of present auto-bidding markets. We try our best to pinpoint how the IC property contributes to every theoretical or empirical phenomenon such that readers could better extrapolate our results. We hope that our work could bring new perspectives to the community, and inspire practitioners to pay closer attention to the IC property and attain a better grasp of real-world markets.

11 This technically deviates from our model. Rigorous treatment is given in Appendix M.