|Thesis abstract: |
Free services are nowadays offered to users through web pages managed by integrators who provide multiple services in one location. The atomic services that are federated can be of two types: content, from which no direct profit can be obtained, and advertising, which is the only source of revenue. Thus, since the integrator must make a profit, among her services there must be at least one that provides advertising. Integrators can be of two kinds: those who generate their own information, and those who use information communicated by third parties. In this thesis we focus on the latter and we refer to the third parties as providers.
To offer the best service and increase the overall revenue, an integrator must target users by selecting the best services and those ads that are more likely to be clicked. In order to achieve this, information (i.e., what providers communicate to the integrator) is needed and, since the more information is collected (i.e., the more providers are federated), the better the services offered, an integrator is incentivised to federate also multiple providers that offer the same service. However, this implies that she has to collect the information received and select what to display. The active role of the integrator in the choice of the services to display makes our problem new, because current integrators, typically, only show to the users the information communicated by the providers without any selection. The aim of the thesis is to design a revenue sharing mechanism for the new federation of services described above. To achieve this goal we resort to mechanism design techniques that indicate how to design the rules of a game to get a particular desired outcome. In particular, the problems we want to address are twofold.
The first one is the design of an auction mechanism for the scenario in which multiple sources of advertising are federated. The mechanism should maximise the overall expected revenue, incentivise the provider to truthfully reveal their information, and guarantee a non-negative revenue to both the integrator and the providers. The design of such a mechanism is particularly challenging because ads displayed affect each others' click probability (i.e., there are allocative externalities) and because, when one or more advertisers submit a bid to multiple providers, the revenue of a provider depends also on the information communicated by the other providers. Due to this, we show that there exists no standard mechanisms (i.e., mechanisms that define the ads' allocation and the providers' payments only on the basis of the communicated information) that satisfies all the desired properties. This is why we focus on execution contingent mechanisms (i.e., mechanisms that compute the payment based on the ads actually clicked). However, even with such mechanisms the results we obtain are not satisfactory. Thus, we turn to consider simplifications of the proposed scenario, and for each of them we design a mechanism. The simplifications focus on restricting the domain and relaxing the mechanism requirements. We provide a theoretical evaluation of all the mechanisms proposed and we empirically compare them.
The second problem we aim to address is the design of a redistribution mechanism that compensates all the providers incentivising them to remain in the federation of services. This problem is challenging, and no redistribution mechanism presented in the literature can be used, because the providers that are federated can belong to different classes. This heterogeneity necessitates the design of a flexible mechanism that defines different compensation for different classes of provider. We design an efficient truthful mechanism that provides all the actors with a non-negative utility and we prove that, as the number of providers goes to infinity, the revenue collected by the integrator can be completely redistributed. Finally, we empirically evaluate the mechanism proposed. All the empirical evaluations in this thesis are based on the Yahoo! Webscope A3 dataset.