A Nash Bargaining Based Bid Optimizer for Sponsored Search Auctions

Abstract

The on-line advertising market involving displaying of Ads against search results by a search engine is growing at a fast rate. A majority of the search engine companies sell their advertising space through auctions which are popularly called sponsored search auctions. In the face of fierce competition, each search engine company faces the threat of its advertisers switching to an alternative search engine in quest of better bang-per-buck. In order to retain customers, the search engine companies have introduced many utilities such as bid optimizer, ad slotting, and budget optimizer to promise enhanced bang-per-buck to the advertisers. The focus of this work is on the bid optimizer which is a software agent that automatically chooses bid values on behalf of the bidders. Bidders will provide a target budget to exhaust and a maximum bid value (willingness to pay). The bid optimizer aims to maximize the bang-per-buck by adjusting the bid amount based on the projected keyword traffic and remaining budget. In this thesis, we develop a novel bid optimizer based on Nash bargaining theory. The thesis is in two parts. In the first part, we address continuous bids while in the second part, we address discrete bids. Our formulation consists of a two person Nash bargaining model, where, the auctioneer is one player and a virtual aggregated agent representing all the n bidders is the other player. In the continuous bids case, the Nash bargaining formulation leads to a convex hull of the utility space of these two players. We show that this convex hull has exactly three corner points which can be computed in O(nlogn) time. Next, we show that the Nash bargaining solution, a point in this convex hull can be mapped to a bid profile of the bidders in O(n) time. Such a bid profile happens to be a local envy-free equilibrium of the underlying game that gets induced among the bidders due to the combined effect of auction rules and the bid optimizer. In the discrete bids case, we show that the Nash bargaining solution always lies on a certain edge of the convex hull such that one end point of the edge is the vector of maximum willingness to pay of all the bidders. We show that the other endpoint of this edge can be computed as a solution of a linear programming problem. We also map this solution to a bid profile of the bidders. For both continuous bids and discrete bids, we describe an algorithmic approach for implementing our idea. We also show experimentally that the proposed bid optimization algorithm, in conjunction with the generalized second price (GSP) auction as the underlying mechanism, outperforms the GSP when we take into account the realistic possibility of bidders dropping from the auction.