AdWords and Generalized On-line Matching II: No Randomized Online Algorithm for b-Matching Has Competitive Ratio Better Than 1 − 1/e, for Every Budget bResearch Paper
Search engines sell advertising slots query by query. Each advertiser states a bid per keyword and a daily budget; queries arrive one at a time, and the engine must assign each to an advertiser immediately, without knowing which queries will come later. Mehta, Saberi, Vazirani and Vazirani (J. ACM 2007) called this the adwords problem and gave a…