The design and analysis of online algorithms, where the input to the algorithm is revealed over time and the algorithm has to make decisions immediately without knowing the future input, has received a revived interest in the last few years primarily due to their application to online advertising. The canonical problem is the Adwords problem, which is motivated by the problem of optimally allocating ad slots on search queries to budget constrained advertisers. It involves simplifications that ignore certain aspects of the actual way this allocation is done. For instance, it assumes a "first-price" pay-per-impression scheme, ignoring the game theoretic aspects, and considers only one slot per query. To be precise, the Adwords problem is as follows.