Home // ICIW 2015, The Tenth International Conference on Internet and Web Applications and Services // View article

On the Power of Combinatorial Bidding in Web Display Ads

Authors:
Khaled Elbassioni
Mukesh Jha

Keywords: Combinatorial auctions; algorithmic mechanism design; Generalized Second Price; truthfulness

Abstract:
Web display advertisement is occupying a major part of the marketing industry. With the vastly increasing number of competing advertisers, allocating web advertising space becomes a challenge, due to the need to run a large-scale auction in order to determine the winners and payments. As a result, some of the most desired properties, such as truthfulness (a.k.a. strategy proofness), and social welfare maximization are typically sacrificed by the auction mechanisms used in practice, in exchange of computational efficiency. Furthermore, those mechanisms typically assume a fixed partition of the advertising space, and use a simple mechanism, such as Generalized Second Price (GSP) auction to avoid the combinatorial explosion of the size of the problem when users are allowed to bid on arbitrary regions of the space. In this paper, we go beyond this non-combinatorial approach, and investigate the implementation of strategy–proof mechanisms which are truthful–in–expectation and approximately socially efficient, with an attempt to understand their computational efficiency, social welfare and revenue, when applied to Web display Ads. Those mechanisms were proposed recently as a theoretical engineering of the computationally less efficient mechanisms of Lavi and Swamy. Our experimental results show that allowing combinatorial bidding can offer substantial improvements in both social welfare and revenue as compared to slot-based methods, such as the GSP mechanism.

Pages: 46 to 55

Copyright: Copyright (c) IARIA, 2015

Publication date: June 21, 2015

Published in: conference

ISSN: 2308-3972

ISBN: 978-1-61208-412-1

Location: Brussels, Belgium

Dates: from June 21, 2015 to June 26, 2015