Collusion in generalized second price ads auctions

Historically in the online advertising world there were two main actors: the publishers, providing the environment in which the auction take place, and the advertisers, participating in the auction. Recently a third figure entered the market of online advertising: the Digital Media Agencies (DMA) that offers to handle the online advertising campaign for their clients. This implied a radical change in the dynamics of the online auctions: the cooperation between advertisers, that before acted as single entities, lets them collude under the same DMA. This scenario has been studied by Francesco Decarolis [1] and Francesco Decarolis and Shakhgildyan [2], from an economic and game theoretical perspective. In this paper, we propose different algorithmic approaches for the optimization of the online campaigns for a set of advertisers. The proposed algorithms operates under different environment assumption, starting from trivial settings and converging to realistic environment simulation. The main algorithm presented in this paper is a graph based online optimizer, that exploits combinatorial multi-armed bandit techniques. Our work adapts the Comb-UCB algorithm by Branislav Kveton and Szepesvari [3] using insights about the problem structure to achieve a faster learning.

Storicamente nel mondo delle campagne pubblicitarie online erano presenti due attori principali: le piattaforme di pubblicazione, che fornisco l’ambiente in cui si svolgono le aste, e i pubblicitari, che partecipano alle stesse. Negli ultimi tempi è apparsa una terza figura sul mercato: le Digital Media Agencies (DMAs) che si pongono come scopo la ges- tione e l’ottimizzazione delle campagne pubblicitarie per i loro clienti. Questo ha portato un cambiamento radicale nelle dinamiche delle aste online: la cooperazione tra pubblic- itari, che prima agivano come entità singole, permette la collusione degli enti controllati dalla stessa DMA. Questo scenario è stato studiato nel dettaglio da Francesco Decarolis [1] e da Francesco Decarolis and Shakhgildyan [2], sia da una prospettiva economica che con un approccio legato alla teoria dei giochi. In questo lavoro, formuliamo una serie di approcci algoritmici differenti per l’ottimizzazione delle campagne pubblicitarie online, per un gruppo di aziende. Gli algoritmi proposti operano seguendo diversi livelli di sem- plificazione dell’ambiente reale, partendo da un livello elementare, fino a convergere a una simulazione verosimile della realtà. L’algoritmo principale proposto in questo lavoro è un algoritmo di ottimizzazione online basato su un grafo, esso si basa sul modello dei combi- natorial multi-armed bandits. Nel nostro lavoro adattiamo il classico Combinatorial-UCB come proposto da Branislav Kveton and Szepesvari [3], utilizzando le informazioni sulla struttura delle aste per velocizzare l’apprendimento e diminuire le perdite.