Incentive compatible revenue sharing mechanisms for the federation of services

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.

Oggigiorno, aggregazioni di servizi gratuiti sono fornite agli utenti tramite pagine web gestite da integratori. I singoli servizi che sono integrati possono essere di due tipi: possono fornire contenuti, dai quali l'integratore non ottiene direttamente profitto, o possono fornire pubblicità, che é l'unica forte di guadagno dell'integratore. Quindi, dato che l'integratore deve poter avere un profitto dall'attività di aggregazione, tra i suoi servizi deve essercene almeno uno che fornisce pubblicità. In questo lavoro consideriamo il caso generale in cui i servizi che l'integratore aggrega sono forniti da terze parti che chiamiamo provider. Per offrire il miglior servizio possibile e aumentare il guadagno totale, l'integratore deve essere in grado di selezionare i servizi che sono di maggior interesse per ogni specifico utente, cioè deve targettizzare i servizi per gli utenti. Per poter far ció al meglio, l'integratore deve raccogliere piú informazioni possibile e, dato che le informazioni sono comunicate dai provider, é motivato ad aggregare un numero di provider maggiore di quanti servizi possano essere effettivamente proposti all'utente. Una fase di selezione dei servizi è quindi necessaria. Questo differenzia la tipologia di integratore qui considerato da quella attualmente esistente che tipicamente ripropone all'utente i servizi forniti dai provider senza targettizzarli. Lo scopo di questa tesi é quello di progettare un meccanismo che definisca come l'integratore ottiene il proprio guadagno e come questo é poi diviso tra tutti gli attori del sistema. In particolare, possiamo dividere il problema qui considerato in due sottoproblemi. Il primo riguarda la progettazione di un meccanismo d'asta per link sponsorizzati per lo scenario caratterizzato da molteplici provider che comunicano pubblicitá. Il meccanismo dovrebbe (i) massimizzare la somma del guadagno di tutti gli attori, (ii) garantire che i provider siano incentivati a comunicare all'integratore l'informazione che possiedono in modo veritiero e (iii) garantire a tutti gli attori un profitto non negativo. La progettazione di questo meccanismo é resa particolarmente difficile dal fatto che i link sponsorizzati si influenzano l'uno con l'altro (sono cioé soggetti a un fenomeno identificato con il nome di allocative externalities) e dal fatto che, nel caso in cui lo stesso link sponsorizzato sia comunicato da più provider, il guadagno che questi ottengono non dipende dalle informazioni che il singolo provider ha comunicato ma dalla fusione di tutte quelle ricevute dall'integratore relative allo stesso link. Per i motivi appena citati, non è possibile progettare un meccanismo standard (cioé un meccanismo che definisce i pagamenti dei provider sulla base dell'informazione ricevuta dall'integratore) che soddisfa le proprietá sopra elencate. Per questo, in questo lavoro, consideriamo meccanismi execution-contingent (ossia meccanismi che definiscono i pagamenti anche in base ai link sponsorizzati che effettivamente sono cliccati dall'utente). Tuttavia, anche usando questi meccanismi, il risultato che otteniamo non é soddisfacente. Per questo motivo consideriamo semplificazioni dello scenario proposto e per ognuna di esse progettiamo un meccanismo. In particolare, semplifichiamo lo scenario in due modi: restringendo il dominio e rilassando i requisiti. Tutti i meccanismi progettati sono stati valutati empiricamente. Il secondo sottoproblema riguarda la progettazione di un meccanismo di redistribuzione che definisce pagamenti per i provider in modo tale che siano incentivati a prendere parte alla federazione di servizi. Questo problema é reso complicato dal fatto che i provider possono appartenere a classi differenti. Ci troviamo di fronte, quindi, ad uno scenario con agenti eterogenei che non é mai stato considerato fino ad ora nella letteratura relativa a meccanismi di redistribuzione. L'eterogeneitá dei provider fa nascere la necessitá di un meccanismo flessibile che sia in grado di differenziare la redistribuzione ottenuta dalle diverse classi di provider. In questo lavoro, proponiamo un meccanismo che soddisfa il requisito di flessibilità e dimostriamo che, tale meccanismo, é in grado di ridistribuire l'intero guadagno dell'integratore (nel caso in cui esso desideri ció) se il numero di provider tende ad infinito. Per questo meccanismo proponiamo una valutazione sperimentale principalmente orientata all'analisi della sua flessibilità. Yahoo! Webscope A3 é il dataset sul quale si basano tutte le valutazioni empiriche proposte nella tesi.