Nash bargaining based ad networks for sponsored search auctions

In this paper, we consider an emerging scenario in sponsored web search auctions where ad networks would be involved as intermediaries between a search engine and its advertisers. In this context, we address the problem of the ad network identifying a bid profile that makes the sponsored search auction attractive to the registered bidders. Given (1) the valuation of the advertisers competing for sponsored slots corresponding to a keyword, and (2) relevant click-through rates, the proposed algorithm generates a bid profile that can be input to a standard generalized second price based sponsored search auction mechanism. The bid profile is derived using a two person Nash bargaining model which ensures a fair share of utility between the search engine and the advertisers. In the proposed model, the auctioneer (search engine) is one player and a virtual aggregated bidder representing all the n advertisers is the other player. We show that the feasible set for the Nash bargaining formulation is a convex hull with three points that can be computed in O(n logn) time. We derive the Nash bargaining solution and show that it can be mapped to a bid profile of the bidders in O(n) time.