@inproceedings{3563f626f99e4c8da6214dba74940500,
title = "The adwords problem: Online keyword matching with budgeted bidders under random permutations",
abstract = "We consider the problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit. The goal is to maximize the revenue generated by these keyword sales, bearing in mind that, as some bidders may eventually exceed their budget, not all keywords should be sold to the highest bidder. We assume that the sequence of keywords (or equivalently, of bids) is revealed on-line. Our concern will be the competitive ratio for this problem versus the off-line optimum. We extend the current literature on this problem by considering the setting where the keywords arrive in a random order. In this setting we are able to achieve a competitive ratio of 1-ε under some mild, but necessary, assumptions. In contrast, it is already known that when the keywords arrive in an adversarial order, the best competitive ratio is bounded away from 1. Our algorithm is motivated by PAC learning, and proceeds in two parts: a training phase, and an exploitation phase.",
keywords = "Adwords, Learning, Matching, Online, Random permutation",
author = "Devenur, \{Nikhil R.\} and Hayes, \{Thomas P.\}",
year = "2009",
doi = "10.1145/1566374.1566384",
language = "English",
isbn = "9781605584584",
series = "Proceedings of the ACM Conference on Electronic Commerce",
pages = "71--78",
booktitle = "EC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce",
note = "2009 ACM Conference on Electronic Commerce, EC'09 ; Conference date: 06-07-2009 Through 10-07-2009",
}