Auctions without commitment in the auto-bidding world

Aranyak Mehta, Andres Perlroth¹¹footnotemark: 1 Google, {aranyak,perlroth}@google.com

Abstract

Advertisers in online ad auctions are increasingly using auto-bidding mechanisms to bid into auctions instead of directly bidding their value manually. One of the prominent auto-bidding formats is that of target cost-per-acquisition (tCPA) which maximizes the volume of conversions subject to a return-of-investment constraint. From an auction theoretic perspective however, this trend seems to go against foundational results that postulate that for profit-maximizing (aka quasi-linear) bidders, it is optimal to use a classic bidding system like marginal CPA (mCPA) bidding rather than using strategies like tCPA.

In this paper we rationalize the adoption of such seemingly sub-optimal bidding within the canonical quasi-linear framework. The crux of the argument lies in the notion of commitment. We consider a multi-stage game where first the auctioneer declares the auction rules; then bidders select either the tCPA or mCPA bidding format (and submit bids accordingly); and then, if the auctioneer lacks commitment, it can revisit the rules of the auction (e.g., may readjust reserve prices depending on the bids submitted by the bidders). Our main result is that so long as a bidder believes that the auctioneer lacks commitment to follow the rule of the declared auction then the bidder will make a higher profit by choosing the tCPA format compared to the classic mCPA format.

We then explore the commitment consequences for the auctioneer. In a simplified version of the model where there is only one bidder, we show that the tCPA subgame admits a credible equilibrium while the mCPA format does not. That is, when the bidder chooses the tCPA format the auctioneer can credibly implement the auction rules announced at the beginning of the game. We also show that, under some mild conditions, the auctioneer’s revenue is larger when the bidder to uses the tCPA format rather than mCPA. We further quantify the value for the auctioneer to be able to commit to the declared auction rules.

Keywords: Auto-bidding, Auction Design, Mechanism Design, Credible mechanisms, Equilibrium, Economics

1 Introduction

Over the past several years, advertisers have increasingly started to use auto-bidding mechanisms to bid in ad auctions instead of directly bidding their value manually (e.g., bidding per keyword in sponsored search). Among the prominent bidding strategies that have been adopted is the target cost per acquisition (tCPA) strategy (see, e.g., Google [2022], Facebook [2022]) where the goal is to maximize the volume of conversions aka acquisitions, subject to an upper bound on cost per conversion¹¹1A related strategy, target return-on-ad-spend (tROAS), maximized conversion value subject to a bound on the cost per value. Our results for tCPA extend naturally to tROAS as well..

From an auction theoretic perspective however, this trend seems to go against foundational results that postulate that for profit-maximizers (aka quasi-linear) bidders, it is optimal to use a classic bidding system (e.g., marginal CPA bidding, henceforth mCPA) rather than using a tCPA. In other words, for an advertiser with a quasi-linear utility functional, it is optimal to bid the marginal value in a truthful auction, while with tCPA bidding, an advertiser does not allow for a direct control over the marginal cost. So a natural question to ask is whether there is an intrinsic value for profit-maximizing bidders in using tCPA format? Put simply, why do advertisers adopt tCPA bidding?

One explanation given for the use of tCPA-like bidding formats is that in many cases bidders may not be intrinsically profit-maximizers which is the classic assumption in economics, but instead care about high-level goal metrics, such as value maximization under return-of-investment constraints (Aggarwal et al. [2019], Balseiro et al. [2021b]). Another related explanation is that the cognitive cost to bid and verify the outcome using tCPA-like formats is low compared to other methods like fine-grained bidding or mCPA.

In this paper, instead of reconsidering the profit-maximization framework, we show that even within this canonical framework we can explain the adoption of formats like tCPA bidding under a certain model and setting. In other words, the paper rationalizes profit-maximizers bidders adopting tCPA mechanisms. We show that so long as a bidder believes that the auctioneer lacks commitment to follow the rule of the declared auction (e.g., readjusts reserve prices after bidders submit their bids), then the bidder prefers to use the tCPA format over the classic mCPA format.

Model: In our model (Sec. 2 for details), there is a set of queries (ad slots) to be sold, and there is a single-shot game between the auctioneer (auctioneer) and the bidders (advertisers). The auctioneer declares that the auction is a per-query second-price auction with a declared reserve-price, and then the bidders choose a bidding format (whether tCPA or mCPA) and corresponding bids. After this, the auctioneer could then potentially deviate from the declared auction by readjusting the reserve prices, at potentially a per-query, personalized-per-bidder level. Finally, the outcomes are revealed.²²2We note that our model is oblivious to the particular auto-bidding algorithms that auto-bidder uses so long as the optimal outcomes are reached.

Prominent in our formulation is the notion of commitment. In a model with commitment we assume that there is some mechanism by which the bidders can trust that the auction declared by the auctioneer will indeed be the one that is implemented. This is the standard model and assumes that there is some form of auditing available. In contrast, in a model without commitment, there is no such mechanism or guarantee, and both the auctioneer and the bidders strategize their actions.

Results: At a high level, our main result is that if a bidder believes the auctioneer does not have commitment, then it prefers to use the tCPA bidding format over the mCPA format. ³³3While our model is in a single-shot game, we note that even in the context of repeated interactions where a bidder can monitor the outcome of the auctions over time, our theory can still directionally explain why some bidders may still prefer a tCPA-format. For example, when a bidder is risk-averse about the auctioneer breaking commitment (e.g., bidder expects the auctioneer to slightly change the auction rules which cannot be observable for the bidder); or for a less-sophisticated bidder to whom is too costly to monitor their outcomes.

We begin (in Sec. 3) with a basic setting which captures much of the intuition and results in an instructive manner. We consider a model in which there is only one buyer in the auction facing an exogenous price landscape for the queries, e.g., a per-query floor set by the publishers who own the corresponding ad slots. In this model, we are able to derive not only the main result that the bidder prefers tCPA bidding (Theorem 1), but also sharp results about the revenue implications for the auctioneer. We prove that there is a credible equilibrium (as defined in Sec. 3) in which the auctioneer declares a reserve price of 0, and sticks to it, while the bidder chooses the tCPA format. Under a mild assumption, this equilibrium is also shown to be beneficial to the auctioneer in terms of revenue as well as efficiency (Theorem 2).

We further study the case where the auctioneer has commitment to a reserve price, but the bidder mistakenly believes it doesn’t. We show that, in this case, there is an instance where the revenue loss can be arbitrarily large (Prop. 9).

We continue to the general model with multiple bidders in Sec. 4. While we are able to solve for the equilibrium in the model of Sec. 3, solving the tCPA equilibrium in the general model with multiple bidders is hard,⁴⁴4Aggarwal et al. [2023] show that it is PPAD-hard to find an equilibrium when there are multiple tCPA bidders. and studying the auctioneer’s revenue implications seems intractable. Nonetheless, we show that a profit-maximizing bidder who believes that the auctioneer does not have commitment prefers the tCPA format to mCPA format (Theorem 3). Our result heavily relies on the auctioneer’s flexibility to readjust reserve prices at a per-query and bidder level reserve. For instance, when the set of queries is too large so readjusting at the query level is too expensive, the auctioneer is constrained to set reserve prices uniformly across queries. For this situation, we provide a companion result showing that under some technical assumption on the symmetry of the game (defined in Sec. 4), that again a bidder prefers the tCPA format over the mCPA format (Theorem 4).

Intuition: To understand the intuition of our main result, that a bidder prefers the tCPA format over the mCPA format, let us decompose the auctioneer’s objective – to maximize revenue – into two elements: the volume of queries the auctioneer sells and the price at which the queries get sold. These two components translate into two economic forces that the auctioneer considers at the moment of readjusting the reserve prices: (i) to induce a high marginal bid from the bidder (so to increase the volume of queries sold) and (ii) to set a reserve-price on the queries as closed as possible to the bidder’s marginal bid. Observe that force (i) is aligned with bidder’s incentive while force (ii) goes in the opposite direction in regard to the bidder’s utility.

In the mCPA format, force (i) disappears as the marginal bid is chosen by the bidder. Thus, the auctioneer’s incentive in the no-commitment game is simply to price at the marginal bid.

In the tCPA format, as the marginal bid is not fixed but rather is chosen by the auctioneer (given the cost per acquisition constraint), force (i) does not disappear, and hence, it mitigates the second force effect on the bidder’s utility. This makes the bidder’s utility higher in the tCPA compared to the mCPA format⁵⁵5In the specific model of Sec. 3, we show that the former force completely dominates the latter, and the incentives of the auctioneer and the bidder are completely aligned..

Remark 1 (On interpreting the results).

Our model is that of a stylistic single-shot interaction between the two parties. There are some marketplaces, including ad auctions, where there is a repeated interaction between the bidders and the auctioneer that alleviates the commitment problem that we study here. For example, with transparent reporting and avenues for experimentation, a bidder can monitor and verify or audit the auctioneers actions and commitments over time even with the mCPA format. Furthermore, in practice, there exist certification processes and third-party audits such as Sarbanes-Oxley (SOX) compliance. Such audits are another method for bidders to have confidence that real-word auction systems are behaving as described. We do not consider the repeated setting in this paper, nor the considerations of audits as a commitment device.

1.1 Related Work

With the importance of auto-bidding in the industry, the topic has become of increasing interest in the literature. In a series of papers, the problem of formulation of tCPA-like auto-bidding formats has been introduced and studied in various aspects. Aggarwal et al. [2019] introduced an optimization framework for auto-bidding, provided optimal bidding algorithms, and also studied the price of anarchy, i.e., the loss in efficiency due to tCPA-like bidding, which was further explored in subsequent work [Deng et al., 2021, Liaw et al., 2022, Deng et al., 2022, Balseiro et al., 2021a, Mehta, 2022]. There has also been recent work on understanding the optimal mechanism design in Bayesian settings Golrezaei et al. [2021], Balseiro et al. [2021b] for ROI constrained bidders. The above papers consider the advertisers as having non-standard ROI utility functions in the main; Balseiro et al. [2021b] explicitly distinguish between utility functions which are volume maximizing (ROI) versus profit maximizing. These works do not consider the question of how to rationalize the use of the tCPA format, but rather study additional consequences and auction design given an exogenous choice of the format. We can interpret our work as endogenizing the choice of format within the larger context between auction and bidding.

We mention that in a sense tCPA auto-bidding generalizes the more well-known budget constrained or financially-constrained model. This has been a very well studied topic with several lines of work studying this model, both from a fundamental perspective, and in the context of ad auctions, e.g., Laffont and Robert [1996], Che and Gale [2000], Feldman et al. [2007], Balseiro and Gur [2019], Gaitonde et al. [2023], Fikioris and Tardos [2022] among many others.

From an auction design perspective, our paper relates to three streams of the literature. The closest papers to our work consider a mechanism design problem with imperfect commitment where the auctioneer (designer) can readjust the rules after observing the agent’s report. Bester and Strausz [2001, 2000]. Our paper differs from those previous results in that we study a multi-item problem (multiple queries) and focus on two main auction rules rather than a general mechanism design approach.

Related to the first stream, Akbarpour and Li [2020], Daskalakis et al. [2020], Ferreira and Weinberg [2020] study the auction rules that are credible. That is, from the auctioneer’s perspective, it is optimal to follow the rules of the declared auction. We contribute to this field by showing that, under some conditions, the tCPA-mechanism is a credible mechanism for the multi-item cases (see Prop. 6).⁶⁶6Daskalakis et al. [2020] also construct a credible auction mechanism with good revenue guarantees.

The third stream of papers study dynamic auctions where the auctioneer cannot commit to the auction that she will choose in future periods Gul et al. [1986], Fudenberg and Tirole [1983], Skreta [2015, 2006], Liu et al. [2019]. These papers show that without commitment the auctioneer cannot obtain a revenue larger than the revenue from the efficient auction. While our work does not consider repeated auctions, our results also show that, under some circumstances, the lack of commitment limits the auctioneer revenue to the efficient outcome (see Prop. 6).

2 Model

Our model considers a platform (henceforth, the auctioneer) using a second price auction to sell $x\in X$ queries, where $X$ belongs to a measurable space $(X,\mathcal{A},\mu)$ . Because our goal is to study the buyers’ behavior under different auto-bidding mechanisms, we fix one of the buyers, henceforth the bidder, and assume that she has a private valuation $v\sim F$ for each query.

From the bidder’s perspective, the cost per conversion on query $x$ , $p(x)$ , has two components: the intrinsic value of the query, which is given by $p_{0}(x)$ and the reserve price $r$ chosen by the auctioneer.⁷⁷7We assume that the intrinsic value $p_{0}:X\to\mathbb{R}_{+}$ is measurable function. This intrinsic price function is quite general to include the case where the pricing comes from other buyers participating in the auction as well as pricing constraints set by the publisher (see Sec. 4 for more details).⁸⁸8Our main result also includes the case where $p_{0}(x)$ may be unknown to the bidder. Therefore, the bidder’s payoff when she buys the queries with prices lower than $p$ is

u(p|v)=\begin{cases}0&\mbox{ if }p<r\\ (v-r)H(r)+\int_{r}^{p}(v-z)dH(z)&\mbox{ if }p\geq r\end{cases},

where $H(p)=\mu(\{p_{0}(x)\leq p\})$ is the volume of queries with intrinsic price less than $p$ .

We impose the following regularity condition on $H$ .

Assumption 1.

The price distribution $H$ is an integrable function (i.e., $\int_{0}^{\infty}H(z)dz<\infty$ ) and is continuously differentiable with $h(p)=H^{\prime}(p)>0$ (positive density).

2.1 Auto-bidding mechanisms

In order to bid for the queries $X$ , the bidder has to choose among the different auto-bidding mechanisms the auctioneer offers to her. We consider two representative and commonly-used mechanisms.

Marginal CPA: The bidder submits a bid $b\in\mathbb{R}_{+}$ and the auto-bidding system bids $b$ , on her behalf, on each of the queries $x\in X$ . Thus, when the bid $b>\max\{r,p_{0}(x)\}$ the bidder receives query $x$ for a price $\max\{r,p_{0}(x)\}$ . We conclude that the bidder’s payoff is

u(b|v;\mbox{mCPA})=\begin{cases}0&\mbox{ if }b<r\\ (v-r)H(r)+\int_{r}^{b}(v-z)h(z)dz&\mbox{ if }b\geq r\end{cases}.

TCPA: The bidder submits a target cost per acquisition $T\geq 0$ , and the auto-bidding system bids $b(T)$ in each of the queries $x\in X$ so that it maximizes the volume of queries subject to the average cost being no more than $T$ . Thus, for $T>r$ we have that

	$\displaystyle b(T;r)\in\arg\max\Big{\{}$	$\displaystyle H(b(T;r))\|\mbox{ s.t. }rH(r)+$		(1)
		$\displaystyle\int_{r}^{b(T;r)}zh(z)dz\leq T\cdot H(b(T;r))\Big{\}}.$

The following lemma, whose proof is deferred to the appendix, shows that the above problem has a unique solution and the tCPA constraint is always binding.

Lemma 1.

There is a unique solution $b(T;r)$ to Problem (1) which is the unique solution to equation

H(b)(b-T)=\int_{r}^{b}H(z)dz.

(2)

Furthermore, for $T\geq r$ , $b(T;r)$ is greater or equal than $T$ , increasing in $T$ and decreasing in $r$ .

From Lemma 1, we observe that given a target $T\geq r$ , the bidder pays $TH(b(T;r))$ for the $H(b(T;r))$ queries she receives. We conclude that the bidder’s payoff is

u(T|v;\mbox{tCPA})=\begin{cases}0&\mbox{ if }T<r\\ (v-T)H(b(T;r))&\mbox{ if }T\geq r\end{cases}.

2.2 Credibility and commitment

To model the auctioneer’s credibility we consider the following four-stage game.

(S1)

Announcement: the auctioneer announces a reserve price which applies for all queries $x\in X$ .
(S2)

Bidding: the bidder chooses an auto-bidding mechanism and submits the bid to the auto-bidder, either marginal or target, accordingly.
(S3)

Credibility: the auctioneer potentially readjusts the reserve price, at a per-query and advertiser level.⁹⁹9We restrict the auctioneer to use reasonable mechanisms where it can only modify reserve prices or bids (from competitors), similar to the model studied in Akbarpour and Li [2020].^,¹⁰¹⁰10For the one bidder model of Sec. 3, it suffices to restrict to uniform readjustment of the reserve across all queries.
(S4)

Auction is realized: The auto-bidding system makes the per-query bids, and the final allocations and respective payments accrue.

The third stage of the game is the key element for our analysis. We say that the auctioneer is credible when reserve prices do not change at S3. This could either be because the auctioneer has commitment, which means that the auctioneer commits not to change reserve prices (i.e. the game does not have S3); or because it has endogenous credibility, which means that along the equilibrium path it is optimal for the auctioneer not to change reserve prices. To distinguish between these two reasons, we denominate as the commitment game the game without S3 and the no commitment game as the game including S3.

The solution concept used in this paper is perfect Bayesian equilibrium.¹¹¹¹11Observe that for the auctioneer, once the bidder submits the bid, any belief about the bidder’s type is irrelevant.

3 One bidder model

The purpose of this section is to distill, in an instructive manner, the main insight of our work by studying the simplest case: the bidder is the only buyer interested in the queries.¹²¹²12Thus, the intrinsic price $p_{0}(x)$ does not come from other bids, but instead it corresponds to particular constraints that publishers (owners of the queries) set on their queries. The tractability of this model, which contrasts with the general model, also allows us to study the revenue consequences of lack of commitment on the auctioneer.

In this model, the auctioneer’s revenue only comes from the queries sold to the bidder.¹³¹³13More generally, the auctioneer’s revenue is a share of the transaction (the other fraction goes to the respective publisher). Our results easily extend to this general setting. Therefore, given a bid of the bidder in either bidding format, the auctioneer’s revenue is

	$\displaystyle\pi(r\|b;\mbox{mCPA})$	$\displaystyle=\begin{cases}0&\mbox{ if }b<r\\ rH(r)+\int_{r}^{b}zh(z)dz&\mbox{ if }b\geq r\end{cases},$
	$\displaystyle\pi(r\|T;\mbox{tCPA})$	$\displaystyle=\begin{cases}0&\qquad\qquad\mbox{ if }T<r\\ TH(b(T;r))&\qquad\qquad\mbox{ if }T\geq r\end{cases}.$

3.1 Commitment Game

We first study the model where the auctioneer commits not to change the reserve prices after observing the bid from the bidder. In this situation, the auctioneer’s problem resembles the classic optimal auction studied in Myerson [1981].

Following the expository spirit of this section, we further simplify the analysis by imposing a standard regularity condition on the distribution $F$ .

Assumption 2.

The virtual valuation $\phi_{F}(v)=v-\frac{1-F(v)}{f(v)}$ is increasing.

Proposition 1.

For the commitment game, the revenue-maximizing mechanism is $(\chi^{*},\tau^{*})$

\displaystyle\chi^{*}(v)=\begin{cases}0&\mbox{ if }v<r_{\mbox{\tiny MYE}}\\ v&\mbox{ if }v\geq r_{\mbox{\tiny MYE}}\end{cases}\qquad\tau^{*}(v)=r_{\mbox{\tiny MYE}}H(r_{\mbox{\tiny MYE}})+\int_{r_{\mbox{\tiny MYE}}}^{v}zh(z)dz

where $r_{\mbox{\tiny MYE}}=\phi_{F}^{-1}(0)$ . Here, the allocation function $\chi(v)$ and transfer function $\tau(v)$ mean that the bidder receives queries $\{x:p_{0}(x)\leq\chi(v)\}$ for a payment of $\tau(v)$ .

Proposition 1 characterizes the revenue-maximizing policy among all feasible auction and bidding formats (in particular, including the mCPA and tCPA formats). We defer the proof to Appendix B.

The next proposition shows that the auctioneer can implement this optimal mechanism in both formats, and hence, making them equivalent.

Proposition 2.

In the commitment model, the mCPA and tCPA mechanisms are equivalent along the equilibrium path. More precisely, in any equilibrium, the auctioneer sets a reserve price $r_{\mbox{\tiny MYE}}$ ; the bidder either bids $b=v$ on the mCPA mechanism or $T$ in tCPA mechanism such that $b(T;r_{\mbox{\tiny MYE}})=v$ .

In particular, we obtain that in the commitment game:

(i)

the auctioneer’s revenue:
$\pi_{C}^{*}=\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\left(vH(v)-\int_{r_{\mbox{\tiny MYE}}}^{v}H(z)\right)dz]$ ,
(ii)

the bidder’s utility: $u_{C}^{*}=\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\int_{r_{\mbox{\tiny MYE}}}^{v}H(z)dz]$ ,
(iii)

the welfare: $W_{C}=\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}vH(v)]$ .

Proof.

First, notice that since the auctioneer does not change the reserve price in the commitment game, the optimal bidding strategy for the bidder is to submit a marginal bid equal to her value. She can do this either directly using the mCPA-format or indirectly, in the tCPA format by submitting a target $T$ that induces the same marginal bid. Thus, from the bidder’s perspective, the mCPA format and the tCPA format are equivalent. Hence, from the auctioneer’s perspective he can implement the optimal mechanism of Proposition 1 by announcing a reserve price of $r_{\mbox{\tiny MYE}}$ at S1. From Proposition 1 we have that the bidder pays $T^{*}(v)=\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\left(vH(v)-\int_{r_{\mbox{\tiny MYE}}}^{v}H(z)\right)$ . The remaining claims of the proposition are direct consequence of this characterization. ∎

3.2 No-commitment game

This section shows that when the auctioneer lacks commitment, the two auto-bidding mechanisms are no longer equivalent. We show that if the bidder chooses the mCPA format, the final auction turns to be equivalent to a first-price auction (FPA). By contrast, when the bidder opts for the tCPA format, the final auction turns to be equivalent to a second-price auction without reserve (SPA).

The mCPA Subgame

We first characterize the set of equilibria for the subgame where the bidder chooses the mCPA format. We present the following straightforward lemma and a direct consequence of the lemma in Proposition 3.

Lemma 2.

Consider the subgame where the bidder chooses the mCPA format and bids $b$ . Then, if the reserve price $r$ announced at S1 is such that $r\neq b$ , then the optimal decision for the auctioneer is to readjust the reserve price to $r=b$ .

Proposition 3 (mCPA equivalent to FPA).

The auction where the bidder chooses the mCPA format is equivalent to a FPA. Thus, for each valuation type $v$ the bidder submits a bid $b^{*}(v)$ solving

\max_{b}(v-b)H(b).

(3)

The previous result describes the negative effect of the lack of commitment from the auctioneer. Under the mCPA format, the auctioneer learns how much the bidder is willing to pay for each query; therefore, the auctioneer’s sequential rationality pushes him to charge such value to the bidder. Thus, the auctioneer cannot credibly commit to keeping any reserve price announced at S0. Anticipating this effect, the bidder shades the bid and by consequence, she gets fewer queries allocated to her compared to the commitment case.

We formalize this discussion in the following proposition.

Definition 1.

We say that an equilibrium is credible if the auctioneer does not change the reserve price after observing the bid.¹⁴¹⁴14Our definition is similar to the self-enforcement agreement theory studied in Aumann [1990].

Proposition 4.

There does not exist a credible equilibrium such that the bidder chooses the mCPA format. Furthermore, all equilibria are payoff equivalent inducing expected payoffs $\pi^{*}({\mbox{mCPA}})=\mathbb{E}_{v}[b^{*}(v)H(b^{*}(v))]$ , $u^{*}({\mbox{mCPA}})=\mathbb{E}_{v}[(v-b^{*}(v))H(b^{*}(v))]$ and expected welfare $W_{\mbox{mCPA}}=\mathbb{E}_{v}[vH(b^{*}(v))]$ , where $b^{*}$ is the solution to Problem (3).

Proof.

From Proposition 2 we have that in any equilibrium, the bidder with valuation-type $v$ bids $b^{*}(v)$ and the auctioneer sets a final reserve price so that $r=b^{*}(v)$ . From the envelope theorem we see from Problem (3) that ${b^{*}}^{\prime}(v)=H(b^{*}(v))$ which implies that $b^{*}(v)$ is increasing on $v$ . This implies that the auctioneer’s initial reserve price $r$ has to be different from at least one of $b^{*}(v)$ and $b^{*}(v^{\prime})$ when $v\neq v^{\prime}$ . This implies that in, any equilibrium, the auctioneer readjusts the reserve price for at least one such bid. We conclude that the there is not a credible equilibrium in the mCPA subgame.

The payoffs described in the proposition are a consequence of that, in any equilibrium, the bidder bids $b^{*}(v)$ gets all queries that have intrinsic prices less than $b^{*}(v)$ for a price $b^{*}(v)$ . ∎

The tCPA Subgame

Similar to the previous analysis, we characterize the set of equilibria for the subgame where the bidder chooses the tCPA format.

Lemma 3.

Consider the subgame where the bidder chooses the tCPA format and bids $T$ . Then, if the reserve price $r$ announced at S1 is such that $r>0$ , then the optimal decision for the auctioneer is to readjust the reserve price to $r=0$ .

Proof.

Clearly, if the auctioneer would a set a reserve price $r\leq T$ otherwise he gets zero profits. For reserve price $r\leq T$ , observe that the auctioneer’s revenue is $TH(b(T;r))$ . From Lemma 1 we have that $b(T;r)$ is decreasing in $r$ , and hence, since $H$ is increasing the optimal reserve price is $r=0$ . ∎

The intuition behind this lemma is that the maximum price to pay is not predetermined as in mCPA case. Instead it is chosen by the auctioneer to meet the tCPA constraint. Because the auctioneer’s revenue is proportional to the volume of queries allocated to the bidder, to maximize such volume, it is optimal to set reserve price $r=0$ . Therefore, the bidder by letting the auctioneer bid on her behalf, makes the auctioneer internalize the negative effect of rent extraction via a reserve, since the latter leads to the auto-bidder decreasing the final marginal bid $b(T;r)$ .

Proposition 5 (tCPA equivalent to SPA).

The auction where the bidder chooses the tCPA format is equivalent to a SPA. For each valuation type $v$ the bidder submits a target $T^{*}(v)$ such that $b(T^{*}(v);0)=v$ . That is, $T^{*}(v)$ solves

H(v)(v-T^{*}(v))=\int_{0}^{v}H(z)dz.

(4)

Proof.

Consider any equilibrium of the game. Because in stage S3, the best response of the auctioneer is to set a reserve price $r=0$ (Lemma 3), the bidder’s optimal response at S2 consists in submitting a target so that the marginal bid equals to her valuation $v$ for a price landscape without reserve price. Hence, she submits a target $T^{*}$ as described in Equation (4). ∎

This proposition starkly contrasts with Proposition 4. In the tCPA format, the bidder believes that the auctioneer will reduce the reserve price while, in the mCPA case, the bidder believes that the auctioneer will increase the reserve price to its bid. This is because in the tCPA format, once the bidder bids the target $T$ , the auctioneer’s incentives are fully aligned with the bidder’s incentive: the auctioneer only cares about maximizing the volume of sold queries.

A second difference with mCPA format is that, in this case, the auctioneer sets a reserve price independently of the bidder’s target. In particular, if the auctioneer announces at S0 a reserve price $r=0$ , he can credibly commit to that price.

The following proposition summarizes these findings.

Proposition 6.

A credible equilibrium exists when the bidder chooses the tCPA format. The seller sets a initial reserve price $r=0$ , the bidder bids $T^{*}$ (the solution to Equation (4)). Moreover, every equilibrium is payoff equivalent inducing expected payoffs $\pi^{*}({\mbox{tCPA}})=\mathbb{E}_{v}[T^{*}(v)H(v)]$ , $u^{*}({\mbox{tCPA}})=\mathbb{E}_{v}[(v-T^{*}(v))H(v)]$ and expected welfare $W_{\mbox{tCPA}}=\mathbb{E}_{v}[vH(v)]$ .

Proof.

The following is a credible equilibrium of the game: the auctioneer sets a reserve price $r=0$ at S1, the bidder chooses the tCPA format and submits the target $T^{*}$ which solves Equation 4 at stage S2, and the auctioneer keeps the reserve price $r=0$ at stage S3.

Furthermore, the subgame after S1 is the same for any initial reserve price that auctioneer announces at S1 (see Proposition 5). Therefore, all equilibria are payoff equivalent. And the expected payoff are an immediate consequence from the fact for every type $v$ , the target is $T^{*}(v)$ is binding in Problem (1) and hence she gets queries $\{x:p_{0}(x)\leq v\}$ for price $T^{*}(v)H(v)$ . ∎

An important consequence of the above results is that without commitment, the auctioneer allocates the queries efficiently (i.e., maximizes welfare).¹⁵¹⁵15This result is reminiscent of the Coasean literature, which, in a different context (durable good monopolist), studies conditions in which a monopolist does not exercise his monopolistic power and allocates efficiently (see Bulow [1982]).

Corollary 1.

In any equilibrium of tCPA subgame, the auctioneer efficiently allocates the queries.

3.3 Utility, Welfare, and Revenue implications in the No-commitment game

We start this section by showing our main result for the specific setting of Section 3: when the auctioneer lacks commitment, it is optimal for the bidder to bid according to the tCPA format. Thus, our result provides a rational explanation as to why quasilinear bidders opt for tCPA auto-bidding mechanisms.

Theorem 1.

In any equilibrium, for every type-valuation $v$ , the bidder strictly prefer to choose the tCPA format over the mCPA format. Thus, $\pi^{*}_{NC}=\pi^{*}(\mbox{tCPA})$ , $u^{*}_{NC}=u^{*}(\mbox{tCPA})$ and $W_{NC}=\mathbb{E}_{v}[vH(v)]$ .

Proof.

Consider $b^{*}(v)$ defined in Equation (3). Then,

	$\displaystyle u^{*}(\mbox{mCPA}\|v)$	$\displaystyle=(v-b^{}(v))H(b^{}(v))$
		$\displaystyle=(v-b^{}(v))H(b^{}(b^{}(v);b^{}(v)))$
		$\displaystyle<(v-b^{}(v))H(b(b^{}(v);0))$
		$\displaystyle=u(b^{*}(v)\|v;\mbox{tCPA})$
		$\displaystyle\leq u^{*}(\mbox{tCPA}\|v).$

The first equality is by definition of $b^{*}$ (Proposition 4). The second equality holds because $H$ is increasing and, hence, with tCPA constraint of $b^{*}(v)$ and reserve price $b^{*}(v)$ the optimal bid is to buy all queries with price less or equal than $b^{*}(v)$ (i.e. $H(b^{*}(v))$ ). The first inequality holds due to Lemma 1. The next equality is by definition of bidding a target $T=b^{*}(v)$ . The last inequality is by definition of $u^{*}(\mbox{tCPA})$ , the bidder’s payoff using the tCPA format with the optimal target. ∎

Regarding the welfare implications, Corollary 1 shows that in the tCPA format, the final allocation is is welfare-optimal. On the other hand, because in the mCPA case the bidder shades her bid (i.e., $b^{*}(v)<v$ ), we have that the allocation is inefficient. We conclude that, from a welfare perspective, the tCPA format is preferable compared to the mCPA format.

Revenue implications

Our previous results show that from the bidder’s (and also welfare) perspective, when the auctioneer does not commit, the bidder prefers to use a tCPA mechanism over the mCPA mechanism. We now tackle the question from the auctioneer’s angle. Does having the tCPA format cause a loss in revenue for the auctioneer? The following result shows that, under some reasonable assumption on $H$ , the auctioneer itself benefits from offering a tCPA format to the bidder.

Assumption 3.

$H$ satisfies that $vh(v)$ is non-decreasing.

Assumption 3 implies that the marginal revenue to sell the queries at price $p$ , $ph(p)$ , is non-decreasing on $p$ . This assumption is quite natural and holds in common settings, for instance, when $H$ is convex, in which case $h$ is non-decreasing.

Theorem 2 (Revenue Comparison).

Suppose that Assumption 3 holds. Then for every valuation-type $v$ we have that $\pi^{*}({\mbox{tCPA}}|v)>\pi^{*}({\mbox{mCPA}}|v)$ . Furthermore, for every $\gamma>0$ , we can find an instance $\langle F,H\rangle$ such that $\pi^{*}({\mbox{tCPA}})>\gamma\cdot\pi^{*}(\mbox{mCPA})$ .

Proof.

Consider the auxiliary function $w(v):=\int_{0}^{v}zh(z)dz$ . Using integration by parts we have that $w(v)=vH(v)-\int_{0}^{v}H(z)dz$ , and using the defintion of $T^{*}(v)$ in Equation (4), we get that $w(v)=T^{*}(v)H(v)$ .

Assumption 3 implies that $w$ is a convex function. Thus, for every $v,v^{\prime}$ , we have that

w(v)\geq w(v^{\prime})+\underbrace{w^{\prime}(v^{\prime})}_{v^{\prime}h(v^{\prime})}(v-v^{\prime}).

(5)

Take $v^{\prime}=b^{*}(v)$ , where $b^{*}(v)$ is the optimal bidding in the mCPA format. Taking the first order conditions on Problem (3) (the solution has to be interior in this problem), we have $h(b^{*}(v))(v-b^{*}(v))=H(b^{*}(v))$ . Therefore, replacing $v^{\prime}$ in Equation (5) we obtain that

T^{*}(v)H(v)\geq w(b^{*}(v))+b^{*}(v)H(b^{*}(v)).

Because $h>0$ , we have that $w>0$ . Therefore, we obtain that $T^{*}(v)H(v)>b^{*}(v)H(b^{*}(v))$ , or equivalently, $\pi^{*}({\mbox{tCPA}}|v)>\pi^{*}({\mbox{mCPA}}|v)$ .

To finish the proof, consider $F(v)=v$ with support in $[0,1]$ (uniform distribution) and $H_{n}(p)=p^{n}$ for $p\in[0,1]$ . Simple computations shows that for every $v\in[0,1]$ , $b^{*}(v)=\frac{v}{n+1}$ , and hence,

\pi^{*}({\mbox{mCPA}})=\int_{0}^{1}\left(\frac{v}{n+1}\right)^{n}dv\leq\frac{1}{(n+1)^{n}}.

On the other hand, the solution to Equation (4) is $T^{*}(v)=\frac{n}{n+1}v$ . This implies that

\pi^{*}({\mbox{tCPA}})=\int_{0}^{1}\frac{n}{n+1}v\cdot v^{n}dv=\frac{n}{(n+1)(n+2)}.

Thus,

\frac{\pi^{*}({\mbox{tCPA}})}{\pi^{*}({\mbox{mCPA}})}\geq\frac{\frac{n}{(n+1)(n+2)}}{\frac{1}{(n+1)^{n}}}=\frac{n(n+1)^{n-1}}{n+2}.

We conclude by taking $n$ large enough such that $\frac{n(n+1)^{n-1}}{n+2}>\gamma$ . ∎

Theorem 2 shows that the revenue on the SPA (the tCPA format) is not equivalent to the revenue obtained in the FPA (the mCPA format). At first glance, this result seems to contradict the well-known Revenue Equivalence Theorem (RET) between these auctions (see Chapter 1.3 of Krishna [2010] for a textbook treatment). While the result is true when the auctioneer only owns one query (in both auctions the revenue is simply $p_{0}(x)$ ), having uniform bidding among heterogeneous queries constraints the bidder to shade the bid so that she receives a suboptimal fraction of queries. Thus, the fraction of queries allocated in the SPA is larger than in the FPA, violating the main condition for the RET¹⁶¹⁶16If the bidder had knowledge of the pricing $p_{0}(x)$ and could bid independently in each of the queries, the FPA would allocate exactly the same as in the SPA, and therefore, RET would apply in such a case..

Even though the condition imposed in Assumption 3 considers a wide range of cases, the following instance – that does not satisfy Assumption 3 – provides an example where the auctioneer prefers not to offer the tCPA mechanism to the bidder.

Proposition 7.

Suppose that the valuation type have support on $[1,\infty)$ and consider the instance

\hat{H}(p)=\begin{cases}0&\mbox{ if }p<1\\ 1-\frac{1}{p}&\mbox{ if }p\geq 1\end{cases}.

Then, $\pi^{*}({\mbox{tCPA}}|v)=\log(v)$ and $\pi^{*}({\mbox{mCPA}}|v)=\sqrt{v}-1$ which implies that $\pi^{*}({\mbox{mCPA}}|v)>\pi^{*}({\mbox{tCPA}}|v)$ . In particular, for every $\gamma>0$ we can find a distribution $F$ so that the instance $\langle F,\hat{H}\rangle$ is such that $\pi^{*}({\mbox{mCPA}})>\gamma\cdot\pi^{*}({\mbox{tCPA}})$ .

3.4 The value of commitment

We finish this section by measuring the value to auctioneer of having commitment in the game. First, we measure the revenue loss of the auctioneer when the auctioneer does not have a commitment mechanism to keep the announced reserve prices, compared to the commitment benchmark. The second measure studies the revenue loss of the auctioneer when, even though he can commit not to change the reserve prices, the bidder has a mistaken belief that the auctioneer would actually readjust reserve prices¹⁷¹⁷17The bidder’s decision on how to bid and which auto-bidding system to choose purely depends on her belief about the auctioneer’s commitment. Thus, Theorem 1 does not rely on what the auctioneer is actually doing in terms of readjusting reserve prices, but instead, it relies on what the bidder believes the auctioneer is doing (see also, Remark 2).. All proofs of this section are delegated to Appendix B.

Proposition 8 (The value of commitment).

Assume that the distribution $F$ has support in $[\underline{v},\overline{v}]$ . Denote by $\psi=\frac{\pi_{\underline{v}\mbox{-}\mbox{\tiny SPA}}}{\pi_{\mbox{\tiny MYE}}}$ , the relative revenue of selling one item with a SPA with reserve price $\underline{v}$ compared to sell it using revenue-optimal auction. Then for every instance $\langle F,H\rangle$ we have that $\pi^{*}_{NC}\geq\psi\cdot\pi^{*}_{C}$ . Moreover, the bound is tight: an instance $\langle F,H\rangle$ exists such that $\pi^{*}_{NC}=\psi\cdot\pi^{*}_{C}$

Proposition 8 shows the more homogeneous impressions are, the higher is the loss of revenue for the auctioneer when he does not have commitment.

Proposition 9 (The value of showing commitment).

We denote by $\pi^{*}_{WB}$ , the the auctioneer’s revenue when the bidder bids the non commitment optimal reserve price $T^{*}$ (see Equation (4)) but the auctioneer keeps the reserve price to $r=r_{\mbox{\tiny MYE}}$ . That is, $\pi^{*}_{WB}=\pi^{*}(r_{\mbox{\tiny MYE}}|T^{*};\mbox{tCPA})$ . Then, for every $\gamma>0$ an instance $\langle F,H\rangle$ exists such that $\pi^{*}_{C}>\gamma\cdot\pi^{*}_{WB}$ .

The last proposition shows the cost of having a misguided bidder in the auction. It further shows that if the auctioneer believes that bidder does not trust the auctioneer’s commitment, then the rational choice for the auctioneer is to declare a reserve price of $0$ instead of $r_{\mbox{\tiny MYE}}$ . The following remark re-emphasizes this point.

Remark 2.

Our result (including the general version of Section 4) that a bidder prefers the tCPA-format only depends on the bidder’s belief about whether the auctioneer can commit to the auction rules he declares. Therefore, even a committed auctioneer may benefit by offering tCPA-like mechanisms as it increases the value for bidders who are skeptical about the auctioneer’s commitment.

4 The general model

This section generalizes Theorem 1 to a setting where the bidder faces competition by other buyers (we will call them extra-buyers), that are interested in the queries $X$ .

We start the section by unfolding the intrinsic price $p_{0}$ when we have multiple buyers. In particular, we allow the intrinsic price to be a random variable whose uncertainty comes from the extra-buyers bidding strategies that may be private, the different conversion probabilities and the publishers’ pricing constraint that may be unknown to the bidder.

The intrinsic price with multiple buyers

We consider $n$ extra-buyers (aside from our original bidder) participating in the auction. Each extra-buyer $i$ has a private valuation $v_{i}$ per conversion on the query, strategically chooses an auto-bidding format and submits a bid according to the format. We denote by $\bm{\sigma}(\bm{v})=(\sigma_{1}(v_{1}),\ldots,\sigma_{n}(v_{n}))$ the extra-buyers’ strategies.

Let $\bm{b}=(b_{1},\ldots,b_{n})$ be the final marginal bids of the extra-buyers; $\bm{q}(x)=(q_{0}(x),q_{j}(x))_{j=1}^{n}$ the probability of conversion on query $x\in X$ for the bidder and the buyers (respectively); and $p_{B}(x)$ the pricing constraint set by the publisher owning query $x$ .¹⁸¹⁸18The functions $\bm{q},p_{B}$ are assumed to be integrable functions. Then, in a second-price auction the realized intrinsic price the bidder faces for a conversion on query $x\in X$ is

p_{0}(x|\bm{b},\bm{q},p_{B})=\max\left\{\frac{\max_{j=1,\ldots,n}b_{j}\cdot q_{j}(x)}{q_{0}(x)},p_{B}(x)\right\}.

Hence, the realized price distribution is

H(p|\bm{b},\bm{q},p_{B})=\int_{\{x:\;p_{0}(x|\bm{b},\bm{q},p_{B})\leq p\}}q_{0}(x)d\mu(x).

From the bidder’s perspective, we consider the following information structure. The bidder believes that extra-buyers valuations $\bm{v}=(v_{i})_{i=1}^{n}$ are drawn independently, with distribution $F_{i}$ with support $[0,\overline{v}_{i}]$ for $i=1,\ldots,n$ .¹⁹¹⁹19Because the valuations can be arbitrarily small, we have that for every valuation-type $v$ of the bidder, $\mathbb{P}[vq_{0}(x)>v_{j}q_{j}(x)\mbox{ for }x\in X\mbox{ (a.e.)}]>0$ . That is, with positive probability, the bidder by bidding her value is the strongest candidate in the auction. The bidder also assesses that the conversion probabilities $\bm{q}$ and the pricing constraint $p_{B}$ are drawn according to $(\bm{q},p_{B})\sim G|_{v}$ . We do not necessarily impose that extra-buyers are playing equilibrium strategies but instead impose that they are individually rational: an extra-buyer never bids above her valuation.

Assumption 4.

For every Extra-Buyer $i$ , we have that $\mathbb{P}[b_{i}\leq v_{i}\mbox{ for }i=1,\ldots,n]=1$ , where $b_{i}$ is Extra-Buyer $i$ ’s final marginal bid.

Regarding the intrinsic price the bidder faces, observe that in the presence of extra-buyers using tCPA format, the final marginal of those tCPA-extra buyers depends on the bidder’s marginal bid $b_{0}$ . Therefore, the intrinsic price the bidder faces is a random variable $p_{0}(\cdot|\omega_{v},b_{0})$ , where $\omega_{v}=(\bm{\sigma}(\bm{v}),\bm{q},p_{B})$ is the random variable containing the bidder’s unknown terms. Consequently, the price distribution is a random variable $H(p|\omega_{v},b_{0})$ . This is precisely why the full model is harder to analyze than the model of Sec. 3 – the price distribution for the bidder is now a function of its own bid.

We assume that $H$ satisfies the general version of Assumption 1 for random variables.²⁰²⁰20All assumptions holding for $\omega_{v}$ , are stated up to a zero measure set.

Assumption 5.

$H(p|\omega_{v},b_{0})$ satisfies Assumption 1 for every $b_{0}$ , $\omega_{v}$ .

The value of the tCPA format

After the previous prelude, we are now in a position to state our main result: in the non-commitment model, the bidder prefers to use the tCPA format. More precisely, we show that if the auctioneer can readjust the auction rule to set a per-query and personalized-per-bidder reserve prices, then the bidder’s expected payoff using the tCPA format is larger than the expected payoff using the mCPA format. We also provide a companion result in the supplementary material showing that when the extra-buyers game is symmetric in a certain sense and the auctioneer is constrained to set a uniform reserve price across queries, then again, the bidder prefers to use the tCPA format.

Recall the notation that $u^{*}(\mbox{tCPA}|v)$ denotes the expected payoffs when the bidder with valuation $v$ chooses the tCPA format and submits an optimal target. Similarly, $u^{*}(\mbox{mCPA}|v)$ is the expected payoff when the bidder chooses the mCPA format and submits an optimal marginal bid. As our main technical result, we show:

Theorem 3.

Suppose that the auctioneer can readjust reserve prices to per-query and personalized-per-bidder level. Then, $u^{*}(\mbox{tCPA}|v)>u^{*}(\mbox{mCPA}|v)$ .

Proof.

Fix the valuation of the bidder to $v$ and let $b_{\tiny\mbox{mCPA}}\in(0,v]$ be an arbitrary bid.

Suppose that the bidder submits $b_{\tiny\mbox{mCPA}}\in[0,v]$ using the mCPA format and assume that the auctioneer has chosen the optimal reserve prices (call this scenario “world $M$ ”). We claim that the bidder weakly improves her payoff by bidding a target $T=b_{\tiny\mbox{mCPA}}$ with the tCPA format (call this scenario “world $T$ ”) for every realization $\omega_{v}$ . Furthermore, the inequality is strict for a positive measure of $\omega_{v}$ . This claim proves the theorem, and we show the claim in the following four steps.

Step 1. Let $X_{\tiny\mbox{mCPA}}(\omega_{v})$ be the subset of queries that the bidder obtains in world M. Then

u(b_{\tiny\mbox{mCPA}}|\mbox{mCPA};v;\omega_{v})=(v-b_{\tiny\mbox{mCPA}})\int_{X_{\tiny\mbox{mCPA}}(\omega_{v})}q_{0}(x)d\mu(x),

where $\mu$ is the measure on the space of queries $X$ . Indeed, by optimality of the auctioneer, the reserve price for the bidder on those queries must be $r=b_{\tiny\mbox{mCPA}}$ .

Step 2.1. We prove that the revenue of the auctioneer in world $T$ is at least the revenue in world $M$ . This is because one strategy for the auctioneer in world $T$ is to simply set a reserve price of $b_{\tiny\mbox{mCPA}}$ for the bidder (equal to its target). Under this, the situation is identical to world $M$ for the bidder (due to Step 1) and for every buyer (because the auto-bidder for our bidder bids $b_{\tiny\mbox{mCPA}}$ on all queries as the reserve is set to the target), yielding the same revenue as in world $M$ ²¹²¹21In case of multiplicity of equilibria, we assume that the same bidding equilibrium arises on worlds $M$ and $T$ as they are indistinguishable to the agents..

Step 2.2. We next prove that the revenue that the auctioneer obtains from the bidder in world $T$ is greater or equal than the revenue from the bidder in world $M$ . Suppose for the sake of a contradiction that this is not true. Due to Step 2.1, this means that the revenue obtained from the extra bidders is higher in world $T$ than in world $M$ . We now leverage the fact that the auctioneer can set a reserve price at query/bidder level, in order to recreate the situation from world $T$ in world $M$ . For each extra-buyer, the auctioneer can add a per-query personalized reserve equal to the bid the bidder submits for the query in world $T$ . Moreover, for the queries $X_{\tiny\mbox{tCPA}}(\omega_{v})$ that the bidder wins in world $T$ , the auctioneer can set a high reserve price on the extra-buyers so that the only feasible candidate is the bidder. With this simulation, the auctioneer can recreate the extra-buyers’ bidding behavior from world $T$ in world $M$ . Thus the auctioneer changed reserves to obtain the same revenue from the extra-buyers in world $M$ as in world $T$ . In this way (only by changing reserves) one could increase the revenue in world $M$ . This contradicts the optimality of the reserve prices the auctioneer chooses in world $M$ .

Step 3. It follows from Step 2.2 that the volume of conversions obtained by the bidder is higher in world $T$ than in world $M$ . This is simply because the revenue from the bidder equals the average cost per conversion times the volume of conversions. The average cost-per-conversion in both the worlds is the same, equal to $b_{\tiny\mbox{mCPA}}$ – in world $T$ because we assume the target is binding (Assumption 5 and Lemma 1), and in world $M$ because the reserve is set to the same value. Since the revenue from the bidder is higher in world $T$ , we conclude that the volume of conversions is higher in world $T$ .

Step 4. We assert that $u(b_{\tiny\mbox{mCPA}}|\mbox{tCPA};v;\omega_{v})\geq u(b_{\tiny\mbox{mCPA}}|\mbox{mCPA};v;\omega_{v})$ . Indeed, observe that

	$\displaystyle u(b_{\tiny\mbox{mCPA}}\|\mbox{tCPA};v;\omega_{v})$	$\displaystyle=(v-b_{\tiny\mbox{mCPA}})\int_{X_{\tiny\mbox{tCPA}}(\omega_{v})}q_{0}(x)d\mu(x)$
		$\displaystyle\geq(v-b_{\tiny\mbox{mCPA}})\int_{X_{\tiny\mbox{mCPA}}(\omega_{v})}q_{0}(x)d\mu_{(}x)$
		$\displaystyle=u(b_{\tiny\mbox{mCPA}}\|\mbox{mCPA};v;\omega_{v})$

where the first equality holds because the target of the bidder in world $T$ is set to $b_{\tiny\mbox{mCPA}}$ , and the tCPA constraint is binding (from Assumption 5 and Lemma 1). The first inequality is from Step 3. The final equality is from Step 1.

Step 5. In step 4, we already proved the weak inequality from the theorem; now we prove the strict inequality. We prove that there exists a positive measure of events $\omega_{v}$ such that $u(b_{\tiny\mbox{mCPA}}|\mbox{tCPA};v;\omega_{v})>u(b_{\tiny\mbox{mCPA}}|\mbox{mCPA};v;\omega_{v})$ . Indeed, because $b_{\tiny\mbox{mCPA}}>0$ , a positive measure of events $\omega_{v}$ exists such that the extra-buyers’ valuations are small enough so that for every query $x\in X$ , $\max_{i=1,\ldots,n}v_{i}q_{i}(x)<b_{\tiny\mbox{mCPA}}q_{0}$ . Hence, by Assumption 4 the auctioneer never allocates queries to extra-buyers. Thus, in world $M$ , the auctioneer’s revenue is $b_{\tiny\mbox{mCPA}}\cdot H(b_{\tiny\mbox{mCPA}}|\omega_{v})$ . In world $T$ , if the bidder bids a target $T=b_{\tiny\mbox{mCPA}}$ , then by reducing the bidder’s reserve price to $r<b_{\tiny\mbox{mCPA}}$ we have the final marginal bid is $b(b_{\tiny\mbox{mCPA}};r)>b_{\tiny\mbox{mCPA}}$ . Thus, the auctioneer obtains a revenue of $T\cdot H(b(b_{\tiny\mbox{mCPA}};r)|\omega_{v})=b_{\tiny\mbox{mCPA}}\cdot H(b(b_{\tiny\mbox{mCPA}};r)|\omega_{v})$ . This is strictly larger than the revenue in world $M$ due to Assumption 5. We conclude that auctioneer sets a reserve price $r<b_{\tiny\mbox{mCPA}}$ in world $T$ . Thus, we obtain

	$\displaystyle u(b_{\tiny\mbox{mCPA}}\|\mbox{tCPA};v;\omega_{v})$	$\displaystyle=(v-b_{\tiny\mbox{mCPA}})H(b(b_{\tiny\mbox{mCPA}};r)\|\omega_{v})$
		$\displaystyle>(v-b_{\tiny\mbox{mCPA}})H(b_{\tiny\mbox{mCPA}})=u(b_{\tiny\mbox{mCPA}}\|\mbox{mCPA};v;\omega_{v}).$

To conclude the proof of the theorem, from Step 4. and Step 5. we derive that

	$\displaystyle u(b_{\tiny\mbox{mCPA}}\|\mbox{mCPA};v)$	$\displaystyle=\mathbb{E}_{\omega_{v}}[u(b_{\tiny\mbox{mCPA}}\|\mbox{mCPA};v;\omega_{v})]$
		$\displaystyle<\mathbb{E}_{\omega_{v}}[u(b_{\tiny\mbox{mCPA}}\|\mbox{tCPA};v;\omega_{v})]\leq u^{*}(\mbox{tCPA}\|v).$

Since $b_{\tiny\mbox{mCPA}}$ is arbitrary, we get that $u^{*}(\mbox{tCPA}|v)<u^{*}(\mbox{mCPA}|v)$ .∎

Theorem 3 strongly relies on the auctioneer’s ability to readjust the reserve price at the query and bidder level. However, when the set of queries is large, readjusting the reserve prices for each query may turn out to be too expensive. In this kind of situation, when the auctioneer is constrained to set a uniform reserve price, we provide a companion result showing that the bidder still prefers the tCPA format under some symmetry condition on the extra-buyers game (see the supplemental material for details).

4.1 Uniform reserves

The proof for Theorem 3 strongly relies on the auctioneer’s ability to readjust the reserve price at the query and bidder level. However, when the set of queries is large, readjusting the reserve prices for each query may turn out to be too expensive for the auctioneer. In this kind of situation, when the auctioneer is constrained to set a uniform reserve price, Theorem 4 shows that the bidder still prefers the tCPA format so long as the extra-buyers game is symmetric. We remark that this result does not rely on how the auctioneer readjusts the extra buyers’ reserve prices.²²²²22This weaker condition on how the auctioneer behaves with the extra-buyers allows to include cases like when some extra-buyers are budgeted constrained, and hence, the auctioneer cannot readjust their reserve prices.

When dealing with uniform reserve prices, the key technical challenge compared to Theorem 3 is that the auctioneer cannot replicate the effect of the bidder’s bidding on the remaining extra-buyers by setting personalized uniform reserve prices. Thus, when the auctioneer readjusts the bidder’s reserve price not only the bidder’s marginal bid changes but also the marginal bids of extra-buyers using a tCPA format. To tackle this problem, we assume that game for extra-buyers using the tCPA format is symmetric.

Definition 2.

The extra-buyers’ game is tCPA-symmetric if for every $\omega_{v}$ and Extra-Buyers $i,j$ using the tCPA format, we have that their final marginal bids $b_{i}$ , $b_{j}$ are the same.²³²³23A sufficient condition for those marginal bids to be the same is that (i) both bidders have the same target ( $T_{i}=T_{j}$ ) and (ii) that for every query $x$ there exists a query $x^{\prime}$ such that $q_{i}(x)=q_{j}(x^{\prime})$ .

Remark 3.

When there is only one extra-buyer is in the auction, the game is tCPA-symmetric.

We are now in position to present Theorem 4.

Theorem 4.

Suppose that the auctioneer is constrained to set a uniform reserve price to the bidder and that the extra-buyers game is tCPA-symmetric. Then, $u^{*}(\mbox{tCPA}|v)>u^{*}(\mbox{mCPA}|v)$ .

The proof of Theorem 4 is similar in spirit to that of Theorem 3, but now we can not use the power of the personalized per-query reserve prices to perform the step where we“simulate world $T$ in world $M$ ”. Instead of such a simulation, we show that in a tCPA-symmetric game, there is a structural property of the bidding behavior in equilibrium, which allows us to prove the result. We defer the proof to Appendix C.

5 Conclusion

This paper attempts to explain why rational bidders (with quasi-linear utilities) choose bidding formats which at first glance are not optimal. The crux of the argument lies in the notion of lack of commitment – the auctioneer can change (ex post) the rules of the declared auction – once we treat the auction and bidding setting as a multi-stage game. It turns out that in a game without commitment, it is rational for the quasi-linear bidder to choose the seemingly suboptimal tCPA format over the classical mCPA format. We prove this in two different settings: a simpler setting with one bidder and exogenous prices, and then in the general model with endogenous prices in the auction based on bids of other buyers. In the simpler model, we also prove that the auctioneer’s revenue is higher with the tCPA format in the no-commitment game compared to the mCPA format, under certain mild conditions. The general model requires more technically involved proofs but the insight is the same: in a world without commitment or with a lack of belief in the other player’s commitment, the tCPA format aligns incentives better. We emphasize that the core issue is in fact not the auctioneer’s commitment, but the bidder’s belief in the same. In the simpler model, we also provide bounds on the value of commitment, and on the loss due to the lack of belief of a bidder in a committed auctioneer. We also note that the problem of commitment may also be overcome in practice via other mechanisms such as verification in a repeated auction setting and via audits.

References

[1]
Aggarwal et al. [2019] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta. 2019. Autobidding with Constraints. In Web and Internet Economics - 15th International Conference, WINE 2019, New York, NY, USA, December 10-12, 2019, Proceedings (Lecture Notes in Computer Science), Vol. 11920. Springer, 17–30.
Aggarwal et al. [2023] Gagan Aggarwal, Andres Perlroth, and Junyao Zhao. 2023. Multi-Channel Auction Design in the Autobidding World. https://doi.org/10.48550/ARXIV.2301.13410
Akbarpour and Li [2020] Mohammad Akbarpour and Shengwu Li. 2020. Credible Auctions: A Trilemma. Econometrica 88, 2 (2020), 425–467. https://doi.org/10.3982/ECTA15925 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.3982/ECTA15925
Aumann [1990] Robert Aumann. 1990. Nash equilibria are not self-enforcing, in “Economic Decision-Making: Games, Econometrics and Optimization”(JJ Gabszewicz, J.-F. Richard, and LA Wolsey, Eds.).
Balseiro et al. [2021a] Santiago Balseiro, Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021a. Robust Auction Design in the Auto-bidding World. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 17777–17788. https://proceedings.neurips.cc/paper/2021/file/948f847055c6bf156997ce9fb59919be-Paper.pdf
Balseiro et al. [2021b] Santiago R. Balseiro, Yuan Deng, Jieming Mao, Vahab S. Mirrokni, and Song Zuo. 2021b. The Landscape of Auto-bidding Auctions: Value versus Utility Maximization. In EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021. ACM, 132–133.
Balseiro and Gur [2019] Santiago R. Balseiro and Yonatan Gur. 2019. Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium. Management Science 65, 9 (September 2019), 3952–3968.
Bester and Strausz [2000] Helmut Bester and Roland Strausz. 2000. Imperfect commitment and the revelation principle: the multi-agent case. Economics Letters 69, 2 (2000), 165–171. https://doi.org/10.1016/S0165-1765(00)00301-3
Bester and Strausz [2001] Helmut Bester and Roland Strausz. 2001. Contracting with Imperfect Commitment and the Revelation Principle: The Single Agent Case. Econometrica 69, 4 (2001), 1077–1098. https://doi.org/10.1111/1468-0262.00231 arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/1468-0262.00231
Bulow [1982] Jeremy I. Bulow. 1982. Durable-Goods Monopolists. Journal of Political Economy 90, 2 (1982), 314–332.
Che and Gale [2000] Yeon-Koo Che and Ian L. Gale. 2000. The Optimal Mechanism for Selling to a Budget-Constrained Buyer. J. Econ. Theory 92 (2000), 198–233.
Daskalakis et al. [2020] Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, and Santhoshini Velusamy. 2020. Simple, Credible, and Approximately-Optimal Auctions. In Proceedings of the 21st ACM Conference on Economics and Computation (EC ’20). Association for Computing Machinery, New York, NY, USA, 713. https://doi.org/10.1145/3391403.3399535
Deng et al. [2022] Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, and Song Zuo. 2022. Efficiency of the First-Price Auction in the Autobidding World. https://doi.org/10.48550/ARXIV.2208.10650
Deng et al. [2021] Yuan Deng, Jieming Mao, Vahab Mirrokni, and Song Zuo. 2021. Towards Efficient Auctions in an Auto-Bidding World. In Proceedings of the Web Conference 2021 (WWW ’21). 3965–3973.
Facebook [2022] Facebook 2022. Auto-bidding products support page. https://www.facebook.com/business/help/1619591734742116. Accessed: 2022-02-09.
Feldman et al. [2007] Jon Feldman, Shanmugavelayutham Muthukrishnan, Martin Pal, and Cliff Stein. 2007. Budget optimization in search-based advertising auctions. In Proceedings of the 8th ACM conference on Electronic commerce. 40–49.
Ferreira and Weinberg [2020] Matheus V. X. Ferreira and S. Matthew Weinberg. 2020. Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments. In Proceedings of the 21st ACM Conference on Economics and Computation (EC ’20). Association for Computing Machinery, New York, NY, USA, 683–712. https://doi.org/10.1145/3391403.3399495
Fikioris and Tardos [2022] Giannis Fikioris and Éva Tardos. 2022. Liquid Welfare guarantees for No-Regret Learning in Sequential Budgeted Auctions. https://doi.org/10.48550/ARXIV.2210.07502
Fudenberg and Tirole [1983] Drew Fudenberg and Jean Tirole. 1983. Sequential Bargaining with Incomplete Information. The Review of Economic Studies 50, 2 (04 1983), 221–247. https://doi.org/10.2307/2297414 arXiv:https://academic.oup.com/restud/article-pdf/50/2/221/4355731/50-2-221.pdf
Gaitonde et al. [2023] Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. 2023. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) (Leibniz International Proceedings in Informatics (LIPIcs)), Yael Tauman Kalai (Ed.), Vol. 251. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 52:1–52:1. https://doi.org/10.4230/LIPIcs.ITCS.2023.52
Golrezaei et al. [2021] Negin Golrezaei, Ilan Lobel, and Renato Paes Leme. 2021. Auction Design for ROI-Constrained Buyers. In Proceedings of the Web Conference 2021 (WWW ’21). 3941–3952.
Google [2022] Google 2022. Auto-bidding products support page. https://support.google.com/google-ads/answer/2979071. Accessed: 2022-02-09.
Gul et al. [1986] Faruk Gul, Hugo Sonnenschein, and Robert Wilson. 1986. Foundations of dynamic monopoly and the coase conjecture. Journal of Economic Theory 39, 1 (1986), 155–190. https://EconPapers.repec.org/RePEc:eee:jetheo:v:39:y:1986:i:1:p:155-190
Krishna [2010] Vijay Krishna. 2010. Auction Theory. In Auction Theory (Second Edition) (second edition ed.). Academic Press, San Diego, iii.
Laffont and Robert [1996] Jean-Jacques Laffont and Jacques Robert. 1996. Optimal auction with financially constrained buyers. Economics Letters 52, 2 (1996), 181–186.
Liaw et al. [2022] Christopher Liaw, Aranyak Mehta, and Andres Perlroth. 2022. Efficiency of non-truthful auctions under auto-bidding. https://doi.org/10.48550/ARXIV.2207.03630
Liu et al. [2019] Qingmin Liu, Konrad Mierendorff, Xianwen Shi, and Weijie Zhong. 2019. Auctions with Limited Commitment. American Economic Review 109, 3 (March 2019), 876–910. https://doi.org/10.1257/aer.20170882
Mehta [2022] Aranyak Mehta. 2022. Auction Design in an Auto-Bidding Setting: Randomization Improves Efficiency Beyond VCG. In Proceedings of the ACM Web Conference 2022 (WWW ’22). Association for Computing Machinery, New York, NY, USA, 173–181. https://doi.org/10.1145/3485447.3512062
Milgrom and Segal [2002] Paul Milgrom and Ilya Segal. 2002. Envelope Theorems for Arbitrary Choice Sets. Econometrica 70, 2 (2002), 583–601.
Myerson [1981] Roger B Myerson. 1981. Optimal auction design. Mathematics of operations research 6, 1 (1981), 58–73.
Rudin [1987] Walter Rudin. 1987. Real and Complex Analysis, 3rd Ed. McGraw-Hill, Inc., USA.
Skreta [2006] Vasiliki Skreta. 2006. Sequentially Optimal Mechanisms. The Review of Economic Studies 73, 4 (2006), 1085–1111. http://www.jstor.org/stable/4123260
Skreta [2015] Vasiliki Skreta. 2015. Optimal auction design under non-commitment. Journal of Economic Theory 159 (2015), 854–890. https://doi.org/10.1016/j.jet.2015.04.007 Symposium Issue on Dynamic Contracts and Mechanism Design.

Appendix A Missing Proofs from Section 2

Proof of Lemma 1.

First, notice that Problem (1) has a unique solution since $H$ is an increasing function (Assumption 1).

Second, for existence of solution, observe that $b=T$ is feasible solution. This implies that the optimal solution has $b(T;r)\geq T$ . Also, by writing the constraint as function of $b$ , $g(b)=rH(r)+\int_{r}^{b}zh(z)dz-TH(b)$ we have that $g$ is increasing on $b>T$ since $g^{\prime}(b)=(b-T)h(b)$ which is strictly by assumption on $H$ . Next, using integration by parts on the integral term in $g$ , we rewrite $g(b)=(b-T)H(b)-\int_{r}^{b}H(z)dz$ . Because $\int_{r}^{\infty}H(z)dz<\infty$ (see Assumption 1), we have that $\lim_{b\to\infty}g(b)=\infty$ . We conclude that Problem (1) has a unique solution satisfying $g(b(T;r))=0$ .

The previous paragraph shows that Equation (2) has a unique solution for $b\in[T,\infty)$ which is $b(T;r)$ . For $b<T$ , observe that the left-hand-side of Equation (2) is negative while the right-hand-side is positive. Therefore, Equation (2) has a unique solution for $b\geq r$ .

To conclude the proof of the lemma observe that $\partial_{T}g(b|T)=-H(b)<0$ . This implies that for $T<T^{\prime}$ $g(b(T;r)|T^{\prime})<g(b(T;r)|T)=0$ . Because $g(\cdot|T^{\prime})$ is increasing, we conclude that $b(T^{\prime};r)>b(T;r)$ . The same logic holds to show that $b(T;r)$ is decreasing in $r$ since $\partial_{r}g(b|r)=H(r)>0$ . ∎

Appendix B Missing Proofs from Section 3

Proof of Proposition 1.

For the proof we denote by $\underline{v},\overline{v}$ the lowest and upper elements in the support of $F$ .

From the revelation principle, without loss of generality we restrict to incentive compatible mechanisms $(\chi(v),\tau(v))$ .

The incentive compatible condition on the mechanism implies that the bidder’s utility satisfies that

vH(\chi(v))-\tau(v)=\max_{v^{\prime}}vH(\chi(v^{\prime}))-\tau(v^{\prime}).

Using the envelope approach [Milgrom and Segal, 2002], we have that the incentive compatibility restriction is equivalent to (i) $\chi(v)$ being non-decreasing (since $H$ is increasing) and (ii) that for almost every type $v$ we have that

\tau(v)=vH(\chi(v))-\int_{\underline{v}}^{v}H(\chi(z))dz\qquad\mbox{ (IC)}.

The previous characterization of $\tau$ allow us to reformulate the auctioneer’s revenue as

	$\displaystyle\int_{\underline{v}}^{\overline{v}}\left(vH(\chi(v))-\int_{\underline{v}}^{v}H(\chi(z))dz\right)$	$\displaystyle f(v)dv=$
		$\displaystyle\int_{\underline{v}}^{\overline{v}}\phi_{F}(v)H(\chi(v))f(v)dv,$

where the equality comes from using integration by parts.²⁴²⁴24The integrability condition on $H$ (Assumption 1) ensures that the integration by parts can be taken for the case where the support of the distribution $F$ is unbounded.

The intrinsic price condition imposes that for every query, the price which is sold has to be at least the respective intrinsic price. This, in terms of $H$ , implies that for every feasible transfer rule $\tau$ and every valuation-types $v>v^{\prime}$ the following inequality holds:

\tau(v)-\tau(v^{\prime})\geq\int_{\chi(v^{\prime})}^{\chi(v)}zh(z)dz\qquad\mbox{ (FC)}.

We claim that if $\chi$ satisfies the incentive-compatibility constraint (IC) and the feasibility constraint (FC) then, up to a zero-measure set of types, $\chi(v)\leq v$ . To see this, since $\chi$ is non-decreasing then is differentiable almost everywhere (see Theorem 7.20 Rudin [1987]). Consequently, $\tau$ is also differentiable almost everywhere. The (IC) condition implies that $\tau^{\prime}(v)=vh(\chi(v))\chi^{\prime}(v)$ , while the (FC) condition implies that $\tau^{\prime}(v)\geq\chi(v)h(\chi(v))\chi^{\prime}(v)$ . We conclude that $\chi(v)\leq v$ for almost every valuation type $v$ .

To conclude the proof, consider the following relaxation of the auctioneer’s problem

	$\displaystyle\max_{\chi(\cdot)}\quad$	$\displaystyle\mathbb{E}_{v}\left[H(\chi(v))\;\phi_{F}(v)\right]$
	s.t.	$\displaystyle\chi(v)\leq v\quad(a.e.).$

Because $H$ is increasing and $\phi_{F}$ is increasing, the above problem admits a pointwise solution which is

\chi^{*}(v)=\begin{cases}0&\mbox{ if }v<r_{\mbox{\tiny MYE}}\\ v&\mbox{ if }v\geq r_{\mbox{\tiny MYE}}\end{cases}.

We conclude the proof by showing that $\chi^{*}$ is solution for the auctioneer’s problem. Indeed, first observe that $\chi^{*}$ is monotone, and hence, $\chi^{*}$ satisfies condition (i) in the incentive-compatibility restriction. Moreover, the transfer rule generated by $\chi^{*}$ is such that for $v\geq r_{\mbox{\tiny MYE}}$ ,

\tau^{*}(v)=vH(v)-\int_{r_{\mbox{\tiny MYE}}}^{v}H(z)dz=r_{\mbox{\tiny MYE}}H(r_{\mbox{\tiny MYE}})+\int_{r_{\mbox{\tiny MYE}}}^{v}zh(z)dz,

where we use integration by parts for the second equality. Clearly, $\tau^{*}$ satisfies the feasibility constraint (FC). We conclude that $\chi^{*}$ is a feasible solution for the auctioneer’s problem, and therefore, $(\chi^{*},\tau^{*})$ is the revenue-maximizing mechanism. ∎

Proof of Proposition 7.

From Equation (4), we have that $T^{*}(v)=v-\frac{\int_{0}^{v}\hat{H}(z)dz}{\hat{H}(v)}=\frac{\log(v)}{\hat{H}(v)}$ . Thus, $\pi^{*}(\mbox{tCPA}|v)=T^{*}(v)\hat{H}(v)=\log(v)$ . Similarly, the first order conditions in Problem (3) implies that $b^{*}(v)$ solves

(v-b^{*}(v))\hat{h}(b^{*}(v))=\hat{H}(b^{*}(v)).

Replacing $\hat{H}$ , we obtain that the unique solution is $b^{*}(v)=\sqrt{v}$ . We conclude since $\pi^{*}(\mbox{mCPA}|v)=b^{*}(v)H(b^{*}(v))=\sqrt{v}-1$ .

Observe that for every $v\geq 1$ , we have that $\pi^{*}(\mbox{tCPA}|v)>\pi^{*}(\mbox{mCPA}|v)$ and $\lim_{v\to\infty}\frac{\pi^{*}(\mbox{tCPA}|v)}{\pi^{*}(\mbox{mCPA}|v)}=\infty$ . Therefore for every $\gamma>0$ , we can find a $\underline{v}>0$ large enough so that if all types in the support of the distribution $F$ are greater than $\underline{v}$ , we have that $\pi^{*}({\mbox{mCPA}})>\gamma\cdot\pi^{*}({\mbox{tCPA}})$ . ∎

Proof of Proposition 8.

Let $\underline{v},\overline{v}$ the smallest and largest elements in the support of $F$ . Using that $\pi^{*}_{NC}=\pi^{*}({\mbox{tCPA}})$ , we get that

	$\displaystyle\pi^{*}_{NC}$	$\displaystyle=\mathbb{E}_{v}[T^{*}(v)H(v)]$
		$\displaystyle=\int_{\underline{v}}^{\overline{v}}\left(vH(v)-\int_{0}^{v}H(z)dz\right)f(v)dv$
		$\displaystyle=\int_{0}^{\underline{v}}H(z)dz+\mathbb{E}_{v}[\phi(v)H(v)]$
		$\displaystyle\geq\underbrace{\mathbb{E}_{v}[\phi(v)H(v)]}.$

The second equality comes from the characterization of $T^{*}$ in Equation (4). The thrid equality is a simple integration by parts argument. The inequality last holds because $H$ is nonnegative.

On the other hand, using integration by parts in the characterization of $\pi^{*}_{C}$ on Proposition 2, we get that

\pi^{*}_{C}=\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\phi(v)H(v)].

Therefore, we conclude that

	$\displaystyle\frac{\pi^{}_{NC}}{\pi^{}_{C}}$	$\displaystyle=1+\frac{\mathbb{E}_{v}[\mathbf{1}_{\{v<r_{\mbox{\tiny MYE}}\}}\phi_{F}(v)H(v)]}{\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\phi_{F}(v)H(v)]}$
		$\displaystyle\geq 1+\frac{H(r_{\mbox{\tiny MYE}})\mathbb{E}[\mathbf{1}_{\{v<r_{\mbox{\tiny MYE}}\}}\phi_{F}(v)]}{H(r_{\mbox{\tiny MYE}})\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\phi_{F}(v)]}$
		$\displaystyle\geq 1+\frac{\mathbb{E}[\mathbf{1}_{\{v<r_{\mbox{\tiny MYE}}\}}\phi_{F}(v)]}{\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\phi_{F}(v)]}$
		$\displaystyle=1+\frac{\pi_{\underline{v}\mbox{-}\mbox{\tiny SPA}}-\pi_{\mbox{\tiny MYE}}}{\pi_{\mbox{\tiny MYE}}}$
		$\displaystyle=\psi$

. The first two inequalities hold because $\mathbb{E}_{v}[\mathbf{1}_{\{v\geq r_{\mbox{\tiny MYE}}\}}\phi_{F}(v)]<0$ and $H$ is positive and increasing. The second to last equality comes from the fact that $\pi_{\underline{v}\mbox{-}\mbox{\tiny SPA}}=\mathbb{E}[\phi_{F}(v)]$ .

To show the tightness of our result, consider $H_{\epsilon}(z)=\mathbf{1}_{\{z\geq\underline{v}\}}+\epsilon z$ . As $\epsilon\to 0$ , we have that $\pi^{*}_{NC}\to\mathbb{E}[\phi(v)]=\pi_{\underline{v}\mbox{-}\mbox{\tiny SPA}}$ while $\pi^{*}_{C}\to\pi_{\mbox{\tiny MYE}}$ . ∎

Proof of Proposition 9.

For $\epsilon>0$ , consider the following instance. $F(v)=v$ (uniform distribution) and

H_{\epsilon}(p)=\begin{cases}\frac{1-\epsilon}{\epsilon}p&\mbox{ if }p\leq\epsilon\\ (1-\epsilon)+\epsilon p&\mbox{ if }p\in[\epsilon,1]\end{cases}.

(6)

From Proposition 1, we have that $r_{\mbox{\tiny MYE}}=1/2$ . Also, from Equation (4) we have that the optimal target $T^{*}_{\epsilon}(1)\leq\epsilon$ . Hence for $\epsilon$ small enough, we have that $T^{*}_{\epsilon}(1)<r_{\mbox{\tiny MYE}}$ , and thus, for every $v\in[0,1]$ we have that $T^{*}_{\epsilon}(v)<T^{*}_{\epsilon}(1)<r_{\mbox{\tiny MYE}}$ since $T^{*}(v)$ is increasing in $v$ (see Lemma 1). Therefore, $\pi^{*}_{WB}=0$ . On the other hand, $\pi^{*}_{NC}\geq r_{\mbox{\tiny MYE}}(1-F(r_{\mbox{\tiny MYE}}))(1-\epsilon)$ . We conclude that for $\epsilon$ small enough $\pi^{*}_{C}>\gamma\cdot\pi^{*}_{WB}$ , independently of the factor $\gamma$ . ∎

Appendix C Proof of Theorem 4

Before proving the theorem, we require the following technical lemma.

Lemma 4 (No Swapping Lemma).

Consider two final marginal bids profile $(b_{0},\bm{b})$ and $(b^{\prime}_{0},\bm{b}^{\prime})$ and a particular realization $\omega_{v}$ . Consider a directed graph $G=(V,E)$ , where each vertex $v$ is one of the participants on the auction and the edge $e=(i,j)$ exists if and only if for profile $(b_{0},\bm{b})$ agent $i$ wins query $x$ and for the profile $(b^{\prime}_{0},\bm{b}^{\prime})$ agent $j$ wins query $x$ . Then the graph $G$ is acyclical.

Proof.

Suppose that for some $\omega_{v}$ , $G$ contains a cycle.

Then consider the sequence of bidders in the auction $i_{1},\ldots,i_{k},i_{1}$ creating the cycle. Let $x_{i_{j}}$ the query that $i_{j}$ wins with the bid profile $(b_{0},\bm{b})$ and that $i_{j+1}$ wins when the bid profile is $(b^{\prime}_{0},\bm{b}^{\prime})$ . Observe that $b_{i_{j}}q_{i_{j}}(x_{i_{j}})>b_{i_{j+1}}q_{i_{j+1}}(x_{i_{j}})$ . Therefore, we derive that

b_{i_{1}}>b_{i_{2}}\frac{q_{i_{2}}(x_{i_{1}})}{q_{i_{1}}(x_{i_{1}})}>b_{i_{1}}\prod_{j=1}^{k}\frac{q_{i_{j+1}}(x_{i_{j}})}{q_{i_{j}}(x_{i_{j}})}.

(7)

where $k+1=i$ .

Using the same logic for the bidding profile $(b^{\prime}_{0},\bm{b}^{\prime})$ we obtain that

b^{\prime}_{i_{1}}<b^{\prime}_{i_{2}}\frac{q_{i_{2}}(x_{i_{1}})}{q_{i_{1}}(x_{i_{1}})}<b^{\prime}_{i_{1}}\prod_{j=1}^{k}\frac{q_{i_{j+1}}(x_{i_{j}})}{q_{i_{j}}(x_{i_{j}})}.

(8)

Equations (7) and (8) generate a contradiction. We conclude that $G$ does not have any cycle. ∎

We are now in a position to prove Theorem 4.

Proof of Theorem 4.

The proof strategy is similar to Theorem 3. Given an arbitrary marginal bid $b_{\tiny\mbox{mCPA}}$ , we want to show that if the bidder submits $b_{\tiny\mbox{mCPA}}\in[0,v]$ using the mCPA format, the bidder can weakly improves her payoff by bidding a target $T=b_{\tiny\mbox{mCPA}}$ with the tCPA format for every realization $\omega_{v}$ . Furthermore, the inequality is strict for a positive measure of $\omega_{v}$ . We split our proof into the following steps.

Let $X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})$ and $X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})$ the subset of queries that the bidder obtains in the mCPA and tCPA cases, respectively. We assert that $X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})\subseteq X^{0}_{\tiny\mbox{tCPA}}(\omega_{v})$ . Suppose for the sake of a contradiction that is not true. Then, consider $x\in X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})\setminus X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})$ . Let $b_{\tiny\mbox{mCPA}}$ and $b^{\prime}_{\tiny\mbox{mCPA}}$ the bidder’s final marginal bid for the mCPA and tCPA cases, respectively. From Lemma 1 we have that $b^{\prime}_{\tiny\mbox{mCPA}}\geq b_{\tiny\mbox{mCPA}}$ . Therefore, since the bidder is losing query $x$ in the tCPA case an extra-buyer $i$ has increased her final marginal bid from $b_{i}$ to $b^{\prime}_{i}$ and wins query $x$ . Thus, for the graph $G$ described in Lemma 4 we have an edge $e=(0,i)$ .

Because the marginal bid of Extra-Buyer $i$ is not constant, it implies that she is using the tCPA format. We assert that there is a query $x^{\prime}\in X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})\setminus X^{0}_{\tiny\mbox{tCPA}}(\omega_{v})$ . Because mCPA extra-buyers do not change their marginal bids and tCPA-extra buyers have a higher marginal bid in the tCPA case (since $b^{\prime}_{i}>b_{i}$ and the game of tCPA-buyers is symmetric), the cost for every query is (weakly) higher in the tCPA case than in the mCPA case. In particular, the average cost-per-acquisition (CPA) of wining queries $X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})$ is at least $T_{i}$ . Moreover, because the queries in $X\setminus X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})$ have a CPA higher than the $T_{i}$ (since $b_{i}\geq T_{i}$ but the Extra-Buyer $i$ did not win those queries in the mCPA case), we have that in order to win query $x$ and, at the same time, keep an average CPA no more than $T_{i}$ , Extra-Buyer $i$ is loosing a query $x^{\prime}\in X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})\setminus X^{0}_{\tiny\mbox{tCPA}}(\omega_{v})$ . If the winner of that query is the bidder, then the edge $e=(i,0)$ belongs to $G$ . From Lemma 4 this is not possible. Suppose the winner of the query is a different Extra-Buyer $k$ . In that case, we can reiterate the logic of this paragraph and either obtain a cycle on $G$ or, again, find another extra buyer winning a new query. Because there is a finite set of extra-buyers, at some point in the iteration $G$ will have a cycle. This is a contradiction. Therefore, $X^{0}_{\tiny\mbox{mCPA}}(\omega_{v})\subseteq X^{0}_{\tiny\mbox{tCPA}}(\omega_{v})$ .

To finish the proof, we follow the same reasoning as the one used for the proof of Theorem 3. We use Step 3. to show the weak inequality for every $\omega_{v}$ and Step 4 to show that the inequality is strict for a positive measure of $\omega_{v}$ . ∎

	$\displaystyle u^{*}(\mbox{mCPA}\|v)$	$\displaystyle=(v-b^{}(v))H(b^{}(v))$
		$\displaystyle=(v-b^{}(v))H(b^{}(b^{}(v);b^{}(v)))$
		$\displaystyle<(v-b^{}(v))H(b(b^{}(v);0))$
		$\displaystyle=u(b^{*}(v)\|v;\mbox{tCPA})$
		$\displaystyle\leq u^{*}(\mbox{tCPA}\|v).$