Revenue Efficient Mechanisms for Online Advertising

nline advertising is an essential part of Internet and the main source of revenue for lots of web-centric companies such as search engines, news websites, Internet social networks, and other types of publishers. Online advertising happens in different settings and includes many challenges and constraints. A key component in each setting is the mechanism which selects and prices the set of winning ads. In this talk we talk about problems of current mechanisms being used in online advertising, candidate new mechanisms, and efficient ways to transition to the target mechanisms.

Generalized Second Price (GSP) auction has been the mechanism of choice in online advertising companies such as Google and Microsoft. Online advertising has changed significantly with the introduction of richer ad formats and page templates and the possibility of advertising across services. We note that GSP cannot be generalized well for these new settings and hence there is a need for transition to a new mechanism. In the first part of the talk we discuss about effective ways to transition to a target mechanism. We argue that truthfulness should be an important property of the target mechanism. We introduce a hybrid mechanism to perform this transition. Our mechanism handles effectively advertisers who do not update their bids quickly or might not directly update to their true valuations in the middle of the transition. In particular, the hybrid mechanism is the same as GSP at the start of the transition and the same as the target mechanism at the end. We analyse the performance of our hybrid mechanism on revenue, social welfare, and click yield.

In the second part of the talk we discuss about the target mechanism and its desired properties. In particular we show that VCG mechanism is not preferable since it is not revenue monotone- its revenue might go down if you increase the number of advertisers. Then, we talk about how to measure revenue of mechanisms and design efficient mechanisms accordingly.

Speaker Details

Mohammad Reza Khani is a fourth year PhD student at University of Maryland advised by Mohammad T. Hajiaghayi. His research interests are algorithmic game theory and approximation, randomized, and online algorithms. Earlier, he received his M.Sc. from University of Alberta under supervision of Mohammad R. Salavatipour at 2011 and B.Sc. from Amirkabir University of Technology at 2009.

Date:
Speakers:
Mohammad Reza Khani
Affiliation:
University of Maryland
    • Portrait of Jeff Running

      Jeff Running