Optimal Allocation Mechanisms When Bidders Ranking for the objects is common

Search engines commonly use “sponsored links†, where certain advertisers’ links are promoted to be placed above others in return for monetary payment. It is natural to assume that all providers value a higher ranked placement more than lower ranked ones. Then how should the seller optimally sell these ranked slots is critical for the search engines. In this paper we study the seller’s (search engine) optimal selling mechanism in the following setting: buyers (advertisers), each of whom has unit demand, compete for positions o ered by the seller. While each buyer’s valuation for each position is private and independent, the ranking for these positions is common among all the buyers. However the rate at which these valuations change might be di erent. We begin with 4 simplified scenarios specifying how buyers valuations change for di erent positions, namely,“parallel†, “convergent†, “divergent†, and “convergent then divergent†. We find that the optimal incentive compatible allocation mechanism is quite di erent in determining the “pivot†types and the order to fill in the positions. Under some conditions, these mechanisms are even ecient in terms of maximizing the total welfare of the auctioneer and bidders. When the buyers’ valuations for lower positions decrease at di erent rates, the seller earns more than the case of simple second-price sequential auction