Balanced allocation mechanism: An optimal mechanism for multiple keywords sponsored search auctions

This paper presents an optimal mechanism for allocating slots of multiple keywords to bidders who have only one budget limit for all their desired keywords; it is called the balanced allocation mechanism. In a balanced allocation, all the bidders and slots for the keywords are partitioned into consecutive and distinct structures called balanced blocks. The study develops efficient algorithms for this mechanism. For instance, an algorithm is developed to create a “perfect schedule” for each independent, balanced block. Using this scheduling, all the slots and budgets of all bidders will be consumed. The balanced allocation mechanism creates a balanced allocation with perfect scheduling for each balanced block. This research confirms that this is an optimal truthful mechanism that maximizes the revenue of a search engine.