# efficiency_of_ad_auctions_with_price_displaying__20458971.pdf

Efficiency of Ad Auctions with Price Displaying

Matteo Castiglioni1, Diodato Ferraioli2, Nicola Gatti1, Alberto Marchesi1, Giulia Romano1*

1Politecnico di Milano, Piazza Leonardo da Vinci 32, Milan, Italy 2Universit a degli Studi di Salerno, Via Giovanni Paolo II, Fisciano, Italy {matteo.castiglioni, nicola.gatti, alberto.marchesi, giulia.romano}@polimi.it, dferraioli@unisa.it

Most of the economic reports forecast that almost half of the worldwide market value unlocked by AI over the next decade (up to 6 trillion USD per year) will be in marketing&sales. In particular, AI will enable the optimization of more and more intricate economic settings, in which multiple different activities need to be jointly automated. This is the case of, e.g., Google Hotel Ads and Tripadvisor, where auctions are used to display ads of similar products or services together with their prices. As in classical ad auctions, the ads are ranked depending on the advertisers bids, whereas, differently from classical settings, ads are displayed together with their prices, so as to provide a direct comparison among them. This dramatically affects users behavior, as well as the properties of ad auctions. We show that, in such settings, social welfare maximization can be achieved by means of a direct-revelation mechanism that jointly optimizes, in polynomial time, the ads allocation and the advertisers prices to be displayed with them. However, in practice it is unlikely that advertisers allow the mechanism to choose prices on their behalf. Indeed, in commonly-adopted mechanisms, ads allocation and price optimization are decoupled, so that the advertisers optimize prices and bids, while the mechanism does so for the allocation, once prices and bids are given. We investigate how this decoupling affects the efficiency of mechanisms. In particular, we study the Price of Anarchy (Po A) and the Price of Stability (Po S) of indirect-revelation mechanisms with both VCG and GSP payments, showing that the Po S for the revenue may be unbounded even with two slots, and the Po A for the social welfare may be as large as the number of slots. Nevertheless, we show that, under some assumptions, simple modifications to the indirect-revelation mechanism with VCG payments achieve a Po S of 1 for the revenue.

Introduction Most of the economic reports forecast that artificial intelligence (AI) will unlock up to 12 trillion USD per year worldwide by the next decade, and almost half of this amount will derive from the marketing&sales area (see, e.g., (Chui et al. 2018)). In particular, AI is playing a crucial role to tackle various problems, including, e.g., auction design (Bachrach et al. 2014), the automation of advertisers budget (Nuara

*All the authors contributed equally. Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

et al. 2018) and bidding strategies (He et al. 2013), and the optimization of conversion funnels (Nuara et al. 2019). In this paper, we focus on recently-emerged online advertising settings where ad auctions are employed to display ads of similar products or services together with their prices. This is the case of, e.g., Google Hotel Ads and Tripadvisor, where users search for the availability of a hotel room in a given date. The web page of results shows a ranking of banners advertising similar hotel rooms that match the search criteria. Each banner displays the name of the advertiser providing the online booking service, together with the per-night selling price of the room. Such settings are similar to standard ad auctions, since the ads are ranked depending on the advertisers bids. On the other hand, they also fundamentally differ from them, as the ad allocation must also take prices into account, and these are displayed inside the banners so as to provide a direct comparison among them. This dramatically affects users behavior, as well as the efficiency and the properties of ad auctions. The goal of this work is to investigate how the additional degree of freedom introduced by prices influences the problem of finding an optimal ad allocation and the revenue of the mechanisms. The price-displaying feature of our setting introduces externalities among the ads, since the probability that a user clicks on an ad depends on the prices displayed with both the ad being clicked and the other ads in the allocation. Several forms of externalities are investigated in the literature on ad auctions. However, to the best of our knowledge, no previous work takes into account price displaying. For instance, Kempe and Mahdian (2008) and Aggarwal et al. (2008) introduce a basic user model that is currently adopted by most of the mechanisms. In this model, a Markovian user observes the slots in a top-down fashion, moving down slot by slot with a given continuation probability and stopping on a slot to observe its ad with the remaining probability. Kempe and Mahdian (2008) also propose richer models where the probability with which a user moves from a slot to the next one depends on the ad actually displayed in the former. In this case, it is not known whether the ad allocation problem admits a polynomial-time algorithm; however, Farina and Gatti (2016, 2017) provide several algorithms showing that in special cases a constant approximation can be achieved. Further externalities models are explored by Fotakis, Krysta, and Telelis (2011) and Gatti et al. (2018), which allow for

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

potentially different externalities for each pair of ads. However, with these models, the ad allocation problem is NPhard and, in some cases, even inapproximable. It is also worth mentioning that similar models are adopted in mobile geo-located advertising by Gatti et al. (2014). In our model, we assume that the probability with which a user clicks on an ad depends on the price displayed with the ad and on the lowest among all displayed prices. In particular, we model the click probability as a monotonically decreasing function of the ad price, assuming that the demand curve is monotonically decreasing in the price and that it is unlikely that a user clicks on an ad with a price larger than her reserve value. We also assume that the click probability is monotonically decreasing in the difference between the ad price and the lowest displayed price, as the user s interest in any feature different from price (e.g., brand and loyalty) decreases as such difference increases. In our setting, the private information of each advertiser (i.e., her type) is a pair composed by the probability with which a user visiting the advertiser s web page produces a conversion (e.g., a purchase) and the advertiser s cost for a unit of product or service. On the other hand, the prices constitute an additional degree of freedom that can be controlled by either the advertisers or the mechanism. As a first step, we present a direct-revelation mechanism that maximizes the social welfare by jointly optimizing over the ad allocations and the prices displayed with the ads. Differently from what happens in most of the externalities models studied in the literature, such optimization problem can be solved in polynomial time for a given discretization of price values. We also study the properties of the directrevelation mechanism when VCG payments are used, showing that incentive compatibility, individual rationality and weak budget-balance hold in our setting. In real-world scenarios, it is unlikely that the advertisers let the mechanism select prices on their behalf, as required by the direct-revelation mechanism. In the (indirectrevelation) mechanisms that are currently adopted in realworld applications, the optimization over ad allocations and that over prices are decoupled. In particular, each advertiser finds her optimal price and bid, while the mechanism optimizes over ad allocations once prices and bids are given. As for the direct-revelation mechanism, the best ad allocation can be found in polynomial time given prices and bids. However, even if these indirect-revelation mechanisms allow the advertisers not to reveal private (and potentially sensitive) information, they can lead to inefficient equilibria. We investigate the equilibrium inefficiency of indirectrevelation mechanisms with GSP and VCG payments, in terms of Price of Anarchy (Po A) and Price of Stability (Po S) in complete information settings. In the literature, Po A and Po S are commonly-adopted efficiency metrics for standard ad auctions, in which the price variable is not taken into account. For instance, Paes Leme and Tardos (2010), Caragiannis et al. (2011), Lucier and Leme (2011), and Caragiannis et al. (2015) show that the Po A for the social welfare of the GSP is upper bounded by 1.3 with complete information and by 3 with incomplete information, while Farina and Gatti (2017) and Giotis and Karlin (2008) study the inef-

Ad Publisher Advertiser 3 s Ecommerce

observation click conversion λ3 q3(p3, pmin) 3

Advertiser 3 s value p3 c3

Figure 1: An example of ad auction with price displaying. A user visits a web page with three ads (ad 1, ad 2, and ad 3) together with their prices (p1, p2, and p3). The user observes slot 3 with probability λ3. Once observed slot 3, the user clicks on the ad displayed in slot 3, i.e., ad 3, with probability q3(p3, pmin) where pmin is the minimum price among p1, p2, p3. The user visits the web page of advertiser 3 (e.g., an online marketplace), and, then, produces a conversion (e.g., purchase) with probability α3. The value that advertiser 3 gets from the conversion is p3 c3.

ficiency with specific externalities, and Gatti et al. (2015) investigate learning issues. In our setting, the externalities preclude the adoption of the tools provided by Roughgarden, Syrgkanis, and Tardos (2017) and Hartline, Hoy, and Taggart (2014) to bound the inefficiency of equilibria for the social welfare and the revenue, respectively, thus pushing us to develop ad hoc approaches. In particular, we show that, in our setting, the inefficiency of the indirect-revelation mechanisms with VCG and GSP mechanisms is much higher than that of the classical mechanisms without prices, even when excluding overbidding, since the Po S for the revenue may be unbounded even with two slots and the Po A for the social welfare may be as large as the number of slots. Furthermore, with VCG payments, the Po S for the social welfare is 1, while, with GSP payments, it is at least 2, suggesting that GSP payments perform worse than VCG ones. A crucial question is whether inefficiency can be reduced when letting the advertisers choose their prices. We show that, under some assumptions, simple modifications to the indirect-revelation mechanism with VCG payments requiring each advertiser to report an additional price achieve a Po S of 1 for the revenue.

Formal Model There is a set N = {1, . . . , n} of n agents, who simultaneously play the role of advertisers and sellers. Each agent sells a single good on her own website (e.g., an online marketplace) and relies on an external ad publisher that advertises the good through a single ad in which the price is displayed. Since the goods being sold by the agents are similar, the price comparison that users perform on the publisher s website results in a high competition level among the agents, as happening in classical comparator websites (Jung, Cho, and Lee 2014). In the following, for the ease of presentation, we use index i N to refer to the agent, her good, and also her ad. Figure 1 provides an overview of our scenario. For every i, we denote with ci R 0 and pi R 0 the

cost of supply and the selling price of agent i s good, respectively. Furthermore, we denote with αi [0, 1] the probability with which a user buys agent i s good when visiting her website. Thus, agent i s expected gain from a visit of a user on her website is αi (pi ci). Let us remark that the conversion probability αi is constant w.r.t. the price pi, since we assume that the user is aware of the price before visiting the website and, thus, she does not visit it if the price is larger than her reserve value. As previously discussed, the user first observes the ads on the publisher s website, together with their prices, and, then, she clicks on an ad so as to visit the corresponding advertiser s website. Therefore, the motivation behind an uncompleted conversion following the user s visit to the advertiser s web page does not concern the price (e.g., it may be due to the user acquiring more information on the seller, or potential extra fees and/or ancillary services). The pair (αi, ci) is a private information of agent i, and sometimes we will refer to it as her type θi. We let Θ = [0, 1] R 0 be the space of types of every agent. The ad publisher has a set M = {1, . . . , m} of slots in which the ads are displayed. An assignment of ads to slots (also called allocation) is represented by a function f : N M { } such that there is at most one ad per slot (i.e., there are no ads i, h N such that i = h and f(i) = f(h) M). All the ads that are not assigned to slots in M are assigned to , meaning that these ads are not displayed. For every slot j M, we denote with λj [0, 1] the probability (called prominence) that a user observes the ad displayed in that slot. As customary in the literature, we assume that λ1 λ2 . . . λm. For the ease of notation, we define λ = 0. Furthermore, for every agent i, we denote with qi [0, 1] the probability (called quality) that a user clicks on ad i conditioned on its observation. In our setting, qi depends on the prices, as they are displayed with the ads. In particular, qi is a function of the prices p = {pi}i N of agents whose ads are displayed, since the user can compare all the prices shown on the web page when deciding the website from which to buy a good. This dependency introduces externalities among the ads. In this work, we assume that qi : R 0 R 0 [0, 1], where qi(pi, pmin) denotes the agent i s quality when her price is pi and the minimum price among all the displayed ads is pmin, with pmin = minh N:f(h) M{ph} (for the sake of notation, we omit the dependency of pmin on f). Moreover, given pmin, qi is (non-strictly) monotonically decreasing in pi since, as previously discussed, a user clicks on the ad if the price is non-larger than the user s reserve value. Finally, qi is (nonstrictly) monotonically increasing in pmin, given pi. The rationale behind this assumption is that, given pi, the probability that a user clicks on ad i decreases as the gap between pi and the minimum price pmin increases, capturing a potential reduction of the user s interest for agent i s good. A simple example is when the users are only interested in the price and, thus, qi is zero if pi > pmin. We also assume that there exists pi R 0 maximizing qi(pi, pi) αi (pi ci) and, thus, there exists pi < that agent i would use when displayed alone. Finally, we remark that, as it is customary in the literature, parameters λ and q are estimated by the ad publisher. Every mechanism receives some input (or bid) from ev-

ery agent i, chooses an allocation f, and charges every agent i of a payment πi. We say that the mechanism is directrevelation if the input provided by agent i belongs to Θ, i.e., it consists of a conversion probability and a cost, which are not necessarily the real ones (her type). Otherwise we say that the mechanism is indirect-revelation. In our setting, a direct-revelation mechanism takes as input a reported type θ i = (α i, c i) Θ for each agent i, and chooses some prices p = {pi}i N and an allocation function f. We let b = {bi}i N be the vector of declared gains, where bi = α i (pi c i) is agent i s gain for the reported type θ i. On the other hand, an indirect-revelation mechanism takes as input a price pi and a declared gain bi for each agent i, and chooses an allocation function f. We say that agent i does not overbid if bi αi (pi ci), where pi is the price given as input and (αi, ci) = θi is the true agent i s type. Given an allocation f, prices p, and bi, we denote with bvi(f, p, bi) = λf(i) qi(pi, pmin) bi the expected (w.r.t. clicks and purchase) value of agent i according to her declared gain. The true expected value that she receives from allocation f is vi = λf(i) qi(pi, pmin) αi (pi ci), while agent i s expected utility is ui = vi πi since the environment is quasi-linear.1 The social welfare of an allocation with respect to the declared gains is d SW(f, p, b) = P i bvi(f, p, bi), where b = {bi}i N. The true social welfare is SW = P i vi. The revenue is instead Rev = P i πi. We informally introduce notable properties of mechanisms; see (Mas-Colell, Whinston, and Green 1995) for formal definitions. A mechanism, both directand indirectrevelation, is individually rational, if for every agent i, the assigned payment πi is non-larger than her value ˆvi(f, p, bi) according the declared gain. Furthermore, a mechanism is weakly budget-balanced if the sum of payments is always non-negative. A direct-revelation mechanism is truthful if for every agent i it is a dominant strategy to report the true type θi = (αi, ci) to the mechanism, i.e., the utility that agent i achieves by reporting θi is at least as large as with every alternative input, regardless of other agents actions. For indirect-revelation mechanisms, we say that a set of inputs is in equilibrium according to Nash (1951) if no agent may increase her utility by submitting a different bid, whenever the inputs of other agents remain unchanged.

Mechanisms Next, we introduce our direct-revelation mechanism and two indirect-revelation mechanisms.

Direct-revelation Mechanism We let MVCG D be the direct-revelation mechanism defined as follows. Given the agent i s input θ i = (α i, c i) Θ, the mechanism defines bi = α i (pi c i) for every price pi. Then, the mechanism computes an assignment f and prices p that maximize the social welfare with respect to the declared gains; formally, d SW(f , p , b) = max f,p d SW(f, p, b).

1The dependency of vi, ui, πi on the arguments f, p, bi is omitted to avoid cumbersome notation.

Finally, the mechanism assigns to each advertiser i in the allocation (i.e., such that f(i) M) the VCG payment

πi = max f,p: f(i)/ M

bvj(f, p, bj) bvj(f , p , bj)

= bvi(f , p , bi) i,

i = d SW(f , p , b) max f,p:f(i)/ M d SW(f, p, b) 0.

It is immediate to check that payments cannot be negative and they are never larger than the value corresponding to the declared gain. Thus, the mechanism is trivially individuallyrational and weakly budget-balanced. Moreover, it is not hard to verify that these payments allow the mechanism to be truthful (essentially this is a VCG mechanism and there is no interdependence among types). Truthfulness also implies that the mechanism maximizes the true social welfare. These observations prove the following theorem. Theorem 1. Mechanism MVCG D is truthful, individually rational, weakly budget-balanced, and maximizes SW.

Indirect-revelation Mechanisms Next, we introduce two alternative mechanisms, namely MVCG I and MGSP I . These mechanisms share the same structure, but they differ in the way they compute the payments. They work as follows. Agent i inputs (pi, bi), where pi R 0 is the price that agent i wants to be displayed for her ad and bi R is the expected gain that i declares to achieve from a click on her ad for price pi. The mechanism computes an assignment g that maximizes the social welfare with respect to the submitted prices and gains; formally

d SW(g , p, b) = max g d SW(g, p, b).

Then, MVCG I assigns to each advertiser i such that g (i) M the VCG payment

πi = max g : g(i)/ M

bvj(g, p, bj) bvj(g , p, bj)

= bvi(g , p, bj) δi,

δi = d SW(g , p, b) max g:g(i)/ M d SW(g, p, b) 0.

W.l.o.g., let the optimal allocation g be such that only the first ℓ m slots are assigned and no slot j > ℓis assigned. MGSP I assigns to each i such that g (i) M and g (i) < ℓ (i.e., i is assigned to a slot different from ℓ) the following payments: ϖi = λg (i)qj(pj, pmin)bj, (1)

where j is such that g (j) = g (i) + 1. When g (i) = ℓ, there are two possible payments. If all the not assigned agents j (i.e., such that g (j) = ) have a price pj < pmin, then ϖi = 0. Otherwise, the payment is

ϖi = λg (i) max j:pj pmin g (j)= {qj(pj, pmin)bj}. (2)

As done for MVCG D , it is immediate to check that payments are at least zero, and they are always less than the value corresponding to the declared gain. Hence, MVCG I is individually rational and weakly budget-balanced. Moreover, one may hope that the inputs that agents select at any equilibrium are such that the allocation selected by the mechanism maximize the social welfare. Unfortunately, we will show in the next sections that this is not the case. The payments of MGSP I are at least zero, and, thus, the mechanism is weakly budged-balanced. Let us also observe that, given agent i, j s.t. g (j) > g (i) or g (j) = pj pmin, we have that qj(pj, pmin)bj qi(pi, pmin)bi. Otherwise, the allocation g achieved from g by fixing g(j) = g (i), g(i) = g (j), and g(k) = g (k) k / {i, j} would achieve a larger social welfare (according to declared gains). Hence, we have that ϖi bvi(g , p, bi), and, thus, the mechanism is individually rational. We remark that for this property to hold, it is fundamental that, in Equation 2, we consider only the not assigned agents j who have a declared price pj pmin. Indeed, an agent j with pj < pmin may have a large qj(pj, pj)bj so that, if the j-th ad is displayed, the minimum price changes from pmin to pj, qj(pj, pj)bj > qi(pi, pmin)bi, and ϖi > bvi(g , p, bi), where i is the agent assigned to the slot ℓ. Nevertheless, this agent may not be chosen by the allocation g because of the negative externalities that its low price would put on other agents (by lowering their value and thus the social welfare). As a result an optimal allocation may not assign all the available slots. We finally observe that, as for MVCG I , even MGSP I may fail to optimize the true social welfare. The following sections will bound the extent of this failure.

Computational Complexity In general, externalities make hard the problem of computing the allocation maximizing the social welfare. In this section, we prove that in our setting the problem of allocating advertisers to slots can be solved in polynomial time by both the directand the indirect-revelation mechanisms. Let us start with the problem of computing the allocation g in the indirect-revelation mechanisms. We show in the next theorem that g can be efficiently computed. Theorem 2. There is an algorithm that computes the allocation g in time O(n2 log n).

Proof. Let b and p be the set of gains and prices submitted by agents. First observe that, given a minimum displayed price pmin, the allocation that maximizes the social welfare (with respect to gains and prices in input), can be trivially computed by sorting agents in {i: pi pmin} in order of qi(pi, pmin)bi and assigning slot 1 to the agent that maximizes this quantity, slot 2 to the second such agent, and so on. Note that this operation requires O(n log n) steps. However, in order to provide the allocation g , we also need to decide which is the best value for pmin. However, since pmin must belong to p, it is sufficient to compute the best allocation by using as minimum displayed price each of the at most n different prices in p, and choosing the allocation that optimizes the social welfare.

Computing g is an easier problem than the one faced by the direct-revelation mechanism, since, for the former, prices are given and we optimize only over the allocation function, while, for the latter, optimization occurs both on the allocation function and prices. Nevertheless, the following theorem shows that f and p can also be computed efficiently, as long as the set P of allowed prices is discrete and finite. Theorem 3. There is an algorithm that computes the allocation f and prices p in time O(n2|P|(|P| + log n)).

Proof. Let bi(p) = α i(p c i) be the expected gain of agent i according to her input when ad i is displayed with price p, where (α i, c i) is the input of agent i. For each agent i and every price ˆp P we compute p i (ˆp) as follows: if maxp P :p ˆp qi(p, ˆp)bi(p) > 0, then

p i (ˆp) = arg max p P :p ˆp qi(p, ˆp)bi(p),

otherwise we set p i (ˆp) = . Roughly speaking, p i (ˆp) is the best price (according to her input) for agent i when the minimum displayed price is ˆp and the i-th ad is displayed (and thus i s price is at least ˆp). Clearly, if there is no price larger than or equal to ˆp guaranteeing to agent i a positive utility, then she prefers to be not displayed. For this reason, in the latter case, we do not assign any value to p i (ˆp). Notice that p i (ˆp) can be computed by evaluating the function for every p P with p ˆp, requiring at most O(|P|) operations. Then, if the minimum displayed price pmin was given, along with the agent to which it is assigned, then we simply choose price p i (pmin) for each remaining agent i (this can be done in O(n P) steps), prune out agents for which p i (pmin) = , and finally compute the corresponding optimal assignment by sorting the remaining agents in order of bi(p i (pmin)), as shown in Theorem 2 (in O(n log n) steps). Unfortunately, selecting pmin is much harder than in the indirect case: not only the value of pmin can assume every value in P (and not just one among at most n alternatives), but we also need to decide which agent should display this price. For this reason, we need to go through every price p P and every agent i and compute the best solution that would be achieved when i is the agent displaying the minimum price p. Since for each of the n P possible choices, computing the best solution requires time O(n P + n log n), we achieve the desired running time.

Observe that the dependence on |P| in Theorem 3 is in some way necessary as long as we would like to keep quality function as general as possible. It is not hard to see that we can avoid to check all prices by doing opportune restriction on the quality functions. We finally highlight that the discretization of the set of prices does not affect the property of the mechanism. In particular, truthfulness continues to hold, since the mechanism is maximal-in-the-range.

Performance of the Indirect Mechanisms For the sake of presentation, we provide the informal definitions of Po S and Po A for social welfare and revenue; formal definitions can be found in (Nisan et al. 2007).

Po S for the social welfare is the minimum w.r.t. all the Nash equilibria ratio between the maximum achievable social welfare and the social welfare of an allocation achievable in a Nash equilibrium of an indirect-revelation mechanism MVCG I or MGSP I . Po A for the social welfare is the maximum w.r.t. all the Nash equilibria ratio between the maximum achievable social welfare and the social welfare of an allocation achievable in a Nash equilibrium of an indirect-revelation mechanism MVCG I or MGSP I . Po S for the revenue is the minimum w.r.t. all the Nash equilibria ratio between the maximum revenue achievable by an individually-rational mechanism and the revenue achievable in a Nash equilibrium of an indirectrevelation mechanism MVCG I or MGSP I . Po A for the revenue is the maximum w.r.t. all the Nash equilibria ratio between the maximum revenue achievable by an individually-rational mechanism and the revenue achievable in a Nash equilibrium of an indirectrevelation mechanism MVCG I or MGSP I . Table 1 summarizes the lower and upper bounds over the mechanisms inefficiency when agents do not overbid; the results when agents overbid are omitted since the inefficiency can be arbitrary even with a single slot. Interestingly, while MVCG I performs as well as MVCG D with a single slot as MVCG I and MVCG D are equivalent in this case since there is no externality; with more than 2 slots the inefficiency can be large both for social welfare and revenue even in the basic case in which slots are indistinguishable and λ = 1. In particular, in our proofs of the upper-bound results, we use a special class of quality functions that we denote as onlymin functions, which assign a value 0 to the quality of an agent when her price is not the minimum among those displayed, and we prove that in many cases no worse instance is possible. With multiple slots, the positive result is that, with MVCG I , the optimal allocation is always achievable by some Nash equilibrium (i.e., Po S = 1). Nevertheless, there are auction instances in which some Nash equilibria lead to allocations whose social welfare is 1/m of the optimal allocation (i.e., Po A = m) or in which all the Nash equilibria lead to a revenue of zero whereas the direct-revelation mechanism MVCG D provides a strictly positive revenue (i.e., Po S = ). MGSP I performs even worse than MVCG I , both

1 slot m 2 slots SW Rev. SW Rev. Po S Po A Po S Po S Po A Po S

MVCG I 1 1 1 ( )

MGSP I 1 1 2 m

Table 1: Lower and upper bounds over Po S and Po A when agents do not overbid. : Po S here is taken w.r.t. the mechanism MVCG D maximizing the social welfare (thus not necessarily maximizing the revenue).

with a single and multiple slots. In the following, we formally provide the results on the lower and upper bounds over the mechanisms inefficiency.

Price of Stability for the Social Welfare Initially, we provide our main positive result in terms of indirect-revelation mechanisms inefficiency. Theorem 4. The Po S for the social welfare of MVCG I is 1.

Proof. Suppose that each agent i reports the pair ( pi, bi) defined as follows: if the mechanism MVCG D displays the ad i when run on truthful bids, then pi is the corresponding price, and bi = αi( pi ci), i.e., the true gain associated to this price; otherwise pi = bi = 0. It is immediate to check that with these bids the allocation returned by MVCG I is exactly the same as the one returned by MVCG D , and, thus, it maximizes social welfare. Unfortunately, we cannot conclude that inputs ( pi, bi) are in equilibrium directly from the truthfulness of MVCG D . Indeed, the payments assigned by the indirect mechanism are different from the ones assigned by the direct mechanism. Moreover, in the former the agent may lie both about the price and about the expected gain, while in the latter an agent may essentially lie only on the expected gain. Still, in the following we prove that inputs ( pi, bi) are in equilibrium, and, thus, the theorem follows. In particular, let p = ( p1, . . . , pn) and b = ( b1, . . . , bn). We prove that the utility ui of agent i when the mechanism MVCG I is run on p and b is at least the utility ui that she achieves if the mechanism would be run on input p = (pi, p i) and b = (bi, b i), for every i, pi, and bi. Indeed if i is allocated by the mechanism MVCG I when run on input p and b, then, since, by definition of bi, vi = bvi(f , p, bi),

ui = vi πi = bvi(f , p, bi) πi

= d SW(f , p, b) max g:g(i)/ M d SW(g, p, b) 0,

where f is the allocation returned by MVCG D on truthful bids. If i is instead, unallocated then

ui = 0 = d SW(f , p, b) max g:g(i)/ M d SW(g, p, b).

Thus, if the agent i is unallocated by the mechanism MVCG I when run on input p and b, then the equilibrium condition is trivially satisfied. Otherwise, let ˇbi = αi(pi ci) and ˇb = (ˇbi, b i). We have:

ui = vi πi = bvi(g , p,ˇbi) bvi(g , p, bi)

+ d SW(g , p, b) max g:g(i)/ M d SW(g, p, b)

= d SW(g , p, ˇb) max g:g(i)/ M d SW(g, p, b),

where the last equality follows since pj = pj and bj = bj for every agent j = i. Since d SW(f , p, b) d SW(g , p, ˇb), because f and p are the allocation and the prices that maximize the social welfare, we have that ui ui, as desired.

The proof of the theorem above shows that, with VCG payments, there is always a Nash equilibrium in which every agent i bids the truthful gain bi and the price that MVCG D would use. Such a strategy profile leads to the same allocation of MVCG D , thus guaranteeing a Po S for the social welfare of 1, but, as we discuss in the following sections, the revenue of the two mechanisms can be different. The same result does not hold in the case of GSP payments, thus leading to a larger Po S for the social welfare. Theorem 5. The Po S for the social welfare of MGSP I is at least 2 even if agents do not overbid.

Price of Anarchy for the Social Welfare We initially focus on the basic case with a single slot, showing that in this case MVCG I and MGSP I are efficient.2

Theorem 6. The Po A for the social welfare of MVCG I and MGSP I is 1 if m = 1 when agents do not overbid. Then, we study the case with multiple slots providing a lower bound on Po A. Theorem 7. The Po A for the social welfare of MVCG I and MGSP I is at least m if m 2 when agents do not overbid.

In the specific case of MVCG I , we show that a Po A larger than m is not possible, and therefore there are no instances worse than those used in the proof of Theorem 7. Most interestingly, this result holds even when qi is not monotonically decreasing in pi. Theorem 8. The Po A for the social welfare of MVCG I is at most m if m 2 when agents do not overbid. Finally, we show that when agents overbid, the inefficiency can be arbitrarily large. Theorem 9. The Po A for the social welfare of MVCG I and MGSP I is even if m = 1 when agents can overbid.

Price of Stability for the Revenue Initially, we provide our main result, showing that MVCG I and MGSP I can be arbitrarily inefficient even with 2 slots.

Theorem 10. The Po S for the revenue of MVCG I and MGSP I is even if m = 2. In the specific case of MVCG I and m = 1, we have a positive result for Po S (Po A is trivially as it is even in second-price single-item auctions). Theorem 11. The Po S for revenue of MVCG I with respect to the mechanism MVCG D is 1 if m = 1. Instead, the above positive result does not hold with MGSP I , as stated below.

Theorem 12. The Po S for the revenue of MGSP I is even if m = 1 when agents do not overbid. In the proof of this theorem we strongly rely upon the definition of GSP payments described above, which restricts payments to depend only on agents submitting a price at

2All the proofs of the theorems in this section and the following one are in (Castiglioni et al. 2022).

least pmin. This payment format turns out to be necessary in order to guarantee individual rationality. We leave open the problem of understanding if a better Price of Stability for the revenue of MGSP I would be possible by considering alternative non-individually rational GSP payments.

A Better Po S for the Revenue with Indirect-revelation Mechanisms As discussed in the previous section, indirect-revelation mechanisms present major weaknesses in terms of efficiency. A natural question is whether we can design indirectrevelation mechanisms with a better efficiency when agents can choose their price. In particular, we focus on MVCG I , as it always guarantees Po S = 1 for the social welfare, and we show that a simple modification of the mechanism leads to Po S = 1 for the revenue when some assumptions hold. We call this new mechanism MVCG I . The rationale is to ask agents for more information. More precisely, the input provided by every agent is a triple composed of (bi, pi, p i ) where (bi, pi) is the input to MVCG I and p i is the price that advertiser i would choose when her ad is the only displayed ad. The property that Po S = 1 is guaranteed when function qi(pi, pi) is differentiable in pi and non-zero in p i . Mechanism MVCG I is defined as follows: 1. every agent i submits a bid (bi, pi, p i ), where bi, pi, and p i are defined as above; 2. the mechanism infers the values of ci and αi for every agent i as follows: ˆci = q(p i , p i ) / dq(pi,pi)

dpi pi=p i + p i ,

and ˆαi = bi pi ˆci if pi = ˆci and ˆαi = 0 otherwise;

3. the mechanism computes an auxiliary allocation, say f, by using the allocation function of MVCG I when the input is (bi, pi) for every agent i; the corresponding social welfare (evaluated with the declared gain bi) is d SW; 4. for every agent i, the mechanism computes an auxiliary allocation, say f i, by using the allocation function of MVCG D when the values inferred above for {ˆαh}h N and {ˆch}h N are provided in input and agent i is removed from the optimization problem. For every maximization, we denote with SW i the corresponding social welfare evaluated with the inferred values {ˆαh}h N and {ˆch}h N. Notice that, as it happens with MVCG D , the prices in output to these maximizations can be different from those agents provide in input;

5. if d SW maxi SW i, then the mechanism chooses allocation f and charges every agent i of a payment πi = SW i (d SW λ f(i) qi(pi, pmin) bi), else no ad is allocated and every agent is charged a payment of zero. Basically, mechanism MVCG I exploits the additional information asked to the agents to infer their types and then uses this information to compute the same payments that MVCG D would charge. Step 5 is necessary to guarantee individual rationality. More precisely, since the allocation f is computed as the indirect mechanism does (without optimizing over prices), while the payments {πi}i N are computed as

the direct mechanism does (optimizing over prices), individual rationality may not be satisfied. We solve this problem setting the payments to 0 (and allocating no ads) when the payments {πi}i N are too large. As a side effect, we have that if the submitted prices are different from the optimal one, it is possible that the mechanism does not assign any slot. Thus, the Po A for the social welfare and revenue can be unbounded. Theorem 13. Mechanism MVCG I is individually rational and weakly budget-balanced. Moreover, the Po S for the revenue of MVCG I is 1. We recall that the algorithm we provide to find the best allocation with MVCG I works when the values that pi can assume are discrete, and the same holds with MVCG I . We also notice that MVCG I requires that p i is not restricted to a set of discrete values, the mechanism could not infer the exact values of αi and ci otherwise. However, requiring price pi to belong to a finite, discrete set of values and price p i to belong to R 0 does not modify the properties of the mechanism since p i is not used in the allocation algorithm.

Conclusions and Future Work In this paper, we investigate how displaying prices together with ads affects the users behavior and the properties of auction mechanisms. Since the goods sold by the agents are similar, a high competition among the agents arises from the price comparison. Specifically, the prices introduce externalities as the probability with which a user clicks on an ad depends on the price of that ad and on the prices of the other displayed ads. Interestingly, the social welfare can be maximized when a direct-revelation mechanism jointly optimizes over the ad allocation and the prices, and this can be done in polynomial time when the prices can assume a finite set of values. However, in practice, it is unlikely that advertisers would allow the mechanism to choose prices on their behalf and, in commonly-adopted mechanisms, ads allocation and price optimization are decoupled, so that the advertisers optimize prices and bids, while the mechanism does so for the allocation, once prices and bids are given. We show that this decoupling makes standard mechanisms with VCG and GSP payments highly inefficient in terms of Po A and Po S for social welfare and revenue. Finally, we investigate whether we can reduce the inefficiency of such mechanisms. We show that we can obtain Po S of 1 for the revenue by asking the advertisers for an additional price that the mechanism exploits to infer some advertisers parameters. Such a modification can be easily implemented without agents revealing their sensitive information. Many research directions can be explored in future. The most interesting concerns how the bidding strategies commonly adopted for standard ad auctions without prices can be extended to our case. In particular, the crucial question is whether, as in the case of the standard GSP without prices, there are bidding strategies converging to notable Nash equilibria. Other interesting questions concern the analysis of Po A and Po S and the design of allocation algorithms when the quality functions satisfy specific properties, such as, e.g., smoothness.

References Aggarwal, G.; Feldman, J.; Muthukrishnan, S.; and P al, M. 2008. Sponsored Search Auctions with Markovian Users. In WINE, 621 628. Bachrach, Y.; Ceppi, S.; Kash, I.; Key, P.; and Kurokawa, D. 2014. Optimising trade-offs among stakeholders in ad auctions. In ACM EC, 75 92. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; and Kyropoulou, M. 2011. On the efficiency of equilibria in Generalized Second Price auctions. In EC. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M.; Lucier, B.; Paes Leme, R.; and Tardos, E. 2015. Bounding the inefficiency of outcomes in generalized second price auctions. Journal of Economic Theory, 156: 343 388. Castiglioni, M.; Ferraioli, D.; Gatti, N.; Marchesi, A.; and Romano, G. 2022. Efficiency of Ad Auctions with Price Displaying. ar Xiv preprint ar Xiv:2201.12275. Chui, M.; Manyika, J.; Miremadi, M.; Henke, N.; Chung, R.; Nel, P.; and Malhotra, S. 2018. Notes From The AI Frontier Insights From Hundreds Of Use Cases. Mc Kinsey Global Institute. Farina, G.; and Gatti, N. 2016. Ad Auctions and Cascade Model: GSP Inefficiency and Algorithms. In AAAI, 489 495. Farina, G.; and Gatti, N. 2017. Adopting the Cascade Model in Ad Auctions: Efficiency Bounds and Truthful Algorithmic Mechanisms. J. Artif. Intell. Res., 59: 265 310. Fotakis, D.; Krysta, P.; and Telelis, O. 2011. Externalities among advertisers in sponsored search. In SAGT, 105 116. Gatti, N.; Lazaric, A.; Rocco, M.; and Trov o, F. 2015. Truthful learning mechanisms for multi-slot sponsored search auctions with externalities. Artificial Intelligence, 227: 93 139. Gatti, N.; Rocco, M.; Ceppi, S.; and Gerding, E. 2014. Mechanism Design for Mobile Geo-Location Advertising. In AAAI, 691 697. Gatti, N.; Rocco, M.; Serafino, P.; and Ventre, C. 2018. Towards better models of externalities in sponsored search auctions. Theoretical Computer Science, 745: 150 162. Giotis, I.; and Karlin, A. 2008. On the equilibria and efficiency of the GSP mechanismin keyword auctions with externalities. In WINE, 629 638. Hartline, J.; Hoy, D.; and Taggart, S. 2014. Price of anarchy for auction revenue. In EC, 693 710. He, D.; Chen, W.; Wang, L.; and Liu, T. 2013. A Game Theoretic Machine Learning Approach for Revenue Maximization in Sponsored Search. In IJCAI, 206 212. Jung, K.; Cho, Y.; and Lee, S. 2014. Online shoppers response to price comparison sites. Journal of Business Research, 67(10): 2079 2087. Kempe, D.; and Mahdian, M. 2008. A cascade model for externalities in sponsored search. In WINE, 585 596. Lucier, B.; and Leme, R. P. 2011. GSP auctions with correlated types. In EC.

Mas-Colell, A.; Whinston, M.; and Green, J. 1995. Microeconomic Theory. Oxford University Press. Nash, J. 1951. Non-cooperative games. Annals of mathematics, 286 295. Nisan, N.; Roughgarden, T.; Tardos, E.; and Vazirani, V. 2007. Algorithmic Game Theory. USA: Cambridge University Press. Nuara, A.; Sosio, N.; Trov o, F.; Zaccardi, M.; Gatti, N.; and Restelli, M. 2019. Dealing with Interdependencies and Uncertainty in Multi-Channel Advertising Campaigns Optimization. In WWW, 1376 1386. Nuara, A.; Trov o, F.; Gatti, N.; and Restelli, M. 2018. A Combinatorial-Bandit Algorithm for the Online Joint Bid/Budget Optimization of Pay-per-Click Advertising Campaigns. In AAAI, 2379 2386. Paes Leme, R.; and Tardos, E. 2010. Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction. In FOCS, 735 744. Roughgarden, T.; Syrgkanis, V.; and Tardos, E. 2017. The Price of Anarchy in Auctions. J. Artif. Intell. Res., 59: 59 101.