A Mechanism for Fair Distribution of Resources with Application to Sponsored Search

As advertisement is shifting from the traditional media to the Internet, advertising in web search engines has emerged in the form of sponsored search. Advertisers pay the search engine to show their content, usually in order to get traffic to their own websites. A large amount of the search engine’s income derives from sponsored search. In sponsored search, a number of advertisers are competing for a limited number of slots in each specific keyword search in the search engine. In order to distribute the available slots among the advertisers, search engines are starting to hold keyword auctions. The questions that appear in this setup from a mechanism design point of view are two, how to assign advertisers to slots (or vice versa), and how to price each slot. This work proposes a novel approach were distributing the slots among the advertisers is based on how much each advertiser values appearing in a keyword search slot at a specific time. The proposed approach makes this value independent of her true payment to the search engine, which can take the form of a flat fee. For this purpose we have designed a new auction mechanism that fairly distributes resources (or goods, e.g., slots) in online fashion, based on the users’ declared preferences, while being socially efficient. While the main motivation for this work was sponsored search, the proposed mechanism can be used in general for the fair distribution of resources in an online fashion among a set of users. Hence, we refer to this mechanism as Fair and Efficient Distribution of Resources (FEDoR). FEDoR can be used even when the auction is done in a distributed fashion (i.e., without central authority), and it provides fairness, social efficiency and incentive compatibility.