Affiliations: [a] Department of Computer Science, Jerusalem College of Technology, Jerusalem, Israel | [b] Department of Computer Science, Ashkelon College, Ashkelon
Correspondence:
[*]
Corresponding author: Rina Azoulay, Department of Computer Science, Jerusalem College of Technology, Havaad Haleumi St., POB 16031, Jerusalem 91160, Israel. E-mail: rrinaa@gmail.com
Abstract: Recently we have witnessed the phenomena of private Website owners who are willing to dedicate space on their Website for advertisements managed by leading search engines (e.g., Google, Bing and Yahoo). In most cases the choice of the advertisements displayed on a certain Website is made without taking into account the preferences of the Website hosting the advertisements. This causes the Website that dedicate space for the ads to be exposed to ads that are irrelevant to the content on the Website. In this paper, we focus on the design of auction protocols that take into account the Website owner's preferences by associating him with a utility function reflecting the value for each ad shown in his space. In doing so we introduce the dispensation scheme into the second price sealed bid auction for both the single and the multi-slot cases. For the single-slot, we propose a mechanism that proved to be individual rational, truthful, and a free advertisement condition is defined. For the multi-slot case, we propose three truthful mechanisms. Simulation results show that the allocation efficiency of two of the proposed mechanisms maintain a near to optimal allocation efficiency compared to optimal allocation calculated using the Hungarian mechanism, while substantially reducing computational complexity from cubic to linear.
Keywords: Auctions, mechanism design, web advertising, performance
