Nicola Gatti
email: nicola.gatti@polimi.it

Alessandro Lazaric
email: alessandro.lazaric@inria.fr

Marco Rocco
email: marco.rocco@polimi.it

Francesco Trovò
email: francesco1.trovo@polimi.it

Truthful Learning Mechanisms for Multi-Slot Sponsored Search Auctions with Externalities $

Keywords: Economic paradigms, mechanism design, online learning, sponsored search auctions

Sponsored Search Auctions (SSAs) constitute one of the most successful applications of microeconomic mechanisms. In mechanism design, auctions are usually designed to incentivize advertisers to bid their truthful valuations and, at the same time, to guarantee both the advertisers and the auctioneer a non-negative utility. Nonetheless, in sponsored search auctions, the Click-Through-Rates (CTRs) of the advertisers are often unknown to the auctioneer and thus standard truthful mechanisms cannot be directly applied and must be paired with an effective learning algorithm for the estimation of the CTRs. This introduces the critical problem of designing a learning mechanism able to estimate the CTRs at the same time as implementing a truthful mechanism with a revenue loss as small as possible compared to the mechanism that can exploit the true CTRs. Previous work showed that, when dominant-strategy truthfulness is adopted, in single-slot auctions the problem can be solved using suitable exploration-exploitation mechanisms able to achieve a cumulative regret (on the auctioneer's revenue) of order O(T 2 3 ), where T is the number of times the auction is repeated. It is also known that, when truthfulness in expectation is adopted, a cumulative re-$ A short, early version of this paper was presented at the

Introduction

SSAs constitute one of the most successful applications of microeconomic mechanisms, producing a revenue of about $6 billion dollars in the US alone in the first half of 2010 [1]. In a SSA, a number of advertisers bids to have their sponsored links (from here on ads) displayed in some slot alongside the search results of a keyword. SSAs currently adopt the pay-per-click payment scheme, which requires positive payments from an advertiser only when its ad is clicked. Given an allocation of ads over the available slots, each ad is associated with a CTR, corresponding to the probability of being clicked by the user. CTRs play a crucial role in the definition of the auction, since the auctioneer relies on (estimates of) the CTRs to determine the allocation of ads over slots and to compute the payment of each ad. Models similar to SSAs are also used in many other advertisement applications. For instance, in contextual advertising, the text of a website is scanned for keywords and an auction is used to select the ads to display in vertical/horizontal slots on the basis of the advertisers' bids and CTRs of the ads in the given context [START_REF] Varian | The VCG auction in theory and practice[END_REF].

In microeconomic literature, SSAs have been formalized as a mechanism design problem [START_REF] Narahari | Game Theoretic Problems in Network Economics and Mechanism Design Solutions[END_REF], where the objective is to design an auction that incentivizes advertisers to bid their truthful valuations (needed for economic stability) and that guarantees both the advertisers and the auctioneer to have a non-negative utility. The most common SSA mechanism is the Generalized Second Price (GSP) auction [START_REF] Edelman | Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords[END_REF][START_REF] Varian | Position auctions[END_REF]. As shown in [START_REF] Edelman | Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords[END_REF], this mechanism is not truthful and advertisers may implement bidding strategies that pay more than bidding their truthful valuations.

While the GSP is still popular in many SSAs, the increasing evidence of its limits is strongly pushing towards the adoption of the more appealing Vickrey-Clarke-Groves (VCG) mechanism, which is already successfully employed in the related scenario of contextual advertising, by Google [START_REF] Varian | The VCG auction in theory and practice[END_REF] and Facebook [START_REF] Hegeman | Facebook's ad auction[END_REF]. The first drawback of the GSP is that its equilibria may be inefficient (in terms of social welfare) w.r.t. the VCG outcome: considering the whole set of Nash equilibria in full information, the Price of Anarchy (PoA) of the GSP is upper bounded by about 1.6, while considering the set of Bayes-Nash equilibria the PoA is upper bounded by about 3.1 [START_REF] Leme | Pure and bayes-nash price of anarchy for generalized second price auction[END_REF]. Similarly, the revenue of a (full information) Nash equilibrium can be arbitrarily small w.r.t. the VCG outcome, while in the Bayesian case the revenue is upper bounded by 6 [START_REF] Brendan Lucier | On revenue in the generalized second price auction[END_REF]. Furthermore, the automated bidding strategies, used in practice by the advertisers to find their best bids, may not even converge to any Nash equilibrium and, under mild assumptions, the states they converge to are shown to be arbitrarily inefficient [START_REF] Markakis | Discrete strategies in keyword auctions and their inefficiency for locally aware bidders[END_REF]. When externalities are introduced, it is known that no Nash equilibrium of the GSP provides a larger revenue than the VCG outcome [START_REF] Kuminov | User modeling in position auctions: reconsidering the gsp and vcg mechanisms[END_REF][START_REF] Gomes | Externalities in keyword auctions: An empirical and theoretical assessment[END_REF]. Finally, there is a recent increase in the use of additional features (such as larger formats, reviews, maps, or phone numbers) arranged by the search engines on the web page together with the ads to increase the attention of the user. It is known that the GSP behaves poorly in this setting, while the VCG is almost equivalent to the standard setting [START_REF] Yoram | Optimising tradeoffs among stakeholders in ad auctions[END_REF].

In this paper, we focus on the problem of designing truthful mechanisms when the CTRs are not known and need to be estimated in SSAs with multiple slots. This problem is particularly relevant in practice because the assumption that all the CTRs are known beforehand is rarely realistic. Furthermore, it also poses interesting scientific challenges since it represents one of the first examples where online learning theory and mechanism designtwo important fields in artificial intelligence that recently received a lot of attention in the literature-are paired to obtain effective methods to learn under equilibrium constraints (notably the truthfulness property). For the sake of completeness, we remark that the combination of these ideas have been used also in the other fields, e.g., crowdsourcing [START_REF] Tran-Thanh | Efficient crowdsourcing of unknown experts using multi-armed bandits[END_REF].

Related works. The problem of estimating the CTRs and identifying the best allocation of ads can be effectively formalized as a Multi-Armed Bandit (MAB) problem [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF], where each ad is an arm and the objective is to minimize the cumulative regret either on the auctioneer's revenue or the social welfare, i.e., the difference in revenue or social welfare, respectively, of the mechanisms implemented over time estimating the CTRs and of the mechanisms that can exploit the true CTRs. The problem of budgeted advertisers (i.e., auctions where the total amount of money each advertiser is willing to pay is limited) with multiple queries is considered in [START_REF] Pandey | Handling Advertisements of Unknown Quality in Search Advertising[END_REF]. This problem is formalized as a budgeted multi-bandit multi-arm problem, where each bandit corresponds to a query, and an algorithm is proposed with theoretical guarantees on auctioneer revenue regret. Nonetheless, the proposed method works in a non-strategic environment, where advertisers do not try to influence the outcome of the auction and always bid their true values. The strategic dimension of SSAs is partially taken into consideration in [START_REF] Langford | Maintaining equilibria during exploration in sponsored search auctions[END_REF], where the advertisers are assumed to play a bidding strategy at the equilibrium of the GSP w.r.t. a set of estimated CTRs available to both the auctioneer and the advertisers. The authors introduce a learning algorithm which explores different rankings of the ads to improve the CTR estimates and, at the same time, to avoid that the advertisers have incentives to deviate from the aforementioned equilibrium strategy. In [START_REF] Gonen | An incentive-compatible multi-armed bandit mechanism[END_REF][START_REF] Gonen | Adaptive incentive-compatible sponsored search auction[END_REF], the authors formulate for the first time the problem of designing truthful learning mechanisms according to the notion of truthfulness in high probability in multi-slot SSAs. The single-slot online advertising is studied also in [START_REF] Nazerzadeh | Dynamic cost-per-action mechanisms and applications to online advertising[END_REF] where the notion of Bayesian Incentive Compatibility (BIC) is taken into consideration and an asymptotically BIC and ex ante efficient mechanism is introduced.

The most complete study of truthful bandit mechanisms so far is reported in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF] and [START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF]. These works provide a complete analysis on the constraints that truthfulness forces on the MAB algorithm with single-slot SSAs, proving that no dominant-strategy truthful bandit mechanism can achieve a regret (over social welfare or auctioneer's revenue) smaller than Ω(T 2 3 ) and that the exploration and exploitation phases must be separate. 1,2 The lower bound over the regret holds also when the truthfulness is in expectation w.r.t. the click realizations. Finally, they also provide nearly-optimal algorithms matching the lower bound on the regret. In both [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF] and [START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF], advertisers' utility is not subject to any form of time discount, in contrast with what happens in practice, where advertisers may favor early small gains over larger gains in the future. However, the mechanisms introduced in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF] and [START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF] are truthful even in presence of discount since the sharp separation of exploration and exploitation would still force advertisers with discounting to reveal their true valuation. 3 When the notion of truthfulness is relaxed, adopting truthfulness in expectation w.r.t. the mechanism randomness, it is possible to obtain in the case of single-slot SSAs a regret Õ(T 1 2 ) (over the social welfare) without separating the exploration and exploitation phases [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF].

When multiple slots are present, a user model is needed to describe how the CTR of an ad changes as its position in the allocation changes. All the models available in the literature assume that the CTR is given by the product of two terms: the probability that an ad is clicked once observed by the user, and the probability that the user observes an ad given the complete allocation of ads over slots. The basic model (commonly referred to as separability model ) prescribes that the probability of observing an ad depends only on its position [START_REF] Narahari | Game Theoretic Problems in Network Economics and Mechanism Design Solutions[END_REF]. Recently, more accurate models have been proposed and one of the most popular models is the cascade model. According to this model, the user scans the slots from top to bottom and the probability that she moves from a given slot to the next depends on the former slot itself and the identity of the ad displayed in it (this kind of user is commonly called Markovian user ) [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF][START_REF] Aggarwal | Sponsored search auctions with markovian users[END_REF]. As a result, the overall probability of observing an ad depends on the slot in which it is displayed and on all the ads allocated above it. The validity of the cascade model has been evaluated and supported by a wide range of experimental investigations [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF][START_REF] Joachims | Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search[END_REF]. The only results on learning mechanisms for SSAs with multiple slots are described in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF], where the authors characterize dominant-strategy truthful mechanisms and provide theoretical bounds over the social welfare regret for the separability model. However, these results are partial (e.g., they do not consider the common case in which the slot-dependent parameters are monotonically decreasing over slots), and they cannot be easily extended to the more challenging case of the cascade model (see Section 3.3).

Original contributions. In the present paper, we build on the results available in the literature and we extend the partial results presented in [START_REF] Gatti | A truthful learning mechanism for contextual multi-slot sponsored search auctions with externalities[END_REF] to a wider range of cases, providing also a number of contributions when the separability model and the cascade model are adopted. More precisely, our results can be summarized as follows.

• Separability model with monotonically decreasing parameters/only positiondependent cascade model. In this case, there are two groups of parameters, one related to the ads (called quality) and one to the slots (called prominence). We studied all the configurations of information incompleteness. When only qualities are unknown, we provide a nonrandomized learning mechanism that is dominant-strategy truthful a posteriori w.r.t. the click realizations and with a regret of Õ(T

3 ) (while it is an open problem whether it is possible to obtain a better upper bound adopting truthfulness in expectation). 4 When only prominences are unknown, we provide a non-randomized learning mechanism that is dominant-strategy truthful in expectation w.r.t. the click realizations with a regret of 0 and a randomized learning mechanism that is dominant-strategy truthful in expectation w.r.t. the realizations of the random component of the mechanism with a regret of O (1). We also show that any dominant-strategy truthful a posteriori w.r.t. all the sources of randomness learning mechanism would have a regret of Θ(T ). When both groups of parameters are unknown, we provide a random learning mechanism that is dominant-strategy truthful in expectation only w.r.t. the realizations of the random component of the mechanism with a regret of Õ(T 2 3 ).

• Cascade model : in the non-factorized cascade model (i.e., when the observation probabilities can be arbitrary) we show that it is possible to obtain a regret of Õ(T

3 ) in dominant-strategy truthful in expectation w.r.t. all the sources of randomness learning mechanisms when only the qualities of the ads are unknown. 5 We show also that in the factorized cascade model (i.e., when the observation probabilities are the products of terms depending on either the slot or the ads as used in [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF]), any non-randomized learning mechanism that is dominant-strategy truthful (even in expectation w.r.t. the click realizations) has a regret of Θ(T ) even in the special case in which only the ad-dependent parameters are unknown (while it is an open problem whether it is possible to obtain a better upper bound adopting a randomized mechanism and truthfulness in expectation w.r.t. the realization of the random component of the mechanism).

• Learning parameters: for each setting described above we provide practical guidelines on how the learning parameters can be tuned to minimize the bound over the regret depending on the characteristics of the auction (e.g., number of slots and advertisers).

• Numerical simulations: we investigate the accuracy of all the theoretical regret bounds in predicting the dependency of the regret on the auction parameters by numerical simulations. We show that the theoretical asymptotic dependency matches the actual dependency we observed by simulation.

Paper organization. The paper is organized as follows. In Section 2, we briefly review the basics of mechanism design and MAB learning. In Section 3, we formalize SSAs, introduces the corresponding online learning mechanism design problem, and it provides a more formal overview of existing results and the new findings of this paper. In Sections 4 and 5, we report and discuss the main regret bounds in the case of position-dependent and position-and ad-dependent externalities. In Section 6, we report numerical simulations aiming at testing the accuracy of the theoretical bounds. Section 7 concludes the paper and proposes future directions of investigation. The detailed proofs of the theorems are reported in appendix.

Preliminaries

Economic Mechanisms

In this section we provide an overview on the definitions and results of mechanism design that are relevant to the paper. The objective of mechanism design [START_REF] Mas-Colell | Microeconomic theory[END_REF] is to design allocation and payment functions satisfying some desirable properties when agents are rational and retain private information representing their preferences-also referred to as the type of the agent. Without loss of generality, mechanism design focuses on specific mechanisms, called direct, in which the only action available to the agents is to report their (potentially non-truthful) type. On the basis of the agents' reports the mechanism determines the allocation of resources to agents and the agents' payments.

The main desirable property of a mechanism is truthfulness, often referred to as Incentive Compatibility (IC), which requires that reporting the true types constitutes an equilibrium strategy profile for the agents. 6 When a mechanism is not truthful, agents should try to optimize their (untruthful) strategies on the basis of some model about the opponents' behavior, but, in absence of common information, no normative model for rational agents exists. This leads the mechanism to be economically unstable, given that the agents continuously change their strategies. Different notions of truthfulness are available. The most common ones are Dominant Strategy Incentive Compatibility (DSIC)-i.e., reporting the true types is the best action an agent can play independently of the actions of the other agents-, ex post incentive compatibility (ex post IC)-i.e., reporting the true types is a Nash equilibrium-, and BIC-i.e., reporting the true types is a Bayes-Nash equilibrium. Interestingly, DSIC and ex post IC are equivalent notions of truthfulness in absence of interdependency among the types of the agents, while BIC is weaker than DSIC, since it only requires that every agent has a Bayesian prior over the types of the other agents and IC is defined in expectation w.r.t. the prior. When there are other sources of randomness in the mechanism design problem (not due to the distribution of probabilities over the types of the agents), e.g., random components of the mechanism or the realization of events, weaker solution concepts, said in expectation, are commonly adopted, e.g., DSIC in expectation or ex post IC in expectation. Instead, we use the term "a posteriori" when the truthfulness holds for every realization. In presence of multiple sources of randomness, a mechanism may be in expectation w.r.t. some sources and a posteriori w.r.t. other sources. When we use only DSIC a posteriori without specifying the source of randomness, we mean DSIC a posteriori w.r.t. all the sources of randomness. Moreover, mechanisms can exploit the realizations of the events adopting different payment functions for each different realization. These mechanisms are said Execution Contingent (EC) [START_REF] Gerding | Scalable mechanism design for the procurement of services with uncertain durations[END_REF][START_REF] Ceppi | Mechanism design for federated sponsored search auctions[END_REF].

In addition to IC, other desirable properties include: Allocative Efficiency (AE)-i.e., the allocation maximizes the social welfare-, Individual Rationality (IR)-i.e., each agent is guaranteed to have no loss when reporting truthfully-, and Weak Budget Balance (WBB)-i.e., the mechanism is guaranteed to have no loss. In presence of sources of randomness, IR and WBB can be in expectation w.r.t. all the possible realizations, or a posteriori if they hold for every possible realization. As for IC, in presence of multiple sources of randomness, these properties may be in expectation w.r.t. some sources and a posteriori w.r.t. other sources. When we use only IR (or WBB) a posteriori without specifying the source of randomness, we mean IR (or WBB) a posteriori w.r.t. all the sources of randomness.

The economic literature provides an important characterization of the allocation functions that can be adopted in IC mechanisms when utilities are quasi linear [START_REF] Mas-Colell | Microeconomic theory[END_REF]. Here, we survey the main results related to DSIC mechanisms where no sources of randomness are present. In unrestricted domains (i.e., the agents' types are defined over spaces with arbitrary structure) for the agents' preferences, only weighted maximal-in-its-range allocation functions can be adopted in DSIC mechanisms [START_REF] Nisan | Computationally feasible vcg mechanisms[END_REF][START_REF] Nisan | Algorithmic Game Theory[END_REF]. More precisely, a weighted maximal-in-its-range allocation function chooses, among a subset of allocations that does not depend on the types reported by the agents (i.e., the range), the allocation maximizing the weighted social welfare, where each agent is associated with a positive (type-independent) weight. It trivially follows that, when the range is composed of all the possible allocations and all the agents have the same weights, only AE mechanisms can be DSIC. When weighted maximal-in-its-range allocation functions are adopted, only weighted Groves payments lead to DSIC mechanisms [START_REF] Mas-Colell | Microeconomic theory[END_REF]. The most common DSIC mechanism is the VCG [START_REF] Mas-Colell | Microeconomic theory[END_REF], in which the range is composed of all the allocations and all the weights are unitary. The idea of the VCG mechanism is that each agent pays the difference between the social welfare of the optimal outcome when she does not participate to the mechanism and the social welfare of the outcome obtained when she participates minute its contribution. (We leave a more formal and detailed description of the VCG mechanism to Appendix A.) Notice that the VCG mechanism satisfies also IR and WBB and, among all the Groves mechanisms, it is the one maximizing the revenue of the auctioneer. We refer to the weighted version of the VCG as Weighted Vickrey-Clarke-Groves (WVCG).

When the domain of the agents' preferences is restricted (i.e., the types are defined over spaces with specific structure, e.g., compact sets or discrete values), weighted maximal-in-its-range property is not necessary for DSIC. The necessary condition is weakly monotonicity [START_REF] Mas-Colell | Microeconomic theory[END_REF], which is also sufficient for convex domains. In specific restricted domains, weak monotonicity leads to simple and operational tools. For instance, when the preferences of the agents are single-parameter linear-i.e., the agents' value is given as the product between the agent's type and an allocation-dependent coefficient called load [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF]-, monotonicity requires that the load is monotonically increasing in the type of the agent. In this case, any DSIC mechanism is based on the Myerson's payments defined in [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF][START_REF] Myerson | Optimal auction design[END_REF]. 7 Notice that the VCG mechanism is still the mechanism maximizing the auctioneer's revenue among all the DSIC mechanisms, including those that are not AE. The Myerson's payments include an integral that may be not easily computable. However, by adopting a random mechanism and accepting DSIC in expectation w.r.t. the realizations of the random component of the mechanism, such integral can be easily estimated by using samples [START_REF] Archer | An approximate truthful mechanism for combinatorial auctions with single parameter agents[END_REF]. Another drawback of the payments described in [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF][START_REF] Myerson | Optimal auction design[END_REF] is that they require the off-line evaluation of the social welfare of the allocations for some agents' types different from the reported ones and this may be not possible in many practical situations. A way to overcome this issue is to adopt the result presented in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF], in which the authors propose an implicit way to calculate the payments. More precisely, given an allocation function in input, a random component is introduced such that with a small probability the reported types of the agents are modified to obtain the allocations that are needed to compute the payments in [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF][START_REF] Myerson | Optimal auction design[END_REF]. The resulting allocation function is less efficient than the allocation function given in input, but the computation of the payments is possible and it is executed online.

Multi-Armed Bandit

The MAB [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] is a simple yet powerful framework formalizing the online decision-making problem under uncertainty. Historically, the MAB framework finds its motivation in optimal experimental design in clinical trials, where two treatments, say A and B, need to be tested. In an idealized version of the clinical trial, T patients are sequentially enrolled in the trial, so that whenever a treatment is tested on a patient, the outcome of the test is recorded and it is used to choose which treatment to provide to the next patient. The objective is to provide the best treatment to the largest number of patients. This raises the challenge of balancing the collection of information and the maximization of the performance of the trial, a problem usually referred to as the exploration-exploitation trade-off. On the one hand, it is important to gather information about the effectiveness of the two treatments by repeatedly providing them at different patients (exploration). On the other hand, as the estimate of effectiveness of the treatments becomes more accurate, the (estimated) best treatment should be selected more often (exploitation). This scenario matches with a large number of applications, such as online advertisements, adaptive routing, and cognitive radio.

In general, the MAB framework can be adopted whenever a set of N arms (e.g., treatments, ads) is available and the rewards (e.g., effectiveness of a treatment, CTR of an ad) associated with each of them are random realizations from unknown distributions. Although this problem can be solved by dynamic programming methods and notably by using the Gittins index solution [START_REF] Gittins | Bandit processes and dynamic allocation indices[END_REF], this requires a prior over the distribution of the reward of the arms and it is often computationally heavy (high-degree polynomial in T ). More recently, a wide range of techniques have been developed to solve the bandit problem. In particular, these algorithms formalize the objective using the notion of regret, which corresponds to the difference in performance over T steps between an optimal selection strategy which knows in advance the performance of all the arms and an adaptive strategy which learns over time which arms to select. Although a complete review of the bandit algorithms is beyond the scope of this paper (see [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF] for a review), we only discuss two results which are relevant to the rest of the paper. The exploration-separated algorithms solve the exploration-exploitation trade-off by introducing a strict separation between the exploration and the exploitation phases. While during the exploration phase all the arms are uniformly selected, in the exploitation phase only the best estimated arm is selected until the end of the experiment. The length τ of the exploration phase is critical to guarantee the success of the experiment and it is possible to show that, if properly tuned, the worst-case cumulative regret scales as Õ(T 2 3 ), matching the lower bound Ω(T 2 3 ). Another class of algorithms relies on the construction of confidence intervals for the reward of each arm and it does not separate exploration and exploitation steps. In particular, the Upper-Confidence Bound (UCB) algorithm [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] gives an extra exploration bonus to arms which have been selected only few times in the past and it achieves a worst-case cumulative regret of order Õ(T 1 2 ), matching the lower bound Ω(T 1 2 ).

Problem statement

In this section we introduce all the notation used throughout the rest of the paper. In particular, we formalize the SSA model, we define the mechanism design problem, and we introduce the learning process.

Symbol Description N Number of ads N = {1, . . . , N } Set of the ads indexes a i , i ∈ N i-th ads q i ∈ [0, 1], i ∈ N Quality for ad a i V = [0, V ], V ∈ R +
Set of the possible values/types for an ad Allocation that maximizes the social welfare given the reported types when advertiser a i is not present

v i ∈ V, i ∈ N Value/types for ad a i v max = max i∈N v i Maximum value v = (v 1 , . . . , v N ) Value profile v -i = (v 1 , . . . , v i-1 , v i-1 , . . . ,
SW -i (θ, v)
Cumulative expected value of the allocation θ minus the expected value of advertiser a i R T (A)

Expected revenue regret of algorithm A over T steps R SW T (A) Expected social welfare regret of algorithm A over T steps Table 1: Notation adopted throughout the paper.

SSA model

We resort to the standard model of SSAs [START_REF] Narahari | Game Theoretic Problems in Network Economics and Mechanism Design Solutions[END_REF]. The notation described in the sequel is summarized in Tab. 1. We denote by N = {1, . . . , N } the set of ads indexes and by a i with i ∈ N the i-th ad (we assume w.l.o.g. each advertiser has only one ad and therefore we can identify by a i the i-th ad and the i-th advertiser indifferently). Each ad a i is characterized by a quality q i corresponding to the probability that a i is clicked once observed by the user, and by the a value v i ∈ V = [0, V ] that a i receives when clicked (a i receives a value of zero if not clicked). We denote by v the profile (v 1 , . . . , v N ) and by v -i the profile obtained by removing v i from v. While the qualities {q i } i∈N may be known by the auctioneer with some level of accuracy, the values {v i } i∈N are private information of the advertisers. We denote by K = {1, . . . , K} with K < N , the set of slot indexes and by s m , with m ∈ K, the m-th slot from top to bottom. For notational convenience, we also define the extended set of slots indexes K = K ∪ {K + 1, . . . , N }. 8We use the ordered pair s m , a i to indicate that ad a i is allocated to slot s m , while we denote by θ an allocation, defined as a collection of pairs s m , a i , and by Θ the set of all the possible allocations. Although in an auction only K ads can be actually displayed, we define an allocation as θ = { s m , a i : m ∈ K , i ∈ N } where both m and i occur exactly once and any ad assigned to a slot s m with m > K is not displayed. We define two maps π : N × Θ → K and α : K × Θ → N such that π(i; θ) returns the index of the slot in which a i is displayed in allocation θ and α(m; θ) returns the index of the ad displayed in slot s m in allocation θ. Given θ ∈ Θ, we have that π(i; θ) = m if and only if α(m; θ) = i.

With more than one slot, it is necessary to adopt a model of the user describing how the value of an advertiser varies over the slots. We assume that the user behaves according to the cascade model defined by [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF][START_REF] Aggarwal | Sponsored search auctions with markovian users[END_REF]. In the cascade model, the user's behavior is defined by a Markov chain whose possible states correspond to the slots, which are observed sequentially from the top to the bottom, and a transition matrix that defines, given the current slot, the probability that the user observes the ad a i displayed in the next slot or stops observing any other ad. More precisely, the probability may depend on the index of the slot (i.e., π(i; θ)), in this case the externalities are said position-dependent, and/or on the ad that precedes a i in the current allocation θ (i.e., a α(π(i;θ)-1;θ) ), in this case the externalities are said addependent.

In the general case, the cascade model can be described by introducing a set of parameters γ m,i defined as the probability that a user, observing ad a i in slot s m , observes the ad in the next slot s m+1 . The probability that a user observes the ad displayed at slot s m in allocation θ is denoted by Γ m (θ) and it is defined as:

Γ m (θ) =        1 if m = 1 m-1 l=1 γ l,α(l;θ) if 2 ≤ m ≤ K 0 otherwise . (1)
Given an allocation θ, the CTR of ad a i is the probability to be clicked once allocated according to θ and it is computed as Γ π(i;θ) (θ)q i , corresponding to the joint probability that the user arrives at observing the slot in which the ad is displayed and then clicks on it. Similarly, the CTR of the ad displayed at slot s m can be computed as Γ m (θ)q α(m;θ) . We notice that, according to this model, the user may click multiple different ads at each impression. Given an allocation θ, the expected value (w.r.t. the click realizations) of advertiser a i from θ is Γ π(i;θ) (θ)q i v i , that is, the product of the CTR Γ π(i;θ) (θ)q i by the value of the advertiser v i . The advertisers' cumulative expected value from allocation θ, commonly referred to as Social Welfare (SW), is:

SW(θ, v) = N i=1 Γ π(i;θ) (θ)q i v i .
In [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF][START_REF] Aggarwal | Sponsored search auctions with markovian users[END_REF], the authors factorize the probability γ m,i as the product of two independent terms: the prominence λ m , which only depends on the slot s m , and the continuation probability c i , which only depends on the ad a i .9

In [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF][START_REF] Aggarwal | Sponsored search auctions with markovian users[END_REF], the authors factorize the probability γ m,i as the product of two independent terms: the prominence λ m , which only depends on the slot s m , and the continuation probability c i , which only depends on the ad a i . 10Finally, we denote by click i m ∈ {0, 1} the no-click/click event for ad a i allocated in slot s m .

Mechanism design problem

A direct-revelation economic mechanism for SSAs is formally defined as a tuple (N , V, Θ, f, {p i } i∈N ) where N is the set of the agents' (i.e., the advertisers) indexes, V is the set of the types of the agents (where the type of ad a i is the single-parameter valuation v i ), Θ is the set of the outcomes (i.e., the allocations), f is the allocation function defined as f : V N → Θ, and p i is the payment function for advertiser a i defined as p i : V N → R. We denote by vi the value reported by advertiser a i to the mechanism, by v the profile of reported values, and by v-i the profile obtained by removing vi from v.

At the beginning of an auction, each advertiser a i reports its value vi . The mechanism chooses the allocation on the basis of the values reported by the advertisers using f (v) and subsequently computes the payment of each advertiser a i as p i (v). The expected utility of advertiser a i is defined as Γ π(i;f (v)) (f (v))q i v i -p i (v), corresponding to the value expected by advertiser a i minus the payment prescribed by the payment function. Notice that the utility is linear in the type of the agent. Since each advertiser is an expected utility maximizer, it will misreport its value (i.e., vi = v i ) whenever this may lead to increase its utility. Mechanism design aims at finding an allocation function f and a vector of payments {p i } i∈N such that some desirable properties-discussed in Section 2.1-are satisfied [START_REF] Mas-Colell | Microeconomic theory[END_REF].

When the parameters q i and γ m,i are known, the VCG mechanism satisfies DSIC in expectation w.r.t. the click realizations, IR in expectation w.r.t. the click realizations, WBB a posteriori w.r.t. the click realizations, and AE. DSIC and IR do not hold a posteriori. In the VCG mechanism, the allocation function, denoted by f * , maximizes the SW given the reported types as

θ * = f * (v) ∈ arg max θ∈Θ {SW(θ, v)} (2)
and the payments are defined as

p * i (v) = SW(θ * -i , v-i ) -SW -i (θ * , v), (3)
where:

• θ * -i = f * (v -i ), i.e.
, the optimal allocation when advertiser a i is not present in the auction, and

• SW -i (θ * , v) = j∈N ,j =i Γ π(j;θ * ) (θ * )q j vj , i.e., the cumulative expected value of the optimal allocation θ * minus the expected value of advertiser a i .

The payment of advertiser a i is the difference between the SW that could be obtained from allocation θ * -i , computed removing ad a i from the auction, and the SW of the efficient allocation θ * without the contribution of advertiser a i . In other words, this corresponds to the cost in terms of efficiency of the presence of a i in the auction. The VCG mechanism can be easily extended to weighted case (the WVCG mechanism). The weighted SW is SW w (θ, v) = N i=1 Γ π(i;θ) (θ)q i v i w i where w i is the weight of advertiser i. In the WVCG, the allocation maximizing the weighted SW is chosen, while the payment is defined as

p w i (v) = 1 w i (SW w (θ * -i , v-i ) -SW w -i (θ * , v)), where SW w -i (θ * , v)) = j∈N ,j =i Γ π(j;θ) (θ)q j v j w j .
The WVCG mechanism is DSIC in expectation w.r.t. the click realizations and IR in expectation w.r.t. the click realizations, but, WVCG being a generalization of the VCG, these properties do not hold a posteriori. This is because an advertiser may have a positive payment even when its ad has not been clicked. Nonetheless, the mechanism can be easily modified to satisfy DSIC w.r.t. the click realizations and IR a posteriori w.r.t. the click realizations by using pay-per-click payments p * ,c i as follows:

p * ,c i (v, click i π(i;θ * ) ) = SW(θ * -i , v-i ) -SW -i (θ * , v) Γ π(i;θ * ) (θ * )q i × click i π(i;θ * ) . (4)
The contingent formulation of the payments is such that

E[p * ,c i (v, click i π(i;θ * ) )] = p * i (v)
, where the expectation is w.r.t. the click event, which is distributed as a Bernoulli random variable with parameter coinciding with the CTR of ad a i in allocation θ * , i.e., Γ π(i;θ * ) (θ * )q i . Similar definitions hold for the WVCG mechanism.

Online learning mechanism design problem

In many practical problems, the parameters (i.e., q i and γ m,i ) are not known in advance by the auctioneer and must be estimated at the same time as the auction is run. This leads to the definition of an iterative process where the auction is repeated over T steps using different estimates of the CTRs. This introduces a tradeoff between exploring different possible allocations, so as to collect information about the parameters, and exploiting the estimated parameters, so as to implement a truthful high-revenue auction (i.e., a VCG mechanism). This problem could be easily cast as a MAB problem [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] and standard techniques could be used to solve it, e.g., [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. Nonetheless, such an approach would completely overlook the strategic dimension of the problem: advertisers may choose their reported values at each step t ∈ {1 . . . , T } to influence the outcome of the auction at t and/or in future steps in order to increase their cumulative utility over all the steps of the horizon T . Thus, in this context, truthfulness requires that reporting the truthful valuation maximizes the cumulative utility over the whole horizon T . The truthfulness can be in dominant strategies if advertisers know everything (including, e.g., the ads that will be clicked at each step t if displayed) or in expectation. As customary, we adopt four forms of truthfulness:

• DSIC a posteriori w.r.t. the click realizations and the realizations of the random component of the mechanism (if such a component is present),

• DSIC in expectation w.r.t. the click realizations and a posteriori w.r.t. the realizations of the random component of the mechanism (if such a component is present),

• DSIC in expectation w.r.t. the realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations, and

• DSIC in expectation w.r.t. both randomization sources.

Here we face the challenging problem where the exploration-exploitation dilemma must be solved so as to maximize the revenue of the auction under the hard constraint of truthfulness. Let A be a mechanism run over T steps. In particular, we only focus on mechanisms which are (at least) DSIC in expectation w.r.t. all sources of randomization, since for non-truthful mechanisms the dynamics of bids is unpredictable. At each step t, A defines an allocation θ t and prescribes an expected payment p i,t (v) for each ad a i . The objective of A is to minimize the loss of the auctioneer w.r.t. the revenue provided by the VCG mechanism computed on the actual parameters, and to preserve the properties of IR and WBB. More precisely, we measure the performance of A as its cumulative expected regret over T steps:

R T (A) = T N i=1 p * i (v) -E T t=1 N i=1 p i,t (v) , (5)
where the expectation is taken w.r.t. the click realizations and the realization of the random component of the mechanism if present. Indeed, we remark that the regret is not defined on the basis of the pay-per-click payments asked on a specific sequence of clicks but on the expected payments p i,t (v). Furthermore, we notice that since the learning mechanism A estimates the CTRs from the observed (random) clicks, the expected payments p i,t (v) are random as well. Finally, the payments are computed on the true valuations v constant over time since the mechanism A is truthful by definition and thus the best option for all advertisers is to bid their true value at any step. The mechanism A is a no-regret mechanism if its per-step regret R T (A)/T decreases to 0 as T increases, i.e., lim

T →∞ R T (A)/T = 0.
Another popular definition of performance [START_REF] Gonen | An incentive-compatible multi-armed bandit mechanism[END_REF][START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF] is the SW regret, that measures the performance of A as follows:

R SW T (A) = T • SW(θ * , v) -E T t=1 SW( θt , v) , (6)
where θt is the allocation prescribed by the learning mechanism at step t and the expectation, as before, is taken w.r.t. the click realizations and the realization of the random component of the mechanism if present. We notice that minimizing the SW regret R SW T does not coincide with minimizing R T . In fact, once the quality estimates are accurate enough, such that θ t is equal to θ * , the SW regret drops to zero. On the other hand, since p i,t (v) is computed according to the estimated qualities, R T (A) might still be positive even if θ t = θ * . In addition, we believe that in practical applications, providing a theoretical bound over the regret of the auctioneer's revenue is more important rather than a bound on the regret of the SW. Nevertheless, we show that the same approach we use to derive the bounds over the auctioneer's revenue can be employed to derive similar bounds over the SW. Finally, we refer to Appendix G for an alternative definition of the regret, related to the deviation between payments.

The study of the problem when K = 1 is well established in the literature. More precisely, the properties required to have a mechanism that is DSIC a posteriori w.r.t. the realizations of the random component of the mechanism are studied in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF] and it is shown that any learning algorithm must split the exploration and the exploitation in two separate phases in order to incentivize the advertisers to report their true values. This condition has a strong impact on the regret R T (A) of the mechanism. In fact, while in a standard bandit problem the distribution-free regret is of order Ω(T 1 2 ), in single-slot auctions, DSIC a posteriori mechanisms have a regret Ω(T 2 3 ). The same result holds for DSIC a posteriori w.r.t. the realizations of the random component of the mechanism and in expectation w.r.t. the click realizations. In [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF], a truthful learning mechanism is designed with nearly optimal regret of order Õ(T 2 3 ). Similar structural properties for DSIC a posteriori w.r.t. the click realizations mechanisms are also studied in [START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF] and similar lower-bounds are derived for the SW regret. In [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] the authors show that, by introducing a random component in the allocation function and resorting to DSIC a posteriori w.r.t. the click realizations and in expectation w.r.t. the realizations of the random component of the mechanism, the separation of exploration and exploitation phases can be avoided. In this case, the upper bound over the regret of the SW is Õ(T 1 2 ), thus matching the best distribution-free bound in standard bandit problems. However, the payments of this mechanism suffer of potentially high variance, which may be an undesirable property in practice. Although we expect that this mechanism could also achieve a revenue regret of the order of Õ(T 1 2 ), no formal proof is known.

In this paper, we focus on the study of the problem when K > 1, which is still mostly unexplored. In this case, a crucial role is played by the CTR model. While with only one slot, the advertisers' CTRs coincide to their qualities q i , with multiple slots the CTRs may also depend on the slots and the allocation of the other ads. The only results on learning mechanisms for SSAs with K > 1 are described in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF][START_REF] Mandal | A novel ex-post truthful mechanism for multislot sponsored search auctions[END_REF], where the authors characterize DSIC a posteriori mechanisms and provide theoretical bounds over the SW regret. More precisely, the authors assume a simple CTR model in which the CTR itself depends on the ad a i and the slot s m . This model differs from the cascade model (see Section 2.1) where the CTR is a more complex function of the quality q i of an ad and the cumulative probability of observation Γ m (θ), which in general depends on both the slot s m and the full allocation θ (i.e., the ads allocated before slot s m ). It can be easily shown that the model studied in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF] does not include and, at the same time, is not included by the cascade model. However, the two models match when the CTRs are separable in two terms, in which the first is the agents' quality and the second is a parameter in [0, 1] monotonically decreasing over the slots (i.e., onlyposition-dependent cascade model). Furthermore, while the cascade model is supported by an empirical activity which confirms its validity as a model of the user behavior [START_REF] Craswell | An experimental comparison of click position-bias models[END_REF][START_REF] Joachims | Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search[END_REF], the model considered in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF] has not been empirically studied. In [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF], the authors show that when the CTRs are unrestricted (e.g., they are not strictly monotonically decreasing in the slots), the regret over the SW is Θ(T ) and therefore at every step (of repetition of the auction) a non-zero regret is accumulated. In addition, the authors provide necessary and, in some situations, sufficient conditions to have DSIC a posteriori w.r.t. the click realizations. More precisely, the authors show that the allocation function of a mechanism that is DSIC a posteriori w.r.t. the click realizations must be monotonic a posteriori w.r.t. the click realizations. We recall that, given v i and v i with

v i > v i and called θ = f (v i , v -i ) and θ = f (v i , v -i ),
f is monotonic in expectation w.r.t. the click realizations if and only if the CTR of ad a i in θ is not strictly smaller than the CTR in θ. The definition of monotonicity a posteriori w.r.t. the click realizations is similar. Given

v i and v i with v i > v i and called θ = f (v i , v -i ) and θ = f (v i , v -i ), f is monotonic a posteriori w.r.t.
the click realizations if and only if the ad a i is clicked in θ whenever it would be clicked in θ. However, the authors do not present in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF] any bound over the regret (except for reporting an experimental evidence that the regret is Ω(T 2 3 ) when the CTRs are separable). In [START_REF] Mandal | A novel ex-post truthful mechanism for multislot sponsored search auctions[END_REF], the authors preliminarily extend the analysis to the case of the cascade model, showing that, even with only ad-dependent externalities, any DSIC a posteriori w.r.t. the click realizations mechanism has a regret Θ(T ).

We summarize in Tab. 2 the known results in the literature and, in bold font, the original results provided in this paper. We first consider the cascade model with only position-dependent externalities analyzing the case where only the parameters {q i } i∈N are unknown to the auctioneer. We show that it is possible to obtain a DSIC a posteriori learning mechanism with a regret Θ(T 2 3 ) over the auctioneer's revenue. 11 Similarly, we show that in this setting, the regret over the SW is Θ(T

) revenue (R T ) 1 - q i DSIC Θ(T 2/3 ) Θ(T 2/3 ) DSICeC Θ(T 2/3 ) Θ(T 2/3 ) DSICeM Θ(T 1/2 ) Õ(T 2/3 ) > 1 (unconstrained) CT R i,m CT R i,m DISC Θ(T ) unknown (unfactorized) cascade q i DISC Θ(T ) Θ(T ) DSICeM Θ(T ) Θ(T ) DSICeC Θ(T 2/3 ) Θ(T 2/3 ) γ i,s DISCeM Θ(T) Θ(T) position-dep. cascade / q i DSIC Θ(T 2/3 ) Θ(T 2/3 ) separable CT R i,m DSICeC Θ(T 2/3 ) Θ(T 2/3 ) DSICeM Õ(T 2/3 ) Õ(T 2/3 ) λm DSIC Θ(T) Θ(T) DSICeC 0 0 DSICeM O(1) O(1) q i , λm DSIC Θ(T) Θ(T) DSICeM Õ(T 2/3 ) Õ(T 2/3 ) ad-dependent cascade q i DSIC Θ(T ) Θ(T ) DSICeC Θ(T 2/3 ) Θ(T 2/3 ) c i DSICeC Θ(T) Θ(T) q i , c i DSICeC Θ(T) Θ(T)
3 ) for both kinds of regret. In Section 5 we study the cascade model with both position-and addependent externalities. We provide a DSIC in expectation w.r.t. the click realizations learning algorithm minimizing the regret over the auctioneer's revenue when only the parameters {q i } i∈N are unknown. 12 Then we provide a result over the SW regret, where the bound is still Θ(T 2 3 ). Finally, in Section 5.2, we consider other situations of lack of information obtaining negative results. More precisely, there is not any no-regret DSIC mechanism in expectation w.r.t. the click realizations and a posteriori w.r.t. realizations of the random component of the mechanism when parameters {c i } i∈N are unknown. This result applies to both kinds of regret and it extends to the more general cascade model.

Learning with Position-Dependent Externalities

In this section we study the multi-slot auctions with only positiondependent cascade model. The CTRs depend only on the quality of the ads and on the position of the slots in which the ads are allocated. Formally, the parameters γ m,i coincide with the prominence parameter, i.e., γ m,i = λ m for every m ∈ K and i ∈ N . As a result, the cumulative probability of observation, defined in Eq. 1, reduces to

Λ m = Γ m (θ) =        1 if m = 1 m-1 l=1 λ l if 2 ≤ m ≤ K 0 otherwise , (7)
where we use Λ m instead of Γ m (θ) for consistency with most of the literature on position-dependent externalities and to stress the difference w.r.t. to the general case described in Section 3.1. When all the parameters are known by the auctioneer, the efficient allocation θ * greatly simplifies. In fact, the expected value of an ad a i for an allocation θ in this case reduces to Λ π(i;θ) q i v i and, since the cumulative probabilities of observation are non-increasing over slots, the efficient allocation simply needs to allocate the slots in decreasing order of their reported values in expectation w.r.t. the qualities, i.e., q i vi . More precisely, for any k ∈ K , let max i∈N (q i vi ; k) be the operator returning the k-th largest value in the set {q 1 v1 , . . . , q N vN }, then θ * is such that, for every m ∈ K , the ad displayed at slot s m is

α(m; θ * ) ∈ arg max i∈N (q i vi ; m). (8)
This condition also simplifies the definition of the efficient allocation θ * -i when a i is removed from N . In fact, for any i, j ∈ N , if π(j; θ * ) < π(i; θ * ) (i.e., ad a j is displayed before a i ) then π(j; θ * -i ) = π(j; θ * ), while if π(j; θ * ) > π(i; θ * ) then π(j; θ * -i ) = π(j; θ * )-1 (i.e., ad a j is moved one slot upward), and w.l.o.g. we assume π(i; θ * -i ) = N . In case of position-dependent externalities, the VCG payments p * i defined in Eq. 3 take the simplified formulation:

p * i (v) =      K+1 l=π(i;θ * )+1 (Λ l-1 -Λ l ) max j∈N (q j vj ; l) if π(i; θ * ) ≤ K 0 otherwise , (9)
which can be written as a per-slot payment as:

p * α(m;θ * ) (v) =      K+1 l=m+1 (Λ l-1 -Λ l ) max i∈N (q i vi ; l) if m ≤ K 0 otherwise . ( 10
)
In the following sections we study the problem of designing incentive compatible mechanisms under different conditions of lack of information over the parameters {q i } i∈N and {Λ m } m∈K . In particular, in Section 4. Compute the estimated quality qi = 1

|B i | t∈B i click i π(i;θ t ) (t) Λ π(i;θ t )

Compute q+

i = qi + η where η is given by ( 14)

Exploitation phase for t = τ + 1, . . . , T do Allocate ads according to f defined in [START_REF] Langford | Maintaining equilibria during exploration in sponsored search auctions[END_REF] For each ad a i , ask for payment pc i defined in ( 18) mechanisms and subsequently we discuss about DSIC in expectation mechanisms.

As in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF][START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF], we formalize the problem as a MAB problem and we study the properties of a learning mechanism where the exploration and exploitation phases are separated, such that during the exploration phase, we estimate the values of {q i } i∈N and during the exploitation phase we use the estimated qualities {q i } i∈N to implement a DSIC a posteriori mechanism. The pseudo code of the algorithm A-VCG1 (Adaptive VCG 1) is given in Fig. 1. The details of the algorithm follow.

Exploration phase. During an exploration phase of length τ , the algorithm receives as input the parameters {Λ m } m∈K and collects data to estimate the quality of each ad. Unlike the single-slot case, where we collect only one sample of no-click/click event per step, here we can exploit the fact that each ad a i has a non-zero CTR whenever it is allocated to a slot s m with m ≤ K. As a result, at each step of the exploration phase, we collect K samples (no-click/click events), one from each slot. Let θ t (for 1 ≤ t ≤ τ ) be a sequence of allocations independent from the advertisers' bids. Let B i = {t : π(i; θ t ) ≤ K, ≤ t ≤ τ } be the set of all the steps when a i is allocated to a valid slot, so that |B i | corresponds to the total number of (noclick/click) samples available for ad a i . We denote by click i π(i;θt) (t) ∈ {0, 1} the no-click/click event at step t for ad a i when displayed in slot s π(i;θt) . Depending on the slot in which the click event happens, the ad a i has different CTR, thus we need to weigh each click sample by the probability of observation Λ m related to the slot in which the ad is allocated. As a result, the estimated quality qi is computed as

qi = 1 |B i | t∈B i click i π(i;θt) (t) Λ π(i;θt) . ( 11
)
Since qi is an unbiased estimate of q i (i.e., E click [q i ] = q i , where E click is the expectation w.r.t. the click realizations), we can resort to the Hoeffding's inequality [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] and a bound over the error of the estimated quality qi for each ad a i .

Proposition 1. For any ad a i , i ∈ N |q i -qi | ≤ t∈B i 1 Λ 2 π(i;θt) 1 2|B i | 2 log 2N δ , (12)
with probability 1 -δ (w.r.t. the click realizations).

During the exploration phase, at each step t ∈ {1, . . . , τ }, we adopt the following sequence of allocations

θ t = { s 1 , a (t mod N )+1 , . . . , s N , a (t+N -1 mod N )+1 }, (13)
thus obtaining |B i | = Kτ /N for all the ads a i . Given that Kτ /N ≥ τ K 2N , Eq. 12 becomes

|q i -qi | ≤ K m=1 1 Λ 2 m N K 2 τ log 2N δ =: η, (14)
where η represents the accuracy of the estimator. 13 The previous inequality is non-trivial only for a long enough exploration phase. In particular, to have a meaningful bound, i.e., |q i -qi | < 1, the length of the exploration phase has to be τ >

K m=1 1 Λ 2 m N K 2 log 2N δ .
During this phase, in order to guarantee DSIC a posteriori, the advertisers cannot be charged with any payment, i.e., all the payments in steps 1 ≤ t ≤ τ are set to 0. In fact, as shown in [START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF], any bid-dependent payment could be easily manipulated by bidders, thus obtaining a non-truthful mechanism, whereas bid-independent payments could lead to a non-IR mechanism to which bidders may prefer not to participate.

Exploitation phase. Once the exploration phase is terminated, an upperconfidence bound over each quality q i is computed as

q+ i = qi + η, (15)
and the exploitation phase is started and run for the remaining T -τ steps.

We define the upper-confidence bound on the SW as

SW(θ, v) = N i=1 Λ π(i;θ) q+ i vi ,
and we define f as the allocation function that displays ads in decreasing order of q+ i vi . Thus f returns the efficient allocation θ on the basis of the estimated qualities as:

θ = f (v) ∈ arg max θ∈Θ { SW(θ, v)}. ( 16
)
The allocation function f is then run for all the steps of the exploitation phase. Notice that f is an affine maximizer, since

f (v) ∈ arg max θ∈Θ N i=1 Λ π(i;θ) q+ i vi = arg max θ∈Θ N i=1 q+ i q i Λ π(i;θ) q i vi = arg max θ∈Θ N i=1 w i Λ π(i;θ) q i vi ,
where each weight w i = q+ i /q i is independent of the advertisers' types v i . Hence, we can apply the WVCG payments (here denoted by p because of the estimated parameters) satisfying the DSIC a posteriori property. In particular, for any a i , we define the payment pi (v) =

1 w i K+1 l=π(i; θ)+1 (Λ l-1 -Λ l ) max j∈N (q + j vj ; l) if π(i; θ) ≤ K 0 otherwise = q i q+ i K+1 l=π(i; θ)+1 (Λ l-1 -Λ l ) max j∈N (q + j vj ; l) if π(i; θ) ≤ K 0 otherwise . ( 17
)
Although these payments cannot be computed by the auctioneer, since the actual {q i } i∈N are unknown, we can resort to the pay-per-click payments

pc i (v,click i π(i; θ) ) = pi (v) Λ π(i; θ) q i = 1 Λ π(i; θ) q+ i K+1 l=π(i; θ)+1 (Λ l-1 -Λ l ) max j∈N (q + j vj ; l) click i π(i; θ) , (18)
which in expectation coincide with the payments pi (v) = E[p c i (v, click i π(i; θ) )] and can be computed at run time. Unlike the payments pi (v), these payments can be computed simply relying on the estimates q+ i and on the knowledge of the probabilities of observation Λ m . The following properties hold for this mechanism.

Theorem 1. The A-VCG1 is:

• DSIC a posteriori, • IR a posteriori,
• WBB a posteriori.

Proof. The allocation function is monotonic a posteriori w.r.t. the click realizations since, by the nature of the externality model, each click realization plan prescribing that an ad is clicked in a given slot prescribes also that the same ad would be clicked in all the slots above. Thus, DSIC a posteriori trivially follows from the fact that the mechanism is a WVCG mechanism and that the payments are pay-per-click.

We now move to the analysis of the performance of A-VCG1 in terms of the regret the mechanism accumulates through T steps.

Theorem 2. Let us consider a sequential auction with N advertisers, K slots, and T steps with position-dependent cascade model with parameters {Λ m } K m=1 and accuracy η as defined in Eq. 14. For any parameter τ ∈ {1, . . . , T } and δ ∈ (0, 1), the A-VCG1 achieves auctioneer's revenue expected regret:

R T ≤ v max K m=1 Λ m 2(T -τ )η + τ + δT . ( 19
)
By setting the parameters to

• δ = K -1 3 T -1 3 N 1 3 • τ = K -1 3 T 2 3 N 1 3 Λ -2 3 min log K 1 3 T 1 3 N 2 3 1 3 ,
where

Λ min = min m∈K Λ m > 0, then the regret is R T ≤ 4v max Λ -2 3 min K 2 3 T 2 3 N 1 3 log K 1 3 T 1 3 N 2 3 1 3 . ( 20
)
We initially introduce some remarks about the above results, and subsequently discuss the proof of the theorem, which can be found in the appendix.

Remark 1 (The bound). Up to numerical constants and logarithmic factors, the bound in Eq. 20 is

R T = Õ(K 2 3 T 2 3 N 1 3
). We first notice that A-VCG1 is a no-regret algorithm since its per-step regret (R T /T ) decreases to 0 as T - 1 3 , thus implying that it asymptotically achieves the same performance as the VCG. Furthermore, we notice that for K = 1 the bound reduces (up to constants) to the single-slot case analyzed in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF]. Unlike the standard bound for MAB algorithms, the regret scales as Õ(T ). As pointed out in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF] and [START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF] this is the unavoidable price the bandit algorithm has to pay to be DSIC a posteriori w.r.t. the realizations of the random component of a mechanism. Finally, the dependence of the regret on N is sub-linear (N 1 3 ) and therefore increasing the number of advertisers does not significantly worsen the regret. The dependency on the number of slots K is similar: according to the bound in Eq. 20 the regret has a sublinear dependency Õ(K 2 3 ), meaning that whenever one slot is added to the auction, 29 the performance of the algorithm does not significantly worsen. By analyzing the difference between the payments of the VCG and A-VCG1, we notice that during the exploration phase the regret is O(τ K) (e.g., if all the ads allocated into the K slots are clicked at each explorative step), while during the exploitation phase the error in estimating the qualities sum over all the K slots, thus suggesting a linear dependency on K for this phase as well. Nonetheless, as K increases, the number of samples available per-ad increases as τ K/N , thus improving the accuracy of the quality estimates by Õ(K -1

2 ) (see Proposition 1). As a result, as K increases, the exploration phase can be shortened (the optimal τ actually decreases as K -1

3 ), thus reducing the regret during the exploration, and still have accurate enough estimates to control the regret of the exploitation phase.

Remark 2 (Distribution-free bound). The bound derived in Theorem 2 is a distribution-free (or worst-case) bound, since it holds for any set of advertisers (i.e., for any {q i } i∈N and {v i } i∈N ). This generality comes at the price that, as illustrated in other remarks and in the numerical simulations (see Section 6), the bound could be inaccurate for some specific sets of advertisers. On the other hand, distribution-dependent bounds (see e.g., the bounds of UCB [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]), where q and v appear explicitly, would be more accurate in predicting the behavior of the algorithm. Nonetheless, they could not be used to optimize the parameters δ and τ , since they would then depend on unknown quantities.

Remark 3 (Parameters). The choice of parameters τ and δ reported in Theorem 2 is obtained by a rough minimization of the upper-bound in Eq. [START_REF] Nazerzadeh | Dynamic cost-per-action mechanisms and applications to online advertising[END_REF]. Each parameter can be computed by knowing the characteristics of the auction (number of steps T , number of slots K, number of ads N , and Λ m ). Moreover, since the values are obtained optimizing an upper-bound of the regret and not directly the true cumulative regret, these values can provide a good guess for the parametrization, but they might not be optimal. In practice, we expect that the regret could be optimized by searching the space of the parameters around the values suggested in Theorem 2.

Remark 4 (DSIC in expectation). In this paper, we do not solve two interesting problems when DSIC in expectation w.r.t. the realizations of the random component of the mechanism is adopted: (i) whether it is possible or not to avoid the separation of the exploration and exploitation phases and (ii) whether it is possible to obtain a regret of Õ(T 1 2 ) as in the case of K = 1 [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF]. Any attempt we tried to extend the result presented in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] to the multi-slot case led to a non-IC mechanism. We briefly provide some examples of adaptation to our framework of the two MAB presented in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF]. None of these attempts provided a monotonic allocation function. We tried to extend the UCB1 in different ways, e.g., by introducing N •K estimators, one for each ad for each slot, or maintaining N estimators weighing in different ways clicks obtained in different slots. The second MAB algorithm, called NewCB, is based on the definition of a set of active ads, i.e., the ones that can be displayed in the unique slot. We considered some extensions for the multi-slot setting (e.g. a single set for all the slots and multiple sets, one for each slot) without identifying monotonic allocation algorithms.

Comments to the proof. The proof uses relatively standard arguments to bound the regret of the exploitation phase. As discussed in Remark 2, the bound is distribution-free and some steps in the proof are conservative upper-bounds on quantities that might be smaller for specific auctions. For instance, the inverse dependency on the smallest cumulative discount factor Λ min in the final bound could be a quite inaccurate upper-bound on the quantity K m=1 1/Λ 2 m . In fact, the parameter τ itself could be optimized as a direct function of K m=1 1/Λ 2 m , thus obtaining a more accurate tuning of the length of the exploration phase and a slightly tighter bound (in terms of constant terms). Furthermore, a crucial step in the proof is the inequality max i∈N (q + i v i ; h)/ max i∈N (q + i v i ; m) ≤ 1, which is likely to become less accurate as the difference between h and m increases (see Eq. C.4 in the proof). For instance, if the qualities q i are drawn from a uniform distribution in (0, 1), as the number of slots increases this quantity reduces as well (on average), thus making the upper-bound by 1 less and less accurate. The accuracy of the proof and the corresponding bound are further studied in the simulations in Section 6.

Besides a bound on the revenue regret, in a similar way we can bound the SW, as in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF]. In particular, we obtain that A-VCG1 is a no-regret algorithm and R SW T = Õ(T 2 3 ). Theorem 3. Let us consider a sequential auction with N advertisers, K slots, and T steps with position-dependent cascade model with parameters {Λ m } K m=1 and accuracy η as defined in Eq. 14. For any parameter τ ∈ {1, . . . , T } and δ ∈ (0, 1), the A-VCG1 achieves a SW regret:

R SW T ≤ v max K (2 (T -τ ) η + τ + δT ) . ( 21
)
By setting the parameters to

• δ = 1 Λ min 2 3 K -1 3 T -1 3 N 1 3 • τ = 1 Λ min 2 3 K -1 3 T 2 3 N 1 3 log 2Λ 2 3 min K 1 3 T 1 3 N 2 3 1 3 ,
where

Λ min = min m∈K Λ m , Λ min > 0, then the regret is R SW T ≤ 4v max 1 Λ min 2 3 K 2 3 T 2 3 N 1 3 log 2Λ 2 3 min K 1 3 T 1 3 N 2 3 1 3 . ( 22
)
Notice that using τ and δ defined in Theorem 2, the bound for

R SW T is Õ(T 2
3 ), even if the parameters are not optimal for this second framework.

Unknown {Λ m } m∈K

We now focus on the situation when the auctioneer knows {q i } i∈N , while {Λ m } m∈K are unknown. By definition of cascade model, {Λ m } m∈K are strictly non-increasing in m. This dramatically simplifies the allocation problem since the optimal allocation can be found without knowing the actual values of {Λ m } m∈K . Indeed, the allocation θ * such that α(m; θ * ) ∈ arg max i∈N (q i vi ; m), ∀m, is optimal for any possible {Λ m } m∈K . However, the lack of knowledge about {Λ m } m∈K makes the design of a truthful mechanism non trivial because the cumulative probabilities of observation appear in the calculation of the payments. In the following, we initially focus on DSIC in expectation mechanisms, providing two mechanisms, the first DSIC in expectation w.r.t. the click realizations and the second DSIC in expectation w.r.t. the realizations of the random component of the mechanism, and finally we discuss about DSIC a posteriori mechanisms.

DSIC in expectation w.r.t. the click realizations mechanism

In this case, we do not need to estimate the parameters {Λ m } m∈K and therefore we do not resort to the MAB framework to solve any explorationexploitation dilemma. The pseudocode of the algorithm A-VCG2 (Adaptive VCG2) is given in Fig. 2. On the basis of the above considerations, we can adopt the allocatively efficient allocation function f * as prescribed by Eq. 8 even if the mechanism does not know the actual values of the parameters {Λ m } m∈K . Nonetheless, the VCG payments defined in Eq. 9 cannot be Input: Qualities parameters {q i } i∈N for t = 1, . . . , T do Allocate ads according to f * as prescribed by [START_REF] Brendan Lucier | On revenue in the generalized second price auction[END_REF] if Ad a i is displayed then Ask for payment p c i defined in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] Figure 2: Pseudo-code for the A-VCG2 mechanism.

computed, since {Λ m } m∈K are unknown. However, by resorting to executioncontingent payments (generalizing the pay-per-click approach), we can impose computable payments that, in expectation, are equal to Eq. 9. 14 More precisely, the contingent payments are computed given the bids v and all click events over the slots and take the form:

p c i v, {click α(m;θ * ) m } K m=1 (23) = π(i;θ * )≤m≤K click α(m;θ * ) m • q α(m;θ * -i ) • vα(m;θ * -i ) q α(m;θ * ) - π(i;θ * )<m≤K click α(m;θ * ) m • vα(m;θ * )
Notice that the payment p c i depends not only on the click of ad a i , but also on the clicks of all the ads displayed below a i . In expectation, the two terms of p c i are:

E click   π(i;θ * )≤m≤K click α(m;θ * ) m • q α(m;θ * -i ) • vα(m;θ * -i ) q α(m;θ * )   = π(j;θ * )≥π(i;θ * ) Λ π(j;θ * -i ) q j vj E click   π(i;θ * )<m≤K click α(m;θ * ) m • vα(m;θ * )   = π(j;θ * )>π(i;θ * )
Λ π(j;θ * ) q j vj and therefore, in expectation, the payment equals those defined in Eq. 9. We discuss the properties of the mechanism in what follows.

Proposition 2. The A-VCG2 is IR a posteriori.

Proof. Rename the ads {a 1 , . . . , a N } such that q 1 v 1 ≥ q 2 v 2 ≥ . . . ≥ q N v N . We can write payments in Eq. 23 as:

p c i v, {click j j } K j=1 = K j=i click j j q j q j+1 v j+1 - K j=i+1 click j j v j
Thus, the utility for advertiser a i is:

u i = click j j v i + K j=i+1 click j j v j - K j=i click j j q j q j+1 v j+1 = K j=i click j j v j - K j=i click j j q j q j+1 v j+1 = K j=i click j j v j - click j j q j q j+1 v j+1 = K j=i click j j q j (q j v j -q j+1 v j+1 ).
Since

click j j q j
≥ 0 by definition and q j v j -q j+1 v j+1 ≥ 0 because of the chosen ordering of the ads, then the utility is always positive and we can conclude that the mechanism is IR a posteriori. Proof. The proof is by counterexample. Consider an environment with 3 ads N = {1, 2, 3} and 2 slots S = {1, 2} s.t. q 1 = 0.5, v 1 = 4, q 2 = 1, v 2 = 1, q 3 = 1, v 3 = 0.5, which correspond to expected values of 2, 1, and 0.5.

The optimal allocation θ * consists in allocating a 1 in s 1 and a 2 in s 2 . Consider a step t when both ad a 1 and a 2 are clicked, from Eq. 23 we have that the payment of a 2 is:

p c 2 v, {click α(m;θ * ) m } K m=1 = 1 q 2 q 3 v 3 = 0.5
If ad a 2 reports a value v2 = 3, the optimal allocation is now a 2 in s 1 e a 1 in s 2 . In the case both a 1 and a 2 are clicked, the payment of a 2 is:

p c 2 v, {click α(m;θ * ) m } K j=1 = 1 q 2 q 1 v 1 + 1 q 1 q 3 v 3 -v 1 = 2 + 1 -4 = -1
Given that, in both cases, the utility is

u 2 = v 2 -p c 2 v, {click α(m;θ * ) m } K m=1
, reporting a non-truthful value is optimal. Thus, we can conclude that the mechanism is not DSIC a posteriori w.r.t. the click realizations. .

Proposition 4.

The A-VCG2 is not WBB a posteriori (w.r.t. the click realizations).

Proof. The proof is by counterexample. Consider an environment with 3 ads N = {1, 2, 3} and 2 slots S = {1, 2} s.t.

q 1 = 1, v 1 = 2, q 2 = 0.5, v 2 = 1, q 3 = 1, v 3 = 0.1.
The optimal allocation θ * consists in allocating a 1 in s 1 e a 2 in s 2 . Consider step t when both ad a 1 and a 2 are clicked, their payments are:

p c 1 v, {click α(m;θ * ) m } K m=1 = 1 q 1 q 2 v 2 + 1 q 2 q 3 v 3 -v 2 = 0.5+2•0.1-1 = 0.2-0.5 < 0 p c 2 = 1 q 2 q 3 v 3 = 0.2 Thus, 3 i=1 p c i v, {click α(m;θ * ) m
} K m=1 = 0.4-0.5 < 0, and we can conclude that the mechanism is not WBB a posteriori. Now we state the following theorem, whose proof is straightforward.

Theorem 5. Let us consider a sequential auction with N advertisers, K slots, and T steps, with position-dependent cascade model with parameters {Λ m } K m=1 . The A-VCG2 achieves an auctioneer's revenue expected regret R T = 0.

An important property of this mechanism is that the expected payments are exactly the VCG payments for the optimal allocation when all the parameters are known. Moreover, the absence of an exploration phase allows us to obtain a per-step expected regret of zero and, thus, the cumulative regret over the T steps of auction is R T = 0. Similar considerations can be applied to the study of the regret over the SW, obtaining the following.

DSIC in expectation w.r.t. the realizations of the random component mechanisms

As for the previous mechanism, also in this case we only need an exploitation phase. Unlike A-VCG2, in this case we need to follow a similar approach as in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] and introduce a random component, which leads to the mechanism, called A-VCG2 reported in Fig. 3.

Since f * is monotonic (see Appendix B) and the problem is with single parameter and linear utilities, payments that guarantee DSIC in expectation w.r.t. the click realizations can be written as Myerson payments:

p * i (v) = Λ π(i;f * (v)) q i vi - vi 0 Λ π(i;f * (v -i ,u)) q i du, (24)
which coincide with the VCG payments defined in Eq. 3 (hence the use of the same notation p * i ). This is justified by the fact that when a mechanism is AE, IR in expectation w.r.t. the click realizations and WBB in expectation w.r.t. the click realizations the only payments that lead to a DSIC in expectation w.r.t. the click realizations mechanism are the VCG payments with Clacke's pivot [START_REF] Green | Incentives in Public Decision Making[END_REF], and thus Eq. 24 coincides with Eq. 3. However, these payments are not directly computable, since the parameters {Λ m } m∈K in the integral are unknown and, as in the case discussed in Section 4.2.1, we cannot replace them by empirical estimates. Nonetheless, we could obtain these payments in expectation by using execution-contingent payments associated with non-optimal allocations where the report vi is randomly modified in an interval between 0 and the actual value. This can be obtained by resorting to the approach proposed in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF], which takes as input a generic allocation function f and introduces a randomized component to it, thus producing a new (random) allocation function that we denote by f . At the cost of reducing the efficiency of the mechanism, this technique allows the computation of the allocation and the payments at the same time, even when payments described in [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF] cannot be directly computed.

In A-VCG2 , we apply this approach to f * , thus obtaining a new allocation function f * . With f * , the advertisers' reported values {v i } i∈N are modified, each with a (small) probability µ ∈ (0, 1). The (potentially) modified values are then used to compute the allocation (using f * ) and the payments. More precisely, with a probability of (1 -µ) N , f * returns the same allocation as f * , while it defines a different allocation with probability of 1 -(1 -µ) N . The reported values {v i } i∈N are modified through the canonical Self-Resampling Procedure (cSRP) described in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] that generates two samples: x i (v i , ω i ) and y i (v i , ω i ), where ω i is the random seed. We sketch the result of cSRP where the function 'rec' is defined in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF]:

(x i , y i ) = cSRP (v i ) = (v i , vi ) w.p. 1 -µ (v i , v i ) otherwise ,
where v i ∼ U([0, vi ]) and v i = rec(v i ). The algorithm in Fig. 4 shows how f * works when the original allocation function is f * . The reported values {v i } i∈N are perturbed through the cSRP (Step 2) and then the allocation is chosen by applying the original allocation function f * to the new values x (Step 4). Finally, the payments are computed as

for all a i , i ∈ N do (x i , y i ) = cSRP (v i ) x = (x 1 , . . . , x N ) θ = f * (x) Figure 4: Definition of f * (v). p B, * ,c i (x, click i π(i;f * (x)) ) = p B, * i (x,y;v) Λ π(i;f * (x)) q i if click i π(i;f * (x)) = 1 0 otherwise =      vi - 1 µ vi if y i < vi 0 otherwise, if click i π(i;f * (x)) = 1 0 otherwise (25)
where

p B, * i (x, y; v) = Λ π(i;f * (x)) q i vi - 1 µ Λ π(i;f * (x)) q i vi if y i < vi 0 otherwise , (26)
with y = (y 1 , . . . , y N ). If we take the expectation of the payments in Eq. 25 w.r.t. the randomization of the mechanism, then we obtain exactly the same form of payments as in Eq. 24 but instantiated for the randomized allocation function f * (for the explicit equation refer to Eq. E.1 in Appendix E). Furthermore, the resulting mechanism is shown to be DSIC in expectation w.r.t. the realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations. As a result we obtained the following properties.

Theorem 6. The A-VCG2 is:

• DSIC in expectation w.r.t. the realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations,

• IR a posteriori,

• WBB in expectation w.r.t. the realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations.

We also obtain the following regret guarantees.

Theorem 7. Let us consider an auction with N advertisers, K slots, and T steps, with position-dependent cascade model with parameters {Λ m } K m=1 . The A-VCG2 achieves an auctioneer's revenue expected regret R T ≤ 2K 2 µv max T .

If we tune the randomization parameter as µ = 1 K 2 T , then we obtain R T = O(1). Notice that µ cannot be just set to zero, since it would lead to a division by zero in Eq. 25. Furthermore, as illustrated in Section 6, an undesirable effect of a small µ is the corresponding increase in the variance in the payments. Thus a proper trade-off should be found when tuning µ in practice. We provide a similar result for the regret over the SW. Theorem 8. Let us consider a sequential auction with N advertisers, K slots, and T steps, with position-dependent cascade model with parameters

{Λ m } K m=1 . The A-VCG2 achieves a SW regret R SW T ≤ K 2 µv max T .

Discussion about DSIC a posteriori mechanisms

One may wonder whether there exists a no-regret DSIC a posteriori mechanism, even at the cost of a worse regret. Resorting to the same arguments used in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF], we show that the answer to such question is negative. Theorem 9. Let us consider a sequential auction with N advertisers, K slots, and T steps, with position-dependent cascade model with parameters {Λ m } K m=1 whose value are unknown. Any online learning mechanism that is DSIC a posteriori achieves an auctioneer's revenue expected regret R T of Θ(T ).

Proof. (sketch) Basically, the A-VCG2 mechanism is DSIC in expectation w.r.t. the click realizations because it adopts execution-contingent payments in which the payment of advertiser a i depends also on the clicks over ads other than a i , while A-VCG2 is DSIC in expectation w.r.t. the realization of the random component of the mechanism because it adopts implicit payments. In order to have DSIC a posteriori, we need payments p i that are deterministic w.r.t. the click realizations over other ads other than a i (i.e., pay-per-click payments are needed) and deterministic w.r.t. any realization of the random component of the mechanism.

We notice that even if {Λ m } m∈K have been estimated (e.g., in an exploitation phase), we cannot have payments leading to DSIC a posteriori. Indeed, with estimates { Λm } m∈K , the allocation function maximizing SW (computed with Λm ) is not an affine maximizer and therefore the adoption of WVCG mechanism would not guarantee DSIC, not even in expectation. As a result, only mechanisms with payments defined in Eq. 24 can be used. However, these payments, if computed exactly (and not estimated in expectation), as required to have DSIC a posteriori, require the knowledge about the actual Λ m related to each slot s m in which an ad can be allocated for each report v ≤ v.

To prove the theorem, we provide a characterization of DSIC a posteriori mechanisms. More precisely, we need a monotonic allocation function and the payments defined in Eq. 24. As mentioned above, these payments require the knowledge about the actual Λ m related to the slot s m in which an ad can be allocated for any report v ≤ v. Thus we have two possibilities:

• In the first case, the ads are partitioned and each partition is associated with a single slot and the ad with the largest expected valuation is chosen at each slot independently. In other words, an ad can be allocated only in one given specific slot and its report determines only whether it is displayed or not (and not where). This case is equivalent to multiple separate-single slot auctions and therefore each auction is DSIC a posteriori as shown in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF]. However, as shown in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF], this mechanism would have a regret Θ(T ).

• In the second case, the ads are partitioned and each partition is associated with multiple slots and for each partition an auction is carried out to determine the allocation over each slot. In other words, an ad can be allocated in one of a given set of slots (associated with its partition) on the basis of its report. In this case, to compute the payments, it would be necessary to know the exact CTR of the ad for each possible slot, but this is possible only in expectation either by using the above execution-contingent, as we do in Section 4.2.1, or by using a random component in the mechanism, as we do in Section 4.2.2. However, in both these case we would not obtain DSIC a posteriori.

Thus, in order to have DSIC a posteriori, we need to adopt the class of mechanisms described in the first case, obtaining R T = Θ(T ).

Unknown {Λ m } m∈K and {q i } i∈N

In this section we study the situation in which both {q i } i∈N and {Λ m } m∈K are unknown. From the results derived in the previous section, we know that Input: Length of exploration phase τ , confidence δ Exploration phase for t = 1, . . . , τ do Allocate ads according to [START_REF] Tran-Thanh | Efficient crowdsourcing of unknown experts using multi-armed bandits[END_REF] Ask for no payment Observe the clicks

{click i 1 (t)} N i=1
Compute the estimated quality qi = 1

|B i | t∈B i click i 1 (t) Compute q+ i = qi + η
where η is given by ( 27)

Exploitation phase for t = τ + 1, . . . , T do Allocate ads according to f as prescribed by Algorithm 1 adopting f instead of f * For each ad a i , ask for payment pB,c i defined in [START_REF] Sarma | Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions[END_REF] Figure 5: Pseudo-code for the A-VCG3 mechanism.

adopting DSIC a posteriori leads to R T = Θ(T ). Thus, we will only focus on DSIC in expectation.

First of all, we remark that the mechanisms presented in Section 4.1 and 4.2 cannot be adopted here and a new mechanism is needed. By combining A-VCG1 and A-VCG2 , we obtain the algorithm A-VCG3 (Adaptive VCG3) illustrated in Fig. 5. As in the case when only the qualities {q i } i∈N are unknown, we formalize the problem as a MAB where the exploration and exploitation phases are separate and where, during the exploration phase, we estimate the values of {q i } i∈N .

Exploration phase. During the first τ steps, estimates of {q i } i∈N are computed. We use the same exploration policy of Section 4.1, but the estimates are computed just using samples from the first slot, since Λ m with m > 1 are unknown. 15 Define B i = {t : π(i; θ t ) = 1, 1 ≤ t ≤ τ } the set of steps where a i is displayed in the first slot, the number of samples collected for a i is 16 The estimated value of q i is:

|B i | = τ N ≥ τ 2N .
qi = 1 |B i | t∈B i click i 1 (t).
such that qi is an unbiased estimate of q i (i.e., E click [q i ] = q i ). By applying the Hoeffding's inequality we obtain an upper bound over the error of the estimated quality qi for each ad a i .

Proposition 5. For any ad {a i } i∈N

|q i -qi | ≤ 1 2|B i | log 2N δ ≤ N τ log 2N δ =: η, ( 27
)
with probability 1 -δ (w.r.t. the click realizations).

In this case, in order to have a meaningful bound, i.e., |q i -qi | < 1, the length of the exploration phase has to be τ > N log 2N δ . After the exploration phase, an upper-confidence bound over each quality is computed as q+ i = qi + η.

Exploitation phase. We first focus on the allocation function. During the exploitation phase we want to use an allocation θ = f (v) maximizing the estimated SW with estimated {q + i } i∈N and the parameters {Λ m } m∈K . Since the actual parameters {Λ m } m∈K are monotonically non-increasing, θ is defined as an allocation { s m , a α(m; θ) } m∈K , where

α(m; θ) ∈ arg max i∈N (q + i vi ; m) = arg max i∈N (q + i Λ m vi ; m).
We now focus on payments. Allocation function f is an affine maximizer (due to weights depending on qi as in Section 4.1), but WVCG payments cannot be computed given that parameters {Λ m } m∈K are unknown. Neither the adoption of execution-contingent payments, like in Eq. 23, is allowed, we cannot have no-regret mechanisms when payments are deterministic. 16 Following the same reasoning of Section 4.1, we consider an exploration time of τ > 2N , which guarantees to have at least two samples to estimate each q+ i .

given that q i is unknown and only estimates qi are available. Thus, we resort to implicit payments as in Section 4.2.2. More precisely, we use the same exploitation phase adopted in Section 4.2.2, except that we use f in place of f * . In this case, we have that the per-click payments are:

pB,c i (x, click i π(i; f (x)) ) = pB i (x,y;v) Λ π(i; f (x)) q i if click i π(i; f (x)) = 1 0 otherwise = =      vi - 1 µ vi if y i < vi 0 otherwise if click i π(i; f (x)) = 1 0 otherwise ( 28
)
where

pB i (x, y; v) = Λ π(i; f (x)) q i vi - 1 µ Λ π(i; f (x)) q i vi if y i < vi 0 otherwise . ( 29
)
We can state the following.

Theorem 10. The A-VCG3 is:

• DSIC in expectation w.r.t. the realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations,

• IR a posteriori,

• WBB in expectation w.r.t. the realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations.

Proof. The proof of DSIC in expectation and WBB in expectation easily follows from the definition of the adopted mechanism as discussed in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF].

The proof of IR a posteriori is similar to the proof of Proposition 2. The fact that the properties hold a posteriori w.r.t. the click realizations follows from [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF].

Now we want to analyze the performance of the mechanism in terms of the regret accumulated through T steps. Notice that in this case we have to focus on two different potential sources of regret: the adoption of a suboptimal (randomized) allocation function and the estimation of the unknown parameters.

Theorem 11. Let us consider a sequential auction with N advertisers, K slots, and T steps, with position-dependent cascade model with parameters {Λ m } K m=1 , accuracy η as defined in Eq. 27 and parameter µ ∈ (0, 1]. For any parameter τ ∈ {1, . . . , T } and δ ∈ (0, 1), the A-VCG3 achieves an auctioneer's revenue expected regret:

R T ≤ v max K [(T -τ ) (2η + 2µN ) + τ + δT ] .
By setting the parameters to

• µ = T -1 3 N -2 3 , • δ = T -1 3 N 1 3 , • τ = T 2 3 N 1 3 log 2N δ 1 3 , then the regret is R T ≤ 6v max KT 2 3 N 1 3 log 2T 1 3 N 2 3 1 3 . ( 30
)
Remark 1 (The bound). Up to numerical constants and logarithmic factors, the previous bound on R T = Õ(T ). We first notice that also in this case we match the lowest possible regret w.r.t. T when exploration and exploitation phases are separate. As a result, the proposed mechanism is a no-regret algorithm and it asymptotically approaches the performance of the VCG (when all the parameter are known). Compared to the results in Section 4.1, the dependency of the regret on K increased by a factor K

1 3
and it is now linear. This is a direct consequence of the exploration phase. In fact, here we cannot take advantage of the samples collected over all the slots, and the qualities are estimated only using samples observed in the first slot. On the other hand, the dependency on N is the same as in Section 4.1.

Remark 2 (Non-separate phases and Õ(T

)). The questions whether it is possible to avoid separating exploration and exploitation and preserve DSIC in expectation (in some form) and whether it is possible to obtain a regret of Õ(T

2 ) are open. Remark 3 (Using samples from multiple slots). An important issue is whether it is possible to exploit samples from the slots below the first one to improve the accuracy of the estimates and reduce the length of the exploration phase. The critical issue here is that the samples from slots below the first are drawn from a Bernoulli distribution with parameter obtained by the product of Λ m and q i , and it is not trivial to find a method to use these samples to improve the estimates. However, we notice that the exploitation of these additional samples would correspond to a reduction of the regret bound of at most K 1 3 , given that the dependency from K cannot be better than in the case discussed in Section 4.1 (i.e., O(K 2 3 )). We can also prove an upper-bound for the regret for the SW of A-VCG3.

Theorem 12. Let us consider an auction with N advertisers, K slots, and T steps, with position-dependent cascade model with parameters {Λ m } K m=1 , accuracy η as defined in Eq. 27 and parameter µ ∈ (0, 1]. For any parameter τ ∈ {1, . . . , T } and δ ∈ (0, 1), the A-VCG3 achieves a SW regret:

R SW T ≤ v max K [(T -τ )(2η + N µ) + τ + δT ] .
By setting the parameters to

• µ = K -1 T -1 3 N 1 3 , • δ = T -1 3 N 1 3 , • τ = T 2 3 N 1 3 log 2N δ 1 3 ,
then the regret is

R SW T ≤ 5v max KT 2 3 N 1 3 log 2T 1 3 N 2 3 1 3 .
Also in this case we obtain a regret on the SW R SW T = Õ(T

3 ).

Learning with Position-and Ad-Dependent Externalities

In this section we deal with the general model in Eq. 1, where both position-and ad-dependent externalities are present and we provide several partial results. In Section 5.1, we analyze the problem of designing a DSIC a posteriori mechanism when only the qualities of the ads are unknown, while in Section 5.2 we highlight some problems that rise when also continuation probabilities are uncertain.

Input: Length of exploration phase τ , confidence δ, position-dependent parameters {Γ m } m∈K Exploration phase for t = 1, . . . , τ do Allocate ads according to [START_REF] Tran-Thanh | Efficient crowdsourcing of unknown experts using multi-armed bandits[END_REF] Ask for no payment Observe the clicks

{click i π(i;θt) (t)} N i=1
Compute the estimated quality qi = 1

|B i | t∈B i click i π(i;θ t ) (t) Γ π(i;θ t )(θ t )
Compute q+ i = qi + η where η is given by ( 31)

Exploitation phase for t = τ + 1, . . . , T do Allocate ads according to f

if Ad a i is clicked then Ask for payment pc i defined in [START_REF] Ceppi | Mechanism design for federated sponsored search auctions[END_REF] Figure 6: Pseudo-code for the A-VCG4 mechanism.

Unknown qualities {q i } i∈N

We first focus on the problem where the only unknown parameters are the qualities {q i } i∈N of the ads and the externality model includes positionand ad-dependent externalities. We focus on DSIC in expectation w.r.t. the click realizations, since there is not any no-regret mechanism that is DSIC a posteriori w.r.t. the click realizations [START_REF] Mandal | A novel ex-post truthful mechanism for multislot sponsored search auctions[END_REF], and we study MAB algorithms that separate the exploration and exploitation phases. The structure of the mechanism we propose, called A-VCG4, is similar to the A-VCG1 and is reported in Fig. 6.

Exploration phase. At each step of the exploration phase of length τ , we collect K samples of no-click/click events. Given a generic exploration policy {θ t } τ t=1 , the estimated quality qi is computed as:

qi = 1 |B i | t∈B i click i π(i;θt) (t) Γ π(i;θt) (θ t )
,

where

B i = {t : π(i; θ t ) ≤ K, 1 ≤ t ≤ τ }.
Since the explorative allocations θ t impact on the cumulative probabilities of observation Γ m (θ t ), we use a variation of Proposition 1 in which Eq. 12 is replaced by:

|q i -qi | ≤ t∈B i 1 Γ π(i;θt) (θ t ) 2 1 2|B i | 2 log 2N δ .
For each exploration policy such that |B i | = Kτ /N ≥ Kτ 2N for any i ∈ N (e.g., the policy defined in Eq. 13), we redefine η as

|q i -qi | ≤ 1 Γ min N Kτ log 2N δ =: η, (31)
where Γ min = min θ∈Θ,m∈K {Γ m (θ)}. In this case, in order to have a meaningful bound, i.e., |q i -qi | < 1, the length of the exploration phase has to be

τ > 1 Γ 2 min N K log 2N δ .
We define the upper-confidence bound q+ i = qi + η. During the exploration phase, in order to preserve the DSIC a posteriori property, the allocations {θ t } τ t=1 do not depend on the reported values of the advertisers and no payments are imposed to the advertisers.

Exploitation phase. We define an upper bound on the SW as

SW(θ, v) = N i=1 Γ π(i;θ) (θ)q + i vi = K m=1 Γ m (θ)q + α(m;θ) vα(m;θ) .
We denote by θ the allocation maximizing SW(f (v), v) and by f the allocation function returning θ:

θ = f (v) ∈ arg max θ∈Θ SW(θ, v).
Once the exploration phase is over, the ads are allocated on the basis of f . Since f is an affine maximizer, the mechanism can impose WVCG payments to the advertisers satisfying the DSIC a posteriori property. In a pay-per-click fashion the advertiser a i is charged

pc i (v, click i π(i; θ) ) = SW( θ-i ) -SW -i ( θ) Γ π(i; θ) ( θ)q + i click i π(i; θ) , (32)
which corresponds, in expectation, to the WVCG payment E pc i (v, click i π(i; θ) ) = pi (v). As a result, we have: position/ad-dependent externalities does not change the dependency of the regret on the number of steps T and the number of ads N . Moreover, the per-step regret still decreases to 0 as T increases. The main difference w.r.t. the bound in Theorem 2 is in the dependency on K and on the smallest quality q min . We believe that the augmented dependence in K is mostly due to an intrinsic difficulty of the position/ad-dependent externalities. As a result, the bound displays a super-linear dependency on the number of slots. The other main difference is that now the regret has an inverse dependency on the smallest quality q min . Inspecting the proof, this dependency is due to the fact that the error of a quality estimate for an ad a i might be amplified by the inverse of the quality itself. As discussed in Remark 2 of Theorem 2, this dependency may also follow from the fact that we have a distributionfree bound. Further discussion on the tightness of this bound is postponed to Section 6.

Remark 2 (Optimization of the parameter τ ). Although the actual qualities {q i } i∈N are unknown, whenever a lower-bound on q min is available, the parameter τ could be better tuned by multiplying it by (q min ) -2 3 , thus reducing the regret from Õ((q min ) -1 ) to Õ((q min ) -2 3 ). Remark 3 (Externalities-dependent bound). We notice that the previous bound does not reduce to the bound in Eq. 20 in which only position-dependent externalities are present. Indeed, the dependency on K is different in the two bounds: from K 2 3 in Eq. 20 to K 4 3 in Eq. 34. This means that the bound in Eq. 34 over-estimates the dependency on K whenever the auction has only position-dependent externalities. It is an interesting open question whether it is possible to derive an auction-dependent bound where the specific values of the cumulative probabilities of observation γ m,i explicitly appear in the bound and which reduces to Eq. 20 for position-dependent externalities.

(Comment to the proof ). While the proof of Theorem 2 could exploit the specific definition of the payments for position-dependent slots and it is a fairly simple extension of [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF], in this case the proof is more complicated because of the dependency of the cumulative probabilities of observation on the actual allocations and decomposes the regret of the exploitation phase in components due to the different allocations ( f instead of f * ) and the different qualities as well (q + i instead of q i ). Using the mechanism described before, it is possible to derive an upperbound over the cumulative regret over the SW of the allocation (as in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF]).

in [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF]) and this parameter is the only uncertain parameter (i.e., the qualities are known).

We focus on the exploitation phase, supposing the exploration phase has produced the estimates {c + i } i∈N for the continuation probabilities {c i } i∈N . The allocation function f presented in [START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF] is able to compute the optimal allocation when {c i } i∈N values are known, but it is not an affine maximizer when applied to the estimated values {c + i } i∈N . In fact, in that case the allocation becomes

f (v) ∈ arg max θ∈Θ K m=1 q α(m;θ) vα(m;θ) m-1 h=1 c+ α(h;θ) . (37)
In this case, it is not possible to isolate a weight depending only on a single ad and thus f (v) is not affine. Furthermore, we can also show that such allocation function is not monotonic.

Proposition 6. The allocation function f in Eq. 37 is not monotonic.

Proof. The proof is by counterexample. Consider an environment with 3 ads and 2 slots such that ad v i c+ i c i a 1 0.85 1 0.89 a 2 1 0.9 0.9 a 3 1.4 0 0 and q i = 1 ∀i ∈ N . The optimal allocation θ computed by f when agents declare their true values v is: ad a 2 is allocated in the first slot and a 3 in the second one. We have CT R a 3 ( θ) = 0.9. If advertiser a 3 reports a larger value, e.g., v3 = 1.6, in the resulting allocation f (v 3 , v -3 ), ad a 1 is displayed into the first slot and a 3 into the second one. In this case CT R a 3 ( θ) = 0.89 < CT R a 3 ( θ), thus the allocation function f is not monotonic.

On the basis of this result, we can state the following theorem. Proof. Let, with abuse of notation, f (v|c) be the allocation function maximizing the SW given parameters c. As shown above, f (v|c) cannot be used in the exploitation phase, because the resulting mechanism would not be DSIC in expectation w.r.t. the click realizations. However, it can be easily observed that a necessary condition to have a no-regret algorithm is that the allocation function used in the exploitation phase, say g(v|c), is such that g(v|c) = f (v|c) for every v and c (that is, they always return the same allocation). Indeed, if there exists at least a v such that g(v|c) = f (v|c), then, as T → +∞, f (v|c) = g(v|c), given that c → c. Thus, since the difference between the values of the allocations is generically strictly positive, the algorithm would suffer from a strictly positive regret when T → +∞ and therefore it would not be a no-regret mechanism. However, any such a g would not be monotonic and therefore it cannot be adopted in a DSIC in expectation w.r.t. the click realizations mechanism. As a result, any online learning mechanism that is DSIC in expectation w.r.t. the click realizations is not a no-regret mechanism.

To complete the proof, we need to provide a mechanism with regret Θ(T ). Such a mechanism can be easily obtained by partitioning ads in groups such that in each group the ads compete only for a single slot. Therefore, each ad can appear in only one slot.

The above result shows that no approach similar to the one described in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] can be adopted even for obtaining DSIC in expectation w.r.t. realizations of the random component of the mechanism. Indeed, the approach described in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] requires in input a monotonic allocation function. This would suggest a negative result in terms of regret also with DSIC in expectation w.r.t. realizations of the random component of the mechanism.

Finally, we provide a result on the regret over the auctioneer's revenue. The proof is straightforward given that the WVCG cannot be adopted due to the above result and therefore the regret over the payments cannot go to zero as T goes to infinite. Theorem 17. Let us consider a sequential auction with N advertisers, K slots, and T steps, with ad-dependent cascade model with parameters {c i } N i=1 whose value are unknown. Any online learning mechanism that is DSIC in expectation w.r.t. the click realizations and a posteriori w.r.t. realization of the random component of the mechanism achieves an auctioneer's revenue expected regret R T = Θ(T ).

Numerical Simulations

In this section we report numerical simulations to validate the theoretical bounds over the regret of the auctioneer's revenue proved in the previous sections. 18 In particular, the theoretical bounds reveal the dependency of (expected) regret on characteristic parameters of the auction (i.e., T , N , K, and q min , and µ if the mechanism is randomized). Nonetheless, the upper bounds may be inaccurate in overestimating the actual performance of the proposed algorithms. In fact, while we prove that the regret can never be larger than the upper bound, some steps in the proofs may be loose, thus leading to bounds which do not accurately predict the behavior of the algorithms in practice. In the following we investigate by means of numerical simulations whether the dependency, in terms of asymptotic order, of the bounds on each single parameter of the auction is accurate except for a numerical constant factor. In all the following experiments, we generate the parameters related to the ads in the same way. The qualities {q i } i∈N are drawn from a uniform distribution in [0.01, 0.1], while the values {v i } i∈N are randomly drawn from a uniform distribution on [0, 1] (v max = 1). On the other hand, the cumulative probabilities of observation {Λ m } m∈K are different case by case.

Since the main objective is to evaluate the asymptotic accuracy of the bounds, we report the relative regret

RR T = R T B(T, K, N, q min )
,

where B(T, K, N, q min ) is the value of the bound for the specific setting (i.e., Eq. 20 and Eq. 30 for position-dependent, and Eq. 34 for position/addependent externalities). We analyze the asymptotic accuracy of the bounds w.r.t. each specific parameter, changing only its value and keeping the values of all the others fixed. Since B is proved to be an upper-bound on the actual regret R T , we expect the relative regret RR T to be always smaller than 1 (RR T = 1 corresponds to the case in which the experimental regret perfectly matches our upper bound). In particular, we say that our upper-bound accurately predicts the actual asymptotic dependency of the regret w.r.t. a specific parameter if the experimental dependence of RR T w.r.t. to the parameter is a constant as the parameter changes. Notice that we do not expect the constant to be close to 1, given that we focus on the asymptotic dependence w.r.t. the parameters and in the steps of the proofs we often use worst-case distribution-free bounds. All the results presented in the following sections are obtained by setting τ and δ as suggested by our bounds and, where it is not differently specified, by averaging over 100 independent runs.

T (×10 3 )
6.1. Position-Dependent Externalities 6.1.1. Unknown {q i } i∈N First of all we analyze the asymptotic accuracy of the bound provided in Section 4.1, where the model presents only position-dependent externalities and the qualities of the ads are unknown. We design the simulations such that λ m = λ for every m with Λ 1 = 1 and Λ K = 0.8 (i.e., λ = K-1 √ 0.8). Thus, Λ min = 0.8 in all the experiments.

In Fig. 7 we analyze the asymptotic accuracy of the bound w.r.t. the parameters T and N . All the three curves in the left plot are completely flat (except for noise due to the randomness of the simulations) showing that the value of the relative regret RR T for different values of K and N does not change as T increases. This suggests that the bound in Theorem 2 effectively predicts the dependency of the regret R T w.r.t. the number of steps T of the auction as Õ(T 2/3 ). The right plot represents the dependency of the relative regret RR T on the number of ads N . In this case we notice that it is relatively accurate as N increases, but there is a transitory effect for smaller values of N where the regret grows faster than predicted by the bound (although B(T, K, N, q min , Λ min ) is still an upper-bound to R T ). Finally, the left plot of Fig. 8 suggests that the asymptotic dependency on K in the bound of Theorem 2 is over-estimated, since the relative regret RR T decreases as K increases. As discussed in the comment to the proof in Section 4, this might be explained by the over-estimation of the term max i (q + i vi ;l) max i (q + i vi ;k) in the proof. In fact, this term is likely to decrease as K increases. In order to validate this intuition, we have identified some experimental settings for which the bound seems to accurately predict the asymptotic dependency on K: q 1 = 0.1, q 2 = 0.095, and q i = 0.09 for every 2 < i ≤ K. As a result, the ratio between the qualities {q i } i∈N is fixed (on average) and does not change with K. The right plot of Fig. 8 shows that, with these values of {q i } i∈N , the ratio RR T is constant for different values of N , implying that in this case the bound accurately predicts the asymptotic behavior of R T . In fact, as commented in the remarks to Theorem 2, we derive distribution-independent bounds where the qualities {q i } i∈N do not appear in the bound. As a result, R T should be intended as a worst case w.r.t. all the possible configurations of qualities and externalities.

Unknown {Λ m } m∈K

We now investigate the asymptotic accuracy of the bound derived for algorithm A-VCG2 presented in Section 4.2.2. We used several probability distributions to generate the values of {λ m } m∈K . We observed that, when they are drawn uniformly from the interval [0.98, 1.00], the numerical simulations confirm our bound (as we show below), whereas the bound seems to overestimate the dependencies on K and µ when the support of the proba- bility distribution is wider (e.g., [ξ, 1.00] with ξ 0.98); we do not report any plot for this second case.

T (×10 3 )
The left plot of Fig. 9 shows the dependence of the ratio RR T w.r.t. T when µ = 0.01. Despite the noise, the ratio seems not to be affected by the variation of T , confirming our bound. In the right plot of Fig. 9, we observe that when T = 10 5 and µ = 0.01 the behavior of the ratio as K changes is essentially the same for different values of N . Furthermore, we observe that the bound is accurate except that it seems to overestimate the dependence when K assumes small values (as it happens in practice). In the left plot of Fig. 10, the ratio RR T seems to be constant as µ varies when T = 10 5 .

We conclude our analysis studying the variance of the payments as µ varies. The bound over R T , provided in Section 4. a µ → 0 in order to reduce the regret. Nonetheless, the regret bounds are obtained in expectation w.r.t. all the sources of randomization and do not consider how single realizations of the learning mechanism may deviate w.r.t. the expected regret. Thus in the right plot of Fig. 10 we investigate the variance of the payments. The variance is excessively high for small values of µ, making the adoption of these value inappropriate. Thus, the choice of µ should consider both these two dimensions of the problem: the regret and the variance of the payments.

6.1.3. Unknown {Λ m } m∈K and {q i } i∈N In this section we analyze the bound provided in Section 4.3 for positiondependent auctions where both the prominences and the qualities are unknown. For these simulations we generate {λ m } m∈K samples from a uniform distribution over [0.5, 1] and we set τ , δ and µ to the values derived for the bound. In particular, in order to balance the increase of variance of the payments when µ decreases, the number of steps is not constant, but it changes as a function of µ as 1000 µ . This means that, in expectation, the bid of a generic ad a i is modified 1000 times over the number of the steps.

In the plots of Fig. 11, we show that the bound in Eq. 30 accurately predicts the asymptotic dependence of the regret w.r.t. the parameters T and N . Indeed, except for the noise due to the high variance of the payments based on the cSRP, the two plots show that fixing the other parameters, the ratio RR T is constant as both T increases and N increases.

The plot in Fig. 12 represents the dependency of the relative regret w.r.t. the parameter K. We can deduce that the bound R T over-estimates the dependency on K for small values of the parameters, while, with larger values, the bound accurately predicts the behavior, the curves being flat.

Position/Ad-Dependent Externalities

In this section we analyze the bound provided in Section 5.1 for auctions with position-dependent and ad-dependent externalities where only the qualities are unknown.

In the bound provided in Theorem 14 the regret R T presents a linear dependency on N and an inverse dependency on the smallest quality q min . In the left plot of Fig. 13 we report RR T as T increases. As it can be observed, the bound accurately predicts the behavior of the regret w.r.t. T as in the case of position-dependent externalities. In the right plot of Fig. 13 we report RR T as we change q min . According to the bound in Eq. 34 the regret should decrease as q min increases (i.e., R T = Õ(q -1 min )) but it is clear from the plot that R T has a much smaller dependency on q min , if any. 19 Finally, we study the dependency on N (Fig. 14). In this case RR T slightly increases and then it tends to flat as N increases. This result suggests that the, theoretically derived, N 1 3 asymptotic dependency of R T w.r.t. the number of ads might be correct. We do not report results on K since the complexity of finding the optimal allocation f * becomes intractable for values of K larger than 8, as shown in [START_REF] Gatti | Which mechanism in sponsored search auctions with externalities?[END_REF], making the empirical evaluation of the bound unfeasible.

Conclusions and Future Work

In this paper, we studied the problem of learning the CTRs of ads in sponsored search auctions with truthful mechanisms. This problem is highly challenging since it requires the combination of online learning tools (i.e., regret minimization algorithms) and economic tools (i.e., truthful mechanisms). While almost all the literature focused on single-slot scenarios, here we focused on multi-slot scenarios. With multiple slots it is necessary to adopt a user model to characterize how the CTR of an ad varies as the allocation of displayed ads varies. Here, we adopted the cascade model, that is the most common model used in the literature. In the paper, we studied a number of scenarios, each with a specific information setting of unknown parameters. For each scenario, we designed a truthful learning mechanism, studied its economic properties, derived an upper bound over the regret, and, for some mechanisms, also a lower bound. We considered both the regret over the auctioneer's revenue and the SW.

We showed that for the cascade model with only position-dependent externalities it is possible to design a truthful no-regret learning mechanism for the general case in which all the parameters are unknown. Our mechanism presents a regret Õ(T

3 ) and it is DSIC in expectation w.r.t. the realization of the random component of the mechanism. However, it remains open whether or not it is possible to obtain a regret Õ(T 1 2 ). For specific cases, in which some parameters are known to the auctioneer, we obtained better results in terms of either incentive compatibility, obtaining dominant strategy truthfulness, or regret, obtaining a regret of zero. We showed that for the cascade model with the position-and ad-dependent externalities it is possible to design a DSIC a posteriori mechanism with a regret Õ(T

3 ) when only the quality is unknown. Instead, even when the cascade model is only with ad-dependent externalities and no parameter is known, it is not possible to obtain a no-regret DSIC a posteriori mechanism. The proof of this result would seem to suggest that the same result holds also when a random mechanism is adopted and the truthfulness is in expectation w.r.t. its realizations. However, we did not produce any proof for that, leaving it for future works. Finally, we empirically evaluated the bounds we provided, showing that the dependency of the regret on the parameters is mostly correct in a worst-case scenario.

Two main questions deserve future investigation. The first question concerns the study of a lower bound for the case in which there are only positiondependent externalities and truthfulness is in expectation in expectation w.r.t. only the realizations of the random component of the mechanism or also w.r.t. the click realizations. Furthermore, it is open whether the separation of exploration and exploitation phases is necessary and, in the negative case, whether it is possible to obtain a regret Õ(T

(q i vi ; m) max i∈N (q + i vi ; m) ≤ 1, (C.1)
where the operator max(•; •) is defined as in Section 4.

Proof. The proof is a straightforward application of Proposition 1. We consider the optimal allocation θ * defined in Eq. 2 and the optimal allocation θ when estimates q+ are adopted defined in Eq. 16. We denote h = α(m; θ * ) ∈ arg max i∈N (q i vi ; m), i.e., the index of the ad allocated in a generic slot in position m. There are two possible scenarios:

• If π(h; θ) < m (the ad is displayed into a higher slot in the approximated allocation θ), then ∃j ∈ N s.

t. π(j; θ * ) < m ∧ π(j; θ) ≥ m. Thus max i∈N (q + i vi ; m) ≥ q+ j vj ≥ q j vj ≥ q h vh = max i∈N (q i vi ; m)
where the second inequality holds with probability 1 -δ;

• If π(h; θ) ≥ m (the ad is displayed into a lower or equal slot in the approximated allocation θ), then

max i∈N (q + i vi ; m) ≥ q+ h vh ≥ q h v h = max i∈N (q i vi ; m)
where the second inequality holds with probability 1 -δ.

In both cases, the statement follows.

Proof. (Theorem 2)

Step 1: expected payments. The proof follows steps similar to those in the proofs in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF]. We first recall that since the mechanism is DSIC in expectation w.r.t. the clicks, then we can directly focus on the regret when the actual values v are bid. For any ad a i such that π(i; θ * ) ≤ K, the expected payments of the VCG mechanism in this case reduce to Eq. 9:

p * i (v) = K+1 l=π(i;θ * )+1 (Λ l-1 -Λ l ) max j∈N (q j v j ; l) ,
while, given the definition of A-VCG1 reported in Section 4.1, the expected payments for at t-th iteration of the auction are

pi,t (v) = 0 if t ≤ τ (exploration) pi (v) if t > τ (exploitation) (C.2)
where the payment for any ad a i such that π(i; θ) ≤ K is defined in Eq. 17 as:

pi (v) = q i q+ i K+1 l=π(i; θ)+1 (Λ l-1 -Λ l ) max j∈N (q + j v j ; l).
Step 2: per-step exploration regret. Since for any 1 ≤ t ≤ τ , A-VCG1 sets all the payments to 0, the per-step regret is

r t = K m=1 p * α(m;θ * ) (v) -0 = K m=1 K l=m ∆ l max i∈N (q i v i ; l + 1) ≤ v max K m=1 Λ m , (C.3)
where ∆ l = Λ l -Λ l+1 . The exploration regret is obtained by summing up r over τ steps.

Step 3: per-step exploitation regret. Now we focus on the expected (w.r.t. click realizations) per-step regret during the exploitation phase. According to the definition of payments, at each step t ∈ {τ + 1, . . . , T } of the exploitation phase we bound the per-step regret r as

r t = K m=1 p * α(m;θ * ) (v) -pα(m; θ) (v) = K m=1 K l=m ∆ l   max i∈N (q i v i ; l + 1) - max i∈N (q + i v i ; l + 1) q+ α(m; θ) q α(m; θ)   = K m=1 K l=m ∆ l max i∈N (q + i v i ; l + 1) q+ α(m; θ)   max i∈N (q i v i ; l + 1) max i∈N (q + i v i ; l + 1) q+ α(m; θ) -q α(m; θ)   = K m=1 K l=m ∆ l max i∈N (q + i v i ; l + 1) max i∈N (q + i v i ; m) v α(m; θ)   max i∈N (q i v i ; l + 1) max i∈N (q + i v i ; l + 1) q+ α(m; θ) -q α(m; θ)   .
By definition of the max operator, since l + 1 > m, it follows that

max i∈N (q + i v i ; l + 1) max i∈N (q + i v i ; m) ≤ 1. (C.4)
Finally, from Lemma 1 and v α(m; θ) ≤ v max , it follows that

r t ≤ K m=1 K l=m v max ∆ l q+ α(m; θ) -q α(m; θ) ≤ v max K m=1 q+ α(m; θ) -q α(m; θ) K l=m ∆ l , (C.5)
with probability at least 1 -δ. Notice that, by definition of ∆ l , K l=m ∆ l = Λ m -Λ K+1 = Λ m . Furthermore, from the definition of q+ i and using Eq. 14 we have that for any ad a i :

q+ i -q i = qi -q i + η ≤ 2η,
with probability at least 1 -δ. Thus, the difference between the payments becomes

r t ≤ 2v max K m=1 Λ m η = 2v max K m=1 Λ m K m=1 1 Λ 2 m N K 2 τ log N δ (C.6)
with probability 1 -δ. 20Step 4: cumulative regret. We first consider the (low-probability) event in which the bound on q+ i derived in Proposition 1. In this case, we cannot guarantee anything about the behavior of the mechanism, since the payments are very inaccurate estimates of the CTRs, and thus the largest possible regret is suffered. In particular, we consider the worst case loss of v max for each slot for each step, leading to a total regret of v max K m=1 Λ m T with probability δ. By summing up the regrets reported in Eq. C.3 during the exploration phase and Eq. C.6 during the exploitation phase and by considering that these bounds hold with probability at least 1 -δ (upperbounded by 1 in the following), we obtain an expected regret

R T ≤ v max K m=1 Λ m 2(T -τ ) K m=1 1 Λ 2 m N K 2 τ log N δ R ei + τ Rer + δT R δ
, where R ei is the upper bound on the regret suffered during the exploitation phase (which holds with probability at least 1 -δ), R er is the upper bound on the regret suffered during the exploitation phase (which holds with probability at least 1 -δ) and R δ is the upper bound on the regret when the bounds do not hold (with probability at most δ). This boundcan be further simplified, given that K m=1 Λ m ≤ K, as

R T ≤ v max K 2(T -τ ) K m=1 1 Λ 2 m N K 2 τ log N δ + τ + δT . (C.7)
Step 5: parameters optimization. Beside describing the performance of A-VCG1, the previous bound also provides guidance for the optimization of the parameters τ and δ. We first simplify the bound in Eq. C.7 as

R T ≤ v max K   2T K m=1 1 Λ 2 m N K 2 τ log N δ + τ + δT   ≤ v max K 2T Λ min N Kτ log N δ + τ + δT , (C.8)
where we used

K m=1 1/Λ 2 m ≤ K/Λ 2 min , with Λ min = min m∈K Λ m .
In order to find the optimal value of τ , we take the derivative of the previous bound w.r.t. τ , set it to zero and obtain

v max K -τ -3 2 T Λ min N K log N δ + 1 = 0, which leads to τ = K -1 3 T 2 3 N 1 3 Λ -2 3 min log N δ 1 3 .
• s ∈ {0, 1} N is a vector where each element s i denotes whether the i-th bid has been preserved or it has been modified by the cSRP, i.e., if x i = vi then s i = 1, otherwise if x i < vi then s i = 0. Notice that s does not provide information about the actual modified values x;

• E x|s [Λ π(i;f (x)) |v]
is the expected value of prominence associated with the slots allocated to ad a i , conditioned on the declared bids v being perturbed as in s.

Moreover, let S = {s|π(i; f * (v)) ≤ K + 1 ⇒ s i = 1 ∀i ∈ N } be all the realizations where the cSRP does not modify the bids of the first K + 1 ads, i.e., the K ads displayed applying f * to the true bids v and the first non-allocated ad.

Step 2: cumulative regret. We proceed by studying the per-ad regret

r i (v) = p * i (v) -p * i (v)
, where the advertisers bid their true values v since the mechanism is DSIC. Given the previous definitions, we rewrite the expected payments p * i (v) as

p * i (v) = P[s ∈ S]Λ π(i;f * (v)) + P[s ∈ S]E x|s ∈S [Λ π(i;f * (x)) |v] q i v i + - v i 0 P[s ∈ S]Λ π(i;f * (v -i ,u)) + P[s ∈ S]E x|s =1
[Λ π(i;f * (x)) |v -i , u] q i du = P[s ∈ S] Λ π(i;f * (v)) q i v i -

v i 0 Λ π(i;f * (v -i ,u)) q i du + + P[s ∈ S] E x|s ∈S [Λ π(i;f * (x)) |v]q i v i - v i 0 E x|s ∈S [Λ π(i;f * (x)) |v -i , u]q i du = P[s ∈ S]p * i (v)+ + P[s ∈ S] E x|s ∈S [Λ π(i;f * (x)) |v]q i v i - v i 0 E x|s ∈S [Λ π(i;f * (x)) |v -i , u]q i du ,
where in the last expression we used the expression of the VCG payments in Eq. 24 according to [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF] and [START_REF] Green | Incentives in Public Decision Making[END_REF]. The per-ad regret is .

r i (v) = p * i (v) -p * i (v) = p * i (v
Since we have that u ≤ v i in the integral and since the allocation function defined in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] is monotonic, we have that

E x|s ∈S [Λ π(i;f * (x)) |v -i , u] ≤ E x|s ∈S [Λ π(i;f * (x)) |v],
which implies that r B i,1 is non-negative. Thus the regret r B i can be bounded as We can now compute the bound on the global regret R T . Since this mechanism does not require any estimation phase, the regret is simply R T ≤ 2K 2 µv max T.

Step 3: parameters optimization. In this case, the bound would suggest to choose a µ → 0, but it is necessary to consider that with µ → 0 the variance of the payment goes to infinity.

Step 1: payments and the regret. Similar to the proof of Theorem 7, we use the form of the VCG payments as in Eq. 24:

p * i (v) = Λ π(i;f * (v)) q i v i -v i 0 Λ π(i;f * (v -i ,u)) q i du, while A-VCG3 uses the contingent payments in Eq. 28, which in expectation become

p i (v) = E x Λ π(i; f (x)) |v q i v i - v i 0 E x Λ π(i; f (x)) |v -i , u q i du. (E.1)
We also need to introduce the expected payments pi (v) = Λ π(i; f (v)) q i v i -

v i 0 Λ π(i; f (v -i ,u)) q i du,
which correspond to the VCG payments except for the use of allocation function f in place of f * . Initially, we compute an upper bound over the per-ad regret r i = p * i -p i for each step of the exploitation phase and we later use this result to compute the upper bound for the regret R T over T steps. We divide the per-ad regret in two different components:

r i (v) = p * i (v) -p i (v) (E.2) = p * i (v) -p * i (v) cSRP regret + p * i (v) -p i (v) learning regret = r B i (v) + r L i (v),
where

• r B i (v) is the regret due to the use of the approach proposed in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] instead of the VCG payments, when all the parameters are known;

• r L i (v) is the regret due to the uncertainty on the parameters when the payments defined in [START_REF] Babaioff | Truthful mechanisms with implicit payment computation[END_REF] are considered.

For the definitions of s and E x|s [Λ π(i;f (x)) |v] refer to the proof of Theorem 7.

Step 2: the per-ad per-step cSRP regret. We can reuse the result obtained in the proof of Theorem 7. In particular, we can use the bound in Eq. D.2, i.e. r B i (v) ≤ (K + 1) µv max . Given that we have assumed N > K, in the remaining parts of this proof we will use the following upper bound: r B i (v) ≤ (K + 1) µv max ≤ N µv max .

Step 3: the per-ad per-step learning regret. Similar to the previous step, we write the learning expected payments based on the cSRP in Eq. E.1 as

p i (v) = P[s = 1]p i (v)+ + P[s = 1] E x|s =1 [Λ π(i; f (x)) |v]q i v i - v i 0 E x|s =1 [Λ π(i; f (x)) |v -i , u]q i du .
Then the per-ad regret is

r L i (v) = p * i (v) -p i (v) = P[s = 1] (p * i (v) -pi (v)) + + P[s = 1] E x|s =1 [Λ π(i;f * (x)) |v]q i v i - v i 0 E x|s =1 [Λ π(i;f * (x)) |v -i , u]q i du ≤vmax + -E x|s =1 [Λ π(i; f (x)) |v]q i v i + v i 0 E x|s =1 [Λ π(i; f (x)) |v -i , u]q i du =-r B i,1 ≤0
≤ p * i (v) -pi (v) + P ∃j : s j = 0 v max ≤ p * i (v) -pi (v) + j∈N P s j = 0 v max = p * i (v) -pi (v) + N µv max .

We now simply notice that payments pi are WVCG payments corresponding to the estimated allocation function f and can be written as pi (v) = q i q+ i SW f-i (v) , v -SW -i f (v) , v , which allows us to use the results stated in proof of Theorem 2 and from Eq. C.5 we can conclude that i:π(i;f * (v)≤K)

(p * i (v) -pi (v)) ≤ 2v max η K m=1
Λ m ≤ 2Kv max η.

Step 4: cumulative regret. We now bring together the two per-step regrets and we have that at each step of the the exploitation phase we have the regret r = N i=1 r i . We first notice that the expected per-step regret r i

The second statement follows from SW(g(v), v)-SW(g(v), v) q i q+ i ≤ j:π(j;g(v))≤K Γ π(j;g(v)) vj q j -q+ j q i q+ i ≤ v max j:π(j;g(v))≤K q j -q j q i q+ i + q j q i q+ i -q+ j q i q+ i = v max j:π(j;g(v))≤K q j q+ i -q i q+ i + (q j -q+ j ) ≤0 q i q+ i ≤ v max q min j:π(j;g(v))≤K (q i -q i + η) ≤ 2Kv max q min η.

Lemma 3. Let G be an arbitrary space of allocation functions, then for any g ∈ G, when |q i -q+ i | ≤ η with probability 1 -δ, we have 0 ≤ SW(g(v), v) -SW(g(v), v) ≤ 2Kv max η, with probability 1 -δ.

Proof. The first inequality follows from SW(g(v), v) -SW(g(v), v) = j:π(j;g(v))≤K Γ π(j;g(v)) (g(v))v j q j -q+ j ≤ v max j:π(j;g(v))≤K (q j -q+ j ) ≤ 0, while the second inequality follows from SW(g(v), v)-SW(g(v), v) = j:π(j;g(v))≤K Γ π(j;g(v)) (g(v))v j q+ j -q j ≤ v max j:π(j;g(v))≤K q+ j -q j = v max j:π(j;g(v))≤K (q j + η -q j ) ≤ 2Kv max η.

We are now ready to proceed with the proof of Theorem 14.

Proof. (Theorem 14)

Step 1: per-ad per-step regret. We first compute the per-step per-ad regret r i = p * i (v) -pi (v) at each step of the exploitation phase for each ad a i . According to the definition of payments we have

r i = SW(f * -i (v), v) -SW( f-i (v), v) q i q+ i r 1 i + SW -i ( f (v), v) q i q+ i -SW -i (f * (v), v) r 2 i .
We bound the first term through Lemma 2 and the following inequalities

r 1 i = SW(f * -i (v), v) -SW(f * -i (v), v) q i q+ i + SW(f * -i (v), v) q i q+ i -SW( f-i (v), v) q i q+ i ≤ max f ∈F -i SW(f (v), v) -SW(f (v), v) q i q+ i + SW(f * -i (v), v) -max f ∈F -i SW( f (v), v) ≤0 q i q+ i ≤ 2Kv max q min η,
with probability 1 -δ. We rewrite r 2 i as

r 2 i = SW( f (v), v) -Γ π(i; f (v)) ( f (v))q + i v i q i q+ i -SW(f * (v), v) + Γ π(i;f * (v)) (f * (v))q i v i = SW( f (v), v) q i q+ i -SW(f * (v), v) r 3 i + Γ π(i;f * (v)) (f * (v)) -Γ π(i; f (v)) ( f (v)) q i v i .
We now focus on the term r 3 i and use Lemma 2 to bound it as

r 3 i = SW( f (v), v) q i q+ i -SW( f (v), v) + SW( f (v), v) -max f ∈F SW(f (v), v) ≤0 81 ≤ max f ∈F SW(f (v), v) q i q+ i -SW(f (v), v)
≤ 2Kv max η.

Step 2: exploitation and cumulative regret. We define I = {i ∈ N | π(i; f ( v)) ≤ K ∨ π(i; f (v)) ≤ K}, |I| ≤ 2K. It is clear that only the ads a i s.t. i ∈ I have a regret r i = 0. The other ads, i ∈ I, have both p * i (v) = 0 and pi (v) = 0. Thus, we can bound the regret r, at each exploitative step, in the following way

r = i∈I (r 1 i + r 2 i ) ≤ i∈I 2Kv max q min η + 2Kv max η + i∈I Γ π(i;f * (v)) (f * (v)) -Γ π(i; f (v)) ( f (v)) q i v i = i∈I 2Kv max q min η + 2Kv max η + N i=1 Γ π(i;f * (v)) (f * (v)) -Γ π(i; f (v)) ( f (v)) q i v i ≤ 8K 2 v max q min η + SW(f * (v), v) -SW( f (v), v) = 8K 2 v max q min η + SW(f * (v), v) -SW(f * (v), v)+ + SW(f * (v), v) -max f ∈F SW(f ) ≤0 + SW( f (v), v) -SW( f (v), v) ≤ 8K 2 v max q min η + SW(f * (v), v) -SW(f * (v), v) r 1 + SW( f (v), v) -SW( f (v), v) r 2
.

The remaining terms r 1 and r 2 can be easily bounded using Lemma 3 as r 1 ≤ 0 and r 2 ≤ 2Kv max η.

Summing up all the terms we finally obtain r ≤ 10K 2 v max q min η with probability 1-δ. Now, considering the per-step regret of the exploration and exploitation phases, we obtain the final bound on the cumulative regret Proof. We initially provide a bound over the per-step regret during the exploitation phase. We consider the two sides of the bound separately. We have that for the first side of the bound we can use the result provided in

Step 3 in the proof of Theorem 2, i.e., q α(m; θ) -max i∈N (q i v i ; l + 1)

  ≤ max i∈N (q i v i ; l + 1) K m=1 K l=m ∆ l   max i∈N (q + i v i ; l + 1) max i∈N (q i v i ; l + 1) -1   .
In order to proceed we need to bound the ratio in the inner term. We first recall that for any ad a i , we have that q+ i v i = (q i + η) v i ≤ (q i + 2η) v i . Let i ∈ arg max j∈N (q j v j ; l + 1) be the ad displayed in s l+1 when the true qualities are known. We distinguish two cases:

• The ad a i shifts from slot l + 1 to a higher precedence slot when allocated according to f , i.e., π(i ; f (v)) ≤ l + 1. In this case we have max i∈N (q + i v i ; l + 1) max i∈N (q i v i ; l + 1)

≤ q+ i v i q i v i ≤ 1 + 2η q min .
• The ad a i shifts from slot l+1 to a lower precedence slot when allocated according to f , i.e., π(i ; f (v)) > l + 1. In this case, there must exist an ad j that in the exact allocation is allocated after i but it is promoted to a higher precedence slot according to f . This corresponds to a j ∈ N such that π(j; f * (v)) ≥ l + 1 but π(j; f (v)) < l + 1. As a result we have max i∈N (q + i v i ; l + 1) max i∈N (q i v i ; l + 1) ≤ q+ j v j q i v i ≤ q j v j + 2ηv j q i v i ≤ q j v j + 2η q j q min v j q i v i Λ π(j;f (x)) v j (q j -q j )   + v max µK 2 ≤ v max max f ∈F   j:π(j;f (x))≤K (q j -q j )   + v max µK 2 ≤ 2v max Kη + v max µK 2 = v max K (2η + Kµ) .

We provide a brief intuition of bounds r 1 and r 2 . The bound r 1 can be explained noticing that when the bids of the ads displayed in f * (v) are not modified we have that α(m; f * (v)) = α(m; f * (x)) where m ≤ K and x s.t. s ∈ S . The bound for r 2 can be understood noticing that when the bids of the ads s.t. π(j; f * (x)) ≤ K are not modified and x i ≤ vi ∀i ∈ N , we obtain SW(f * (x), v) = SW(f * (x), x) ≤ max θ∈Θ SW(θ, x) = SW( f (x), x) ≤ SW( f (x), v).

Step 2: cumulative regret. We can now compute the upper bound for the global regret

R SW T ≤ v max K [(T -τ )(2η + Kµ) + τ + δT ]

Figure 1 :

 1 Figure 1: Pseudo-code for the A-VCG1 mechanism.

2 3 )

 3 instead of Õ(T 1 2

Theorem 4 .Proposition 3 .

 43 The A-VCG2 is:• DSIC in expectation w.r.t. the click realizations,• IR a posteriori,• WBB in expectation w.r.t. the click realizations,• AE.Proof. It trivially follows from the fact that the allocation function is AE and the payments in expectation equal the VCG ones and by Proposition 2. The A-VCG2 is not DSIC a posteriori (w.r.t. the click realizations).

Input:Figure 3 :

 3 Figure 3: Pseudo-code for the A-VCG2 mechanism.

Corollary 1 .

 1 Let us consider a sequential auction with N advertisers, K slots, and T steps, with position-dependent cascade model with parameters {Λ m } K m=1 . The A-VCG2 achieves an SW regret R SW T = 0.

Theorem 16 .

 16 Let us consider a sequential auction with N advertisers, K slots, and T steps, with ad-dependent cascade model with parameters {c i } N i=1 whose value are unknown. Any online learning mechanism that is DSIC in expectation w.r.t. the click realizations and a posteriori w.r.t. the realization of the random component of the mechanism achieves a SW regret R SW T = Θ(T ).

Figure 7 :

 7 Figure 7: Position-dependent externalities with unknown {q i } i∈N . Dependency of the relative regret on T (left) and N (right).

Figure 8 :

 8 Figure 8: Position-dependent externalities with unknown {q i } i∈N . Dependency of the relative regret on K for two experimental settings (distinguished by the probability distribution according to q are drawn).

Figure 9 :

 9 Figure 9: Position-dependent externalities with unknown {Λ m } m∈K . Dependency of the relative regret on T (left) and K (right).

Figure 10 :

 10 Figure 10: Position-dependent externalities with unknown {Λ m } m∈K . Dependency of the relative regret on µ (left). Variance of the revenue of the auctioneer (right).

Figure 11 :

 11 Figure 11: Position-dependent externalities with unknown {q i } i∈N and {Λ m } m∈K . Dependency of the relative regret on T (left) and N (right).

Figure 12 :Figure 13 :

 1213 Figure 12: Position-dependent externalities with unknown {q i } i∈N and {Λ m } m∈K . Dependency of the relative regret on K.

Figure 14 :

 14 Figure 14: Dependency of the relative regret RR T on N .

1 ≤0≤

 1 r B i (v) = P[s ∈ S]p * i (v) -P[s ∈ S]r B i,P[s ∈ S]p * i (v) ≤ P ∃j : s j = 0 ∧ π(j; f * (v)) ≤ K + 1 v max ≤ j∈N :π(j;f * (v))≤K+1 P[s j = 0]v max = (K + 1) µv max ≤ 2Kµv max .(D.2)

  α(m;θ * ) (v) -pα(m; θ) (v)) ≤ 2Kv max η,with probability 1 -δ. Now we bound the other side.

  ; θ) (v) -p * α(m;θ * ) (v) i v i ; l + 1) q+ α(m; θ)

+≤

  P[s ∈ S ] ≤Kµ SW(f * (v), v) -E x|s ∈S SW( f (x), v)|v ≤ SW(f * (v), v) -E x|s∈S SW( f (x), v)|v + + Kµ     SW(f * (v), v) -E x|s ∈S SW( f (x), v)|v SW(f * (v), v) -E x|s∈S SW(f * (x), v)|v r 1 ≤0 + + E x|s∈S SW(f * (x), v)|v -E x|s∈S SW( f (x), v)|v r 2 ≤0 + + E x|s∈S SW( f (x), v)|v -E x|s∈S SW( f (x), v)|v + v max µK 2 ≤ max f ∈F E x|s∈S SW(f (x), v) -SW(f (x), v)|v + v max µK 2 ≤ max f ∈F   j:π(j;f (x))≤K

2 3

 3 ). In Section 4.2, we consider the opposite case where only the parameters {Λ m } m∈K are unknown. We focus on mechanisms that are DSIC in expectation w.r.t. the click realizations and a posteriori w.r.t. the random component of the mechanism in Section 4.2.1, and DSIC in expectation w.r.t. the realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations in Section 4.2.2. In the first case we observe that we can obtain a mechanism11 A preliminary version of this result appears in[START_REF] Gatti | A truthful learning mechanism for contextual multi-slot sponsored search auctions with externalities[END_REF].

	slots	CTR model	unknown	solution	regret over	regret over
			parameters	concept	welfare (R SW T

Table 2 :

 2 In the second scenario, both the regrets are bounded by a constant and the mechanism is IR a posteriori and WBB in expectation w.r.t. the random component of the mechanism. In Section 4.2.3, we derive a negative result on the possibility of having no-regret DSIC a posteriori w.r.t. both sources of randomness mechanisms. Obviously, this negative result extends to all the generalizations of the cascade model with only position-dependent externalities. We conclude the analysis of the position-dependent model studying, in Section 4.3, the case where both {Λ m } m∈K and {q i } i∈N are unknown by the auctioneer, showing that it is possible to obtain DSIC in expectation w.r.t. the random component of the mechanism and a posteriori w.r.t. the click realizations mechanisms with bounds of Õ(T

Results available on the regret of learning mechanisms in SSA, with in bold the original results derived in this paper. 'DSIC' stands for 'DSIC a posteriori '; 'DSICeC' stands for 'DSIC in expectation w.r.t. the click realizations and a posteriori w.r.t. realizations of the random component of the mechanism'; 'DSICeM' stands for 'DSIC in expectation w.r.t. realizations of the random component of the mechanism and a posteriori w.r.t. the click realizations'.

with a regret (both over the auctioneer's revenue and over the SW) of 0, but the obtained mechanism is WBB only in expectation w.r.t. the click realizations.

  1, we assume that the actual values of {q i } i∈N are unknown by the auctioneer, while those of {Λ m } m∈K are known. In Section 4.2, we assume that the actual values of {Λ m } m∈K are unknown by the auctioneer, while those of {q i } i∈N are known. Finally, in Section 4.3, we assume that both {q i } i∈N and {Λ m } m∈K are unknown.4.1. Unknown qualities {q i } i∈NIn this section we assume that the qualities of the ads {q i } i∈N are unknown, while {Λ m } m∈K are known. We initially focus on DSIC a posteriori Input: Length of exploration phase τ , confidence δ, position-dependent parameters {Λ m } m∈K

	Exploration phase
	for t = 1, . . . , τ do
	Allocate ads according to (13)
	Ask for no payment
	Observe the clicks {click i π(i;θt) (t)} N i=1

  For any slot s m with m ∈ K, with probability 1 -δ,

	cSRP canonical Self-Resampling Procedure. 37, 57, 73, 74, 76, 91 CTR Click-Through-Rate. 1, 2, 3, 5, 11, 15, 17, 18, 20, 23, 25, 40, 59 Lemma 1. max i∈N
	DSIC Dominant Strategy Incentive Compatibility. 8, 9, 16, 17, 18, 19, 20,
	21, 20, 21, 23, 24, 26, 27, 28, 29, 30, 32, 34, 35, 36, 38, 39, 40, 43, 44,
	45, 47, 50, 51, 52, 60, 67, 69, 74
	EC Execution Contingent. 8
	GSP Generalized Second Price. 2, 3, 4
	IC Incentive Compatibility. 8, 9, 30
	IR Individual Rationality. 8, 9, 16, 17, 18, 21, 26, 28, 33, 34, 36, 38, 43, 47,
	67
	MAB Multi-Armed Bandit. 3, 4, 7, 10, 11, 17, 24, 29, 30, 32, 41, 45
	PoA Price of Anarchy. 3
	SSA Sponsored Search Auction. 1, 2, 3, 4, 5, 7, 12, 13, 15, 20, 67
	SW Social Welfare. 15, 16, 17, 18, 19, 20, 21, 23, 27, 31, 36, 39, 42, 45, 47,
	49, 50, 51, 52, 59, 88, 91
	UCB Upper-Confidence Bound. 11, 30
	1 VCG Vickrey-Clarke-Groves. 1, 3, 9, 16, 17, 18, 24, 29, 32, 34, 36, 44, 48, 2 ). The second question concerns a similar study related to the case with only ad-dependent exter-67, 69, 73, 74, 75, 76, 77, 84, 88
	nalities. WBB Weak Budget Balance. 8, 9, 16, 18, 21, 28, 34, 35, 36, 38, 43, 48, 67
	Glossary WVCG Weighted Vickrey-Clarke-Groves. 9, 17, 27, 28, 39, 42, 47, 52, 77
	AE Allocative Efficiency. 8, 9, 16, 34, 36, 67, 84, 88
	BIC Bayesian Incentive Compatibility. 3, 8

  ) -P[s ∈ S]p * i (v)+ -P[s ∈ S] E x|s ∈S [Λ π(i;f * (x)) |v]q i v i -E x|s ∈S [Λ π(i;f * (x)) |v -i , u]q i du = P[s ∈ S]p * i (v)+ -P[s ∈ S] E x|s ∈S [Λ π(i;f * (x)) |v]q i v i -E x|s ∈S [Λ π(i;f * (x)) |v -i , u]q i du

	v i
	0
	r B i,1
	v i
	0

The need for having separated phases between exploration and exploitation to limit the strategic manipulation of the mechanism is underlined also in[START_REF] Langford | Maintaining equilibria during exploration in sponsored search auctions[END_REF], where the authors study learning approaches for the GSP. Interestingly, experimental simulations show that having exploration phases in which no payment is applied can allow the auctioneer to have even a short-term gain[START_REF] Sai-Ming | Value of learning in sponsored search auctions[END_REF].

In our paper, we focus on the no-discount case and we use learning mechanisms that separate the phases of exploration and exploitation. As in[START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF] and[START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF], our learning mechanisms keep to be truthful even when discounting is present.

We use the same acronym also for 'Incentive Compatible' referred to a mechanism.

See Appendix B for the definition of monotonicity in single-parameter linear environments and Myerson's payments.

Although K < N is the most common case, the results could be smoothly extended to K > N .

The allocation problem when either all the prominence probabilities λ m s or all the continuation probabilities c i s are equal to one can be solved in polynomial time, while, although no formal proof is known, the allocation problem with arbitrary λ m s and c i s is commonly believed to be N P-hard[START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF]. However, the allocation problem can be solved exactly in specific settings, and in many other cases, efficient approximation algorithms can be used[START_REF] Gatti | Which mechanism in sponsored search auctions with externalities?[END_REF]. In this paper, we ignore approximation schemes and we only focus on optimal allocation functions.

The allocation problem when either all the prominence probabilities λ m s or all the continuation probabilities c i s are equal to one can be solved in polynomial time, while, although no formal proof is known, the allocation problem with arbitrary λ m s and c i s is commonly believed to be N P-hard[START_REF] Kempe | A cascade model for externalities in sponsored search[END_REF]. However, the allocation problem can be solved

exactly in specific settings, and in many other cases, efficient approximation algorithms can be used[START_REF] Gatti | Which mechanism in sponsored search auctions with externalities?[END_REF]. In this paper, we ignore approximation schemes and we only focus on optimal allocation functions.

A preliminary version of this result appears in[START_REF] Gatti | A truthful learning mechanism for contextual multi-slot sponsored search auctions with externalities[END_REF]. In the current paper we provide a more accurate bound filling the gap between the dependence over N and K predicted by the theoretical bound and the results in the numerical simulation.

Notice that, from now on, we realistically assume that all the ads have at least two samples to initialize their estimates q+ i . This hypothesis allows us to remove the floor notation in the bounds and, in the case of A-VCG1, it leads to an exploration time τ ≥ 2N/K.

In pay-per-click payments, an advertiser pays only once its ad is clicked; in our execution-contingent payments, an advertiser pays also when the ads of other advertisers are clicked.

In the following, we report some considerations about the case in which also the samples from the slots below the first are considered. Let us observe that, even if we use only the samples from the first slot, the algorithms[START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF][START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF] that apply to the single-slot case cannot be adopted here unless to accept a regret Θ(T ). This is essentially due to the fact that algorithms[START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF][START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: Extended abstract[END_REF] have deterministic payments, but, as we show in Section 4.2.3,

Since the bounds over the regret of the SW present a structure similar to those over the auctioneer's revenue, their empirical analysis is omitted.

From this experiment is not clear whether RR T = Õ(q -1 min ), thus implying that R T does not depend on q min at all, or RR T is sublinear in q min , which would correspond to a dependency R T = Õ(q -z min ) with 0 < z < 1.

Notice that in the logarithmic term the factor of 2 we have in Proposition 1 disappears since in this proof we only need the one-sided version of the bound.

Theorem 13. The A-VCG4 is:

• DSIC in expectation w.r.t. the click realizations,

• IR a posteriori,

• WBB a posteriori.

We are interested in bounding the regret of the auctioneer's revenue due to A-VCG4 compared to the auctioneer's revenue of the VCG mechanism when all the parameters are known. Theorem 14. Let us consider a sequential auction with N advertisers, K slots, and T steps with position/ad-dependent externalities and cumulative discount factors {Γ m (θ)} K m=1 and accuracy η defined as in Eq. 31. For any parameter τ ∈ {1, . . . , T } and δ ∈ (0, 1), the A-VCG4 achieves an auctioneer's revenue expected regret:

where q min = min i∈N q i . By setting the parameters to

Remark 1 (Differences w.r.t. position-dependent externalities.) Up to constants and logarithmic factors, the previous distribution-free bound on R T is Õ(T ). 17 We first notice that moving from position-to 17 We notice that in [START_REF] Gatti | A truthful learning mechanism for contextual multi-slot sponsored search auctions with externalities[END_REF] we provided a bound O(T 2 3 N K 2 3 ) that did not match with the numerical simulations and we conjectured a bound of O(T ). Here we show the conjecture is actually correct.

We obtain the same dependence over T , as for the regret on the revenue. Theorem 15. Let us consider a sequential auction with N advertisers, K slots, and T steps. The auction has position/ad-dependent externalities and cumulative discount factors {Γ m (θ)} K m=1 and accuracy η defined as in Eq. 31. For any parameter τ ∈ {1, . . . , T } and δ ∈ (0, 1), the A-VCG4 achieves a SW regret:

By setting the parameters to

Thus 3 ). In particular notice that A-VCG4 is a zero-regret algorithm. We notice that unlike the bound on the revenue regret, in this case R SW T does not display any dependency on q min , which suggests that the problem of minimizing the SW regret may be easier. Roughly speaking, this is due to the fact that the accuracy of the estimated qualities is only used to determine the allocation f but they do not determine the performance of f itself, which is measured according to its actual SW. On the other hand, in the computation of the revenue regret, the qualities q+ i are used to determine the payments and this may lead to an additional error, which is reflected in the presence of q min in the bound.

Further extensions

In this section we provide a negative, in terms of regret, result under DSIC in expectation w.r.t. the click realizations and a posteriori w.r.t. the realization of the random component of the mechanism when the parameter γ m,i depends only on the ad a i (we denote it by c i = γ m,i for any m ∈ K as Appendix A. Vickrey-Clarke-Groves mechanism Consider a generic direct-revelation mechanism M = (N , V, Θ, f, {p i } i∈N ) as defined in Section 3.2. Differently from the SSA case, in general the type of an agent, denoted by v i for consistency with the rest of the paper, is a vector of parameters. We define a function val i : Θ × V → R + , which returns the value obtained by agent a i when its type is v i and the allocation chosen by the mechanism is θ.

The VCG mechanism is obtained coupling the two following functions:

• the allocation function f which returns the allocation maximising the social welfare, i.e.,

• the payment rule p i , which defines the payment required from agent a i , i.e.,

where we denote by f (v -i ) the allocation returned by f when agent i does not participate to the auction.

In this quasi-linear environment, when there are no interdependencies among the types of the agents and the no-single-agent effect [START_REF] Narahari | Game Theoretic Problems in Network Economics and Mechanism Design Solutions[END_REF] holds, the VCG mechanism is AE, DSIC a posteriori, IR a posteriori, and WBB a posteriori.

Appendix B. Monotonicity and Myerson's payments

Consider a generic direct-revelation mechanism M = (N , V, Θ, f, {p i } i∈N ) as defined in Section 3.2. A single-parameter linear environment is such that

• the type of each agent a i is a scalar v i (single-parameter assumption),

• the utility function of agent a i is u

where z i : Θ → R is a function of the allocation (linear assumption).

An allocation function f is monotonic in a single-parameter linear environment if for any v-i

for any v i ≥ v i . Essentially, z i is monotonically increasing in v i once v-i has been fixed. In such environments, it is always possible to design a DSIC mechanism imposing the following payments [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF]:

where h i : V N -1 → R is a generic function not depending on the type of agent a i .

Appendix C. Proof of Revenue Regret in Theorem 2

We start by reporting the proof of Proposition 1.

Proof. (Proposition 1)

The derivation is a simple application of the Hoeffding's bound. We first notice that each of the terms in the empirical average qi (Eq. 11) is bounded in [0; 1/Λ π(i;θt) ]. Thus we obtain

By reordering the terms in the previous expression we have

which guarantees that all the empirical estimates qi are within η of q i for all the ads with probability, at least, 1 -δ.

Before stating the main result of this section, we need the following lemma.

Substituting this value of τ into Eq. C.8 leads to the optimized bound

We are now left with the choice of the confidence parameter δ ∈ (0, 1), which can be easily set to optimize the asymptotic rate (i.e., ignoring constants and logarithmic factors) as

We thus obtain the final bound

We have to impose the constraints that T > N K (given by δ < 1) and that T > τ , i.e., T > N KΛ 2 min log N δ . The two constraints imply:

Appendix D. Proof of Revenue Regret in Theorem 7

Unlike the setting considered in Theorem 2, here the regret is only due to the use of a randomized mechanism, since no parameter estimation is actually needed.

Proof. (Theorem 7)

Step 1: payments and additional notation. We recall that according to [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF] and [START_REF] Green | Incentives in Public Decision Making[END_REF] the expected VCG payments can be written, as in Eq. 24, in the form

while the A-VCG2 mechanism prescribes contingent payments as in Eq. 25, which lead to expected payments

Given the randomness of the allocation function of A-VCG2 , we need to introduce the following additional notation:

The proof of Theorem 11 needs to combine the result of Theorem 7 and the regret due to the estimation of the parameters similarly to what is done in Theorem 2.

Proof. (Theorem 11)

for each ad a i is defined as the difference between the VCG payments p * i (v) and the (expected) payments p i (v) computed by the randomized mechanism when the estimates q+ are used. We notice that p * i (v) can be strictly positive only for the K displayed ads, while p i (v) ≥ 0 ∀i ∈ N , due to the mechanism randomization. Thus, p * i (v) -p i (v) > 0 only for at most K ads. Thus we obtain the per-step regret

Finally, the global regret becomes

Step 5: parameters optimization. We first simplify further the previous bound as

We first optimize the value of τ , take the derivative of the previous bound w.r.t. τ and set it to zero and obtain

.

Once replaced into Eq. E.3 we obtain

78

The optimization of the asymptotic order of the bound can then be obtained by setting µ and δ so as to equalize the orders of the second and third term in the bound. In particular, by setting

we obtain the final bound

Notice that, since δ < 1, this implies that T > N , and, since µ < 1, it must be the case T > N -2 > 1 that always holds. Moreover T > τ , thus

Appendix F. Proof of Revenue Regret in Theorem 14

Before deriving the proof of Theorem 14, we prove two lemmas that we use in what follows.

Lemma 2. Let G be an arbitrary space of allocation functions, then for any g ∈ G, when |q i -q+ i | ≤ η with probability 1 -δ, then for any v we have

with probability 1 -δ.

Proof. By using the definition of SW and SW we have the following sequence of inequalities

Step 3: parameter optimization. Let c := 5 Γ min q min , then we first simplify the previous bound as

Taking the derivative w.r.t. τ leads to

.

Once replaced in the bound, we obtain

Finally, we choose δ to optimize the asymptotic order by setting

which leads to the final bound

.

Notice that this bound imposes constraints on the value of T , indeed, T > τ , thus T > c

The problem associated with the previous bound is that τ and δ depends on q min , which is an unknown quantity. Thus actually choosing this value to optimize the bound may be unfeasible. An alternative choice of τ and δ is obtained by optimizing the bound removing the dependency on q min . Let d := 5 Γ min , then we choose

,

This leads to the final bound

q min log 2N

Given that δ < 1, this implies that T > KN d 2 , and T > τ implies T > d 2 KN log 2N δ . Together they impose

Appendix G. Deviation Regret

The definition of regret in Eq. 5 measures the cumulative difference between the revenue of the VCG compared to the one obtained by A-VCG1 over T steps. Upper-bounds over this quantity guarantees that the loss in terms of revenue does not increase linearly with T . As illustrated in the previous sections, the key passage in the proofs is the upper-bounding of the regret at each step of the exploitation phase (i.e., r = N i=1 (p * i (v) -pi (v))). Nonetheless, we notice that this quantity could be negative as well. In this section we introduce a different notion of regret ( RT ) that we study only for A-VCG1, leaving for the future a more comprehensive analysis of the other algorithms. Let us consider the following simple example. Let N = 3, K = 1, v i = 1 for all the ads, and q 1 = 0.1, q 2 = 0.2, and q 3 = 0.3. Let assume that after the exploration phase we have q+ 1 = 0.1, q+ 2 = 0.29, q+ 3 = 0.3. The standard VCG mechanism allocates ad a 3 and asks for a payment p * 3 (v) = 0.2. During the exploitation phase A-VCG1 also allocates a 3 but asks for an (expected) payment p3 (v) = (q + 2 /q + 3 )q 3 = 0.29. Thus, the regret in each exploitation step is r = p * 3 (v) -p3 (v) = -0.09. Although this result might seem surprising, it is due to the fact that while both A-VCG1 and VCG are truthful, in general A-VCG1 is not AE. We recall that a mechanism is AE if for any set of advertisers it always maximizes the social welfare. In the example, if for instance the true quality of ad a 3 is q 3 = 0.28, then the allocation induced by q+ s is not efficient anymore. For this reason, we characterized the behavior of A-VCG1 compared to the VCG considering the deviation between their payments, defined as

where we consider the definition of pi in Eq. C.2. We leave to further investigation the study of this regret for the other considered mechanisms.

Theorem 18. Let us consider a sequential auction with N advertisers, K slots, and T steps with position-dependent cascade model with parameters {Λ m } K m=1 and accuracy η as defined in Eq. 14. For any parameter τ ∈ {1, . . . , T } and δ ∈ (0, 1), the A-VCG1 achieves an auctioneer's revenue expected regret:

where q min = min i∈N q i . By setting the parameters to

Using these results we obtain

with probability 1 -δ. As a result we have

with probability 1 -δ. The final bound on the expected regret is thus

We first simplify the previous bound as

and choosing the parameters

The fact δ < 1 implies that T > N K , and

Remark (the bound). We notice that the bound is very similar to the bound for the regret R T but now an inverse dependency on q min appears. This suggests that bounding the deviation between the two mechanisms is more difficult than bounding the revenue loss and that, as the qualities become smaller, the A-VCG1 could be less and less efficient and, thus, have a larger and larger revenue. This result has two important implications. (i) If SW maximization is an important requirement in the design of the learning mechanism, we should analyze the loss of A-VCG1 in terms of social welfare and provide (probabilistic) guarantees about the number of steps the learning mechanism need in order to be AE (see [START_REF] Gonen | An incentive-compatible multi-armed bandit mechanism[END_REF] for a similar analysis). (ii) If social welfare is not a priority, this result implies that a learning mechanism could be preferable w.r.t. the standard VCG mechanism. We believe that further theoretical analysis and experimental validation are needed to understand better both aspects.

Appendix H. Proofs of Social-Welfare Regret in Theorems 3 and 15

Before stating the main result of this section, we need the following technical lemma. Lemma 4. Let us consider an auction with N advertisers, K slots, and T steps, and a mechanism that separates the exploration (τ steps) and the exploitation phases (T -τ steps). Consider an arbitrary space of allocation functions G, g ∈ arg max g ∈G SW (g (v), v) and |q i -q+ i | ≤ η with probability 1 -δ. For any g ∈ G, an upper bound of SW regret R SW T of the mechanism adopting g instead of g is:

Proof. We now prove the bound on the social welfare, starting from the cumulative per-step regret during the exploitation phase.

The two remaining terms r 1 and r 2 can be easily bounded by using Lemma 3

Thus, we can conclude that:

Proof. (Theorem 3)

Step 1: cumulative regret. We apply Lemma 4 to the position-dependent cascade model with {q i } i∈N unknowns, obtaining

Step 2: parameter optimization. First we notice that adopting the value of the parameters identified in Theorem 2 we obtain an upper bound Õ(T

3 ) for the global regret R SW T . In order to find values that better optimize the bound over R SW T , let e := 1 Λ min , then we first simplify the previous bound as

Taking the derivative of the previous bound w.r.t. τ leads to

.

Once replaced in the bound, we obtain

Finally, we choose δ to optimize the asymptotic order by setting

The final bound is

Given that δ < 1 this implies that T > e 2 K -1 N . This constrain is satisfied imposing T > τ , i.e.,

T > e 2 K -1 N log 2N δ .

Proof. (Theorem 15)

Step 1: cumulative regret. We apply Lemma 4 to the model with position-and ad-dependent externalities with {q i } i∈N unknowns, obtaining

Step 2: parameter optimization. First we notice that adopting the value of the parameters identified in Theorem 14 we obtain an upper bound Õ(T

3 ) for the global regret R SW T .

90

In order to find values that better optimize the bound over R SW T , it is possible to use the procedure followed in the proof of Theorem 3 with e := The bound over the SW regret R SW T can be easily derived considering that each bid is modified by the cSRP with a probability of µ. Thus we can define S = {s |s ∈ {0, 1} N , π(i; f * (v)) ≤ K ⇒ s i = 1}, i.e., the set of the random realizations where the cSRP does not modify the bids of the ads displayed when the allocation function f * is applied to the true bids v. Thus we have: Step 1: per-step regret. We start computing the per-step regret over the SW during the exploitation phase.

First of all we introduce the following definition: S = {s |s ∈ {0, 1} N , π(i; f * (v)) ≤ K ⇒ s i = 1}, i.e., the set of the random realization where the cSRP does not modify the bids of the ads displayed when the allocation function is f * is applied to the true bids v.

We now provide the bound over the regret. Step 3: parameter optimization. We first simplify the previous bound as

Taking the derivative of the previous bound w.r.t. τ leads to + µK 2 v max T + δv max KT.

Finally, we choose δ and µ to optimize the asymptotic order by setting

The final bound is

log 2T Given that δ < 1 this implies that T > N and, given that µ < 1 we have that T > N K 3 . Both the constraints are satisfied imposing T > τ , i.e., T > N log 2N δ .