Sponsored search auctions 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 to assure 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 an optimal mechanism designed with 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 per-step regret (over the auctioneer's revenue) of
order $O(T^{-1/3})$ (where T is the number of times the auction is repeated).
It is also known that, when truthfulness in expectation is adopted, a per-step
regret (over the social welfare) of order $O(T^{-1/2})$ can be obtained. In
this paper we extend the results known in the literature to the case of
multi-slot auctions. In this case, a model of the user is needed to
characterize how the advertisers' valuations change over the slots. We adopt
the cascade model that is the most famous model in the literature for sponsored
search auctions. We prove a number of novel upper bounds and lower bounds both
on the auctioneer's revenue loss and social welfare w.r.t. to the VCG auction
and we report numerical simulations investigating the accuracy of the bounds in
predicting the dependency of the regret on the auction parameters.

该论文扩展了有关单 Slot 拍卖中的 sponsored search auctions 的机制设计的研究，并研究了使用级联模型来解决多 Slot 拍卖中的 CTR 估计和真实机制设计的问题。