We consider the "Offline Ad Slot Scheduling" problem, where advertisers must be scheduled to "sponsored search" slots during a given period of time. Advertisers specify a budget constraint, as well as a maximum cost per click, and may not be assigned to more than one slot for a particular search. We give a truthful mechanism under the utility model where bidders try to maximize their clicks, subject to their personal constraints. In addition, we show that the revenue-maximizing mechanism is not truthful, but has a Nash equilibrium whose outcome is identical to our mechanism. As far as we can tell, this is the first treatment of sponsored search that directly incorporates both multiple slots and budget constraints into an analysis of incentives. Our mechanism employs a descending-price auction that maintains a solution to a certain machine scheduling problem whose job lengths depend on the price, and hence is variable over the auction. The price stops when the set of bidders that can afford that price pack exactly into a block of ad slots, at which point the mechanism allocates that block and continues on the remaining slots. To prove our result on the equilibrium of the revenue-maximizing mechanism, we first show that a greedy algorithm suffices to solve the revenue-maximizing linear program; we then use this insight to prove that bidders allocated in the same block of our mechanism have no incentive to deviate from bidding the fixed price of that block.
@cite_0: We study a multi-unit auction with multiple bidders, each of whom has a private valuation and a budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard assumptions, we prove that it is impossible to design a non-trivial truthful auction which allocates all units, while we provide the design of an asymptotically revenue-maximizing truthful mechanism which may allocate only some of the units. Our asymptotic parameter is a budget dominance parameter which measures the size of the budget of a single agent relative to the maximum revenue. We discuss the relevance of these results for the design of Internet ad auctions.
@cite_16: We study the problem of optimally allocating online advertisement space to budget-constrained advertisers. This problem was defined and studied from the perspective of worst-case online competitive analysis by Our objective is to find an algorithm that takes advantage of the given estimates of the frequencies of keywords to compute a near optimal solution when the estimates are accurate, while at the same time maintaining a good worst-case competitive ratio in case the estimates are totally incorrect. This is motivated by real-world situations where search engines have stochastic information that provide reasonably accurate estimates of the frequency of search queries except in certain highly unpredictable yet economically valuable spikes in the search pattern. Our approach is a black-box approach: we assume we have access to an oracle that uses the given estimates to recommend an advertiser everytime a query arrives. We use this oracle to design an algorithm that provides two performance guarantees: the performance guarantee in the case that the oracle gives an accurate estimate, and its worst-case performance guarantee. Our algorithm can be fine tuned by adjusting a parameter α, giving a tradeoff curve between the two performance measures with the best competitive ratio for the worst-case scenario at one end of the curve and the optimal solution for the scenario where estimates are accurate at the other en. Finally, we demonstrate the applicability of our framework by applying it to two classical online problems, namely the lost cow and the ski rental problems.
@cite_0 consider the problem of budget-constrained bidders for multiple items of a single type, with a utility function that is profit-maximizing, modulo being under the budget (being over the budget gives an unbounded negative utility). They give a truthful mechanism allocating some portion of the items that is revenue-optimal, and prove that in their model, under reasonable assumptions, truthful mechanisms that allocate all the units are impossible. Our work is different both because of the different utility function and the generalization to multiple slots with a scheduling constraint. Using related methods, @cite_16 consider an online setting where an unknown number of copies of an item arrive online, and give a truthful mechanism with a constant competitive ratio guarantee.